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

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

CVE-2016-6313

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

漏洞代码段:

POOLBLOCKS=30
DIGESTLEN=20
BLOCKLEN=64

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

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

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

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

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

取当前的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实现了该功能代码:

#!/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为预测随机数代码

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

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

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

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

patch分析

1.7.3patch之后的代码为:

我们再来分析下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