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