1 /* $NetBSD: md5.c,v 1.1.1.2 2010/03/08 02:14:20 lukem Exp $ */ 2 3 /* md5.c -- MD5 message-digest algorithm */ 4 /* OpenLDAP: pkg/ldap/libraries/liblutil/md5.c,v 1.19.2.4 2009/01/22 00:00:58 kurt Exp */ 5 /* This work is part of OpenLDAP Software <http://www.openldap.org/>. 6 * 7 * Copyright 1998-2009 The OpenLDAP Foundation. 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted only as authorized by the OpenLDAP 12 * Public License. 13 * 14 * A copy of this license is available in the file LICENSE in the 15 * top-level directory of the distribution or, alternatively, at 16 * <http://www.OpenLDAP.org/license.html>. 17 */ 18 /* This work was adapted for inclusion in OpenLDAP Software by 19 * Kurt D. Zeilenga based upon code developed by Colin Plumb 20 * and subsequently modified by Jim Kingdon. 21 */ 22 23 /* 24 * This code implements the MD5 message-digest algorithm. 25 * The algorithm is due to Ron Rivest. This code was 26 * written by Colin Plumb in 1993, no copyright is claimed. 27 * This code is in the public domain; do with it what you wish. 28 * 29 * Equivalent code is available from RSA Data Security, Inc. 30 * This code has been tested against that, and is equivalent, 31 * except that you don't need to include two pages of legalese 32 * with every copy. 33 * 34 * To compute the message digest of a chunk of bytes, declare an 35 * MD5Context structure, pass it to MD5Init, call MD5Update as 36 * needed on buffers full of bytes, and then call MD5Final, which 37 * will fill a supplied 16-byte array with the digest. 38 */ 39 40 /* This code was modified in 1997 by Jim Kingdon of Cyclic Software to 41 not require an integer type which is exactly 32 bits. This work 42 draws on the changes for the same purpose by Tatu Ylonen 43 <ylo@cs.hut.fi> as part of SSH, but since I didn't actually use 44 that code, there is no copyright issue. I hereby disclaim 45 copyright in any changes I have made; this code remains in the 46 public domain. */ 47 48 #include "portable.h" 49 50 #include <ac/string.h> 51 52 /* include socket.h to get sys/types.h and/or winsock2.h */ 53 #include <ac/socket.h> 54 55 #include <lutil_md5.h> 56 57 /* Little-endian byte-swapping routines. Note that these do not 58 depend on the size of datatypes such as ber_uint_t, nor do they require 59 us to detect the endianness of the machine we are running on. It 60 is possible they should be macros for speed, but I would be 61 surprised if they were a performance bottleneck for MD5. */ 62 63 static ber_uint_t 64 getu32( const unsigned char *addr ) 65 { 66 return (((((unsigned long)addr[3] << 8) | addr[2]) << 8) 67 | addr[1]) << 8 | addr[0]; 68 } 69 70 static void 71 putu32( ber_uint_t data, unsigned char *addr ) 72 { 73 addr[0] = (unsigned char)data; 74 addr[1] = (unsigned char)(data >> 8); 75 addr[2] = (unsigned char)(data >> 16); 76 addr[3] = (unsigned char)(data >> 24); 77 } 78 79 /* 80 * Start MD5 accumulation. Set bit count to 0 and buffer to mysterious 81 * initialization constants. 82 */ 83 void 84 lutil_MD5Init( struct lutil_MD5Context *ctx ) 85 { 86 ctx->buf[0] = 0x67452301; 87 ctx->buf[1] = 0xefcdab89; 88 ctx->buf[2] = 0x98badcfe; 89 ctx->buf[3] = 0x10325476; 90 91 ctx->bits[0] = 0; 92 ctx->bits[1] = 0; 93 } 94 95 /* 96 * Update context to reflect the concatenation of another buffer full 97 * of bytes. 98 */ 99 void 100 lutil_MD5Update( 101 struct lutil_MD5Context *ctx, 102 const unsigned char *buf, 103 ber_len_t len 104 ) 105 { 106 ber_uint_t t; 107 108 /* Update bitcount */ 109 110 t = ctx->bits[0]; 111 if ((ctx->bits[0] = (t + ((ber_uint_t)len << 3)) & 0xffffffff) < t) 112 ctx->bits[1]++; /* Carry from low to high */ 113 ctx->bits[1] += len >> 29; 114 115 t = (t >> 3) & 0x3f; /* Bytes already in shsInfo->data */ 116 117 /* Handle any leading odd-sized chunks */ 118 119 if ( t ) { 120 unsigned char *p = ctx->in + t; 121 122 t = 64-t; 123 if (len < t) { 124 AC_MEMCPY(p, buf, len); 125 return; 126 } 127 AC_MEMCPY(p, buf, t); 128 lutil_MD5Transform(ctx->buf, ctx->in); 129 buf += t; 130 len -= t; 131 } 132 133 /* Process data in 64-byte chunks */ 134 135 while (len >= 64) { 136 AC_MEMCPY(ctx->in, buf, 64); 137 lutil_MD5Transform(ctx->buf, ctx->in); 138 buf += 64; 139 len -= 64; 140 } 141 142 /* Handle any remaining bytes of data. */ 143 144 AC_MEMCPY(ctx->in, buf, len); 145 } 146 147 /* 148 * Final wrapup - pad to 64-byte boundary with the bit pattern 149 * 1 0* (64-bit count of bits processed, MSB-first) 150 */ 151 void 152 lutil_MD5Final( unsigned char *digest, struct lutil_MD5Context *ctx ) 153 { 154 unsigned count; 155 unsigned char *p; 156 157 /* Compute number of bytes mod 64 */ 158 count = (ctx->bits[0] >> 3) & 0x3F; 159 160 /* Set the first char of padding to 0x80. This is safe since there is 161 always at least one byte free */ 162 p = ctx->in + count; 163 *p++ = 0x80; 164 165 /* Bytes of padding needed to make 64 bytes */ 166 count = 64 - 1 - count; 167 168 /* Pad out to 56 mod 64 */ 169 if (count < 8) { 170 /* Two lots of padding: Pad the first block to 64 bytes */ 171 memset(p, '\0', count); 172 lutil_MD5Transform(ctx->buf, ctx->in); 173 174 /* Now fill the next block with 56 bytes */ 175 memset(ctx->in, '\0', 56); 176 } else { 177 /* Pad block to 56 bytes */ 178 memset(p, '\0', count-8); 179 } 180 181 /* Append length in bits and transform */ 182 putu32(ctx->bits[0], ctx->in + 56); 183 putu32(ctx->bits[1], ctx->in + 60); 184 185 lutil_MD5Transform(ctx->buf, ctx->in); 186 putu32(ctx->buf[0], digest); 187 putu32(ctx->buf[1], digest + 4); 188 putu32(ctx->buf[2], digest + 8); 189 putu32(ctx->buf[3], digest + 12); 190 memset(ctx, '\0', sizeof(ctx)); /* In case it's sensitive */ 191 } 192 193 #ifndef ASM_MD5 194 195 /* The four core functions - F1 is optimized somewhat */ 196 197 /* #define F1(x, y, z) (x & y | ~x & z) */ 198 #define F1(x, y, z) (z ^ (x & (y ^ z))) 199 #define F2(x, y, z) F1(z, x, y) 200 #define F3(x, y, z) (x ^ y ^ z) 201 #define F4(x, y, z) (y ^ (x | ~z)) 202 203 /* This is the central step in the MD5 algorithm. */ 204 #define MD5STEP(f, w, x, y, z, data, s) \ 205 ( w += f(x, y, z) + data, w &= 0xffffffff, w = w<<s | w>>(32-s), w += x ) 206 207 /* 208 * The core of the MD5 algorithm, this alters an existing MD5 hash to 209 * reflect the addition of 16 longwords of new data. MD5Update blocks 210 * the data and converts bytes into longwords for this routine. 211 */ 212 void 213 lutil_MD5Transform( ber_uint_t *buf, const unsigned char *inraw ) 214 { 215 register ber_uint_t a, b, c, d; 216 ber_uint_t in[16]; 217 int i; 218 219 for (i = 0; i < 16; ++i) 220 in[i] = getu32 (inraw + 4 * i); 221 222 a = buf[0]; 223 b = buf[1]; 224 c = buf[2]; 225 d = buf[3]; 226 227 MD5STEP(F1, a, b, c, d, in[ 0]+0xd76aa478, 7); 228 MD5STEP(F1, d, a, b, c, in[ 1]+0xe8c7b756, 12); 229 MD5STEP(F1, c, d, a, b, in[ 2]+0x242070db, 17); 230 MD5STEP(F1, b, c, d, a, in[ 3]+0xc1bdceee, 22); 231 MD5STEP(F1, a, b, c, d, in[ 4]+0xf57c0faf, 7); 232 MD5STEP(F1, d, a, b, c, in[ 5]+0x4787c62a, 12); 233 MD5STEP(F1, c, d, a, b, in[ 6]+0xa8304613, 17); 234 MD5STEP(F1, b, c, d, a, in[ 7]+0xfd469501, 22); 235 MD5STEP(F1, a, b, c, d, in[ 8]+0x698098d8, 7); 236 MD5STEP(F1, d, a, b, c, in[ 9]+0x8b44f7af, 12); 237 MD5STEP(F1, c, d, a, b, in[10]+0xffff5bb1, 17); 238 MD5STEP(F1, b, c, d, a, in[11]+0x895cd7be, 22); 239 MD5STEP(F1, a, b, c, d, in[12]+0x6b901122, 7); 240 MD5STEP(F1, d, a, b, c, in[13]+0xfd987193, 12); 241 MD5STEP(F1, c, d, a, b, in[14]+0xa679438e, 17); 242 MD5STEP(F1, b, c, d, a, in[15]+0x49b40821, 22); 243 244 MD5STEP(F2, a, b, c, d, in[ 1]+0xf61e2562, 5); 245 MD5STEP(F2, d, a, b, c, in[ 6]+0xc040b340, 9); 246 MD5STEP(F2, c, d, a, b, in[11]+0x265e5a51, 14); 247 MD5STEP(F2, b, c, d, a, in[ 0]+0xe9b6c7aa, 20); 248 MD5STEP(F2, a, b, c, d, in[ 5]+0xd62f105d, 5); 249 MD5STEP(F2, d, a, b, c, in[10]+0x02441453, 9); 250 MD5STEP(F2, c, d, a, b, in[15]+0xd8a1e681, 14); 251 MD5STEP(F2, b, c, d, a, in[ 4]+0xe7d3fbc8, 20); 252 MD5STEP(F2, a, b, c, d, in[ 9]+0x21e1cde6, 5); 253 MD5STEP(F2, d, a, b, c, in[14]+0xc33707d6, 9); 254 MD5STEP(F2, c, d, a, b, in[ 3]+0xf4d50d87, 14); 255 MD5STEP(F2, b, c, d, a, in[ 8]+0x455a14ed, 20); 256 MD5STEP(F2, a, b, c, d, in[13]+0xa9e3e905, 5); 257 MD5STEP(F2, d, a, b, c, in[ 2]+0xfcefa3f8, 9); 258 MD5STEP(F2, c, d, a, b, in[ 7]+0x676f02d9, 14); 259 MD5STEP(F2, b, c, d, a, in[12]+0x8d2a4c8a, 20); 260 261 MD5STEP(F3, a, b, c, d, in[ 5]+0xfffa3942, 4); 262 MD5STEP(F3, d, a, b, c, in[ 8]+0x8771f681, 11); 263 MD5STEP(F3, c, d, a, b, in[11]+0x6d9d6122, 16); 264 MD5STEP(F3, b, c, d, a, in[14]+0xfde5380c, 23); 265 MD5STEP(F3, a, b, c, d, in[ 1]+0xa4beea44, 4); 266 MD5STEP(F3, d, a, b, c, in[ 4]+0x4bdecfa9, 11); 267 MD5STEP(F3, c, d, a, b, in[ 7]+0xf6bb4b60, 16); 268 MD5STEP(F3, b, c, d, a, in[10]+0xbebfbc70, 23); 269 MD5STEP(F3, a, b, c, d, in[13]+0x289b7ec6, 4); 270 MD5STEP(F3, d, a, b, c, in[ 0]+0xeaa127fa, 11); 271 MD5STEP(F3, c, d, a, b, in[ 3]+0xd4ef3085, 16); 272 MD5STEP(F3, b, c, d, a, in[ 6]+0x04881d05, 23); 273 MD5STEP(F3, a, b, c, d, in[ 9]+0xd9d4d039, 4); 274 MD5STEP(F3, d, a, b, c, in[12]+0xe6db99e5, 11); 275 MD5STEP(F3, c, d, a, b, in[15]+0x1fa27cf8, 16); 276 MD5STEP(F3, b, c, d, a, in[ 2]+0xc4ac5665, 23); 277 278 MD5STEP(F4, a, b, c, d, in[ 0]+0xf4292244, 6); 279 MD5STEP(F4, d, a, b, c, in[ 7]+0x432aff97, 10); 280 MD5STEP(F4, c, d, a, b, in[14]+0xab9423a7, 15); 281 MD5STEP(F4, b, c, d, a, in[ 5]+0xfc93a039, 21); 282 MD5STEP(F4, a, b, c, d, in[12]+0x655b59c3, 6); 283 MD5STEP(F4, d, a, b, c, in[ 3]+0x8f0ccc92, 10); 284 MD5STEP(F4, c, d, a, b, in[10]+0xffeff47d, 15); 285 MD5STEP(F4, b, c, d, a, in[ 1]+0x85845dd1, 21); 286 MD5STEP(F4, a, b, c, d, in[ 8]+0x6fa87e4f, 6); 287 MD5STEP(F4, d, a, b, c, in[15]+0xfe2ce6e0, 10); 288 MD5STEP(F4, c, d, a, b, in[ 6]+0xa3014314, 15); 289 MD5STEP(F4, b, c, d, a, in[13]+0x4e0811a1, 21); 290 MD5STEP(F4, a, b, c, d, in[ 4]+0xf7537e82, 6); 291 MD5STEP(F4, d, a, b, c, in[11]+0xbd3af235, 10); 292 MD5STEP(F4, c, d, a, b, in[ 2]+0x2ad7d2bb, 15); 293 MD5STEP(F4, b, c, d, a, in[ 9]+0xeb86d391, 21); 294 295 buf[0] += a; 296 buf[1] += b; 297 buf[2] += c; 298 buf[3] += d; 299 } 300 #endif 301 302 #ifdef TEST 303 /* Simple test program. Can use it to manually run the tests from 304 RFC1321 for example. */ 305 #include <stdio.h> 306 307 int 308 main (int argc, char **argv ) 309 { 310 struct lutil_MD5Context context; 311 unsigned char checksum[LUTIL_MD5_BYTES]; 312 int i; 313 int j; 314 315 if (argc < 2) 316 { 317 fprintf (stderr, "usage: %s string-to-hash\n", argv[0]); 318 return EXIT_FAILURE; 319 } 320 for (j = 1; j < argc; ++j) 321 { 322 printf ("MD5 (\"%s\") = ", argv[j]); 323 lutil_MD5Init (&context); 324 lutil_MD5Update (&context, argv[j], strlen (argv[j])); 325 lutil_MD5Final (checksum, &context); 326 for (i = 0; i < LUTIL_MD5_BYTES; i++) 327 { 328 printf ("%02x", (unsigned int) checksum[i]); 329 } 330 printf ("\n"); 331 } 332 return EXIT_SUCCESS; 333 } 334 #endif /* TEST */ 335