1/* 2 * md5 crypt implementation 3 * 4 * original md5 crypt design is from Poul-Henning Kamp 5 * this implementation was created based on the code in freebsd 6 * at least 32bit int is assumed, key is limited and $1$ prefix is mandatory, 7 * on error "*" is returned 8 */ 9#include <string.h> 10#include <stdint.h> 11 12/* public domain md5 implementation based on rfc1321 and libtomcrypt */ 13 14struct md5 { 15 uint64_t len; /* processed message length */ 16 uint32_t h[4]; /* hash state */ 17 uint8_t buf[64]; /* message block buffer */ 18}; 19 20static uint32_t rol(uint32_t n, int k) { return (n << k) | (n >> (32-k)); } 21#define F(x,y,z) (z ^ (x & (y ^ z))) 22#define G(x,y,z) (y ^ (z & (y ^ x))) 23#define H(x,y,z) (x ^ y ^ z) 24#define I(x,y,z) (y ^ (x | ~z)) 25#define FF(a,b,c,d,w,s,t) a += F(b,c,d) + w + t; a = rol(a,s) + b 26#define GG(a,b,c,d,w,s,t) a += G(b,c,d) + w + t; a = rol(a,s) + b 27#define HH(a,b,c,d,w,s,t) a += H(b,c,d) + w + t; a = rol(a,s) + b 28#define II(a,b,c,d,w,s,t) a += I(b,c,d) + w + t; a = rol(a,s) + b 29 30static const uint32_t tab[64] = { 310xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501, 320x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821, 330xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8, 340x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a, 350xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70, 360x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665, 370xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1, 380x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 39}; 40 41static void processblock(struct md5 *s, const uint8_t *buf) 42{ 43 uint32_t i, W[16], a, b, c, d; 44 45 for (i = 0; i < 16; i++) { 46 W[i] = buf[4*i]; 47 W[i] |= (uint32_t)buf[4*i+1]<<8; 48 W[i] |= (uint32_t)buf[4*i+2]<<16; 49 W[i] |= (uint32_t)buf[4*i+3]<<24; 50 } 51 52 a = s->h[0]; 53 b = s->h[1]; 54 c = s->h[2]; 55 d = s->h[3]; 56 57 i = 0; 58 while (i < 16) { 59 FF(a,b,c,d, W[i], 7, tab[i]); i++; 60 FF(d,a,b,c, W[i], 12, tab[i]); i++; 61 FF(c,d,a,b, W[i], 17, tab[i]); i++; 62 FF(b,c,d,a, W[i], 22, tab[i]); i++; 63 } 64 while (i < 32) { 65 GG(a,b,c,d, W[(5*i+1)%16], 5, tab[i]); i++; 66 GG(d,a,b,c, W[(5*i+1)%16], 9, tab[i]); i++; 67 GG(c,d,a,b, W[(5*i+1)%16], 14, tab[i]); i++; 68 GG(b,c,d,a, W[(5*i+1)%16], 20, tab[i]); i++; 69 } 70 while (i < 48) { 71 HH(a,b,c,d, W[(3*i+5)%16], 4, tab[i]); i++; 72 HH(d,a,b,c, W[(3*i+5)%16], 11, tab[i]); i++; 73 HH(c,d,a,b, W[(3*i+5)%16], 16, tab[i]); i++; 74 HH(b,c,d,a, W[(3*i+5)%16], 23, tab[i]); i++; 75 } 76 while (i < 64) { 77 II(a,b,c,d, W[7*i%16], 6, tab[i]); i++; 78 II(d,a,b,c, W[7*i%16], 10, tab[i]); i++; 79 II(c,d,a,b, W[7*i%16], 15, tab[i]); i++; 80 II(b,c,d,a, W[7*i%16], 21, tab[i]); i++; 81 } 82 83 s->h[0] += a; 84 s->h[1] += b; 85 s->h[2] += c; 86 s->h[3] += d; 87} 88 89static void pad(struct md5 *s) 90{ 91 unsigned r = s->len % 64; 92 93 s->buf[r++] = 0x80; 94 if (r > 56) { 95 memset(s->buf + r, 0, 64 - r); 96 r = 0; 97 processblock(s, s->buf); 98 } 99 memset(s->buf + r, 0, 56 - r); 100 s->len *= 8; 101 s->buf[56] = s->len; 102 s->buf[57] = s->len >> 8; 103 s->buf[58] = s->len >> 16; 104 s->buf[59] = s->len >> 24; 105 s->buf[60] = s->len >> 32; 106 s->buf[61] = s->len >> 40; 107 s->buf[62] = s->len >> 48; 108 s->buf[63] = s->len >> 56; 109 processblock(s, s->buf); 110} 111 112static void md5_init(struct md5 *s) 113{ 114 s->len = 0; 115 s->h[0] = 0x67452301; 116 s->h[1] = 0xefcdab89; 117 s->h[2] = 0x98badcfe; 118 s->h[3] = 0x10325476; 119} 120 121static void md5_sum(struct md5 *s, uint8_t *md) 122{ 123 int i; 124 125 pad(s); 126 for (i = 0; i < 4; i++) { 127 md[4*i] = s->h[i]; 128 md[4*i+1] = s->h[i] >> 8; 129 md[4*i+2] = s->h[i] >> 16; 130 md[4*i+3] = s->h[i] >> 24; 131 } 132} 133 134static void md5_update(struct md5 *s, const void *m, unsigned long len) 135{ 136 const uint8_t *p = m; 137 unsigned r = s->len % 64; 138 139 s->len += len; 140 if (r) { 141 if (len < 64 - r) { 142 memcpy(s->buf + r, p, len); 143 return; 144 } 145 memcpy(s->buf + r, p, 64 - r); 146 len -= 64 - r; 147 p += 64 - r; 148 processblock(s, s->buf); 149 } 150 for (; len >= 64; len -= 64, p += 64) 151 processblock(s, p); 152 memcpy(s->buf, p, len); 153} 154 155/*- 156 * Copyright (c) 2003 Poul-Henning Kamp 157 * All rights reserved. 158 * 159 * Redistribution and use in source and binary forms, with or without 160 * modification, are permitted provided that the following conditions 161 * are met: 162 * 1. Redistributions of source code must retain the above copyright 163 * notice, this list of conditions and the following disclaimer. 164 * 2. Redistributions in binary form must reproduce the above copyright 165 * notice, this list of conditions and the following disclaimer in the 166 * documentation and/or other materials provided with the distribution. 167 * 168 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 169 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 170 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 171 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 172 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 173 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 174 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 175 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 176 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 177 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 178 * SUCH DAMAGE. 179 */ 180 181/* key limit is not part of the original design, added for DoS protection */ 182#define KEY_MAX 30000 183#define SALT_MAX 8 184 185static const unsigned char b64[] = 186"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; 187 188static char *to64(char *s, unsigned int u, int n) 189{ 190 while (--n >= 0) { 191 *s++ = b64[u % 64]; 192 u /= 64; 193 } 194 return s; 195} 196 197static char *md5crypt(const char *key, const char *setting, char *output) 198{ 199 struct md5 ctx; 200 unsigned char md[16]; 201 unsigned int i, klen, slen; 202 const char *salt; 203 char *p; 204 205 /* reject large keys */ 206 klen = strnlen(key, KEY_MAX+1); 207 if (klen > KEY_MAX) 208 return 0; 209 210 /* setting: $1$salt$ (closing $ is optional) */ 211 if (strncmp(setting, "$1$", 3) != 0) 212 return 0; 213 salt = setting + 3; 214 for (i = 0; i < SALT_MAX && salt[i] && salt[i] != '$'; i++); 215 slen = i; 216 217 /* md5(key salt key) */ 218 md5_init(&ctx); 219 md5_update(&ctx, key, klen); 220 md5_update(&ctx, salt, slen); 221 md5_update(&ctx, key, klen); 222 md5_sum(&ctx, md); 223 224 /* md5(key $1$ salt repeated-md weird-key[0]-0) */ 225 md5_init(&ctx); 226 md5_update(&ctx, key, klen); 227 md5_update(&ctx, setting, 3 + slen); 228 for (i = klen; i > sizeof md; i -= sizeof md) 229 md5_update(&ctx, md, sizeof md); 230 md5_update(&ctx, md, i); 231 md[0] = 0; 232 for (i = klen; i; i >>= 1) 233 if (i & 1) 234 md5_update(&ctx, md, 1); 235 else 236 md5_update(&ctx, key, 1); 237 md5_sum(&ctx, md); 238 239 /* md = f(md, key, salt) iteration */ 240 for (i = 0; i < 1000; i++) { 241 md5_init(&ctx); 242 if (i % 2) 243 md5_update(&ctx, key, klen); 244 else 245 md5_update(&ctx, md, sizeof md); 246 if (i % 3) 247 md5_update(&ctx, salt, slen); 248 if (i % 7) 249 md5_update(&ctx, key, klen); 250 if (i % 2) 251 md5_update(&ctx, md, sizeof md); 252 else 253 md5_update(&ctx, key, klen); 254 md5_sum(&ctx, md); 255 } 256 257 /* output is $1$salt$hash */ 258 memcpy(output, setting, 3 + slen); 259 p = output + 3 + slen; 260 *p++ = '$'; 261 static const unsigned char perm[][3] = { 262 0,6,12,1,7,13,2,8,14,3,9,15,4,10,5 }; 263 for (i=0; i<5; i++) p = to64(p, 264 (md[perm[i][0]]<<16)|(md[perm[i][1]]<<8)|md[perm[i][2]], 4); 265 p = to64(p, md[11], 2); 266 *p = 0; 267 268 return output; 269} 270 271char *__crypt_md5(const char *key, const char *setting, char *output) 272{ 273 static const char testkey[] = "Xy01@#\x01\x02\x80\x7f\xff\r\n\x81\t !"; 274 static const char testsetting[] = "$1$abcd0123$"; 275 static const char testhash[] = "$1$abcd0123$9Qcg8DyviekV3tDGMZynJ1"; 276 char testbuf[64]; 277 char *p, *q; 278 279 p = md5crypt(key, setting, output); 280 /* self test and stack cleanup */ 281 q = md5crypt(testkey, testsetting, testbuf); 282 if (!p || q != testbuf || memcmp(testbuf, testhash, sizeof testhash)) 283 return "*"; 284 return p; 285} 286