pbctf2020 | LeaK - crypto-writeup-public

pbctf2020

#!/usr/bin/env python3

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from ecdsa import SECP256k1
from ecdsa.ecdsa import Public_key, Private_key
from flag import flag
import hashlib
import random

g = SECP256k1.generator
order = int(SECP256k1.order)
secret = random.randrange(2, order - 1)
pubkey = Public_key(g, g * secret)
privkey = Private_key(pubkey, secret)

arr = []
for i in range(30):
    h = random.randrange(2, order - 1)
    k = random.randrange(2, order - 1)
    sig = privkey.sign(h, k)
    
    lea_k = int("0x" + "{:064x}".format(k)[10:-10], 16)

    arr.append((h, lea_k, int(sig.r), int(sig.s)))

print(arr)

sha256 = hashlib.sha256()
sha256.update(str(secret).encode())
key = sha256.digest()

aes = AES.new(key, mode=AES.MODE_ECB)
print(aes.encrypt(pad(flag, 16)).hex())

ECDSAで、nonceの前後40bitずつがちぎられて中央の176bitが 30個与えられる

ECDSAでは $s \equiv k^{-1}(h + rd) \mod n$ なので

$k = 2^{216}a + 2^{40}b + c$ とおく（ $b$ が lea_k）

すると

$2^{216}as + 2^{40}bs + cs \equiv h + rd \mod n$

さらに変形して

$r^{-1}(2^{216}as + 2^{40}bs + cs - h) \equiv d \mod n$

これを2インスタンス作って

$r_{1}^{-1}(2^{216}a_{1}s_{1} + 2^{40}b_{1}s_{1} + c_{1}s_{1} - h_{1}) \equiv d \mod n$

$r_{2}^{-1}(2^{216}a_{2}s_{2} + 2^{40}b_{2}s_{2} + c_{2}s_{2} - h_{2}) \equiv d \mod n$

差を取ると4変数のMultivariate Polynomialができるので multivariate coppersmith

$m, d$ は適当に大きくしていく

$f(a_1, a_2, c_1, c_2) = r_{1}^{-1}((2^{216}a_{1} + 2^{40}b_{1} + c_{1})s_{1} - h_{1}) \ - r_{2}^{-1}((2^{216}a_{2} + 2^{40}b_{2} + c_{2})s_{2} - h_{2}) \equiv 0 \mod n$

import itertools
from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence

# https://github.com/defund/coppersmith
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()
    
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = PolynomialSequence([], f.parent())
    for i in range(m+1):
        power = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = power
            for variable, shift in zip(f.variables(), shifts):
                g *= variable^shift
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)
    B = B.change_ring(ZZ)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in B*monomials:
        if h.is_zero():
            continue
        H.append(h.change_ring(QQ))
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            V = I.variety(ring=ZZ)
            if V:
                roots = []
                for root in V:
                    root = map(R, map(root.__getitem__, f.variables()))
                    roots.append(tuple(root))
                return roots

    return []

# ---

from ecdsa import SECP256k1
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
import hashlib

n = int(SECP256k1.order)

params, ciphertext = open("output").read().strip().split("\n")
params = eval(params)
ciphertext = long_to_bytes(int(ciphertext, 16))

h1, b1, r1, s1 = params[0]
h2, b2, r2, s2 = params[1]

r1inv = int(inverse_mod(r1, n))
r2inv = int(inverse_mod(r2, n))

PR.<a1,c1,a2,c2> = PolynomialRing(Zmod(n))
f = r1inv*((2^216*a1 + 2^40*b1 + c1)*s1 - h1) - r2inv*((2^216*a2 + 2^40*b2 + c2)*s2 - h2)
a1,c1,a2,c2 = small_roots(f, [2^40, 2^40, 2^40, 2^40], m=2, d=2)[0]

k = 2^216*a1 + 2^40*b1 + c1
d = int(s1 * k - h1) * r1inv % n

sha256 = hashlib.sha256()
sha256.update(str(d).encode())
key = sha256.digest()

aes = AES.new(key, mode=AES.MODE_ECB)
print(aes.decrypt(ciphertext))