zephyr/lib/quad_cksum.c

   1 /* Lifted from the krb5 1.6 source tree and hacked slightly to fit in here
   2    Karl Ramm 12/21/08 */
   3 /*
   4  * lib/des425/quad_cksum.c
   5  *
   6  * Copyright 1985, 1986, 1987, 1988,1990 by the Massachusetts Institute
   7  * of Technology.
   8  * All Rights Reserved.
   9  *
  10  * Export of this software from the United States of America may
  11  *   require a specific license from the United States Government.
  12  *   It is the responsibility of any person or organization contemplating
  13  *   export to obtain such a license before exporting.
  14  *
  15  * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
  16  * distribute this software and its documentation for any purpose and
  17  * without fee is hereby granted, provided that the above copyright
  18  * notice appear in all copies and that both that copyright notice and
  19  * this permission notice appear in supporting documentation, and that
  20  * the name of M.I.T. not be used in advertising or publicity pertaining
  21  * to distribution of the software without specific, written prior
  22  * permission.  Furthermore if you modify this software you must label
  23  * your software as modified software and not distribute it in such a
  24  * fashion that it might be confused with the original M.I.T. software.
  25  * M.I.T. makes no representations about the suitability of
  26  * this software for any purpose.  It is provided "as is" without express
  27  * or implied warranty.
  28  *
  29  *
  30  * This routine does not implement:
  31  *
  32  *
  33  * Quadratic Congruential Manipulation Dectection Code
  34  *
  35  * ref: "Message Authentication"
  36  *              R.R. Jueneman, S. M. Matyas, C.H. Meyer
  37  *              IEEE Communications Magazine,
  38  *              Sept 1985 Vol 23 No 9 p 29-40
  39  *
  40  * This routine, part of the Athena DES library built for the Kerberos
  41  * authentication system, calculates a manipulation detection code for
  42  * a message.  It is a much faster alternative to the DES-checksum
  43  * method. No guarantees are offered for its security.
  44  *
  45  * Implementation for 4.2bsd
  46  * by S.P. Miller       Project Athena/MIT
  47  */
  48
  49 /*
  50  * Algorithm (per paper):
  51  *              define:
  52  *              message to be composed of n m-bit blocks X1,...,Xn
  53  *              optional secret seed S in block X1
  54  *              MDC in block Xn+1
  55  *              prime modulus N
  56  *              accumulator Z
  57  *              initial (secret) value of accumulator C
  58  *              N, C, and S are known at both ends
  59  *              C and , optionally, S, are hidden from the end users
  60  *              then
  61  *                      (read array references as subscripts over time)
  62  *                      Z[0] = c;
  63  *                      for i = 1...n
  64  *                              Z[i] = (Z[i+1] + X[i])**2 modulo N
  65  *                      X[n+1] = Z[n] = MDC
  66  *
  67  *              Then pick
  68  *                      N = 2**31 -1
  69  *                      m = 16
  70  *                      iterate 4 times over plaintext, also use Zn
  71  *                      from iteration j as seed for iteration j+1,
  72  *                      total MDC is then a 128 bit array of the four
  73  *                      Zn;
  74  *
  75  *                      return the last Zn and optionally, all
  76  *                      four as output args.
  77  *
  78  * Modifications:
  79  *      To inhibit brute force searches of the seed space, this
  80  *      implementation is modified to have
  81  *      Z       = 64 bit accumulator
  82  *      C       = 64 bit C seed
  83  *      N       = 2**63 - 1
  84  *  S   = S seed is not implemented here
  85  *      arithmetic is not quite real double integer precision, since we
  86  *      cant get at the carry or high order results from multiply,
  87  *      but nontheless is 64 bit arithmetic.
  88  */
  89 /*
  90  * This code purports to implement the above algorithm, but fails.
  91  *
  92  * First of all, there was an implicit mod 2**32 being done on the
  93  * machines where this was developed because of their word sizes, and
  94  * for compabitility this has to be done on machines with 64-bit
  95  * words, so we make it explicit.
  96  *
  97  * Second, in the squaring operation, I really doubt the carry-over
  98  * from the low 31-bit half of the accumulator is being done right,
  99  * and using a modulus of 0x7fffffff on the low half of the
 100  * accumulator seems completely wrong.  And I challenge anyone to
 101  * explain where the number 83653421 comes from.
 102  *
 103  * --Ken Raeburn  2001-04-06
 104  */
 105
 106
 107 /* System include files */
 108 #include <sys/types.h>
 109 #include <stdio.h>
 110 #include <errno.h>
 111
 112 #include <internal.h>
 113
 114 /* Definitions for byte swapping */
 115
 116 /* vax byte order is LSB first. This is not performance critical, and
 117    is far more readable this way. */
 118 #define four_bytes_vax_to_nets(x) ((((((x[3]<<8)|x[2])<<8)|x[1])<<8)|x[0])
 119 #define vaxtohl(x) four_bytes_vax_to_nets(((const unsigned char *)(x)))
 120 #define two_bytes_vax_to_nets(x) ((x[1]<<8)|x[0])
 121 #define vaxtohs(x) two_bytes_vax_to_nets(((const unsigned char *)(x)))
 122
 123 /*** Routines ***************************************************** */
 124 #ifdef HAVE_KRB5
 125 unsigned long
 126 z_quad_cksum(const unsigned char *in,   /* input block */
 127              u_int32_t *out,            /* optional longer output */
 128              long length,               /* original length in bytes */
 129              int out_count,             /* number of iterations */
 130              unsigned char *c_seed      /* secret seed, 8 bytes */
 131              )
 132 {
 133
 134     /*
 135      * this routine both returns the low order of the final (last in
 136      * time) 32bits of the checksum, and if "out" is not a null
 137      * pointer, a longer version, up to entire 32 bytes of the
 138      * checksum is written unto the address pointed to.
 139      */
 140
 141     register u_int32_t z;
 142     register u_int32_t z2;
 143     register u_int32_t x;
 144     register u_int32_t x2;
 145     const unsigned char *p;
 146     register int32_t len;
 147     register int i;
 148
 149     /* use all 8 bytes of seed */
 150
 151     z = vaxtohl(c_seed);
 152     z2 = vaxtohl((const char *)c_seed+4);
 153     if (out == NULL)
 154         out_count = 1;          /* default */
 155
 156     /* This is repeated n times!! */
 157     for (i = 1; i <=4 && i<= out_count; i++) {
 158         len = length;
 159         p = in;
 160         while (len) {
 161             /*
 162              * X = Z + Input ... sort of.  Carry out from low half
 163              * isn't done, so we're using all 32 bits of x now.
 164              */
 165             if (len > 1) {
 166                 x = (z + vaxtohs(p));
 167                 p += 2;
 168                 len -= 2;
 169             }
 170             else {
 171                 x = (z + *(const unsigned char *)p++);
 172                 len = 0;
 173             }
 174             x2 = z2;
 175             /*
 176              * I think this is supposed to be a squaring operation.
 177              * What it really is, I haven't figured out yet.
 178              *
 179              * Explicit mod 2**32 is for backwards compatibility.  Why
 180              * mod 0x7fffffff and not 0x80000000 on the low half of
 181              * the (supposed) accumulator?  And where does the number
 182              * 83653421 come from??
 183              */
 184             z  = (((x * x) + (x2 * x2)) & 0xffffffff) % 0x7fffffff;
 185             z2 = ((x * (x2+83653421)) & 0xffffffff) % 0x7fffffff; /* modulo */
 186         }
 187
 188         if (out != NULL) {
 189             *out++ = z;
 190             *out++ = z2;
 191         }
 192     }
 193     /* return final z value as 32 bit version of checksum */
 194     return z;
 195 }
 196 #endif