从TSJCTF & Codegate的两道crypto题中学习新姿势

Lyutoon 2022-03-03 10:47:00

0x00 背景

周末的时候参加了TSJCTF和codegate的比赛,感觉其中有两道题思路比较新颖,有一些新的知识值得学习,记录一下以便日后翻阅。

0x01 TSJCTF Signature

  • Category: Crypto
  • Solve: 2/428

源码:

from fastecdsa.curve import secp256k1 as CURVE
from Crypto.Cipher import AES
from hashlib import sha256
from secrets import randbelow

d = randbelow(CURVE.q)
P = d * CURVE.G


def sign(z):
    k = d ^ z
    r = (k * CURVE.G).x
    s = pow(k, -1, CURVE.q) * (z + r * d) % CURVE.q
    return r, s


messages = [
    "https://www.youtube.com/watch?v=16M9oC-a5bY",
    "https://www.youtube.com/watch?v=QDadz5JZCw8",
    "https://www.youtube.com/watch?v=kyNh7KnsTN0",
    "https://www.youtube.com/watch?v=Lqn42JJxS3I",
    "https://www.youtube.com/watch?v=dQw4w9WgXcQ",
    "https://www.youtube.com/watch?v=1Gw_-E784l0",
]

for m in messages:
    z = int(sha256(m.encode()).hexdigest(), 16)
    print(z, *sign(z))


from secret import flag

msg = f"Congrats! This is your flag: {flag}"
key = sha256(str(d).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR)
print(cipher.encrypt(msg.encode()))

可以看出,本题采用了secp256k1作为曲线实现了一个有漏洞的ecdsa,分别对五个消息进行了签名,并且提供了它们的签名。

以往来看遇到的脆弱的ecdsa问题基本都出现在nonce上,最经典的就是使用了bias nonce,也就是nonce的bit数相较于q比较小,这就造成了当人们收集到很多签名的时候可以将求解d转化为求解hnp

但本题使用的并不是bias nonce,可以看出它的nonce是由d ^ z产生的(也就是d xor z),虽然与q的bit数相差不多,但这样的nonce在attacker获取到很多签名之后也是可以泄露d的,接下来我们来推导一下这个过程:

首先我们知道:
image.png
那么对于签名过程:(省略了mod q)
image.png
在正常情况下,我们如果收集256组签名,那么可以直接解线性方程组求出di,也就是d的每一个bit即可恢复d,但在这里,我们的0<= di <= 1,因此可以转化为求解svp即可。

主要方程:
image.png

具体构造如下:
image.png
其中:
image.png
对矩阵
image.png
做LLL,我们可以知道目标向量即是LLL之后的一个行向量,遍历所得到的所有行,若该行的第7个元素是1,而且从第7个以后的元素都是0或1,那么这一行大概率就是包含d所有256位比特信息的一行,因此可以恢复出d,恢复之后即可拿到key,但是由于这个是AES-CTR模式,还需要一个nonce,刚好题目中给了明文的第一个block,那么利用AES-ECB模式对plantext_block0 ^ ciphertext_block0进行解密即可获得nonce。之后就可以正常解密了。

exp:

from pwn import *
from Crypto.Cipher import AES
from hashlib import *
from fastecdsa.curve import secp256k1 as CURVE

with open('/mnt/f/ctf/play/chall (1)/output.txt', 'r') as f:
    data = f.readlines()
    sigs = []
    for vec in data[:6]:
        z, r, s = map(int, vec.strip().split())
        sigs.append((z, r, s))
    c = data[-1].strip()
    c = eval(c)

m = 6
n = 257

UL = matrix.identity(m) * CURVE.q
UR = matrix.zero(m, n)
DR = matrix.identity(n)

main_mat = []
for i in range(6):
    z, r, s = sigs[i]
    vec = [-(s-1)*z]
    zbin = bin(z)[2:].zfill(256)
    assert len(zbin) == 256
    zbin = zbin[::-1]
    for i in range(256):
        tmp = (2^i) * (r + (2*int(zbin[i])-1) * s) % (CURVE.q)
        vec.append(tmp)
    main_mat.append(vec)
mat = matrix(ZZ, main_mat).T

M = block_matrix(ZZ, [[UL, UR], [mat, DR]])
M = M.LLL()
for row in M:
    if row[6] == 1 and set(row[7:]).issubset([0, 1]):
        print('Find solution!')
        d = int(''.join(list(map(str, row[7:][::-1]))), 2)
        print(d)
        break

key = sha256(str(d).encode()).digest()[:16]
fake_cipher = AES.new(key, AES.MODE_ECB)
prefix = b"Congrats! This is your flag: "
nonce = fake_cipher.decrypt(xor(prefix[:16], c[:16]))[:8]
cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
print(cipher.decrypt(c))
Find solution!
113469799004661487320247409448796883146298153010773207076143627146899378821364
b'Congrats! This is your flag: TSJ{who_needs_gaussian_elimination_when_you_have_LLL?_https://github.com/jonasnick/ecdsaPredictableNonce}'

0x01 Codegate2022 Prime-Generator

  • Category: Crypto
  • Solve:10/141

源码:

from Crypto.Util.number import *
import os

BITS = 512
UPPER_BITS = 296
LOWER_BITS = BITS - UPPER_BITS

UPPER = bytes_to_long(os.urandom(UPPER_BITS // 8)) << LOWER_BITS
FLAG = b'codegate2022{this_is_a_sample_flag}'

def menu1():
    while True:
        lower = bytes_to_long(os.urandom(LOWER_BITS // 8))
        p = UPPER | lower
        if isPrime(p): return lower

def menu2():
    p = UPPER + menu1()
    q = getPrime(512)
    e = 0x10001
    n = p * q
    return n, pow(bytes_to_long(FLAG + b'\x00' + os.urandom(128 - 2 - len(FLAG))), e, n)

while True:
    print("1. Generate 10 random primes (only lower bits)")
    print("2. Encrypt a flag")
    idx = int(input("> "))
    if idx == 1:
        print("How many? (Up to 10)")
        num = int(input("> "))
        for _ in range(min(10, num)):
            print(menu1())
    elif idx == 2:
        n, c = menu2()
        print(f"n : {n}")
        print(f"c : {c}")
UPPER = bytes_to_long(os.urandom(UPPER_BITS // 8)) << LOWER_BITS

可以看出这个题目给了两个功能:menu1menu2menu1会生成一个形如UPPER*(2^216) + lower的素数,并返回它的低216bits,其中UPPER在每次交互的时候是不变的(296bits)。menu2会调用menu1生成一个如上格式的素数作为p,再随机生成一个512bit的q,进行RSA加密,并返回n和密文c。

乍一看思路其实很清晰,我们只需要拿到UPPER即拿到了p的高位,即可用partial p attack对n进行分解。那么如何从无限多的低位中拿到UPPER呢?

这里我们用到了一个有用的结论,因为UPPER*(2^216) + lower是一个素数,那么对于比较小的素数p来说,我们有:
image.png
只要我们拿到足够多的lower并且根据这个事实筛选掉不符合条件的值,我们就可以得到UPPER mod p的值了,之后我们利用CRT即可恢复UPPER。因为UPPER为296bits,那么前50个素数(不包括2)即可作为p来使用。

因为比赛已经结束,赛后复盘并没有在服务器上搭建环境,本地模拟了大致的流程:

模拟流程及exp:

from Crypto.Util.number import *
import os

BITS = 512
UPPER_BITS = 296
LOWER_BITS = BITS - UPPER_BITS

UPPER = bytes_to_long(os.urandom(UPPER_BITS // 8)) << LOWER_BITS
FLAG = b'codegate2022{this_is_a_sample_flag}'

def menu1():
    while True:
        lower = bytes_to_long(os.urandom(LOWER_BITS // 8))
        p = UPPER | lower
        if isPrime(p): return lower

def menu2():
    p = UPPER + menu1()
    q = getPrime(512)
    e = 0x10001
    n = p * q
    return n, pow(bytes_to_long(FLAG + b'\x00' + os.urandom(128 - 2 - len(FLAG))), e, n)

def check_fine(reminder):
    flag = 0
    for x in reminder:
        if len(x) > 1:
            flag = 1
            break
    return flag

sieve = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229]
reminder = [[x for x in range(k)] for k in sieve]
constant = 2^216

while check_fine(reminder):
    lowers = [menu1() for i in range(10)]
    for lower in lowers:
        for i in range(len(sieve)):
            RHS = (-lower * inverse(constant, sieve[i])) % sieve[i]
            if RHS in reminder[i]:
                reminder[i].remove(RHS)
crt_rem = []
for v in reminder:
    crt_rem.append(v[0])
upper = crt(crt_rem, sieve)

e = 0x10001
n, c = menu2()

P.<x> = PolynomialRing(Zmod(n))
f = x + upper * constant
root = f.small_roots(X=constant, beta=0.4, epsilon=5/32)[0]
p = int(f(root))
q = n // p
assert p * q == n
phi = (p-1)*(q-1)
d = int(inverse(e, phi))
m = int(pow(c, d, n))
print(long_to_bytes(m))
b'codegate2022{this_is_a_sample_flag}\x00\xef\x10v\xdfn\x11\x89Z\x18\x1f\xddx\xcd\x9b\x82\xdd\x1f\x8bx\xaa\xec\x93U\xa4\x7f\xd9\xe9r\xb9\xb0wk-\x9d\xe5\x88\td\x8d\x94\x7f\xdc\xad\xb1\xf3\xb1\xb1\xc3\xd3r\x03\\\x8f<\x13A}@\x98h\xcb/\x82\xeewU\x1b\xcf}]\xddZ\xc8X\xe9O\xce\x9d\xd2<+\xab\xa5\x05+\xa7\xca\x1f\x0c\xd5L'

0x02 小结

TSJCTF中的那道nonce相关题目其实是真实的案例改编的,他原本来自github.com/obscuren/secp256k1-go,一个golong的密码学库,其中就选择了这样的bad nonce,当然这个库现在已经404了。总而言之这些题目是比较新颖和有趣的,无论是新的ecdsanonce问题还是巧用crt的新奇思路,都让我学到了很多知识,国际赛的质量还是挺高的。

我正在「Funny Web CTF」和朋友们讨论有趣的话题,你⼀起来吧?

0x03 参考:

https://blog.maple3142.net/2022/02/28/tsjctf-2021-writeups/#signature

评论

L

Lyutoon

这个人很懒,没有留下任何介绍

随机分类

神器分享 文章:71 篇
软件安全 文章:17 篇
渗透测试 文章:154 篇
Ruby安全 文章:2 篇
数据分析与机器学习 文章:12 篇

扫码关注公众号

WeChat Offical Account QRCode

最新评论

J

JANlittle

hxd这是哪个分区赛的题呀,方不方便放个附件?

PuPp1T.

好的 再去搜集一些资料大概一两周左右补上 太感谢师傅指点啦

NorthShad0w

不是很全可能你找的资料太老了,有空可以补一补 sekurlsa 少了 clou

gxh191

谢谢大佬,我转web了

C

CDxiaodong

学到了 感谢大佬

目录