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 #include <afs/stds.h>
  69
  70 RCSID
  71     ("$Header$");
  72
  73 #include <mit-cpyright.h>
  74
  75 /* System include files */
  76 #ifndef KERNEL
  77 #include <stdio.h>
  78 #endif
  79 #include <errno.h>
  80
  81 /* Application include files */
  82 #include <des.h>
  83 #include "des_internal.h"
  84 #include "des_prototypes.h"
  85
  86 /* Definitions for byte swapping */
  87
  88 #ifdef LSBFIRST
  89 #define vaxtohl(x) (*((afs_uint32 *)(x)))
  90 #define vaxtohs(x) (*((unsigned short *)(x)))
  91 #else
  92 static afs_uint32 four_bytes_vax_to_nets();
  93 #define vaxtohl(x) four_bytes_vax_to_nets((char *)(x))
  94 static unsigned short two_bytes_vax_to_nets();
  95 #define vaxtohs(x) two_bytes_vax_to_nets((char *)(x))
  96 #endif
  97
  98 /*** Routines ***************************************************** */
  99
 100 /*
 101     des_cblock *c_seed;         * secret seed, 8 bytes *
 102     unsigned char *in;          * input block *
 103     afs_uint32 *out;            * optional longer output *
 104     int out_count;              * number of iterations *
 105     afs_int32 length;           * original length in bytes *
 106 */
 107
 108 afs_uint32
 109 des_quad_cksum(unsigned char *in, afs_uint32 * out, afs_int32 length,
 110                int out_count, des_cblock * c_seed)
 111 {
 112
 113     /*
 114      * this routine both returns the low order of the final (last in
 115      * time) 32bits of the checksum, and if "out" is not a null
 116      * pointer, a longer version, up to entire 32 bytes of the
 117      * checksum is written unto the address pointed to.
 118      */
 119
 120     register afs_uint32 z;
 121     register afs_uint32 z2;
 122     register afs_uint32 x;
 123     register afs_uint32 x2;
 124     register unsigned char *p;
 125     register afs_int32 len;
 126     register int i;
 127
 128     /* use all 8 bytes of seed */
 129
 130     z = vaxtohl(c_seed);
 131     z2 = vaxtohl((char *)c_seed + 4);
 132     if (out == NULL)
 133         out_count = 1;          /* default */
 134
 135     /* This is repeated n times!! */
 136     for (i = 1; i <= 4 && i <= out_count; i++) {
 137         len = length;
 138         p = in;
 139         while (len) {
 140             if (len > 1) {
 141                 x = (z + vaxtohs(p));
 142                 p += 2;
 143                 len -= 2;
 144             } else {
 145                 x = (z + *(char *)p++);
 146                 len = 0;
 147             }
 148             x2 = z2;
 149             z = ((x * x) + (x2 * x2)) % 0x7fffffff;
 150             z2 = (x * (x2 + 83653421)) % 0x7fffffff;    /* modulo */
 151             if (des_debug & 8)
 152                 printf("%ld %ld\n", z, z2);
 153         }
 154
 155         if (out != NULL) {
 156             *out++ = z;
 157             *out++ = z2;
 158         }
 159     }
 160     /* return final z value as 32 bit version of checksum */
 161     return z;
 162 }
 163
 164 #ifdef MSBFIRST
 165
 166 static unsigned short
 167 two_bytes_vax_to_nets(char *p)
 168 {
 169     union {
 170         char pieces[2];
 171         unsigned short result;
 172     } short_conv;
 173
 174     short_conv.pieces[0] = p[1];
 175     short_conv.pieces[1] = p[0];
 176     return (short_conv.result);
 177 }
 178
 179 static afs_uint32
 180 four_bytes_vax_to_nets(char *p)
 181 {
 182     union {
 183         char pieces[4];
 184         afs_uint32 result;
 185     } long_conv;
 186
 187     long_conv.pieces[0] = p[3];
 188     long_conv.pieces[1] = p[2];
 189     long_conv.pieces[2] = p[1];
 190     long_conv.pieces[3] = p[0];
 191     return (long_conv.result);
 192 }
 193
 194 #endif