1 /* Lifted from the krb5 1.6 source tree and hacked slightly to fit in here
4 * lib/des425/quad_cksum.c
6 * Copyright 1985, 1986, 1987, 1988,1990 by the Massachusetts Institute
10 * Export of this software from the United States of America may
11 * require a specific license from the United States Government.
12 * It is the responsibility of any person or organization contemplating
13 * export to obtain such a license before exporting.
15 * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
16 * distribute this software and its documentation for any purpose and
17 * without fee is hereby granted, provided that the above copyright
18 * notice appear in all copies and that both that copyright notice and
19 * this permission notice appear in supporting documentation, and that
20 * the name of M.I.T. not be used in advertising or publicity pertaining
21 * to distribution of the software without specific, written prior
22 * permission. Furthermore if you modify this software you must label
23 * your software as modified software and not distribute it in such a
24 * fashion that it might be confused with the original M.I.T. software.
25 * M.I.T. makes no representations about the suitability of
26 * this software for any purpose. It is provided "as is" without express
27 * or implied warranty.
30 * This routine does not implement:
33 * Quadratic Congruential Manipulation Dectection Code
35 * ref: "Message Authentication"
36 * R.R. Jueneman, S. M. Matyas, C.H. Meyer
37 * IEEE Communications Magazine,
38 * Sept 1985 Vol 23 No 9 p 29-40
40 * This routine, part of the Athena DES library built for the Kerberos
41 * authentication system, calculates a manipulation detection code for
42 * a message. It is a much faster alternative to the DES-checksum
43 * method. No guarantees are offered for its security.
45 * Implementation for 4.2bsd
46 * by S.P. Miller Project Athena/MIT
50 * Algorithm (per paper):
52 * message to be composed of n m-bit blocks X1,...,Xn
53 * optional secret seed S in block X1
57 * initial (secret) value of accumulator C
58 * N, C, and S are known at both ends
59 * C and , optionally, S, are hidden from the end users
61 * (read array references as subscripts over time)
64 * Z[i] = (Z[i+1] + X[i])**2 modulo N
70 * iterate 4 times over plaintext, also use Zn
71 * from iteration j as seed for iteration j+1,
72 * total MDC is then a 128 bit array of the four
75 * return the last Zn and optionally, all
76 * four as output args.
79 * To inhibit brute force searches of the seed space, this
80 * implementation is modified to have
81 * Z = 64 bit accumulator
84 * S = S seed is not implemented here
85 * arithmetic is not quite real double integer precision, since we
86 * cant get at the carry or high order results from multiply,
87 * but nontheless is 64 bit arithmetic.
90 * This code purports to implement the above algorithm, but fails.
92 * First of all, there was an implicit mod 2**32 being done on the
93 * machines where this was developed because of their word sizes, and
94 * for compabitility this has to be done on machines with 64-bit
95 * words, so we make it explicit.
97 * Second, in the squaring operation, I really doubt the carry-over
98 * from the low 31-bit half of the accumulator is being done right,
99 * and using a modulus of 0x7fffffff on the low half of the
100 * accumulator seems completely wrong. And I challenge anyone to
101 * explain where the number 83653421 comes from.
103 * --Ken Raeburn 2001-04-06
107 /* System include files */
108 #include <sys/types.h>
112 #include <internal.h>
114 /* Definitions for byte swapping */
116 /* vax byte order is LSB first. This is not performance critical, and
117 is far more readable this way. */
118 #define four_bytes_vax_to_nets(x) ((((((x[3]<<8)|x[2])<<8)|x[1])<<8)|x[0])
119 #define vaxtohl(x) four_bytes_vax_to_nets(((const unsigned char *)(x)))
120 #define two_bytes_vax_to_nets(x) ((x[1]<<8)|x[0])
121 #define vaxtohs(x) two_bytes_vax_to_nets(((const unsigned char *)(x)))
123 /*** Routines ***************************************************** */
126 z_quad_cksum(const unsigned char *in, /* input block */
127 uint32_t *out, /* optional longer output */
128 long length, /* original length in bytes */
129 int out_count, /* number of iterations */
130 unsigned char *c_seed /* secret seed, 8 bytes */
135 * this routine both returns the low order of the final (last in
136 * time) 32bits of the checksum, and if "out" is not a null
137 * pointer, a longer version, up to entire 32 bytes of the
138 * checksum is written unto the address pointed to.
142 register uint32_t z2;
144 register uint32_t x2;
145 const unsigned char *p;
146 register int32_t len;
149 /* use all 8 bytes of seed */
152 z2 = vaxtohl((const char *)c_seed+4);
154 out_count = 1; /* default */
156 /* This is repeated n times!! */
157 for (i = 1; i <=4 && i<= out_count; i++) {
162 * X = Z + Input ... sort of. Carry out from low half
163 * isn't done, so we're using all 32 bits of x now.
166 x = (z + vaxtohs(p));
171 x = (z + *(const unsigned char *)p++);
176 * I think this is supposed to be a squaring operation.
177 * What it really is, I haven't figured out yet.
179 * Explicit mod 2**32 is for backwards compatibility. Why
180 * mod 0x7fffffff and not 0x80000000 on the low half of
181 * the (supposed) accumulator? And where does the number
182 * 83653421 come from??
184 z = (((x * x) + (x2 * x2)) & 0xffffffff) % 0x7fffffff;
185 z2 = ((x * (x2+83653421)) & 0xffffffff) % 0x7fffffff; /* modulo */
193 /* return final z value as 32 bit version of checksum */