src/lib/des425/quad_cksum.c

   1 /*
   2  * lib/des425/quad_cksum.c
   3  *
   4  * Copyright 1985, 1986, 1987, 1988,1990 by the Massachusetts Institute
   5  * of Technology.
   6  * All Rights Reserved.
   7  *
   8  * Export of this software from the United States of America may
   9  *   require a specific license from the United States Government.
  10  *   It is the responsibility of any person or organization contemplating
  11  *   export to obtain such a license before exporting.
  12  *
  13  * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
  14  * distribute this software and its documentation for any purpose and
  15  * without fee is hereby granted, provided that the above copyright
  16  * notice appear in all copies and that both that copyright notice and
  17  * this permission notice appear in supporting documentation, and that
  18  * the name of M.I.T. not be used in advertising or publicity pertaining
  19  * to distribution of the software without specific, written prior
  20  * permission.  M.I.T. makes no representations about the suitability of
  21  * this software for any purpose.  It is provided "as is" without express
  22  * or implied warranty.
  23  *
  24  *
  25  * Quadratic Congruential Manipulation Dectection Code
  26  *
  27  * ref: "Message Authentication"
  28  *              R.R. Jueneman, S. M. Matyas, C.H. Meyer
  29  *              IEEE Communications Magazine,
  30  *              Sept 1985 Vol 23 No 9 p 29-40
  31  *
  32  * This routine, part of the Athena DES library built for the Kerberos
  33  * authentication system, calculates a manipulation detection code for
  34  * a message.  It is a much faster alternative to the DES-checksum
  35  * method. No guarantees are offered for its security.  Refer to the
  36  * paper noted above for more information
  37  *
  38  * Implementation for 4.2bsd
  39  * by S.P. Miller       Project Athena/MIT
  40  */
  41
  42 /*
  43  * Algorithm (per paper):
  44  *              define:
  45  *              message to be composed of n m-bit blocks X1,...,Xn
  46  *              optional secret seed S in block X1
  47  *              MDC in block Xn+1
  48  *              prime modulus N
  49  *              accumulator Z
  50  *              initial (secret) value of accumulator C
  51  *              N, C, and S are known at both ends
  52  *              C and , optionally, S, are hidden from the end users
  53  *              then
  54  *                      (read array references as subscripts over time)
  55  *                      Z[0] = c;
  56  *                      for i = 1...n
  57  *                              Z[i] = (Z[i+1] + X[i])**2 modulo N
  58  *                      X[n+1] = Z[n] = MDC
  59  *
  60  *              Then pick
  61  *                      N = 2**31 -1
  62  *                      m = 16
  63  *                      iterate 4 times over plaintext, also use Zn
  64  *                      from iteration j as seed for iteration j+1,
  65  *                      total MDC is then a 128 bit array of the four
  66  *                      Zn;
  67  *
  68  *                      return the last Zn and optionally, all
  69  *                      four as output args.
  70  *
  71  * Modifications:
  72  *      To inhibit brute force searches of the seed space, this
  73  *      implementation is modified to have
  74  *      Z       = 64 bit accumulator
  75  *      C       = 64 bit C seed
  76  *      N       = 2**63 - 1
  77  *  S   = S seed is not implemented here
  78  *      arithmetic is not quite real double integer precision, since we
  79  *      cant get at the carry or high order results from multiply,
  80  *      but nontheless is 64 bit arithmetic.
  81  */
  82
  83
  84 /* System include files */
  85 #include <stdio.h>
  86 #include <errno.h>
  87
  88 /* Application include files */
  89 #include <krb5/krb5.h>
  90 #include <krb5/mit-des.h>
  91 #include "des.h"
  92 /* Definitions for byte swapping */
  93
  94 /* vax byte order is LSB first. This is not performance critical, and
  95    is far more readable this way. */
  96 #define four_bytes_vax_to_nets(x) ((((((x[3]<<8)|x[2])<<8)|x[1])<<8)|x[0])
  97 #define vaxtohl(x) four_bytes_vax_to_nets(((unsigned char *)(x)))
  98 #define two_bytes_vax_to_nets(x) ((x[1]<<8)|x[0])
  99 #define vaxtohs(x) two_bytes_vax_to_nets(((unsigned char *)(x)))
 100
 101 /* Externals */
 102 extern char *errmsg();
 103 #ifndef HAVE_ERRNO
 104 extern int errno;
 105 #endif
 106 extern int des_debug;
 107
 108 /*** Routines ***************************************************** */
 109
 110 unsigned long INTERFACE
 111 des_quad_cksum(in,out,length,out_count,c_seed)
 112     mit_des_cblock *c_seed;             /* secret seed, 8 bytes */
 113     unsigned char *in;          /* input block */
 114     unsigned long *out;         /* optional longer output */
 115     int out_count;              /* number of iterations */
 116     long length;                /* original length in bytes */
 117 {
 118
 119     /*
 120      * this routine both returns the low order of the final (last in
 121      * time) 32bits of the checksum, and if "out" is not a null
 122      * pointer, a longer version, up to entire 32 bytes of the
 123      * checksum is written unto the address pointed to.
 124      */
 125
 126     register unsigned long z;
 127     register unsigned long z2;
 128     register unsigned long x;
 129     register unsigned long x2;
 130     register unsigned char *p;
 131     register long len;
 132     register int i;
 133
 134     /* use all 8 bytes of seed */
 135
 136     z = vaxtohl(c_seed);
 137     z2 = vaxtohl((char *)c_seed+4);
 138     if (out == NULL)
 139         out_count = 1;          /* default */
 140
 141     /* This is repeated n times!! */
 142     for (i = 1; i <=4 && i<= out_count; i++) {
 143         len = length;
 144         p = in;
 145         while (len) {
 146             if (len > 1) {
 147                 x = (z + vaxtohs(p));
 148                 p += 2;
 149                 len -= 2;
 150             }
 151             else {
 152                 x = (z + *(unsigned char *)p++);
 153                 len = 0;
 154             }
 155             x2 = z2;
 156             z  = ((x * x) + (x2 * x2)) % 0x7fffffff;
 157             z2 = (x * (x2+83653421))   % 0x7fffffff; /* modulo */
 158 #ifdef DEBUG
 159             if (des_debug & 8)
 160                 printf("%d %d\n",z,z2);
 161 #endif
 162         }
 163
 164         if (out != NULL) {
 165             *out++ = z;
 166             *out++ = z2;
 167         }
 168     }
 169     /* return final z value as 32 bit version of checksum */
 170     return z;
 171 }