作者：Hcamael

本次分析源于去年HITCON的一題密碼學題目, 比賽完了本來就準備分析一波, 但是一直拖到了現在, 該題利用到了CVE-2016-6313, 可以預測到gcrypt生成的隨機數中第580-600共20byte的值

CVE-2016-6313

網上對該CVE沒啥詳細的分析, 就ppp的wp寫的比較詳細

漏洞代碼段:

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實現了該功能代碼:

#!/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, 查看動態鏈接到的庫是否是你編譯安裝的那個庫.

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

Paper 本文由 Seebug Paper 發布，如需轉載請注明來源。本文地址：http://www.bjnorthway.com/170/