MD5算法及hash扩展攻击

0x00 简介

在这里主要介绍

MD5的算法原理
hash扩展攻击的场景
php种一些函数的区别

这是CTF里面很老的利用方式，一直没看，主要是没碰到过对应的环境

不能说完全不可能，但是在实际的环境中，还是很难碰到如此理想的环境

实际案例：phpwind 利用哈希长度扩展攻击进行getshell

工具：hashpump

0x01 MD5算法

概要

MD5信息摘要算法，一种被广泛使用的密码散列函数，提供消息完整性，MD5的长度为128位（按照16进制编码，16字节，得到32个字符）是一个散列值（hash value）。

特性

长度固定，任意长度的数据都会输出相同长度的md5值
不可逆
对原数据进行任何改动，改变一个字节输出数据也会有很大差异

对于MD5称呼也都不一样，个人感觉，非此类工作者随意

认为MD5属于加密算法的人觉得MD5与其他加密算法相似，都为将明文进行运算等各种操作得到与明文完全不相同的数据，而认为MD5不属于加密算法的人认为没有解密算法，无法称为加密算法，当然，第二种相比来说更加严谨，默认情况下不称为加密算法

应用

密码保护
电子签名
……

算法实现

首先需要对信息进行填充，对输入数据进行按位(bit)数据填充，长度进行补齐使消息的长度 X 变成X = n*512+448，也就是X mod 512=448

在进行填充时，在消息后面进行填充，填充第一位为1，其余为0

如果数据长度正好为n*512+448

我们也要对数据进行填充，变成 (n+1)*512+448

最后的64位用于填充原消息的长度

最终被用来处理的数据就为n*512+448+64 = N*512

初始化

初始化的参数，或者说四个幻数在内存地址上从低到高为：

A = 0×01234567
B = 0×89ABCDEF
C = 0xFEDCBA98
D = 0×76543210

每个标准幻数的大小与 md5输出大小一致

在程序中，使用小端字节序，md5为四个标准幻数进行多轮哈希运算

（小端模式：高字节在前，低字节在后）

则在程序中应该为：(这里直接翻出来PHP源码的关于MD5的初始化)

PHPAPI void PHP_MD5Init(PHP_MD5_CTX *ctx)
{
	ctx->a = 0x67452301;
	ctx->b = 0xefcdab89;
	ctx->c = 0x98badcfe;
	ctx->d = 0x10325476;

	ctx->lo = 0;
	ctx->hi = 0;
}

在数据填充部分，我们知道，我们已经将原始数据填充为：N个512位（n个64字节）

然后将每个64字节分成16份，每份4字节

然后定义了四个函数进行处理

F(a,b,c,d,Mi,s,tj)
G(a,b,c,d,Mi,s,tj)
H(a,b,c,d,Mi,s,tj)
I(a,b,c,d,Mi,s,tj)

其中，a，b，c，d表示4个标准幻数
第五个为每一份的四字节数据，也就是第i个子分组（一共有16个分组）
第六个和第七个表示为固定长度，用于执行逻辑与、或、非、异或运算、加法运算、移位运算

每十六个分组，也就是64字节执行一次

每个函数都要处理16个分组

php源码中处理循序如下，这是固定的

/* Round 1 */
STEP(F, a, b, c, d, SET(0), 0xd76aa478, 7)
STEP(F, d, a, b, c, SET(1), 0xe8c7b756, 12)
STEP(F, c, d, a, b, SET(2), 0x242070db, 17)
STEP(F, b, c, d, a, SET(3), 0xc1bdceee, 22)
STEP(F, a, b, c, d, SET(4), 0xf57c0faf, 7)
STEP(F, d, a, b, c, SET(5), 0x4787c62a, 12)
STEP(F, c, d, a, b, SET(6), 0xa8304613, 17)
STEP(F, b, c, d, a, SET(7), 0xfd469501, 22)
STEP(F, a, b, c, d, SET(8), 0x698098d8, 7)
STEP(F, d, a, b, c, SET(9), 0x8b44f7af, 12)
STEP(F, c, d, a, b, SET(10), 0xffff5bb1, 17)
STEP(F, b, c, d, a, SET(11), 0x895cd7be, 22)
STEP(F, a, b, c, d, SET(12), 0x6b901122, 7)
STEP(F, d, a, b, c, SET(13), 0xfd987193, 12)
STEP(F, c, d, a, b, SET(14), 0xa679438e, 17)
STEP(F, b, c, d, a, SET(15), 0x49b40821, 22)

/* Round 2 */
STEP(G, a, b, c, d, GET(1), 0xf61e2562, 5)
STEP(G, d, a, b, c, GET(6), 0xc040b340, 9)
STEP(G, c, d, a, b, GET(11), 0x265e5a51, 14)
STEP(G, b, c, d, a, GET(0), 0xe9b6c7aa, 20)
STEP(G, a, b, c, d, GET(5), 0xd62f105d, 5)
STEP(G, d, a, b, c, GET(10), 0x02441453, 9)
STEP(G, c, d, a, b, GET(15), 0xd8a1e681, 14)
STEP(G, b, c, d, a, GET(4), 0xe7d3fbc8, 20)
STEP(G, a, b, c, d, GET(9), 0x21e1cde6, 5)
STEP(G, d, a, b, c, GET(14), 0xc33707d6, 9)
STEP(G, c, d, a, b, GET(3), 0xf4d50d87, 14)
STEP(G, b, c, d, a, GET(8), 0x455a14ed, 20)
STEP(G, a, b, c, d, GET(13), 0xa9e3e905, 5)
STEP(G, d, a, b, c, GET(2), 0xfcefa3f8, 9)
STEP(G, c, d, a, b, GET(7), 0x676f02d9, 14)
STEP(G, b, c, d, a, GET(12), 0x8d2a4c8a, 20)

/* Round 3 */
STEP(H, a, b, c, d, GET(5), 0xfffa3942, 4)
STEP(H, d, a, b, c, GET(8), 0x8771f681, 11)
STEP(H, c, d, a, b, GET(11), 0x6d9d6122, 16)
STEP(H, b, c, d, a, GET(14), 0xfde5380c, 23)
STEP(H, a, b, c, d, GET(1), 0xa4beea44, 4)
STEP(H, d, a, b, c, GET(4), 0x4bdecfa9, 11)
STEP(H, c, d, a, b, GET(7), 0xf6bb4b60, 16)
STEP(H, b, c, d, a, GET(10), 0xbebfbc70, 23)
STEP(H, a, b, c, d, GET(13), 0x289b7ec6, 4)
STEP(H, d, a, b, c, GET(0), 0xeaa127fa, 11)
STEP(H, c, d, a, b, GET(3), 0xd4ef3085, 16)
STEP(H, b, c, d, a, GET(6), 0x04881d05, 23)
STEP(H, a, b, c, d, GET(9), 0xd9d4d039, 4)
STEP(H, d, a, b, c, GET(12), 0xe6db99e5, 11)
STEP(H, c, d, a, b, GET(15), 0x1fa27cf8, 16)
STEP(H, b, c, d, a, GET(2), 0xc4ac5665, 23)

/* Round 4 */
STEP(I, a, b, c, d, GET(0), 0xf4292244, 6)
STEP(I, d, a, b, c, GET(7), 0x432aff97, 10)
STEP(I, c, d, a, b, GET(14), 0xab9423a7, 15)
STEP(I, b, c, d, a, GET(5), 0xfc93a039, 21)
STEP(I, a, b, c, d, GET(12), 0x655b59c3, 6)
STEP(I, d, a, b, c, GET(3), 0x8f0ccc92, 10)
STEP(I, c, d, a, b, GET(10), 0xffeff47d, 15)
STEP(I, b, c, d, a, GET(1), 0x85845dd1, 21)
STEP(I, a, b, c, d, GET(8), 0x6fa87e4f, 6)
STEP(I, d, a, b, c, GET(15), 0xfe2ce6e0, 10)
STEP(I, c, d, a, b, GET(6), 0xa3014314, 15)
STEP(I, b, c, d, a, GET(13), 0x4e0811a1, 21)
STEP(I, a, b, c, d, GET(4), 0xf7537e82, 6)
STEP(I, d, a, b, c, GET(11), 0xbd3af235, 10)
STEP(I, c, d, a, b, GET(2), 0x2ad7d2bb, 15)
STEP(I, b, c, d, a, GET(9), 0xeb86d391, 21)

处理完这16组之后，然后再将计算得到的4个标准幻数的值与上一轮或开始值相加，然后作为第二轮输入，重复每一次（这里也就是hash扩展攻击所在了）

最后通过

PHPAPI void make_digest_ex(char *md5str, const unsigned char *digest, int len) /* {{{ */
{
	static const char hexits[17] = "0123456789abcdef";
	int i;

	for (i = 0; i < len; i++) {
		md5str[i * 2]       = hexits[digest[i] >> 4];
		md5str[(i * 2) + 1] = hexits[digest[i] &  0x0F];
	}
	md5str[len * 2] = '\0';
}

最终得到的更新后的标准幻数，按顺序得出我们的md5值，这里再强调一下，前面也说了是小端排序，所以应该是这样的

0x02 hash扩展攻击

条件

可以获取到一个已知值或者可控制的和密钥拼接的的hash值
密钥拼接在前，可控值应在后

这里也以网上的例子来跟一下流程

<?php

$flag = "XXXXXXXXXXXXXXXXXXXXXXX";
$secret = "aaaaaaaaaa"; // This secret is 10 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);#exit()/die() 函数输出一条消息，并退出当前脚本
        }
        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
    }
}
<html>
<body>

<h1>Admins Only!</h1>
<p>If you have the correct credentials, log in below. If not, please LEAVE.</p>
<form method="POST">
    Username: <input type="text" name="username"> <br>
    Password: <input type="password" name="password"> <br>
    <button type="submit">Submit</button>
</form>

</body>
</html>

?>

关键代码，下面两处代码满足了我们需要的条件

1
2
3

if ($COOKIE["getmein"] === md5($secret . urldecode($username . $password)))

setcookie("sample-hash", md5($secret . urldecode("admin" . "admin")),

接下来从流程上说明，为什么需要这两个条件

流程

首先假设密钥是十位字符以aaaaaaaaaa代替

那么aaaaaaaaaaadminadmin的位数是20，也就是20字节

要想补全56字节需要一个\x80和35个\x00，然后再加上原始字符的位数

20*8=160bit，转换成16禁止就是\xa0，其余再补\x00

如下

1	aaaaaaaaaaadminadmin\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xa0\x00\x00\x00\x00\x00\x00\x00

第一个条件

后面位置可控如$key.$_GET['pass']

这样我们就可以伪造上面算出来的数据，从而向后端传入。但是这样肯定是不行的，因为，如果刚补满，会再补一组

所以上面的数据后面还要再加数据，再加的数据，会成为下一组代补的数据

这就引出了第二个条件

第二个条件

知道aaaaaaaaaaadminadmin的hash值

由于，上一组的计算结果是作为下一组的幻数，也可以说是初始化的变量传入的

所以知道aaaaaaaaaaadminadmin的hash值，就是知道

1	aaaaaaaaaaadminadmin\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xa0\x00\x00\x00\x00\x00\x00\x00

的计算结果，而后面再拼接一个随便什么东西，那就是以上面的结果位初始化幻数重新计算hash值

这样就不需要知道密钥到底是什么就可以伪造了