MD5 填充和小端字节序

Question

我一直在尝试自己重新创建 MD5 算法。 我似乎无法正确理解算法。看来我 填充和字节顺序有问题。

#include <stdio.h>
#include <stdint.h>

/* F, G, H and I are basic MD5 functions.
 */
#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 rotates x left n bits.
 */
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))

/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
Rotation is separate from addition to prevent recomputation.
 */
#define FF(a, b, c, d, x, s, ac) { \
 (a) += F ((b), (c), (d)) + (x) + (uint32_t)(ac); \
 (a) = ROTATE_LEFT ((a), (s)); \
 (a) += (b); \
  }
#define GG(a, b, c, d, x, s, ac) { \
 (a) += G ((b), (c), (d)) + (x) + (uint32_t)(ac); \
 (a) = ROTATE_LEFT ((a), (s)); \
 (a) += (b); \
  }
#define HH(a, b, c, d, x, s, ac) { \
 (a) += H ((b), (c), (d)) + (x) + (uint32_t)(ac); \
 (a) = ROTATE_LEFT ((a), (s)); \
 (a) += (b); \
  }
#define II(a, b, c, d, x, s, ac) { \
 (a) += I ((b), (c), (d)) + (x) + (uint32_t)(ac); \
 (a) = ROTATE_LEFT ((a), (s)); \
 (a) += (b); \
  }

#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 21

void MD5_hash(uint32_t *message, uint32_t *digest) {
 const uint32_t d0 = 0x67452301;
 const uint32_t d1 = 0xEFCDAB89;
 const uint32_t d2 = 0x98BADCFE;
 const uint32_t d3 = 0x10325476;

 uint32_t a, b, c, d, *x;

 a = d0;
 b = d1;
 c = d2;
 d = d3;

 x = message;

 /* Round 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 */

 /* Round 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, 0x02441453); /* 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 */

 /* Round 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, 0x04881d05); /* 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 */

 /* Round 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 */

 a += d0;
 b += d1;
 c += d2;
 d += d3;

 digest[0] = a;
 digest[1] = b;
 digest[2] = c;
 digest[3] = d;
}

int main(void) {
 uint32_t message[16], digest[4];

 message[0] = 0x61800000;
 message[1] = 0x00000000;
 message[2] = 0x00000000;
 message[3] = 0x00000000;
 message[4] = 0x00000000;
 message[5] = 0x00000000;
 message[6] = 0x00000000;
 message[7] = 0x00000000;
 message[8] = 0x00000000;
 message[9] = 0x00000000;
 message[10] = 0x00000000;
 message[11] = 0x00000000;
 message[12] = 0x00000000;
 message[13] = 0x00000000;
 message[14] = 0x08000000;
 message[15] = 0x00000000;

 digest[0] = 0x00000000;
 digest[1] = 0x00000000;
 digest[2] = 0x00000000;
 digest[3] = 0x00000000;

 MD5_hash(message, digest);

 printf("%08X %08X %08X %08X\n", digest[0], digest[1], digest[2], digest[3]);
}

上面的代码是我的实现。现在，我的问题是，如何填充特定消息？例如，如果我的消息是“a”，则消息是：0x61800000...08000000000000。这是正确的吗？ （消息[0] = 0x61800000 ...消息[14] = 0x08000000，消息[15] = 0x000000000）。我认为我的字节顺序或对填充指令的解释可能是错误的。谁能启发我吗？

（以上代码的输出为：5058CD0E 2476E559 CF86AEA4 8A173599）；

Answer 1

好吧，我自己实现了，并且在实现过程中遇到了同样的障碍/障碍。

A + Padding 是 0x61800000，这是正确的，但用于长度指示的 64 位是大端格式。因此，在这 64 位中，最后 4 个字节为零，前面的 4 个字节包含消息字节的长度 * 8 位，最低有效位在最高有效位之前。

您从 MD5 哈希的 RFC 标准复制的代码存在另一个问题。 MD5Transform 函数从 char 数组格式（从左到右）复制数据，并要求将它们打包为（小端）格式的 32 位整数。执行计算周期后，您需要将结果从（小端）32 位整数转换为 char 数组格式，这要求您反转在 MD5Transform 的初始调用期间完成的编码步骤。

希望这有帮助。

Answer 2

我最近在实现 MD5 时遇到了类似的麻烦。如果您使用的是 Windows 或其他使用小端的操作系统，请尝试以下操作：

message[0] = 0x00008061;
message[1] = 0x00000000;
message[2] = 0x00000000;
message[3] = 0x00000000;
message[4] = 0x00000000;
message[5] = 0x00000000;
message[6] = 0x00000000;
message[7] = 0x00000000;
message[8] = 0x00000000;
message[9] = 0x00000000;
message[10] = 0x00000000;
message[11] = 0x00000000;
message[12] = 0x00000000;
message[13] = 0x00000000;
message[14] = 0x00000008;
message[15] = 0x00000000;

这可能不是您唯一的问题（如果确实如此）。我尝试在我的小端操作系统上使用正确的 MD5 算法（已被确认可以使用小端填充提供正确的输出）使用您的大端填充，它给了我以下输出： 0ecd585059e57624a4ae86cf9935178a 这可能意味着您只需再次检查您的算法即可。

Answer 3

我意识到这是一个相当老的问题，但我在尝试自己实现 RIPEMD-160 并试图找出消息块和消息调度构建过程时遇到了这个问题。

对我来说解决这个问题的方法是将填充位/字节附加到消息字节中，直到指定为消息长度的剩余 64 位。

然后我将消息长度添加为 Little Endian 中的 uint64。例如，对于输入字符串“a”，消息块在十六进制的 32 位组中如下所示（从左到右）：

61 80 00 00   00 00 00 00   00 00 00 00   00 00 00 00
00 00 00 00   00 00 00 00   00 00 00 00   00 00 00 00
00 00 00 00   00 00 00 00   00 00 00 00   00 00 00 00
00 00 00 00   00 00 00 00   08 00 00 00   00 00 00 00

接下来，我将所有 32 位组转换为 Little Endian 中的 uint32 字并运行这些值通过压缩功能。

我遇到的最后一个“陷阱”步骤是将压缩函数的结果转换为 5 个寄存器的 160 位/20 字节输出值ALSO IN LITTLE ENDIAN：

final_value := 20byte array
append(final_value, LittleEndian(h0))
append(final_value, LittleEndian(h1))
append(final_value, LittleEndian(h2))
append(final_value, LittleEndian(h3))
append(final_value, LittleEndian(h4))

然后可以将这个最终值输出为十六进制字符串，它与 Dobbertin 等人中给出的参考值相匹配。等人。纸

干杯