CVE-2016-6313 随机数预测分析

本次分析源于去年HITCON的一题密码学题目, 比赛完了本来就准备分析一波, 但是一直拖到了现在, 该题利用到了CVE-2016-6313, 可以预测到gcrypt生成的随机数中第580-600共20byte的值

CVE-2016-6313

网上对该CVE没啥详细的分析, 就ppp的wp写的比较详细

漏洞代码段:

1
2
3
POOLBLOCKS=30
DIGESTLEN=20
BLOCKLEN=64

random1

其中pool为随机数池, 一串未知的随机数, 循环结束后的p则是我们最终得到的随机数

从代码中可以看出, 整个POOLSIZE = POOLBLOCKS * DIGESTLEN = 600

随机数池以600byte为单位进行生成随机数

在600byte的随机池中又以20byte进行分块, 但是循环只循环了29次, 其中最开始的20byte不变.

在循环中对随机数的处理, 有这么一个逻辑
random2

取当前的POOLBLOCK的前20byte和后44byte组成64byte, 进入_gcry_sha1_mixblock函数进行sha1的hash计算.

如果当前POOLBLOCK后面不足44byte则从开头获取

这就会导致, 当计算最后一个POOLBLOCK时, 新生成的hash值为前20byte+开头的44byte进行sha1的hash计算, 而这些值都为输出的随机数.

也就是说, 如果我们已知前580bytes的随机数, 则可以预测到580-600之间20byte的随机数.

sha1计算

其中_gcry_sha1_mixblock和正常sha1函数的区别是, _gcry_sha1_mixblock不增加padding, hash初始值由第一个参数决定.

在代码中_gcry_sha1_mixblock的第一个参数是&md, 为上一次hash计算的结果, 也就是前20byte的值

用python实现了该功能代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#!/usr/bin/env python
# -*- coding:utf-8 -*-
import ctypes
import struct
def ROTL32(x, r):
try:
a = (x << r) ^ (x >> (32 - r))
except:
print type(x)
print type(r)
exit(-1)
return a
class SHA1():
def __init__(self):
self.length_ = 0
self.unprocessed_ = 0
self.hash_ = [
0x67452301,
0xefcdab89,
0x98badcfe,
0x10325476,
0xc3d2e1f0
]
def sha1_process(self):
wblock = []
for x in xrange(80):
wblock.append(0)
for x in xrange(16):
wblock[x] = self.block[x]
for x in xrange(16, 80):
wblock[x] = ROTL32(wblock[x - 3] ^ wblock[x - 8] ^ wblock[x - 14] ^ wblock[x - 16], 1) & 0xFFFFFFFF
a = self.hash_[0]
b = self.hash_[1]
c = self.hash_[2]
d = self.hash_[3]
e = self.hash_[4]
for x in xrange(20):
temp = ROTL32(a, 5) + (((c ^ d) & b) ^ d) + e + wblock[x] + 0x5A827999
temp &= 0xFFFFFFFF
e = d
d = c
c = ROTL32(b, 30) & 0xFFFFFFFF
b = a
a = temp
for x in xrange(20, 40):
temp = ROTL32(a, 5) + (b ^ c ^ d) + e + wblock[x] + 0x6ED9EBA1
temp &= 0xFFFFFFFF
e = d
d = c
c = ROTL32(b, 30) & 0xFFFFFFFF
b = a
a = temp
for x in xrange(40, 60):
temp = ROTL32(a, 5) + ((b & c) | (b & d) | (c & d)) + e + wblock[x] + 0x8F1BBCDC
temp &= 0xFFFFFFFF
e = d
d = c
c = ROTL32(b, 30) & 0xFFFFFFFF
b = a
a = temp
for x in xrange(60, 80):
temp = ROTL32(a, 5) + (b ^ c ^ d) + e + wblock[x] + 0xCA62C1D6
temp &= 0xFFFFFFFF
e = d
d = c
c = ROTL32(b, 30) & 0xFFFFFFFF
b = a
a = temp
self.hash_[0] += a
self.hash_[1] += b
self.hash_[2] += c
self.hash_[3] += d
self.hash_[4] += e
for x in xrange(5):
self.hash_[x] &= 0xFFFFFFFF
def str_to_block(self, x):
self.block = []
for i in xrange(x, x + 64, 4):
tmp = self.msg[i: i + 4]
tmp = int(tmp.encode('hex') or '0', 16)
self.block.append(tmp)
def sha1(self, msg, length):
self.msg = msg
self.length_ = length
self.msg += (64 - length % 64) * '\x00'
self.str_to_block(0)
self.sha1_process()
return self.final()
def final(self):
for x in xrange(5):
self.hash_[x] = ctypes.c_uint32(self.hash_[x])
result = ""
for x in self.hash_:
result += "{:0>8}".format(hex(x.value)[2:-1])
return result
if __name__ == '__main__':
hash_test = SHA1()
msg = "a"*64
print hash_test.sha1(msg, len(msg))

测试

代码见:
https://github.com/Hcamael/ctf-library/tree/master/OTP

其中hint_test.c为测试代码, check_random.py为预测随机数代码

1
2
3
$ gcc hint_test.c -o test -lgcrypt
$ ./test | xargs python check_random.py
the random can be predicted

需要装libgcrypt库, 源码见参考链接2, 自行编译安装, 影响版本见参考链接1.

如在测试过程中失败, 首先检测编译安装的版本是否是含有漏洞的版本, 然后再用ldd test, 查看动态链接到的库是否是你编译安装的那个库.

random3

ps: 我是使用1.7.2版本编译安装进行测试, 测试成功

patch分析

1.7.3patch之后的代码为:
random4

我们再来分析下patch之后的代码

patch的逻辑很简单, 从前20byte+后44byte进行sha1计算变成了, 当前20byte加后44byte

前20byte的值我们是可以获知的, 但是当前POOLBLOCK的20byte我们却无法知道, 所以就无法再进行随机数预测了.

总结

具体利用就是HITCON 2016 OTP 密码学题目, 题解payload见参考链接3

参考:

  1. https://bugzilla.redhat.com/show_bug.cgi?id=CVE-2016-6313
  2. https://github.com/gpg/libgcrypt/blob/libgcrypt-1.7.3/random/random-csprng.c
  3. https://github.com/pwning/public-writeup/blob/master/hitcon2016/Crypto150-otp/README.md
  4. https://github.com/Hcamael/ctf-library/tree/master/OTP
文章目录
  1. 1. CVE-2016-6313
  2. 2. sha1计算
  3. 3. 测试
  4. 4. patch分析
  5. 5. 总结