Crypto

Length Extension Attack

其实本人对密码学还是有点兴趣的(?)，但是之前并没有记录下之前对于一些密码学攻击的研究，这里还是一点点积累吧


Length Extension Attack – 哈希长度扩展攻击

背景

hash函数一般来说是用来签名的。比如说，如果我们需要使用一个登陆验证的时候，我们可以使用下面的代码

1
2
3
def genMac(name):
    Mac = hashlib.md5(name).hexdigest()
    return Mac

其中Mac(message authentication code),也就是身份认证码。我们将这个Mac交给用户，然后下一次登陆的时候，我们将会利用上面的Mac进行比较，确定是否是同一个登陆:

1
2
3
4
5
def checkAuth(name, mac):
    CheckMac = hashlib.md5(name).hexdigest()
    if mac == CheckMac:
        return True
    return False

那么很多人都会想到说，这个md5我们本地生成一个就好啦，于是服务器端一般会藏一个secret字符串在服务器，让md5的生成规则不被用户了解:

1
2
3
def genMac(name):
    Mac = hashlib.md5(secret+name).hexdigest()
    return Mac

也就是说这个时候，如果我们不知道服务器端的secret字符串，理论上是没有办法生成我们指定名字的Mac，比如说

1
2
3
4
5
6
def genMac(name):
    if name == "root":
        print("you have no permision")

    Mac = hashlib.md5(secret+name).hexdigest()
    return Mac

这个时候，没有办法生成root的Mac。然后管理员的登陆的确认逻辑变为:

1
2
3
4
5
def checkRoot(name, mac):
    CheckMac = hashlib.md5(secret+name).hexdigest()
    if mac == CheckMac and name.find('root')>=0:
        return True
    return False

这个时候，由于不知道secret，我们就不能够伪造root的Mac值。不过这个可以注意到，这里对于name的判断只是判断其是否包含root，这个地方就暗示此处有可以利用的地方。

MD5类hash函数的原理

网上搜索了一下，MD5，SHA1，SHA2这类算法都属于一种叫做Merkle–Damgård结构的哈希函数，也就是抗冲突加密散列函数，总的来说，这个结构的函数的特征有:

  • 按照block划分，并且在结尾存在padding表示长度
  • 对于长度不足的block用标志位进行填充
  • 长度过长的时候，会迭代进行加密(待考证)

这里我们先研究MD5中的哈希长度扩展攻击，所以简单介绍MD5的加密过程以及部分攻击相关的细节。

MD5加密逻辑

准备材料:

  • 8bit的四个寄存器ABCD
  • 需要处理的明文

处理过程:

这里主要不是介绍MD5加密，所以省略了大部分的MD5加密细节（比如说，在一轮加密结束之后，会发生寄存器值的交换，但是这里没有展现出来）。这里我们着重介绍对攻击有效的部分
在一开始的时候，ABCD四个寄存器会被初始化成不同的整数，然后进行类似下列的加密:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
+--------------+--------------+--------------+--------------+
|      A       |      B       |      C       |      D       |
+--------------+--------------+--------------+--------------+
       |              |              |               |        
       |              |              |               |        
       |              |              |               |        
+--------------+--------------+--------------+--------------+       +----------------------------------+
|                     非线性函数F                            |<------| 我们的输入明文按照512bit划分的block|
+--------------+--------------+--------------+--------------+       +----------------------------------+
       |              |              |               |
       |              |              |               |
       |              |              |               |
       v              v              v               v         
+--------------+--------------+--------------+--------------+
|      A       |      B       |      C       |      D       |
+--------------+--------------+--------------+--------------+

从图中我们能够指导，MD5加密是一个迭代的过程。

  • 首先ABCD通过非线性函数和我们输入的明文block进行加密，得到四个不同的数字
  • 将四组数字重新放回到到四个寄存器中
  • 如果我们输入的字符串长度大于512bit的时候，其就会将第一轮计算得到的ABCD作为递归开始的ABCD
  • 反复进行上面123步骤，直到我们输入的字符串长度到头为止。

最后将得到的ABCD连接，就能够得到加密完成的hash值。

Padding的选择

当我们的输入比较短，比如说是secretdata，那么此时的输入只有10个字节，也就是80bit，那么此时MD5会用以下的填充规则进行填充:

  • 首先在结尾跟上一个\x80，表示这之后是padding
  • 在56字节之后，最后的8个字节用来记录有效输入字符串的bit数

因此，对于字符串secret，得到的结果应该如下:

1
2
3
4
0000  73 65 63 72 65 74 64 61 74 61 80 00 00 00 00 00  secretdata......
0010  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0020  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0030  00 00 00 00 00 00 00 00 50 00 00 00 00 00 00 00  ........P.......

其中0x50 == 80,正好就是当前填入的有效bit数。

攻击 – 攻击原理

攻击的最根本的原理就在之前提到的迭代处理上。我们处理一下当前手上能够得到的信息

  • 我们能够得到的mac是hash(secret+data)，其中data是我们自己输入的。
  • MD5的加密中，ABCD寄存器中的值才是hash值本身
  • 在处理过相同的内容的时候，得到的ABCD的值是相等的

我们的目的是

  • 得到hash(secret+data+root)的内容(由于判断是find(‘root’)>=0,也就是说不一定要从root开始，前面可以填充不同的内容)

那么，首先想到，如果我们输入的内容是data，那么程序就会将其拼接成

1
2
3
4
0000  73 65 63 72 65 74 64 61 74 61 80 00 00 00 00 00  secretdata......
0010  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0020  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0030  00 00 00 00 00 00 00 00 50 00 00 00 00 00 00 00  ........P.......

那么，在进行MD5加密的时候，加密结束的时候得到的值就会是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
+--------------+--------------+--------------+--------------+
|      A       |      B       |      C       |      D       |
+--------------+--------------+--------------+--------------+
       |              |              |               |        
       |              |              |               |        
       |              |              |               |        
+--------------+--------------+--------------+--------------+       +----------------------------------+
|                     非线性函数F                            |<------|       secretdata + padding       |
+--------------+--------------+--------------+--------------+       +----------------------------------+
       |              |              |               |
       |              |              |               |
       |              |              |               |
       v              v              v               v         
+--------------+--------------+--------------+--------------+
|     A1       |     B1       |     C1       |      D1      |
+--------------+--------------+--------------+--------------+

得到的hash值就是A1B1C1D1组合而成的。从另一个角度来说，A1B1C1D1表示的是当前上下文的状态。于是，如果我们此时能够构造出下列的情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
+--------------+--------------+--------------+--------------+
|     A1       |     B1       |     C1       |      D1      |
+--------------+--------------+--------------+--------------+
       |              |              |               |        
       |              |              |               |        
       |              |              |               |        
+--------------+--------------+--------------+--------------+       +----------------------------------+
|                     非线性函数F                            |<------|          root + padding          |
+--------------+--------------+--------------+--------------+       +----------------------------------+
       |              |              |               |
       |              |              |               |
       |              |              |               |
       v              v              v               v         
+--------------+--------------+--------------+--------------+
|      A2      |       B2     |      C2      |       D2     |
+--------------+--------------+--------------+--------------+

那么这个时候，A2B2C2D2就是一个包含了secret和root的hash值。此时完全不需要知道secret的具体内容！

攻击 – 数据伪造

这个地方最关键的就是伪造数据。由于Padding的存在，使得我们可以通过合理增加padding，让关键字符串落在下一段block中的方式，利用上下文。
以上述例子为例，

1
2
3
4
0000  73 65 63 72 65 74 64 61 74 61 80 00 00 00 00 00  secretdata......
0010  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0020  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0030  00 00 00 00 00 00 00 00 50 00 00 00 00 00 00 00  ........P.......

此处是服务器上MD5算法中见到的字符，我们为了满足这个形式，可以主动将第一段数据填充够56字节，形成一个和第一次hash同样的值，然后第二次的时候，我们将我们需要的值放在数据的尾部

1
2
3
4
5
0000  73 65 63 72 65 74 64 61 74 61 80 00 00 00 00 00  secretdata......
0010  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0020  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0030  00 00 00 00 00 00 00 00 50 00 00 00 00 00 00 00  ........P.......
0040  61 70 70 65 6e 64                                append

这样的形式就能够形成我们需求的形式。然后，由于secret在服务器端，那么客户端上构造的字符串就应该是长这个样子的:

1
2
3
4
0000  64 61 74 61 80 00 00 00 00 00 00 00 00 00 00 00  data............
0010  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0020  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0030  00 00 50 00 00 00 00 00 00 00 61 70 70 65 6e 64  ..P.......append

（倒也没有说是64字节对齐，只是数据secret和append相等罢了）

也就是说，攻击形式是:

1
发送data --> 得到包含secret的hash --> 构造数据，造成第一次加密完全相等的形式，并且在尾部添加字符串 --> 计算hash -->通过发送构造字符串和hash通过验证，完成攻击

工具的使用

这个东西构造还是蛮麻烦的，python里面直接就有一个库叫做hashpumpy可以用，用法如下:

1
2
hashnum = hashlib.md5(secret+'data').hexdigest() # 假设生成了一个hashnum用作Mac
(token,fake) = hashpumpy.hashpump(hashnum, 'data','root',len('data')) # 参数为(传入data时候得到的hash值，data本身，需要输入的数据，比如name data的长度)

其生成的token即为包含了data和root的hash值，而fake则是包含了root的数据。

后记

可能因为看英文会一个一个字去看，最近只有看英文的blog才能够学的到东西(汗)，果然还是得静下心来看东西才行。

大部分的数据都来自参考博客
参考博客
(https://blog.skullsecurity.org/2012/everything-you-need-to-know-about-hash-length-extension-attacks)[https://blog.skullsecurity.org/2012/everything-you-need-to-know-about-hash-length-extension-attacks]