lib/md5.c

   1 /* $USAGI: md5.c,v 1.2 2000/11/02 11:59:24 yoshfuji Exp $ */
   2 /*      $KAME: md5.c,v 1.2 2000/05/27 07:07:48 jinmei Exp $     */
   3 /*      $Id: md5.c,v 1.6 2006/01/17 23:39:04 vincent Exp $ */
   4
   5 /*
   6  * Copyright (C) 2004 6WIND
   7  *                          <Vincent.Jardin@6WIND.com>
   8  * All rights reserved.
   9  *
  10  * This MD5 code is Big endian and Little Endian compatible.
  11  */
  12
  13 /*
  14  * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project.
  15  * All rights reserved.
  16  *
  17  * Redistribution and use in source and binary forms, with or without
  18  * modification, are permitted provided that the following conditions
  19  * are met:
  20  * 1. Redistributions of source code must retain the above copyright
  21  *    notice, this list of conditions and the following disclaimer.
  22  * 2. Redistributions in binary form must reproduce the above copyright
  23  *    notice, this list of conditions and the following disclaimer in the
  24  *    documentation and/or other materials provided with the distribution.
  25  * 3. Neither the name of the project nor the names of its contributors
  26  *    may be used to endorse or promote products derived from this software
  27  *    without specific prior written permission.
  28  *
  29  * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
  30  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  31  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  32  * ARE DISCLAIMED.  IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
  33  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  34  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  35  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  36  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  37  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  38  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  39  * SUCH DAMAGE.
  40  */
  41
  42 #include <zebra.h>
  43 #include "md5.h"
  44
  45 #define SHIFT(X, s) (((X) << (s)) | ((X) >> (32 - (s))))
  46
  47 #define F(X, Y, Z) (((X) & (Y)) | ((~X) & (Z)))
  48 #define G(X, Y, Z) (((X) & (Z)) | ((Y) & (~Z)))
  49 #define H(X, Y, Z) ((X) ^ (Y) ^ (Z))
  50 #define I(X, Y, Z) ((Y) ^ ((X) | (~Z)))
  51
  52 #define ROUND1(a, b, c, d, k, s, i) { \
  53         (a) = (a) + F((b), (c), (d)) + X[(k)] + T[(i)]; \
  54         (a) = SHIFT((a), (s)); \
  55         (a) = (b) + (a); \
  56 }
  57
  58 #define ROUND2(a, b, c, d, k, s, i) { \
  59         (a) = (a) + G((b), (c), (d)) + X[(k)] + T[(i)]; \
  60         (a) = SHIFT((a), (s)); \
  61         (a) = (b) + (a); \
  62 }
  63
  64 #define ROUND3(a, b, c, d, k, s, i) { \
  65         (a) = (a) + H((b), (c), (d)) + X[(k)] + T[(i)]; \
  66         (a) = SHIFT((a), (s)); \
  67         (a) = (b) + (a); \
  68 }
  69
  70 #define ROUND4(a, b, c, d, k, s, i) { \
  71         (a) = (a) + I((b), (c), (d)) + X[(k)] + T[(i)]; \
  72         (a) = SHIFT((a), (s)); \
  73         (a) = (b) + (a); \
  74 }
  75
  76 #define Sa       7
  77 #define Sb      12
  78 #define Sc      17
  79 #define Sd      22
  80
  81 #define Se       5
  82 #define Sf       9
  83 #define Sg      14
  84 #define Sh      20
  85
  86 #define Si       4
  87 #define Sj      11
  88 #define Sk      16
  89 #define Sl      23
  90
  91 #define Sm       6
  92 #define Sn      10
  93 #define So      15
  94 #define Sp      21
  95
  96 #define MD5_A0  0x67452301
  97 #define MD5_B0  0xefcdab89
  98 #define MD5_C0  0x98badcfe
  99 #define MD5_D0  0x10325476
 100
 101 /* Integer part of 4294967296 times abs(sin(i)), where i is in radians. */
 102 static const uint32_t T[65] = {
 103         0,
 104         0xd76aa478,     0xe8c7b756,     0x242070db,     0xc1bdceee,
 105         0xf57c0faf,     0x4787c62a,     0xa8304613,     0xfd469501,
 106         0x698098d8,     0x8b44f7af,     0xffff5bb1,     0x895cd7be,
 107         0x6b901122,     0xfd987193,     0xa679438e,     0x49b40821,
 108
 109         0xf61e2562,     0xc040b340,     0x265e5a51,     0xe9b6c7aa,
 110         0xd62f105d,     0x2441453,      0xd8a1e681,     0xe7d3fbc8,
 111         0x21e1cde6,     0xc33707d6,     0xf4d50d87,     0x455a14ed,
 112         0xa9e3e905,     0xfcefa3f8,     0x676f02d9,     0x8d2a4c8a,
 113
 114         0xfffa3942,     0x8771f681,     0x6d9d6122,     0xfde5380c,
 115         0xa4beea44,     0x4bdecfa9,     0xf6bb4b60,     0xbebfbc70,
 116         0x289b7ec6,     0xeaa127fa,     0xd4ef3085,     0x4881d05,
 117         0xd9d4d039,     0xe6db99e5,     0x1fa27cf8,     0xc4ac5665,
 118
 119         0xf4292244,     0x432aff97,     0xab9423a7,     0xfc93a039,
 120         0x655b59c3,     0x8f0ccc92,     0xffeff47d,     0x85845dd1,
 121         0x6fa87e4f,     0xfe2ce6e0,     0xa3014314,     0x4e0811a1,
 122         0xf7537e82,     0xbd3af235,     0x2ad7d2bb,     0xeb86d391,
 123 };
 124
 125 static const uint8_t md5_paddat[MD5_BUFLEN] = {
 126         0x80,   0,      0,      0,      0,      0,      0,      0,
 127         0,      0,      0,      0,      0,      0,      0,      0,
 128         0,      0,      0,      0,      0,      0,      0,      0,
 129         0,      0,      0,      0,      0,      0,      0,      0,
 130         0,      0,      0,      0,      0,      0,      0,      0,
 131         0,      0,      0,      0,      0,      0,      0,      0,
 132         0,      0,      0,      0,      0,      0,      0,      0,
 133         0,      0,      0,      0,      0,      0,      0,      0,
 134 };
 135
 136 static void md5_calc (const uint8_t *, md5_ctxt *);
 137
 138 void md5_init(md5_ctxt *ctxt)
 139 {
 140         ctxt->md5_n = 0;
 141         ctxt->md5_i = 0;
 142         ctxt->md5_sta = MD5_A0;
 143         ctxt->md5_stb = MD5_B0;
 144         ctxt->md5_stc = MD5_C0;
 145         ctxt->md5_std = MD5_D0;
 146         memset (ctxt->md5_buf, 0, sizeof(ctxt->md5_buf));
 147 }
 148
 149 void md5_loop(md5_ctxt *ctxt, const void *vinput, uint len)
 150 {
 151         uint gap, i;
 152         const uint8_t *input = vinput;
 153
 154         ctxt->md5_n += len * 8; /* byte to bit */
 155         gap = MD5_BUFLEN - ctxt->md5_i;
 156
 157         if (len >= gap) {
 158                 memcpy (ctxt->md5_buf + ctxt->md5_i, input, gap);
 159                 md5_calc(ctxt->md5_buf, ctxt);
 160
 161                 for (i = gap; i + MD5_BUFLEN <= len; i += MD5_BUFLEN) {
 162                         md5_calc((input + i), ctxt);
 163                 }
 164
 165                 ctxt->md5_i = len - i;
 166                 memcpy (ctxt->md5_buf, (input + i), ctxt->md5_i);
 167         } else {
 168                 memcpy (ctxt->md5_buf + ctxt->md5_i, input, len);
 169                 ctxt->md5_i += len;
 170         }
 171 }
 172
 173 void md5_pad(md5_ctxt *ctxt)
 174 {
 175         uint gap;
 176
 177         /* Don't count up padding. Keep md5_n. */
 178         gap = MD5_BUFLEN - ctxt->md5_i;
 179         if (gap > 8) {
 180                 memcpy (ctxt->md5_buf + ctxt->md5_i, md5_paddat,
 181                         gap - sizeof(ctxt->md5_n));
 182         } else {
 183                 /* including gap == 8 */
 184                 memcpy (ctxt->md5_buf + ctxt->md5_i, md5_paddat, gap);
 185                 md5_calc (ctxt->md5_buf, ctxt);
 186                 memcpy (ctxt->md5_buf, md5_paddat + gap,
 187                         MD5_BUFLEN - sizeof(ctxt->md5_n));
 188         }
 189
 190         /* 8 byte word */
 191         if (BYTE_ORDER == LITTLE_ENDIAN)
 192           memcpy (&ctxt->md5_buf[56], &ctxt->md5_n8[0], 8);
 193         else
 194           {
 195             ctxt->md5_buf[56] = ctxt->md5_n8[7];
 196             ctxt->md5_buf[57] = ctxt->md5_n8[6];
 197             ctxt->md5_buf[58] = ctxt->md5_n8[5];
 198             ctxt->md5_buf[59] = ctxt->md5_n8[4];
 199             ctxt->md5_buf[60] = ctxt->md5_n8[3];
 200             ctxt->md5_buf[61] = ctxt->md5_n8[2];
 201             ctxt->md5_buf[62] = ctxt->md5_n8[1];
 202             ctxt->md5_buf[63] = ctxt->md5_n8[0];
 203           }
 204         md5_calc(ctxt->md5_buf, ctxt);
 205 }
 206
 207 void md5_result(uint8_t *digest, md5_ctxt *ctxt)
 208 {
 209         /* 4 byte words */
 210         if (BYTE_ORDER == LITTLE_ENDIAN)
 211           memcpy (digest, &ctxt->md5_st8[0], 16);
 212         else if (BYTE_ORDER == BIG_ENDIAN)
 213           {
 214             digest[ 0] = ctxt->md5_st8[ 3]; digest[ 1] = ctxt->md5_st8[ 2];
 215             digest[ 2] = ctxt->md5_st8[ 1]; digest[ 3] = ctxt->md5_st8[ 0];
 216             digest[ 4] = ctxt->md5_st8[ 7]; digest[ 5] = ctxt->md5_st8[ 6];
 217             digest[ 6] = ctxt->md5_st8[ 5]; digest[ 7] = ctxt->md5_st8[ 4];
 218             digest[ 8] = ctxt->md5_st8[11]; digest[ 9] = ctxt->md5_st8[10];
 219             digest[10] = ctxt->md5_st8[ 9]; digest[11] = ctxt->md5_st8[ 8];
 220             digest[12] = ctxt->md5_st8[15]; digest[13] = ctxt->md5_st8[14];
 221             digest[14] = ctxt->md5_st8[13]; digest[15] = ctxt->md5_st8[12];
 222           }
 223 }
 224
 225 static void md5_calc(const uint8_t *b64, md5_ctxt * ctxt)
 226 {
 227         uint32_t A = ctxt->md5_sta;
 228         uint32_t B = ctxt->md5_stb;
 229         uint32_t C = ctxt->md5_stc;
 230         uint32_t D = ctxt->md5_std;
 231 #if (BYTE_ORDER == LITTLE_ENDIAN)
 232         const uint32_t *X = (const uint32_t *)b64;
 233 #elif (BYTE_ORDER == BIG_ENDIAN)
 234         uint32_t X[16];
 235
 236         if (BYTE_ORDER == BIG_ENDIAN)
 237           {
 238             /* 4 byte words */
 239             /* what a brute force but fast! */
 240             uint8_t *y = (uint8_t *)X;
 241             y[ 0] = b64[ 3]; y[ 1] = b64[ 2]; y[ 2] = b64[ 1]; y[ 3] = b64[ 0];
 242             y[ 4] = b64[ 7]; y[ 5] = b64[ 6]; y[ 6] = b64[ 5]; y[ 7] = b64[ 4];
 243             y[ 8] = b64[11]; y[ 9] = b64[10]; y[10] = b64[ 9]; y[11] = b64[ 8];
 244             y[12] = b64[15]; y[13] = b64[14]; y[14] = b64[13]; y[15] = b64[12];
 245             y[16] = b64[19]; y[17] = b64[18]; y[18] = b64[17]; y[19] = b64[16];
 246             y[20] = b64[23]; y[21] = b64[22]; y[22] = b64[21]; y[23] = b64[20];
 247             y[24] = b64[27]; y[25] = b64[26]; y[26] = b64[25]; y[27] = b64[24];
 248             y[28] = b64[31]; y[29] = b64[30]; y[30] = b64[29]; y[31] = b64[28];
 249             y[32] = b64[35]; y[33] = b64[34]; y[34] = b64[33]; y[35] = b64[32];
 250             y[36] = b64[39]; y[37] = b64[38]; y[38] = b64[37]; y[39] = b64[36];
 251             y[40] = b64[43]; y[41] = b64[42]; y[42] = b64[41]; y[43] = b64[40];
 252             y[44] = b64[47]; y[45] = b64[46]; y[46] = b64[45]; y[47] = b64[44];
 253             y[48] = b64[51]; y[49] = b64[50]; y[50] = b64[49]; y[51] = b64[48];
 254             y[52] = b64[55]; y[53] = b64[54]; y[54] = b64[53]; y[55] = b64[52];
 255             y[56] = b64[59]; y[57] = b64[58]; y[58] = b64[57]; y[59] = b64[56];
 256             y[60] = b64[63]; y[61] = b64[62]; y[62] = b64[61]; y[63] = b64[60];
 257           }
 258 #endif
 259
 260         ROUND1(A, B, C, D,  0, Sa,  1); ROUND1(D, A, B, C,  1, Sb,  2);
 261         ROUND1(C, D, A, B,  2, Sc,  3); ROUND1(B, C, D, A,  3, Sd,  4);
 262         ROUND1(A, B, C, D,  4, Sa,  5); ROUND1(D, A, B, C,  5, Sb,  6);
 263         ROUND1(C, D, A, B,  6, Sc,  7); ROUND1(B, C, D, A,  7, Sd,  8);
 264         ROUND1(A, B, C, D,  8, Sa,  9); ROUND1(D, A, B, C,  9, Sb, 10);
 265         ROUND1(C, D, A, B, 10, Sc, 11); ROUND1(B, C, D, A, 11, Sd, 12);
 266         ROUND1(A, B, C, D, 12, Sa, 13); ROUND1(D, A, B, C, 13, Sb, 14);
 267         ROUND1(C, D, A, B, 14, Sc, 15); ROUND1(B, C, D, A, 15, Sd, 16);
 268
 269         ROUND2(A, B, C, D,  1, Se, 17); ROUND2(D, A, B, C,  6, Sf, 18);
 270         ROUND2(C, D, A, B, 11, Sg, 19); ROUND2(B, C, D, A,  0, Sh, 20);
 271         ROUND2(A, B, C, D,  5, Se, 21); ROUND2(D, A, B, C, 10, Sf, 22);
 272         ROUND2(C, D, A, B, 15, Sg, 23); ROUND2(B, C, D, A,  4, Sh, 24);
 273         ROUND2(A, B, C, D,  9, Se, 25); ROUND2(D, A, B, C, 14, Sf, 26);
 274         ROUND2(C, D, A, B,  3, Sg, 27); ROUND2(B, C, D, A,  8, Sh, 28);
 275         ROUND2(A, B, C, D, 13, Se, 29); ROUND2(D, A, B, C,  2, Sf, 30);
 276         ROUND2(C, D, A, B,  7, Sg, 31); ROUND2(B, C, D, A, 12, Sh, 32);
 277
 278         ROUND3(A, B, C, D,  5, Si, 33); ROUND3(D, A, B, C,  8, Sj, 34);
 279         ROUND3(C, D, A, B, 11, Sk, 35); ROUND3(B, C, D, A, 14, Sl, 36);
 280         ROUND3(A, B, C, D,  1, Si, 37); ROUND3(D, A, B, C,  4, Sj, 38);
 281         ROUND3(C, D, A, B,  7, Sk, 39); ROUND3(B, C, D, A, 10, Sl, 40);
 282         ROUND3(A, B, C, D, 13, Si, 41); ROUND3(D, A, B, C,  0, Sj, 42);
 283         ROUND3(C, D, A, B,  3, Sk, 43); ROUND3(B, C, D, A,  6, Sl, 44);
 284         ROUND3(A, B, C, D,  9, Si, 45); ROUND3(D, A, B, C, 12, Sj, 46);
 285         ROUND3(C, D, A, B, 15, Sk, 47); ROUND3(B, C, D, A,  2, Sl, 48);
 286
 287         ROUND4(A, B, C, D,  0, Sm, 49); ROUND4(D, A, B, C,  7, Sn, 50);
 288         ROUND4(C, D, A, B, 14, So, 51); ROUND4(B, C, D, A,  5, Sp, 52);
 289         ROUND4(A, B, C, D, 12, Sm, 53); ROUND4(D, A, B, C,  3, Sn, 54);
 290         ROUND4(C, D, A, B, 10, So, 55); ROUND4(B, C, D, A,  1, Sp, 56);
 291         ROUND4(A, B, C, D,  8, Sm, 57); ROUND4(D, A, B, C, 15, Sn, 58);
 292         ROUND4(C, D, A, B,  6, So, 59); ROUND4(B, C, D, A, 13, Sp, 60);
 293         ROUND4(A, B, C, D,  4, Sm, 61); ROUND4(D, A, B, C, 11, Sn, 62);
 294         ROUND4(C, D, A, B,  2, So, 63); ROUND4(B, C, D, A,  9, Sp, 64);
 295
 296         ctxt->md5_sta += A;
 297         ctxt->md5_stb += B;
 298         ctxt->md5_stc += C;
 299         ctxt->md5_std += D;
 300 }
 301
 302 /* From RFC 2104 */
 303 void
 304 hmac_md5(text, text_len, key, key_len, digest)
 305 unsigned char*  text;                   /* pointer to data stream */
 306 int             text_len;               /* length of data stream */
 307 unsigned char*  key;                    /* pointer to authentication key */
 308 int             key_len;                /* length of authentication key */
 309 uint8_t*        digest;                 /* caller digest to be filled in */
 310
 311 {
 312     MD5_CTX context;
 313     unsigned char k_ipad[65];    /* inner padding -
 314                                  * key XORd with ipad
 315                                  */
 316     unsigned char k_opad[65];    /* outer padding -
 317                                  * key XORd with opad
 318                                  */
 319     unsigned char tk[16];
 320     int i;
 321     /* if key is longer than 64 bytes reset it to key=MD5(key) */
 322     if (key_len > 64) {
 323
 324        MD5_CTX      tctx;
 325
 326        MD5Init(&tctx);
 327        MD5Update(&tctx, key, key_len);
 328        MD5Final(tk, &tctx);
 329
 330        key = tk;
 331        key_len = 16;
 332     }
 333
 334     /*
 335      * the HMAC_MD5 transform looks like:
 336      *
 337      * MD5(K XOR opad, MD5(K XOR ipad, text))
 338      *
 339      * where K is an n byte key
 340      * ipad is the byte 0x36 repeated 64 times
 341      * opad is the byte 0x5c repeated 64 times
 342      * and text is the data being protected
 343      */
 344
 345     /* start out by storing key in pads */
 346     bzero( k_ipad, sizeof k_ipad);
 347     bzero( k_opad, sizeof k_opad);
 348     bcopy( key, k_ipad, key_len);
 349     bcopy( key, k_opad, key_len);
 350
 351     /* XOR key with ipad and opad values */
 352     for (i=0; i<64; i++) {
 353        k_ipad[i] ^= 0x36;
 354        k_opad[i] ^= 0x5c;
 355     }
 356     /*
 357      * perform inner MD5
 358      */
 359     MD5Init(&context);                  /* init context for 1st
 360                                          * pass */
 361     MD5Update(&context, k_ipad, 64);    /* start with inner pad */
 362     MD5Update(&context, text, text_len); /* then text of datagram */
 363     MD5Final((uint8_t *)digest, &context);      /* finish up 1st pass */
 364     /*
 365      * perform outer MD5
 366      */
 367     MD5Init(&context);                  /* init context for 2nd
 368                                          * pass */
 369     MD5Update(&context, k_opad, 64);    /* start with outer pad */
 370     MD5Update(&context, digest, 16);    /* then results of 1st
 371                                          * hash */
 372     MD5Final((uint8_t *)digest, &context);      /* finish up 2nd pass */
 373 }