初探MD5原理及哈希拓展攻击

发表于 2019-07-23 分类于学习笔记阅读次数：

学点密码学。

前言

MD5消息摘要算法一种被广泛使用的密码散列函数，输入长度小于2^64【18446744073709551616位的消息，输出一个128位【16Byte的散列值，输入信息以512位一组的分组为单位处理。一般128位的MD5散列被表示为32个字符的十六进制数字。

原理

末尾填充

首先是对原文求余，判断原文位数模除512的结果是否为448。

若不满足以上条件，则对其进行填充，第一位填充1，剩余位数填充0，直到满足最后结果长度模除512的值为448，若取余结果大于448，则再填充一组512长度的值。

需要注意的是，这边填充的内容是小端序，如下。

1	1 > 00 00 00 01 > 01 00 00 00 > 0x80

因此在Python中填充第一位的内容为，实现代码如下。

message = "south"
# 分组长度为512位，即64
group_length = 64
# 余数长度为448位，即56
remainder = 56
distance = len(message) % group_length
message = message.encode()
message += b"\x80"
if distance > remainder:
    message += b"\x00" * (group_length + remainder - distance - 1)
else:
    message += b"\x00" * (remainder - distance - 1)

剩下的64位是记录原文的真实长度的，因为MD5处理的是长度小于2^64位的数据。

1
2
3

# 计算消息长度
length = struct.pack('<Q', len(message) * 8)
message += length

变量初始化

用4个32位的寄存器A，B，C，D存放4个固定的32位整型参数【0123456789abcdeffedcba9876543210，用于第一轮迭代，注意是小端序。

1	A, B, C, D = 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476

分组处理

在根据原文长度按512位一组分组后，每一组再按32位一组分16组，然后以16个子分组为一轮，依次经过函数计算后，再同上一步定义的ABCD四个初始变量计算生成新的ABCD变量，用于下一次计算。

这是MD5官方使用的四个函数，在512位分组的32位子分组中运算的时候，第一轮使用F函数，第二轮使用G函数，第三轮次使用H函数，在第四轮次使用I函数，每次都只用到BCD三个变量。

F(B, C, D) = (B & C) | ((~B) & D)
G(B, C, D) = (B & D) | (C & (~D))
H(B, C, D) = B ^ C ^ D
I(B, C, D) = C ^ (B | (~D))

调用函数之后，田字格是相加，Mi是32位分组的原文，Ki是伪随机数生成的常数，把它们相加，和0xffffffff做与运算是为保证结果不超过32位。

# 伪随机数k
k = [int(math.floor(abs(math.sin(i + 1)) * (2 ** 32))) for i in range(64)]
……
# 分成16个组，I代表1组32位
m = list(struct.unpack('<' + 'I' * 16, chunk))
a, b, c, d = A, B, C, D
# 64轮运算，每一轮运算只用到了b, c, d三个
for i in range(64):
    if i < 16:
        f = (b & c) | ((~b) & d)
        # 用于标识处于第几组信息
        flag = i
    elif i < 32:
        f = (b & d) | (c & (~d))
        flag = (5 * i + 1) % 16
    elif i < 48:
        f = (b ^ c ^ d)
        flag = (3 * i + 5) % 16
    else:
        f = c ^ (b | (~d))
        flag = (7 * i) % 16
        
		res = (a + f + k[i] + m[flag]) & 0xffffffff

然后将相加结果左移s【常量位，再加上B的值，同作与运算后赋值给B，同时，把D赋值给原A，B赋值给原C，C赋值给原D，如下。

# 左移
lrot = lambda x, n: (x << n) | (x >> 32 - n)
# 常量s
s = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
     5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 4,
     11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
     6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]
……
for i in range(64):
		tmp = b + lrot(res, s[i])
  	a, b, c, d = d, tmp & 0xffffffff, b, c

最后拼接ABCD即可。

完整代码

代码修改自MD5原理及Python实现。

import struct
import math

# 左移
lrot = lambda x, n: (x << n) | (x >> 32 - n)

# 初始向量
A, B, C, D = 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476

# 左移位数s
s = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
     5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 4,
     11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
     6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]

# 伪随机数k
k = [int(math.floor(abs(math.sin(i + 1)) * (2 ** 32))) for i in range(64)]


def initialize(message):
    global A, B, C, D
    # 分组长度为512位，即64
    group_length = 64
    # 余数长度为448位，即56
    remainder = 56
    distance = len(message) % group_length
    message = message.encode()
    message += b"\x80"
    if distance > remainder:
        message += b"\x00" * (group_length + remainder - distance - 1)
    else:
        message += b"\x00" * (remainder - distance - 1)
    # 计算消息长度
    length = struct.pack('<Q', len(message) * 8)
    message += length
    while len(message) > 0:
        solve(message[:group_length])
        message = message[group_length:]


def solve(chunk):
    global A, B, C, D
    # 分成16个组，I代表1组32位
    m = list(struct.unpack('<' + 'I' * 16, chunk))
    a, b, c, d = A, B, C, D
    # 64轮运算，每一轮运算只用到了b, c, d三个
    for i in range(64):
        if i < 16:
            f = (b & c) | ((~b) & d)
            # 用于标识处于第几组信息
            flag = i
        elif i < 32:
            f = (b & d) | (c & (~d))
            flag = (5 * i + 1) % 16
        elif i < 48:
            f = (b ^ c ^ d)
            flag = (3 * i + 5) % 16
        else:
            f = c ^ (b | (~d))
            flag = (7 * i) % 16
        res = (a + f + k[i] + m[flag]) & 0xffffffff
        tmp = b + lrot(res, s[i])
        a, b, c, d = d, tmp & 0xffffffff, b, c
    A = (A + a) & 0xffffffff
    B = (B + b) & 0xffffffff
    C = (C + c) & 0xffffffff
    D = (D + d) & 0xffffffff


def hex_digest():
    global A, B, C, D
    res = struct.pack('<IIII', A, B, C, D)
    return bytes.hex(res)


message = input()
initialize(message)
print(hex_digest())

哈希拓展攻击

例题。

<?php
$flag = "XXXXXXXXXXXXXXXXXXXXXXX";
$secret = "XXXXXXXXXXXXXXX"; // This secret is 15 characters long for security!

$username = $_POST["username"];
$password = $_POST["password"];

if (!empty($_COOKIE["getmein"])) {
    if (urldecode($username) === "admin" && urldecode($password) != "admin") {
        if ($_COOKIE["getmein"] === md5($secret . urldecode($username . $password))) {
            echo "Congratulations! You are a registered user.\n";
            die ("The flag is " . $flag);
        } else {
            die ("Your cookies don't match up! STOP HACKING THIS SITE.");
        }
    } else {
        die ("You are not an admin! LEAVE.");
    }
}

setcookie("sample-hash", md5($secret . urldecode("admin" . "admin")), time() + (60 * 60 * 24 * 7));

if (empty($_COOKIE["source"])) {
    setcookie("source", 0, time() + (60 * 60 * 24 * 7));
} else {
    if ($_COOKIE["source"] != 0) {
        echo ""; // This source code is outputted here
    }
}

已知secret长度，已知md5($secret . urldecode("admin" . "admin"))的值。

那么根据MD5的原理可知，实际加密数据如下。

1 2	message = secret + "adminadmin" res = message + "\x80" + "\x00" * (56 - len(message) % 64 - 1)

而MD5是根据消息长度分组加密的，上一组计算的输出作为下一组的输入，那么在这里只需要将已知md5($secret . urldecode("admin" . "admin"))的值作为初始化的ABCD输入，设加密消息为"south"，就可以不需要知道前面secret的值得到如下加密数据。

# 接上文代码
south = "south"
res = res + south + "\x80" + "\x00" * (56 - len(south) % 64 - 1)
# 实际加密的值为 secret + "adminadmin" + "\x80" + "\x00" * (56 - len(message) % 64 - 1) + "south"

后面的$username**和**$password可控，那么使得$username=admin**，**$password=admin00south即可。

此时，满足例题的绕过。

Refer

漫画：什么是MD5算法？

MD5原理及Python实现

哈希长度扩展攻击的简介以及HashPump安装使用方法