lib/md5.c

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