tools/mkcrypt/mkcrypt.c

   1 /*-
   2  * Copyright (c) 2007
   3  *      Thorsten Glaser <tg@mirbsd.de>
   4  *
   5  * Provided that these terms and disclaimer and all copyright notices
   6  * are retained or reproduced in an accompanying document, permission
   7  * is granted to deal in this work without restriction, including un-
   8  * limited rights to use, publicly perform, distribute, sell, modify,
   9  * merge, give away, or sublicence.
  10  *
  11  * Advertising materials mentioning features or use of this work must
  12  * display the following acknowledgement:
  13  *      This product includes material provided by Thorsten Glaser.
  14  *      This product includes software developed by Niels Provos.
  15  *
  16  * This work is provided "AS IS" and WITHOUT WARRANTY of any kind, to
  17  * the utmost extent permitted by applicable law, neither express nor
  18  * implied; without malicious intent or gross negligence. In no event
  19  * may a licensor, author or contributor be held liable for indirect,
  20  * direct, other damage, loss, or other issues arising in any way out
  21  * of dealing in the work, even if advised of the possibility of such
  22  * damage or existence of a defect, except proven that it results out
  23  * of said person's immediate fault when using the work as intended.
  24  */
  25
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29 #include <unistd.h>
  30 #include <sys/types.h>
  31
  32 #define MD5_BLOCK_LENGTH                64
  33 #define MD5_DIGEST_LENGTH               16
  34 #define MD5_DIGEST_STRING_LENGTH        (MD5_DIGEST_LENGTH * 2 + 1)
  35
  36 typedef struct MD5Context {
  37         u_int32_t state[4];
  38         u_int64_t count;
  39         u_int8_t  buffer[MD5_BLOCK_LENGTH];
  40 } MD5_CTX;
  41
  42 /* low-level MD5 functions from md5c.c */
  43 void    MD5Init(MD5_CTX *);
  44 void    MD5Update(MD5_CTX *, const u_int8_t *, size_t);
  45 void    MD5Pad(MD5_CTX *);
  46 void    MD5Final(u_int8_t [MD5_DIGEST_LENGTH], MD5_CTX *);
  47 void    MD5Transform(u_int32_t [4], const u_int8_t [MD5_BLOCK_LENGTH]);
  48
  49 /* high-level functions from mdXhl.c */
  50 char   *MD5End(MD5_CTX *, char *);
  51 char   *MD5File(const char *, char *);
  52 char   *MD5FileChunk(const char *, char *, off_t, off_t);
  53 char   *MD5Data(const u_int8_t *, size_t, char *);
  54
  55 void to64(char *, u_int32_t, int);
  56 char *md5crypt(const char *pw, const char *salt);
  57 int pwd_gensalt(char *, int);
  58
  59 static unsigned char itoa64[] =         /* 0 ... 63 => ascii - 64 */
  60         "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
  61
  62 void
  63 to64(char *s, u_int32_t v, int n)
  64 {
  65         while (--n >= 0) {
  66                 *s++ = itoa64[v&0x3f];
  67                 v >>= 6;
  68         }
  69 }
  70
  71 #define PUT_64BIT_LE(cp, value) do {                                    \
  72         (cp)[7] = (value) >> 56;                                        \
  73         (cp)[6] = (value) >> 48;                                        \
  74         (cp)[5] = (value) >> 40;                                        \
  75         (cp)[4] = (value) >> 32;                                        \
  76         (cp)[3] = (value) >> 24;                                        \
  77         (cp)[2] = (value) >> 16;                                        \
  78         (cp)[1] = (value) >> 8;                                         \
  79         (cp)[0] = (value); } while (0)
  80
  81 #define PUT_32BIT_LE(cp, value) do {                                    \
  82         (cp)[3] = (value) >> 24;                                        \
  83         (cp)[2] = (value) >> 16;                                        \
  84         (cp)[1] = (value) >> 8;                                         \
  85         (cp)[0] = (value); } while (0)
  86
  87 static u_int8_t PADDING[MD5_BLOCK_LENGTH] = {
  88         0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  89         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  90         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  91 };
  92
  93 /*
  94  * Start MD5 accumulation.  Set bit count to 0 and buffer to mysterious
  95  * initialization constants.
  96  */
  97 void
  98 MD5Init(MD5_CTX *ctx)
  99 {
 100         ctx->count = 0;
 101         ctx->state[0] = 0x67452301;
 102         ctx->state[1] = 0xefcdab89;
 103         ctx->state[2] = 0x98badcfe;
 104         ctx->state[3] = 0x10325476;
 105 }
 106
 107 /*
 108  * Update context to reflect the concatenation of another buffer full
 109  * of bytes.
 110  */
 111 void
 112 MD5Update(MD5_CTX *ctx, const unsigned char *input, size_t len)
 113 {
 114         size_t have, need;
 115
 116         /* Check how many bytes we already have and how many more we need. */
 117         have = (size_t)((ctx->count >> 3) & (MD5_BLOCK_LENGTH - 1));
 118         need = MD5_BLOCK_LENGTH - have;
 119
 120         /* Update bitcount */
 121         ctx->count += (u_int64_t)len << 3;
 122
 123         if (len >= need) {
 124                 if (have != 0) {
 125                         memcpy(ctx->buffer + have, input, need);
 126                         MD5Transform(ctx->state, ctx->buffer);
 127                         input += need;
 128                         len -= need;
 129                         have = 0;
 130                 }
 131
 132                 /* Process data in MD5_BLOCK_LENGTH-byte chunks. */
 133                 while (len >= MD5_BLOCK_LENGTH) {
 134                         MD5Transform(ctx->state, input);
 135                         input += MD5_BLOCK_LENGTH;
 136                         len -= MD5_BLOCK_LENGTH;
 137                 }
 138         }
 139
 140         /* Handle any remaining bytes of data. */
 141         if (len != 0)
 142                 memcpy(ctx->buffer + have, input, len);
 143 }
 144
 145 /*
 146  * Pad pad to 64-byte boundary with the bit pattern
 147  * 1 0* (64-bit count of bits processed, MSB-first)
 148  */
 149 void
 150 MD5Pad(MD5_CTX *ctx)
 151 {
 152         u_int8_t count[8];
 153         size_t padlen;
 154
 155         /* Convert count to 8 bytes in little endian order. */
 156         PUT_64BIT_LE(count, ctx->count);
 157
 158         /* Pad out to 56 mod 64. */
 159         padlen = MD5_BLOCK_LENGTH -
 160             ((ctx->count >> 3) & (MD5_BLOCK_LENGTH - 1));
 161         if (padlen < 1 + 8)
 162                 padlen += MD5_BLOCK_LENGTH;
 163         MD5Update(ctx, PADDING, padlen - 8);            /* padlen - 8 <= 64 */
 164         MD5Update(ctx, count, 8);
 165 }
 166
 167 /*
 168  * Final wrapup--call MD5Pad, fill in digest and zero out ctx.
 169  */
 170 void
 171 MD5Final(unsigned char digest[MD5_DIGEST_LENGTH], MD5_CTX *ctx)
 172 {
 173         int i;
 174
 175         MD5Pad(ctx);
 176         if (digest != NULL) {
 177                 for (i = 0; i < 4; i++)
 178                         PUT_32BIT_LE(digest + i * 4, ctx->state[i]);
 179                 memset(ctx, 0, sizeof(*ctx));
 180         }
 181 }
 182
 183
 184 /* The four core functions - F1 is optimized somewhat */
 185
 186 /* #define F1(x, y, z) (x & y | ~x & z) */
 187 #define F1(x, y, z) (z ^ (x & (y ^ z)))
 188 #define F2(x, y, z) F1(z, x, y)
 189 #define F3(x, y, z) (x ^ y ^ z)
 190 #define F4(x, y, z) (y ^ (x | ~z))
 191
 192 /* This is the central step in the MD5 algorithm. */
 193 #define MD5STEP(f, w, x, y, z, data, s) \
 194         ( w += f(x, y, z) + data,  w = w<<s | w>>(32-s),  w += x )
 195
 196 /*
 197  * The core of the MD5 algorithm, this alters an existing MD5 hash to
 198  * reflect the addition of 16 longwords of new data.  MD5Update blocks
 199  * the data and converts bytes into longwords for this routine.
 200  */
 201 void
 202 MD5Transform(u_int32_t state[4], const u_int8_t block[MD5_BLOCK_LENGTH])
 203 {
 204         u_int32_t a, b, c, d, in[MD5_BLOCK_LENGTH / 4];
 205
 206 #if BYTE_ORDER == LITTLE_ENDIAN
 207         memcpy(in, block, sizeof(in));
 208 #else
 209         for (a = 0; a < MD5_BLOCK_LENGTH / 4; a++) {
 210                 in[a] = (u_int32_t)(
 211                     (u_int32_t)(block[a * 4 + 0]) |
 212                     (u_int32_t)(block[a * 4 + 1]) <<  8 |
 213                     (u_int32_t)(block[a * 4 + 2]) << 16 |
 214                     (u_int32_t)(block[a * 4 + 3]) << 24);
 215         }
 216 #endif
 217
 218         a = state[0];
 219         b = state[1];
 220         c = state[2];
 221         d = state[3];
 222
 223         MD5STEP(F1, a, b, c, d, in[ 0] + 0xd76aa478,  7);
 224         MD5STEP(F1, d, a, b, c, in[ 1] + 0xe8c7b756, 12);
 225         MD5STEP(F1, c, d, a, b, in[ 2] + 0x242070db, 17);
 226         MD5STEP(F1, b, c, d, a, in[ 3] + 0xc1bdceee, 22);
 227         MD5STEP(F1, a, b, c, d, in[ 4] + 0xf57c0faf,  7);
 228         MD5STEP(F1, d, a, b, c, in[ 5] + 0x4787c62a, 12);
 229         MD5STEP(F1, c, d, a, b, in[ 6] + 0xa8304613, 17);
 230         MD5STEP(F1, b, c, d, a, in[ 7] + 0xfd469501, 22);
 231         MD5STEP(F1, a, b, c, d, in[ 8] + 0x698098d8,  7);
 232         MD5STEP(F1, d, a, b, c, in[ 9] + 0x8b44f7af, 12);
 233         MD5STEP(F1, c, d, a, b, in[10] + 0xffff5bb1, 17);
 234         MD5STEP(F1, b, c, d, a, in[11] + 0x895cd7be, 22);
 235         MD5STEP(F1, a, b, c, d, in[12] + 0x6b901122,  7);
 236         MD5STEP(F1, d, a, b, c, in[13] + 0xfd987193, 12);
 237         MD5STEP(F1, c, d, a, b, in[14] + 0xa679438e, 17);
 238         MD5STEP(F1, b, c, d, a, in[15] + 0x49b40821, 22);
 239
 240         MD5STEP(F2, a, b, c, d, in[ 1] + 0xf61e2562,  5);
 241         MD5STEP(F2, d, a, b, c, in[ 6] + 0xc040b340,  9);
 242         MD5STEP(F2, c, d, a, b, in[11] + 0x265e5a51, 14);
 243         MD5STEP(F2, b, c, d, a, in[ 0] + 0xe9b6c7aa, 20);
 244         MD5STEP(F2, a, b, c, d, in[ 5] + 0xd62f105d,  5);
 245         MD5STEP(F2, d, a, b, c, in[10] + 0x02441453,  9);
 246         MD5STEP(F2, c, d, a, b, in[15] + 0xd8a1e681, 14);
 247         MD5STEP(F2, b, c, d, a, in[ 4] + 0xe7d3fbc8, 20);
 248         MD5STEP(F2, a, b, c, d, in[ 9] + 0x21e1cde6,  5);
 249         MD5STEP(F2, d, a, b, c, in[14] + 0xc33707d6,  9);
 250         MD5STEP(F2, c, d, a, b, in[ 3] + 0xf4d50d87, 14);
 251         MD5STEP(F2, b, c, d, a, in[ 8] + 0x455a14ed, 20);
 252         MD5STEP(F2, a, b, c, d, in[13] + 0xa9e3e905,  5);
 253         MD5STEP(F2, d, a, b, c, in[ 2] + 0xfcefa3f8,  9);
 254         MD5STEP(F2, c, d, a, b, in[ 7] + 0x676f02d9, 14);
 255         MD5STEP(F2, b, c, d, a, in[12] + 0x8d2a4c8a, 20);
 256
 257         MD5STEP(F3, a, b, c, d, in[ 5] + 0xfffa3942,  4);
 258         MD5STEP(F3, d, a, b, c, in[ 8] + 0x8771f681, 11);
 259         MD5STEP(F3, c, d, a, b, in[11] + 0x6d9d6122, 16);
 260         MD5STEP(F3, b, c, d, a, in[14] + 0xfde5380c, 23);
 261         MD5STEP(F3, a, b, c, d, in[ 1] + 0xa4beea44,  4);
 262         MD5STEP(F3, d, a, b, c, in[ 4] + 0x4bdecfa9, 11);
 263         MD5STEP(F3, c, d, a, b, in[ 7] + 0xf6bb4b60, 16);
 264         MD5STEP(F3, b, c, d, a, in[10] + 0xbebfbc70, 23);
 265         MD5STEP(F3, a, b, c, d, in[13] + 0x289b7ec6,  4);
 266         MD5STEP(F3, d, a, b, c, in[ 0] + 0xeaa127fa, 11);
 267         MD5STEP(F3, c, d, a, b, in[ 3] + 0xd4ef3085, 16);
 268         MD5STEP(F3, b, c, d, a, in[ 6] + 0x04881d05, 23);
 269         MD5STEP(F3, a, b, c, d, in[ 9] + 0xd9d4d039,  4);
 270         MD5STEP(F3, d, a, b, c, in[12] + 0xe6db99e5, 11);
 271         MD5STEP(F3, c, d, a, b, in[15] + 0x1fa27cf8, 16);
 272         MD5STEP(F3, b, c, d, a, in[2 ] + 0xc4ac5665, 23);
 273
 274         MD5STEP(F4, a, b, c, d, in[ 0] + 0xf4292244,  6);
 275         MD5STEP(F4, d, a, b, c, in[7 ] + 0x432aff97, 10);
 276         MD5STEP(F4, c, d, a, b, in[14] + 0xab9423a7, 15);
 277         MD5STEP(F4, b, c, d, a, in[5 ] + 0xfc93a039, 21);
 278         MD5STEP(F4, a, b, c, d, in[12] + 0x655b59c3,  6);
 279         MD5STEP(F4, d, a, b, c, in[3 ] + 0x8f0ccc92, 10);
 280         MD5STEP(F4, c, d, a, b, in[10] + 0xffeff47d, 15);
 281         MD5STEP(F4, b, c, d, a, in[1 ] + 0x85845dd1, 21);
 282         MD5STEP(F4, a, b, c, d, in[8 ] + 0x6fa87e4f,  6);
 283         MD5STEP(F4, d, a, b, c, in[15] + 0xfe2ce6e0, 10);
 284         MD5STEP(F4, c, d, a, b, in[6 ] + 0xa3014314, 15);
 285         MD5STEP(F4, b, c, d, a, in[13] + 0x4e0811a1, 21);
 286         MD5STEP(F4, a, b, c, d, in[4 ] + 0xf7537e82,  6);
 287         MD5STEP(F4, d, a, b, c, in[11] + 0xbd3af235, 10);
 288         MD5STEP(F4, c, d, a, b, in[2 ] + 0x2ad7d2bb, 15);
 289         MD5STEP(F4, b, c, d, a, in[9 ] + 0xeb86d391, 21);
 290
 291         state[0] += a;
 292         state[1] += b;
 293         state[2] += c;
 294         state[3] += d;
 295 }
 296
 297 /*
 298  * UNIX password
 299  *
 300  * Use MD5 for what it is best at...
 301  */
 302
 303 char *
 304 md5crypt(const char *pw, const char *salt)
 305 {
 306         /*
 307          * This string is magic for this algorithm.  Having
 308          * it this way, we can get get better later on
 309          */
 310         static const unsigned char *magic = (const unsigned char *)"$1$";
 311
 312         static char     passwd[120], *p;
 313         static const unsigned char *sp,*ep;
 314         unsigned char   final[16];
 315         int sl,pl,i;
 316         MD5_CTX ctx,ctx1;
 317         u_int32_t l;
 318
 319         /* Refine the Salt first */
 320         sp = (const unsigned char *)salt;
 321
 322         /* If it starts with the magic string, then skip that */
 323         if(!strncmp((const char *)sp,(const char *)magic,strlen((const char *)magic)))
 324                 sp += strlen((const char *)magic);
 325
 326         /* It stops at the first '$', max 8 chars */
 327         for(ep=sp;*ep && *ep != '$' && ep < (sp+8);ep++)
 328                 continue;
 329
 330         /* get the length of the true salt */
 331         sl = ep - sp;
 332
 333         MD5Init(&ctx);
 334
 335         /* The password first, since that is what is most unknown */
 336         MD5Update(&ctx,(const unsigned char *)pw,strlen(pw));
 337
 338         /* Then our magic string */
 339         MD5Update(&ctx,magic,strlen((const char *)magic));
 340
 341         /* Then the raw salt */
 342         MD5Update(&ctx,sp,sl);
 343
 344         /* Then just as many characters of the MD5(pw,salt,pw) */
 345         MD5Init(&ctx1);
 346         MD5Update(&ctx1,(const unsigned char *)pw,strlen(pw));
 347         MD5Update(&ctx1,sp,sl);
 348         MD5Update(&ctx1,(const unsigned char *)pw,strlen(pw));
 349         MD5Final(final,&ctx1);
 350         for(pl = strlen(pw); pl > 0; pl -= 16)
 351                 MD5Update(&ctx,final,pl>16 ? 16 : pl);
 352
 353         /* Don't leave anything around in vm they could use. */
 354         memset(final,0,sizeof final);
 355
 356         /* Then something really weird... */
 357         for (i = strlen(pw); i ; i >>= 1)
 358                 if(i&1)
 359                     MD5Update(&ctx, final, 1);
 360                 else
 361                     MD5Update(&ctx, (const unsigned char *)pw, 1);
 362
 363         /* Now make the output string */
 364         snprintf(passwd, sizeof(passwd), "%s%.*s$", magic,
 365             sl, (const char *)sp);
 366
 367         MD5Final(final,&ctx);
 368
 369         /*
 370          * and now, just to make sure things don't run too fast
 371          * On a 60 Mhz Pentium this takes 34 msec, so you would
 372          * need 30 seconds to build a 1000 entry dictionary...
 373          */
 374         for(i=0;i<1000;i++) {
 375                 MD5Init(&ctx1);
 376                 if(i & 1)
 377                         MD5Update(&ctx1,(const unsigned char *)pw,strlen(pw));
 378                 else
 379                         MD5Update(&ctx1,final,16);
 380
 381                 if(i % 3)
 382                         MD5Update(&ctx1,sp,sl);
 383
 384                 if(i % 7)
 385                         MD5Update(&ctx1,(const unsigned char *)pw,strlen(pw));
 386
 387                 if(i & 1)
 388                         MD5Update(&ctx1,final,16);
 389                 else
 390                         MD5Update(&ctx1,(const unsigned char *)pw,strlen(pw));
 391                 MD5Final(final,&ctx1);
 392         }
 393
 394         p = passwd + strlen(passwd);
 395
 396         l = (final[ 0]<<16) | (final[ 6]<<8) | final[12]; to64(p,l,4); p += 4;
 397         l = (final[ 1]<<16) | (final[ 7]<<8) | final[13]; to64(p,l,4); p += 4;
 398         l = (final[ 2]<<16) | (final[ 8]<<8) | final[14]; to64(p,l,4); p += 4;
 399         l = (final[ 3]<<16) | (final[ 9]<<8) | final[15]; to64(p,l,4); p += 4;
 400         l = (final[ 4]<<16) | (final[10]<<8) | final[ 5]; to64(p,l,4); p += 4;
 401         l =                    final[11]                ; to64(p,l,2); p += 2;
 402         *p = '\0';
 403
 404         /* Don't leave anything around in vm they could use. */
 405         memset(final, 0, sizeof final);
 406
 407         return passwd;
 408 }
 409
 410 int pwd_gensalt(char *salt, int saltlen) {
 411
 412         *salt = '\0';
 413
 414         if (saltlen < 13) {     /* $1$8salt$\0 */
 415                 return 0;
 416         }
 417
 418         strcpy(salt, "$1$");
 419         to64(&salt[3], random(), 4);
 420         to64(&salt[7], random(), 4);
 421         strcpy(&salt[11], "$");
 422         return 1;
 423 }
 424
 425 int main(int argc, char *argv[]) {
 426         char salt[16];
 427         char *pw;
 428
 429         if (!argv[1]) {
 430                 fprintf(stderr, "Syntax Error!\n");
 431                 return (1);
 432         }
 433         if (!pwd_gensalt(salt, sizeof (salt)))
 434                 return (255);
 435         if ((pw = md5crypt(argv[1], salt)) == NULL) {
 436                 fprintf(stderr, "Error generating password!\n");
 437                 return (1);
 438         }
 439         printf("%s\n", pw);
 440         return (0);
 441 }