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         {                                                                      \
  54                 (a) = (a) + F((b), (c), (d)) + X[(k)] + T[(i)];                \
  55                 (a) = SHIFT((a), (s));                                         \
  56                 (a) = (b) + (a);                                               \
  57         }
  58
  59 #define ROUND2(a, b, c, d, k, s, i)                                            \
  60         {                                                                      \
  61                 (a) = (a) + G((b), (c), (d)) + X[(k)] + T[(i)];                \
  62                 (a) = SHIFT((a), (s));                                         \
  63                 (a) = (b) + (a);                                               \
  64         }
  65
  66 #define ROUND3(a, b, c, d, k, s, i)                                            \
  67         {                                                                      \
  68                 (a) = (a) + H((b), (c), (d)) + X[(k)] + T[(i)];                \
  69                 (a) = SHIFT((a), (s));                                         \
  70                 (a) = (b) + (a);                                               \
  71         }
  72
  73 #define ROUND4(a, b, c, d, k, s, i)                                            \
  74         {                                                                      \
  75                 (a) = (a) + I((b), (c), (d)) + X[(k)] + T[(i)];                \
  76                 (a) = SHIFT((a), (s));                                         \
  77                 (a) = (b) + (a);                                               \
  78         }
  79
  80 #define Sa       7
  81 #define Sb      12
  82 #define Sc      17
  83 #define Sd      22
  84
  85 #define Se       5
  86 #define Sf       9
  87 #define Sg      14
  88 #define Sh      20
  89
  90 #define Si       4
  91 #define Sj      11
  92 #define Sk      16
  93 #define Sl      23
  94
  95 #define Sm       6
  96 #define Sn      10
  97 #define So      15
  98 #define Sp      21
  99
 100 #define MD5_A0  0x67452301
 101 #define MD5_B0  0xefcdab89
 102 #define MD5_C0  0x98badcfe
 103 #define MD5_D0  0x10325476
 104
 105 /* Integer part of 4294967296 times abs(sin(i)), where i is in radians. */
 106 static const uint32_t T[65] = {
 107         0,        0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf,
 108         0x4787c62a, 0xa8304613, 0xfd469501, 0x698098d8, 0x8b44f7af, 0xffff5bb1,
 109         0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
 110
 111         0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x2441453,
 112         0xd8a1e681, 0xe7d3fbc8, 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
 113         0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
 114
 115         0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9,
 116         0xf6bb4b60, 0xbebfbc70, 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05,
 117         0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
 118
 119         0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92,
 120         0xffeff47d, 0x85845dd1, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
 121         0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391,
 122 };
 123
 124 static const uint8_t md5_paddat[MD5_BUFLEN] = {
 125         0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 126         0,    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 127         0,    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 128 };
 129
 130 static void md5_calc(const uint8_t *, md5_ctxt *);
 131
 132 void md5_init(md5_ctxt *ctxt)
 133 {
 134         ctxt->md5_n = 0;
 135         ctxt->md5_i = 0;
 136         ctxt->md5_sta = MD5_A0;
 137         ctxt->md5_stb = MD5_B0;
 138         ctxt->md5_stc = MD5_C0;
 139         ctxt->md5_std = MD5_D0;
 140         memset(ctxt->md5_buf, 0, sizeof(ctxt->md5_buf));
 141 }
 142
 143 void md5_loop(md5_ctxt *ctxt, const void *vinput, uint len)
 144 {
 145         uint gap, i;
 146         const uint8_t *input = vinput;
 147
 148         ctxt->md5_n += len * 8; /* byte to bit */
 149         gap = MD5_BUFLEN - ctxt->md5_i;
 150
 151         if (len >= gap) {
 152                 memcpy(ctxt->md5_buf + ctxt->md5_i, input, gap);
 153                 md5_calc(ctxt->md5_buf, ctxt);
 154
 155                 for (i = gap; i + MD5_BUFLEN <= len; i += MD5_BUFLEN) {
 156                         md5_calc((input + i), ctxt);
 157                 }
 158
 159                 ctxt->md5_i = len - i;
 160                 memcpy(ctxt->md5_buf, (input + i), ctxt->md5_i);
 161         } else {
 162                 memcpy(ctxt->md5_buf + ctxt->md5_i, input, len);
 163                 ctxt->md5_i += len;
 164         }
 165 }
 166
 167 void md5_pad(md5_ctxt *ctxt)
 168 {
 169         uint gap;
 170
 171         /* Don't count up padding. Keep md5_n. */
 172         gap = MD5_BUFLEN - ctxt->md5_i;
 173         if (gap > 8) {
 174                 memcpy(ctxt->md5_buf + ctxt->md5_i, md5_paddat,
 175                        gap - sizeof(ctxt->md5_n));
 176         } else {
 177                 /* including gap == 8 */
 178                 memcpy(ctxt->md5_buf + ctxt->md5_i, md5_paddat, gap);
 179                 md5_calc(ctxt->md5_buf, ctxt);
 180                 memcpy(ctxt->md5_buf, md5_paddat + gap,
 181                        MD5_BUFLEN - sizeof(ctxt->md5_n));
 182         }
 183
 184         /* 8 byte word */
 185         if (BYTE_ORDER == LITTLE_ENDIAN)
 186                 memcpy(&ctxt->md5_buf[56], &ctxt->md5_n8[0], 8);
 187         else {
 188                 ctxt->md5_buf[56] = ctxt->md5_n8[7];
 189                 ctxt->md5_buf[57] = ctxt->md5_n8[6];
 190                 ctxt->md5_buf[58] = ctxt->md5_n8[5];
 191                 ctxt->md5_buf[59] = ctxt->md5_n8[4];
 192                 ctxt->md5_buf[60] = ctxt->md5_n8[3];
 193                 ctxt->md5_buf[61] = ctxt->md5_n8[2];
 194                 ctxt->md5_buf[62] = ctxt->md5_n8[1];
 195                 ctxt->md5_buf[63] = ctxt->md5_n8[0];
 196         }
 197         md5_calc(ctxt->md5_buf, ctxt);
 198 }
 199
 200 void md5_result(uint8_t *digest, md5_ctxt *ctxt)
 201 {
 202         /* 4 byte words */
 203         if (BYTE_ORDER == LITTLE_ENDIAN)
 204                 memcpy(digest, &ctxt->md5_st8[0], 16);
 205         else if (BYTE_ORDER == BIG_ENDIAN) {
 206                 digest[0] = ctxt->md5_st8[3];
 207                 digest[1] = ctxt->md5_st8[2];
 208                 digest[2] = ctxt->md5_st8[1];
 209                 digest[3] = ctxt->md5_st8[0];
 210                 digest[4] = ctxt->md5_st8[7];
 211                 digest[5] = ctxt->md5_st8[6];
 212                 digest[6] = ctxt->md5_st8[5];
 213                 digest[7] = ctxt->md5_st8[4];
 214                 digest[8] = ctxt->md5_st8[11];
 215                 digest[9] = ctxt->md5_st8[10];
 216                 digest[10] = ctxt->md5_st8[9];
 217                 digest[11] = ctxt->md5_st8[8];
 218                 digest[12] = ctxt->md5_st8[15];
 219                 digest[13] = ctxt->md5_st8[14];
 220                 digest[14] = ctxt->md5_st8[13];
 221                 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                 /* 4 byte words */
 238                 /* what a brute force but fast! */
 239                 uint8_t *y = (uint8_t *)X;
 240                 y[0] = b64[3];
 241                 y[1] = b64[2];
 242                 y[2] = b64[1];
 243                 y[3] = b64[0];
 244                 y[4] = b64[7];
 245                 y[5] = b64[6];
 246                 y[6] = b64[5];
 247                 y[7] = b64[4];
 248                 y[8] = b64[11];
 249                 y[9] = b64[10];
 250                 y[10] = b64[9];
 251                 y[11] = b64[8];
 252                 y[12] = b64[15];
 253                 y[13] = b64[14];
 254                 y[14] = b64[13];
 255                 y[15] = b64[12];
 256                 y[16] = b64[19];
 257                 y[17] = b64[18];
 258                 y[18] = b64[17];
 259                 y[19] = b64[16];
 260                 y[20] = b64[23];
 261                 y[21] = b64[22];
 262                 y[22] = b64[21];
 263                 y[23] = b64[20];
 264                 y[24] = b64[27];
 265                 y[25] = b64[26];
 266                 y[26] = b64[25];
 267                 y[27] = b64[24];
 268                 y[28] = b64[31];
 269                 y[29] = b64[30];
 270                 y[30] = b64[29];
 271                 y[31] = b64[28];
 272                 y[32] = b64[35];
 273                 y[33] = b64[34];
 274                 y[34] = b64[33];
 275                 y[35] = b64[32];
 276                 y[36] = b64[39];
 277                 y[37] = b64[38];
 278                 y[38] = b64[37];
 279                 y[39] = b64[36];
 280                 y[40] = b64[43];
 281                 y[41] = b64[42];
 282                 y[42] = b64[41];
 283                 y[43] = b64[40];
 284                 y[44] = b64[47];
 285                 y[45] = b64[46];
 286                 y[46] = b64[45];
 287                 y[47] = b64[44];
 288                 y[48] = b64[51];
 289                 y[49] = b64[50];
 290                 y[50] = b64[49];
 291                 y[51] = b64[48];
 292                 y[52] = b64[55];
 293                 y[53] = b64[54];
 294                 y[54] = b64[53];
 295                 y[55] = b64[52];
 296                 y[56] = b64[59];
 297                 y[57] = b64[58];
 298                 y[58] = b64[57];
 299                 y[59] = b64[56];
 300                 y[60] = b64[63];
 301                 y[61] = b64[62];
 302                 y[62] = b64[61];
 303                 y[63] = b64[60];
 304         }
 305 #endif
 306
 307         ROUND1(A, B, C, D, 0, Sa, 1);
 308         ROUND1(D, A, B, C, 1, Sb, 2);
 309         ROUND1(C, D, A, B, 2, Sc, 3);
 310         ROUND1(B, C, D, A, 3, Sd, 4);
 311         ROUND1(A, B, C, D, 4, Sa, 5);
 312         ROUND1(D, A, B, C, 5, Sb, 6);
 313         ROUND1(C, D, A, B, 6, Sc, 7);
 314         ROUND1(B, C, D, A, 7, Sd, 8);
 315         ROUND1(A, B, C, D, 8, Sa, 9);
 316         ROUND1(D, A, B, C, 9, Sb, 10);
 317         ROUND1(C, D, A, B, 10, Sc, 11);
 318         ROUND1(B, C, D, A, 11, Sd, 12);
 319         ROUND1(A, B, C, D, 12, Sa, 13);
 320         ROUND1(D, A, B, C, 13, Sb, 14);
 321         ROUND1(C, D, A, B, 14, Sc, 15);
 322         ROUND1(B, C, D, A, 15, Sd, 16);
 323
 324         ROUND2(A, B, C, D, 1, Se, 17);
 325         ROUND2(D, A, B, C, 6, Sf, 18);
 326         ROUND2(C, D, A, B, 11, Sg, 19);
 327         ROUND2(B, C, D, A, 0, Sh, 20);
 328         ROUND2(A, B, C, D, 5, Se, 21);
 329         ROUND2(D, A, B, C, 10, Sf, 22);
 330         ROUND2(C, D, A, B, 15, Sg, 23);
 331         ROUND2(B, C, D, A, 4, Sh, 24);
 332         ROUND2(A, B, C, D, 9, Se, 25);
 333         ROUND2(D, A, B, C, 14, Sf, 26);
 334         ROUND2(C, D, A, B, 3, Sg, 27);
 335         ROUND2(B, C, D, A, 8, Sh, 28);
 336         ROUND2(A, B, C, D, 13, Se, 29);
 337         ROUND2(D, A, B, C, 2, Sf, 30);
 338         ROUND2(C, D, A, B, 7, Sg, 31);
 339         ROUND2(B, C, D, A, 12, Sh, 32);
 340
 341         ROUND3(A, B, C, D, 5, Si, 33);
 342         ROUND3(D, A, B, C, 8, Sj, 34);
 343         ROUND3(C, D, A, B, 11, Sk, 35);
 344         ROUND3(B, C, D, A, 14, Sl, 36);
 345         ROUND3(A, B, C, D, 1, Si, 37);
 346         ROUND3(D, A, B, C, 4, Sj, 38);
 347         ROUND3(C, D, A, B, 7, Sk, 39);
 348         ROUND3(B, C, D, A, 10, Sl, 40);
 349         ROUND3(A, B, C, D, 13, Si, 41);
 350         ROUND3(D, A, B, C, 0, Sj, 42);
 351         ROUND3(C, D, A, B, 3, Sk, 43);
 352         ROUND3(B, C, D, A, 6, Sl, 44);
 353         ROUND3(A, B, C, D, 9, Si, 45);
 354         ROUND3(D, A, B, C, 12, Sj, 46);
 355         ROUND3(C, D, A, B, 15, Sk, 47);
 356         ROUND3(B, C, D, A, 2, Sl, 48);
 357
 358         ROUND4(A, B, C, D, 0, Sm, 49);
 359         ROUND4(D, A, B, C, 7, Sn, 50);
 360         ROUND4(C, D, A, B, 14, So, 51);
 361         ROUND4(B, C, D, A, 5, Sp, 52);
 362         ROUND4(A, B, C, D, 12, Sm, 53);
 363         ROUND4(D, A, B, C, 3, Sn, 54);
 364         ROUND4(C, D, A, B, 10, So, 55);
 365         ROUND4(B, C, D, A, 1, Sp, 56);
 366         ROUND4(A, B, C, D, 8, Sm, 57);
 367         ROUND4(D, A, B, C, 15, Sn, 58);
 368         ROUND4(C, D, A, B, 6, So, 59);
 369         ROUND4(B, C, D, A, 13, Sp, 60);
 370         ROUND4(A, B, C, D, 4, Sm, 61);
 371         ROUND4(D, A, B, C, 11, Sn, 62);
 372         ROUND4(C, D, A, B, 2, So, 63);
 373         ROUND4(B, C, D, A, 9, Sp, 64);
 374
 375         ctxt->md5_sta += A;
 376         ctxt->md5_stb += B;
 377         ctxt->md5_stc += C;
 378         ctxt->md5_std += D;
 379 }
 380
 381 /* From RFC 2104 */
 382 void hmac_md5(text, text_len, key, key_len,
 383               digest) unsigned char *text; /* pointer to data stream */
 384 int text_len;                              /* length of data stream */
 385 unsigned char *key;                        /* pointer to authentication key */
 386 int key_len;                               /* length of authentication key */
 387 uint8_t *digest;                           /* caller digest to be filled in */
 388
 389 {
 390         MD5_CTX context;
 391         unsigned char k_ipad[65]; /* inner padding -
 392                                   * key XORd with ipad
 393                                   */
 394         unsigned char k_opad[65]; /* outer padding -
 395                                   * key XORd with opad
 396                                   */
 397         unsigned char tk[16];
 398         int i;
 399         /* if key is longer than 64 bytes reset it to key=MD5(key) */
 400         if (key_len > 64) {
 401
 402                 MD5_CTX tctx;
 403
 404                 MD5Init(&tctx);
 405                 MD5Update(&tctx, key, key_len);
 406                 MD5Final(tk, &tctx);
 407
 408                 key = tk;
 409                 key_len = 16;
 410         }
 411
 412         /*
 413          * the HMAC_MD5 transform looks like:
 414          *
 415          * MD5(K XOR opad, MD5(K XOR ipad, text))
 416          *
 417          * where K is an n byte key
 418          * ipad is the byte 0x36 repeated 64 times
 419          * opad is the byte 0x5c repeated 64 times
 420          * and text is the data being protected
 421          */
 422
 423         /* start out by storing key in pads */
 424         bzero(k_ipad, sizeof k_ipad);
 425         bzero(k_opad, sizeof k_opad);
 426         bcopy(key, k_ipad, key_len);
 427         bcopy(key, k_opad, key_len);
 428
 429         /* XOR key with ipad and opad values */
 430         for (i = 0; i < 64; i++) {
 431                 k_ipad[i] ^= 0x36;
 432                 k_opad[i] ^= 0x5c;
 433         }
 434         /*
 435          * perform inner MD5
 436          */
 437         MD5Init(&context);                     /* init context for 1st
 438                                                 * pass */
 439         MD5Update(&context, k_ipad, 64);       /* start with inner pad */
 440         MD5Update(&context, text, text_len);   /* then text of datagram */
 441         MD5Final((uint8_t *)digest, &context); /* finish up 1st pass */
 442         /*
 443          * perform outer MD5
 444          */
 445         MD5Init(&context);                     /* init context for 2nd
 446                                                 * pass */
 447         MD5Update(&context, k_opad, 64);       /* start with outer pad */
 448         MD5Update(&context, digest, 16);       /* then results of 1st
 449                                                 * hash */
 450         MD5Final((uint8_t *)digest, &context); /* finish up 2nd pass */
 451 }