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