TetCTF 2020-yaecc

roger

题目描述如下：

Who knows the backdoor wins!
nc 207.148.119.58 7777

审计代码可知，题目模拟了一版ECDSA（NIST-p256 曲线）的实现，我们的任务是根据若干消息/签名对来求私钥，为了便于描述我们先描述一下本题用到的符号系统：

(R,S):签名
a:私钥
k:nonce
H:msg的哈希值
N:曲线的点群阶

在ECDSA中，有如下表达式成立：

R*a − S*k + H ≡ 0 (mod N)

根据ECDSA算法，当对消息进行签名时，nonce应当随机均匀的从区间[0,N)当中进行选择，以p256为例，N的大小应当为256比特，但是在本题当中，nonce只有240比特，因此我们可以考虑将我们本题当中的问题（根据消息/签名对求私钥）转化为格上的CVP问题。

假设我们已经收集了D对消息/签名对，此时有：

Ri*a − Si*ki + Hi ≡ 0 (mod N) i=1,2,3,...,D

等式两边乘上Si的逆，得：

(Si^(-1))*Ri*a − ki + (Si^(-1))*Hi ≡ 0 (mod N)

设Ai = (Si^(-1))*Ri，Bi = -(Si^(-1))*Hi，整理得：

Ai*a ≡ Bi + ki (mod N)

即：

Ai*a - li*N = Bi + ki （li为整数）

将方程用向量形式表示如下：

TetCTF 2020-yaecc

其中(1/2**16)是根据256（a的比特数）-240（k的比特数）= 16计算而来。

对于每一个表达式Ri*a − Si*ki + Hi ≡ 0 (mod N)来讲，一对消息/签名对就可以提供私钥的16比特的信息，因此理论上来讲D（即消息/签名对的对数）= 256/16 = 16即可，在写脚本时我们收集的数量比这一理论值略多一些即可。

将上述推导写成SageMath代码形式如下：

from sage.all import *
from pwn import *
from hashlib import sha256
import os
from Crypto.Util.number import bytes_to_long

EC = EllipticCurve(
    GF(0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff),
    [-3, 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b]
)
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
Zn = Zmod(n)
G = EC((0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
        0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5))
P = G
Q = EC((0xc97445f45cdef9f0d3e05e1e585fc297235b82b5be8ff3efca67c59852018192,
        0xb28ef557ba31dfcbdd21ac46e2a91e3c304f44cb87058ada2cb815151e610046))
pubkey = EC((50590195252452518804028762265927043036734617153869060607666882619539230027822,
        36611353725619757431858072740028832533174535444901899686884685372270344860185))

class DualEcDrbg(object):
    def __init__(self, seed):
        self.s = ZZ(bytes_to_long(seed))

    def next_bits(self):
        self.s = ZZ((self.s * P)[0])
        return ZZ((self.s * Q)[0]) & (2 ** 240 - 1)

def sign(private_key, message, rand):
    z = Zn(ZZ(sha256(message).hexdigest(), 16))
    k = Zn(rand.next_bits())
    assert k != 0
    K = ZZ(k) * G
    r = Zn(K[0])
    assert r != 0
    s = (z + r * private_key) / k
    assert s != 0
    return r, s

data = []
for _ in range(50):
    s = remote("207.148.119.58", 7777)
    m = eval(s.recvline())
    sig = eval(s.recvline())
    data.append((m, sig))
    s.close()
print len(data)
print data[0]
with open("data.txt", "w") as f:
    f.write(str(data))

size = 20
m = []
Ai = [-1]
Bi = [0]
r0, s0 = map(Zn, data[0][1])
z0 = Zn(ZZ(sha256(str(data[0][0])).hexdigest(), 16))
for i in range(size):
    message, sig = data[i+1]
    ri, si = map(Zn, sig)
    zi = z = Zn(ZZ(sha256(str(message)).hexdigest(), 16))
    A = - (s0 * ri) / (r0 * si)
    B = (z0 * ri) / (si * r0) - zi / si
    Ai.append(A)
    Bi.append(B)

Ai.append(0)
Bi.append(n//2^16)
m.append(Ai)
for i in range(size):
    m.append([0]*(i+1) + [n] + [0]*(size-i))

m.append(Bi)
m = Matrix(ZZ, m)

mLLL = m.LLL()

for irow, row in enumerate(mLLL):
    k0 = Zn(row[0])
    d = (s0*k0-z0)/r0
    if pubkey == ZZ(d)*G:
        print d
        break
    k0 = Zn(-row[0])
    d = (s0*k0-z0)/r0
    if pubkey == ZZ(d)*G:
        print d
        break

msg2 = b"I am admin"
rand = DualEcDrbg(os.urandom(16))
sig = sign(ZZ(d), msg2, rand)
s = remote("207.148.119.58", 7777)
s.sendline(str(sig))
ret = s.recvline()
print ret

执行脚本即可得到flag：

TetCTF{_0oops____Sm4ll_k_ru1n3d_th3_p4rty_}

monkeyman

支持学逆向论坛，资源不错！