| 附录A - 执行参考(文件源代码)附录中包括取自RSAREF的文件：一个保护私人邮件的加密工具global.h -- 通用头文件md5.h -- MD5头文件md5c.c -- MD5源代码如果想得到更详细的信息，可以发电子邮件到 rsaref@rsa.com附录中还包括：mddriver.c -- MD2, MD4 及 MD5 的测试驱动引擎此引擎默认是为测试MD5编译使用的，但也可以将MD标志中对C函数编译命令行修改成2或4，来支持对MD2或MD4的测试编译。 这种执行具有可移植性，能够在很多不同的平台上实现。当然根据特定平台，对这个执行进行优化设计也不难，这个工作可以留给读者来完成。例如：在 "little-endian"平台上，在一个32-bit的字中位于最内存地址最前的字节，其意义性最小，也没有严格的约束，因此对MD5传输解码的调用完全可以用一个典型的模型来取代。(newlaos:不明白) A.1 global.h/* GLOBAL.H - RSAREF 类型及常数*//* PROTOTYPES should be set to one if and only if the compiler supportsfunction argument prototyping.如果使PROTOTYPES没有被C语言编译器定义的话，就默认为0*/#ifndef PROTOTYPES#define PROTOTYPES 0#endif/* POINTER 用来定义通用的指针类型 */typedef unsigned char *POINTER;/* UINT2 定义一个双字节的字 */typedef unsigned short int UINT2;/* UINT4 定义一个四字节的字 */typedef unsigned long int UINT4;/* PROTO_LIST 的定义依据上面对PROTOTYPE的定义.如果用 PROTOTYPES, 那么 PROTO_LIST 返回就列表，否则返回一个空列表*/#if PROTOTYPES#define PROTO_LIST(list) list#else#define PROTO_LIST(list) ()#endif A.2 md5.h/* MD5.H - MD5C.C 的头文件*//* Copyright (C) 1991-2, RSA 数据安全公司版权所有. 1991年MD5使用授权声明(略)/* MD5 context. */typedef struct {UINT4 state[4]; /* state (ABCD) */UINT4 count[2]; /* bit数, modulo 2^64 (lsb first) */unsigned char buffer[64]; /* 输入缓冲 */} MD5_CTX;void MD5Init PROTO_LIST ((MD5_CTX *));void MD5Update PROTO_LIST((MD5_CTX *, unsigned char *, unsigned int));void MD5Final PROTO_LIST ((unsigned char [16], MD5_CTX *)); A.3 md5c.c MD5的源代码＃i nclude "global.h"＃i nclude "md5.h"/* 定义MD5变换过程用到的常量*/#define S11 7#define S12 12#define S13 17#define S14 22#define S21 5#define S22 9#define S23 14#define S24 20#define S31 4#define S32 11#define S33 16#define S34 23#define S41 6#define S42 10#define S43 15#define S44 21static void MD5Transform PROTO_LIST ((UINT4 [4], unsigned char [64]));static void Encode PROTO_LIST((unsigned char *, UINT4 *, unsigned int));static void Decode PROTO_LIST((UINT4 *, unsigned char *, unsigned int));static void MD5_memcpy PROTO_LIST ((POINTER, POINTER, unsigned int));static void MD5_memset PROTO_LIST ((POINTER, int, unsigned int));static unsigned char PADDING[64] = {0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};/* F, G, H 和 I 为MD5的基本函数*/#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))#define H(x, y, z) ((x) ^ (y) ^ (z))#define I(x, y, z) ((y) ^ ((x) | (~z)))/* ROTATE_LEFT 定义对x进行循环左移，使x只剩下n位bits值.*/#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))/* FF, GG, HH 和 II 的分别代表第 1, 2, 3 及 4次循环位移与加法运算相分离，以防止再运算*/#define FF(a, b, c, d, x, s, ac) { (a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); (a) = ROTATE_LEFT ((a), (s)); (a) += (b); }#define GG(a, b, c, d, x, s, ac) { (a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); (a) = ROTATE_LEFT ((a), (s)); (a) += (b); }#define HH(a, b, c, d, x, s, ac) { (a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); (a) = ROTATE_LEFT ((a), (s)); (a) += (b); }#define II(a, b, c, d, x, s, ac) { (a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); (a) = ROTATE_LEFT ((a), (s)); (a) += (b); }/* MD5 初始化. 开始 MD5 操作, 并写入一个新的内容(context) (newlaos:内容的最终结果就是MD5的信息摘要了)*/void MD5Init (context)MD5_CTX *context; /* context */{context->count[0] = context->count[1] = 0;/* 加载初始化常数。*/context->state[0] = 0x67452301;context->state[1] = 0xefcdab89;context->state[2] = 0x98badcfe;context->state[3] = 0x10325476;}/* MD5 数据块更新操作。继续MD5 信息摘要操作Continues an MD5 message-digestoperation, processing another message block, and updating thecontext.*/void MD5Update (context, input, inputLen)MD5_CTX *context; /* MD5内容 */unsigned char *input; /* 输入的数据块 */unsigned int inputLen; /* 输入的数据块长度 */{unsigned int i, index, partLen;/* 计算字节数除以64的余数(字节数 mod 64) */index = (unsigned int)((context->count[0] >> 3) & 0x3F);/* 更新bit位数 */if ((context->count[0] += ((UINT4)inputLen << 3))< ((UINT4)inputLen << 3))context->count[1]++;context->count[1] += ((UINT4)inputLen >> 29);partLen = 64 - index;/* 尽可能多地变换*/if (inputLen >= partLen) {MD5_memcpy((POINTER)&context->buffer[index], (POINTER)input, partLen);MD5Transform (context->state, context->buffer);for (i = partLen; i + 63 < inputLen; i += 64)MD5Transform (context->state, &input[i]);index = 0;}elsei = 0;/* 对剩下的数据进行缓存 */MD5_memcpy((POINTER)&context->buffer[index], (POINTER)&input[i],inputLen-i);}/* MD5 结束. 结束一个生成 MD5 信息摘要过程的操作, 将信息摘要写入内容Context.*/void MD5Final (digest, context)unsigned char digest[16]; /* 信息摘要 */MD5_CTX *context; /* 内容context */{unsigned char bits[8];unsigned int index, padLen;/* 保存bit位数 */Encode (bits, context->count, 8);/* 将数据补长至对64求模(余数)为56*/index = (unsigned int)((context->count[0] >> 3) & 0x3f);padLen = (index < 56) ? (56 - index) : (120 - index);MD5Update (context, PADDING, padLen);/* 增加长度 (补长前) */MD5Update (context, bits, 8);/* 保存摘要状态 */Encode (digest, context->state, 16);/* 将敏感信息至为最初状态*/MD5_memset ((POINTER)context, 0, sizeof (*context));}/* MD5 基本变换. 基于块(512位)的变换*/static void MD5Transform (state, block)UINT4 state[4];unsigned char block[64];{UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16];Decode (x, block, 64);/* 第 1 轮循环*/FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 *//* 第 2 轮循环*/GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */GG (d, a, b, c, x[10], S22, 0x2441453); /* 22 */GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 *//* 第 3 轮循环*/HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */HH (b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 *//* 第 4 轮循环*/II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */state[0] += a;state[1] += b;state[2] += c;state[3] += d;/* Zeroize sensitive information.*/MD5_memset ((POINTER)x, 0, sizeof (x));}/* 将(UINT4)输入加密为(unsigned char)输出。假定长度为4的整数倍*/static void Encode (output, input, len)unsigned char *output;UINT4 *input;unsigned int len;{unsigned int i, j;for (i = 0, j = 0; j < len; i++, j += 4) {output[j] = (unsigned char)(input[i] & 0xff);output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);}}/*将 (unsigned char)输入解密为(UINT4)输出。假定长度为4的整数倍。*/static void Decode (output, input, len)UINT4 *output;unsigned char *input;unsigned int len;{unsigned int i, j;for (i = 0, j = 0; j < len; i++, j += 4)output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) |(((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24);}/* Note: Replace "for loop" with standard memcpy if possible.*/static void MD5_memcpy (output, input, len)POINTER output;POINTER input;unsigned int len;{unsigned int i;for (i = 0; i < len; i++)output[i] = input[i];}/* Note: Replace "for loop" with standard memset if possible.*/static void MD5_memset (output, value, len)POINTER output;int value;unsigned int len;{unsigned int i;for (i = 0; i < len; i++)((char *)output)[i] = (char)value;} A.4 mddriver.c/* MDDRIVER.C - MD2, MD4 及 MD5 的测试驱动*//* 如果没有用C语言编译器的标志定义的话，默认是进行MD5测试驱动*/#ifndef MD#define MD MD5#endif＃i nclude <stdio.h>＃i nclude <time.h>＃i nclude <string.h>＃i nclude "global.h"#if MD == 2＃i nclude "md2.h"#endif#if MD == 4＃i nclude "md4.h"#endif#if MD == 5＃i nclude "md5.h"#endif/* 测试块的长度, 测试块的数目。*/#define TEST_BLOCK_LEN 1000#define TEST_BLOCK_COUNT 1000static void MDString PROTO_LIST ((char *));static void MDTimeTrial PROTO_LIST ((void));static void MDTestSuite PROTO_LIST ((void));static void MDFile PROTO_LIST ((char *));static void MDFilter PROTO_LIST ((void));static void MDPrint PROTO_LIST ((unsigned char [16]));#if MD == 2#define MD_CTX MD2_CTX#define MDInit MD2Init#define MDUpdate MD2Update#define MDFinal MD2Final#endif#if MD == 4#define MD_CTX MD4_CTX#define MDInit MD4Init#define MDUpdate MD4Update#define MDFinal MD4Final#endif#if MD == 5#define MD_CTX MD5_CTX#define MDInit MD5Init#define MDUpdate MD5Update#define MDFinal MD5Final#endif/* 主驱动参数定义 (可以合起来使用):-sstring - 摘要字符串-t - 进行时间测试-x - 运行测试脚本filename - 摘要文件(none) - 摘要标准输入*/int main (argc, argv)int argc;char *argv[];{int i;if (argc > 1)for (i = 1; i < argc; i++)if (argv[i][0] == ‘-‘ && argv[i][1] == ‘s‘)MDString (argv[i] + 2);else if (strcmp (argv[i], "-t") == 0)MDTimeTrial ();else if (strcmp (argv[i], "-x") == 0)MDTestSuite ();elseMDFile (argv[i]);elseMDFilter ();return (0);}/* 计算一个字符串信息摘要，并输出结果*/static void MDString (string)char *string;{MD_CTX context;unsigned char digest[16];unsigned int len = strlen (string);MDInit (&context);MDUpdate (&context, string, len);MDFinal (digest, &context);printf ("MD%d (\"%s\") = ", MD, string);MDPrint (digest);printf ("\n");}/* 测量对 TEST_BLOCK_COUNT TEST_BLOCK_LEN-byte 数据块进行摘要计算所需的时间*/static void MDTimeTrial (){MD_CTX context;time_t endTime, startTime;unsigned char block[TEST_BLOCK_LEN], digest[16];unsigned int i;printf("MD%d time trial. Digesting %d %d-byte blocks ...", MD,TEST_BLOCK_LEN, TEST_BLOCK_COUNT);/* Initialize block */for (i = 0; i < TEST_BLOCK_LEN; i++)block[i] = (unsigned char)(i & 0xff);/* Start timer */time (&startTime);/* Digest blocks */MDInit (&context);for (i = 0; i < TEST_BLOCK_COUNT; i++)MDUpdate (&context, block, TEST_BLOCK_LEN);MDFinal (digest, &context);/* Stop timer */time (&endTime);printf (" done\n");printf ("Digest = ");MDPrint (digest);printf ("\nTime = %ld seconds\n", (long)(endTime-startTime));printf("Speed = %ld bytes/second\n",(long)TEST_BLOCK_LEN * (long)TEST_BLOCK_COUNT/(endTime-startTime));}/* 计算一系列字符串的信息摘要，并输出结果*/static void MDTestSuite (){printf ("MD%d test suite:\n", MD);MDString ("");MDString ("a");MDString ("abc");MDString ("message digest");MDString ("abcdefghijklmnopqrstuvwxyz");MDString("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789");MDString("12345678901234567890123456789012345678901234567890123456789012345678901234567890");}/* 计算一个文件的信息摘要，并输出结果*/static void MDFile (filename)char *filename;{FILE *file;MD_CTX context;int len;unsigned char buffer[1024], digest[16];if ((file = fopen (filename, "rb")) == NULL)printf ("%s can‘t be opened\n", filename);else {MDInit (&context);while (len = fread (buffer, 1, 1024, file))MDUpdate (&context, buffer, len);MDFinal (digest, &context);fclose (file);printf ("MD%d (%s) = ", MD, filename);MDPrint (digest);printf ("\n");}}/* 计算标准输入的信息摘要，并输出结果*/static void MDFilter (){MD_CTX context;int len;unsigned char buffer[16], digest[16];MDInit (&context);while (len = fread (buffer, 1, 16, stdin))MDUpdate (&context, buffer, len);MDFinal (digest, &context);MDPrint (digest);printf ("\n");}/* 以16进制的形式输出一份信息摘要*/static void MDPrint (digest)unsigned char digest[16];{unsigned int i;for (i = 0; i < 16; i++)printf ("%02x", digest[i]);} A.5 对编写好的MD5程序进行一系列测试MD5 系列测试(驱动参数 "-x") 得到的结果应该为:MD5 系列测试:MD5 ("") = d41d8cd98f00b204e9800998ecf8427eMD5 ("a") = 0cc175b9c0f1b6a831c399e269772661MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13bMD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =d174ab98d277d9f5a5611c2c9f419d9fMD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 57edf4a22be3c955ac49da2e2107b67a安全考虑及常用的攻击方式在这份备忘录里讨论的MD5安全级别，主要是考虑将MD5加密算法与公钥加密系统相配合，构成混合的签名认证机制，将具有极高的安全。 MD5是被用来单向变换用户口令和对信息签名的单向散列算法。一种单向散列的强度体现在它能把任意的输入随机化到什么程度并且能产生唯一的输出。对单向散列的直接攻击可以分为普通直接攻击和“生日”攻击。 ● 对MD5的普通直接攻击 所谓直接攻击又叫野蛮攻击。攻击者为了找到一份和原始明文 m 散列结果相同的明文 m‘ ，就是 H(m)=H(m‘) 。普通直接攻击，顾名思义就是穷举可能的明文去产生一个和 H(m) 相同的散列结果。对MD5来说散列结果为128-bits，就是说如果攻击者有一台每秒尝试1,000,000,000条明文的机器需要算约10^22 年，同时兴许会同时发现m本身:))。● 对MD5的生日攻击 生日攻击实际上只是为了找到两条能产生同样散列结果的明文。记得那个有名的概率生日问题吗？在 N 个人中至少有两个人生日相同的概率是多少？所谓生日攻击实际上只是用概率来指导散列冲突的发现，对于MD5来说如果尝试2^64条明文，那么它们之间至少有一对发生冲突的概率就是 50％。仅此而已，对当今的科技能力来说，它也是不可能的。一台上面谈到的机器平均需要运行585年才能找到一对，而且并不能马上变成实际的攻击成果。因为码长和速度的关系，对crypt(3)的生日攻击就成功得多。● 其他对MD5的攻击 微分攻击被证明对MD5的一次循环是有效的，但对全部4次循环无效。（微分攻击是通过比较分析有特定区别的明文在通过加密后的变化传播情况来攻击加密体系的。）有一种成功的MD5攻击，不过它是对MD5代码本身做了手脚，是一种crack而不是hack更算不上cryptanalysis了。● 口令长度和信息论 根据传统信息论，英语的每个8-bits字母的信息熵为1.3bits。如果口令足够长，MD5的结果就会足够随机。对 128-bits 的MD5输出来说，一个长达98个字符的口令将给出一个随机的密匙。(8/1.3)*(128/8) = 98.46 chars可是谁会用一个象下面这样长的口令呢？ 12345678901234567890123456789012345678901235678901234567890 1234567890123456789012345678 1.3 bits 的信息熵来自于英语语法的规律性这个事实，字母出现概率的不等造成了熵的减小。如果26个拉丁字母出现的概率均等，信息熵将会增至log(26)/log(2) = 4.7 bits 这样一个随机密匙所需口令长度就减为 27.23 chars 了，如果再加上大小写和几个符号还可以减少。关于选择口令的问题可以参考任何关于安全性的书籍，它们都适用。 作者通讯地址(newlaos:未翻译:)Ronald L. RivestMassachusetts Institute of TechnologyLaboratory for Computer ScienceNE43-324545 Technology SquareCambridge, MA 02139-1986Phone: (617) 253-5880EMail: rivest@theory.lcs.mit.edu |
