2 * Copyright 1985, 1986, 1987, 1988 by the Massachusetts Institute
5 * For copying and distribution information, please see the file
8 * Quadratic Congruential Manipulation Dectection Code
10 * ref: "Message Authentication"
11 * R.R. Jueneman, S. M. Matyas, C.H. Meyer
12 * IEEE Communications Magazine,
13 * Sept 1985 Vol 23 No 9 p 29-40
15 * This routine, part of the Athena DES library built for the Kerberos
16 * authentication system, calculates a manipulation detection code for
17 * a message. It is a much faster alternative to the DES-checksum
18 * method. No guarantees are offered for its security. Refer to the
19 * paper noted above for more information
21 * Implementation for 4.2bsd
22 * by S.P. Miller Project Athena/MIT
26 * Algorithm (per paper):
28 * message to be composed of n m-bit blocks X1,...,Xn
29 * optional secret seed S in block X1
33 * initial (secret) value of accumulator C
34 * N, C, and S are known at both ends
35 * C and , optionally, S, are hidden from the end users
37 * (read array references as subscripts over time)
40 * Z[i] = (Z[i+1] + X[i])**2 modulo N
46 * iterate 4 times over plaintext, also use Zn
47 * from iteration j as seed for iteration j+1,
48 * total MDC is then a 128 bit array of the four
51 * return the last Zn and optionally, all
52 * four as output args.
55 * To inhibit brute force searches of the seed space, this
56 * implementation is modified to have
57 * Z = 64 bit accumulator
60 * S = S seed is not implemented here
61 * arithmetic is not quite real double integer precision, since we
62 * cant get at the carry or high order results from multiply,
63 * but nontheless is 64 bit arithmetic.
66 #include <afsconfig.h>
67 #include <afs/param.h>
71 #include <mit-cpyright.h>
73 /* System include files */
79 /* Application include files */
81 #include "des_internal.h"
82 #include "des_prototypes.h"
84 /* Definitions for byte swapping */
87 #define vaxtohl(x) *((afs_uint32 *)(x))
88 #define vaxtohs(x) *((unsigned short *)(x))
90 static afs_uint32 four_bytes_vax_to_nets();
91 #define vaxtohl(x) four_bytes_vax_to_nets((char *)(x))
92 static unsigned short two_bytes_vax_to_nets();
93 #define vaxtohs(x) two_bytes_vax_to_nets((char *)(x))
96 /*** Routines ***************************************************** */
99 des_cblock *c_seed; * secret seed, 8 bytes *
100 unsigned char *in; * input block *
101 afs_uint32 *out; * optional longer output *
102 int out_count; * number of iterations *
103 afs_int32 length; * original length in bytes *
106 afs_uint32 des_quad_cksum(unsigned char *in, afs_uint32 *out,
107 afs_int32 length, int out_count, des_cblock *c_seed)
111 * this routine both returns the low order of the final (last in
112 * time) 32bits of the checksum, and if "out" is not a null
113 * pointer, a longer version, up to entire 32 bytes of the
114 * checksum is written unto the address pointed to.
117 register afs_uint32 z;
118 register afs_uint32 z2;
119 register afs_uint32 x;
120 register afs_uint32 x2;
121 register unsigned char *p;
122 register afs_int32 len;
125 /* use all 8 bytes of seed */
128 z2 = vaxtohl((char *)c_seed+4);
130 out_count = 1; /* default */
132 /* This is repeated n times!! */
133 for (i = 1; i <=4 && i<= out_count; i++) {
138 x = (z + vaxtohs(p));
143 x = (z + *(char *)p++);
147 z = ((x * x) + (x2 * x2)) % 0x7fffffff;
148 z2 = (x * (x2+83653421)) % 0x7fffffff; /* modulo */
150 printf("%ld %ld\n",z,z2);
158 /* return final z value as 32 bit version of checksum */
163 static unsigned short two_bytes_vax_to_nets(char *p)
167 unsigned short result;
170 short_conv.pieces[0] = p[1];
171 short_conv.pieces[1] = p[0];
172 return(short_conv.result);
175 static afs_uint32 four_bytes_vax_to_nets(char *p)
182 long_conv.pieces[0] = p[3];
183 long_conv.pieces[1] = p[2];
184 long_conv.pieces[2] = p[1];
185 long_conv.pieces[3] = p[0];
186 return(long_conv.result);