src/des/quad_cksum.c

   1 /*
   2  * Copyright 1985, 1986, 1987, 1988 by the Massachusetts Institute
   3  * of Technology.
   4  *
   5  * For copying and distribution information, please see the file
   6  * <mit-cpyright.h>.
   7  *
   8  * Quadratic Congruential Manipulation Dectection Code
   9  *
  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
  14  *
  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
  20  *
  21  * Implementation for 4.2bsd
  22  * by S.P. Miller       Project Athena/MIT
  23  */
  24
  25 /*
  26  * Algorithm (per paper):
  27  *              define:
  28  *              message to be composed of n m-bit blocks X1,...,Xn
  29  *              optional secret seed S in block X1
  30  *              MDC in block Xn+1
  31  *              prime modulus N
  32  *              accumulator Z
  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
  36  *              then
  37  *                      (read array references as subscripts over time)
  38  *                      Z[0] = c;
  39  *                      for i = 1...n
  40  *                              Z[i] = (Z[i+1] + X[i])**2 modulo N
  41  *                      X[n+1] = Z[n] = MDC
  42  *
  43  *              Then pick
  44  *                      N = 2**31 -1
  45  *                      m = 16
  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
  49  *                      Zn;
  50  *
  51  *                      return the last Zn and optionally, all
  52  *                      four as output args.
  53  *
  54  * Modifications:
  55  *      To inhibit brute force searches of the seed space, this
  56  *      implementation is modified to have
  57  *      Z       = 64 bit accumulator
  58  *      C       = 64 bit C seed
  59  *      N       = 2**63 - 1
  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.
  64  */
  65
  66 #include <afsconfig.h>
  67 #include <afs/param.h>
  68
  69 RCSID("$Header$");
  70
  71 #include <mit-cpyright.h>
  72
  73 /* System include files */
  74 #include <stdio.h>
  75 #include <errno.h>
  76
  77 /* Application include files */
  78 #include <des.h>
  79 #include "des_internal.h"
  80 /* Definitions for byte swapping */
  81
  82 #ifdef LSBFIRST
  83 #define vaxtohl(x) *((afs_uint32 *)(x))
  84 #define vaxtohs(x) *((unsigned short *)(x))
  85 #else
  86 static afs_uint32 four_bytes_vax_to_nets();
  87 #define vaxtohl(x) four_bytes_vax_to_nets((char *)(x))
  88 static unsigned short two_bytes_vax_to_nets();
  89 #define vaxtohs(x) two_bytes_vax_to_nets((char *)(x))
  90 #endif
  91
  92 /* Externals */
  93 extern char *errmsg();
  94 extern int des_debug;
  95
  96 /*** Routines ***************************************************** */
  97
  98 afs_uint32
  99 des_quad_cksum(in,out,length,out_count,c_seed)
 100     des_cblock *c_seed;         /* secret seed, 8 bytes */
 101     unsigned char *in;          /* input block */
 102     afs_uint32 *out;            /* optional longer output */
 103     int out_count;              /* number of iterations */
 104     afs_int32 length;           /* original length in bytes */
 105 {
 106
 107     /*
 108      * this routine both returns the low order of the final (last in
 109      * time) 32bits of the checksum, and if "out" is not a null
 110      * pointer, a longer version, up to entire 32 bytes of the
 111      * checksum is written unto the address pointed to.
 112      */
 113
 114     register afs_uint32 z;
 115     register afs_uint32 z2;
 116     register afs_uint32 x;
 117     register afs_uint32 x2;
 118     register unsigned char *p;
 119     register afs_int32 len;
 120     register int i;
 121
 122     /* use all 8 bytes of seed */
 123
 124     z = vaxtohl(c_seed);
 125     z2 = vaxtohl((char *)c_seed+4);
 126     if (out == NULL)
 127         out_count = 1;          /* default */
 128
 129     /* This is repeated n times!! */
 130     for (i = 1; i <=4 && i<= out_count; i++) {
 131         len = length;
 132         p = in;
 133         while (len) {
 134             if (len > 1) {
 135                 x = (z + vaxtohs(p));
 136                 p += 2;
 137                 len -= 2;
 138             }
 139             else {
 140                 x = (z + *(char *)p++);
 141                 len = 0;
 142             }
 143             x2 = z2;
 144             z  = ((x * x) + (x2 * x2)) % 0x7fffffff;
 145             z2 = (x * (x2+83653421))   % 0x7fffffff; /* modulo */
 146             if (des_debug & 8)
 147                 printf("%ld %ld\n",z,z2);
 148         }
 149
 150         if (out != NULL) {
 151             *out++ = z;
 152             *out++ = z2;
 153         }
 154     }
 155     /* return final z value as 32 bit version of checksum */
 156     return z;
 157 }
 158 #ifdef MSBFIRST
 159
 160 static unsigned short two_bytes_vax_to_nets(p)
 161     char *p;
 162 {
 163     union {
 164         char pieces[2];
 165         unsigned short result;
 166     } short_conv;
 167
 168     short_conv.pieces[0] = p[1];
 169     short_conv.pieces[1] = p[0];
 170     return(short_conv.result);
 171 }
 172
 173 static afs_uint32 four_bytes_vax_to_nets(p)
 174     char *p;
 175 {
 176     union {
 177         char pieces[4];
 178         afs_uint32 result;
 179     } long_conv;
 180
 181     long_conv.pieces[0] = p[3];
 182     long_conv.pieces[1] = p[2];
 183     long_conv.pieces[2] = p[1];
 184     long_conv.pieces[3] = p[0];
 185     return(long_conv.result);
 186 }
 187
 188 #endif