TSJ CTF 2022 (II): Signature

Signature is a crypto challenge from TSJ CTF 2022, which ended up having two solves. From this challenge, we can see how ECDSA private keys can be recovered by having a (weak) deterministic ephemeral key, $k$.

Challenge Summary⌗

Suppose that $d$ is the private key for ECDSA (over curve secp256k1). We are given six signatures signed with the above private key. However, $k$ is computed by $k = d \oplus z$ ($z$ is the hash of the message) rather than generated randomly.

$d$ is then used to derive a key for AES-CTR which is used to encrypt the message, which is in the form Congrats! This is your flag: [FLAG]. The objective is to recover the flag.

Solution⌗

Part I: Modelling the unknowns with a linear congruence⌗

Below is the most important equation that is used to solve the challenge:

\[k \cdot s \equiv z + r \cdot d\ (\text{mod}\ n) \qquad [\dagger]\]

From the challenge setting, we have six pairs of $(z, r, s)$. Also, $k$ is deterministic and is given by $k = d \oplus z$. If we write

\[k = \sum_{i=0}^{255} 2^i \cdot k_i \qquad \text{and} \qquad d = \sum_{i=0}^{255} 2^i \cdot d_i,\]

here $k_i, d_i \in \{0, 1\}$. We can express $k_i$ in terms of $d_i$ for each $i = 0, 1, ..., 255$. If we denote $z_i$ by the $i$-th bit of $z$, we have the below truth table that everybody knows:

Since $z_i$'s are known, we can simply write $k_i$ in terms of $d_i$:

\[k_i = \begin{cases} d_i & \text{if}\ z_i = 0 \\ 1 - d_i & \text{otherwise} \end{cases}.\]

It is just that simple. If we let $i = i_1, i_2, ..., i_p$ to be the indexes such that $z_i = 0$ and $i = j_1, j_2, ..., j_q$ be the indexes such that $z_i = 1$, we can rewrite $[\dagger]$ as an equation with 256 bits of unknown (reduced from 512 bits):

\[\begin{aligned} &0 \equiv z + r \cdot \left(\sum_{i=0}^{255} 2^i \cdot d_i\right) - \left(\sum_{i=0}^{255} 2^i \cdot k_i\right) \cdot s \\ & \qquad \equiv z + r \cdot \left(\sum_{u=1}^p 2^{i_u} \cdot d_{i_u} + \sum_{u=1}^q 2^{j_u} \cdot d_{j_u}\right) - \left(\sum_{u=1}^p 2^{i_u} \cdot k_{i_u} + \sum_{u=1}^q 2^{j_u} \cdot k_{j_u}\right) \cdot s \\ & \qquad \equiv z + r \cdot \left(\sum_{u=1}^p 2^{i_u} \cdot d_{i_u} + \sum_{u=1}^q 2^{j_u} \cdot d_{j_u}\right) - \left(\sum_{u=1}^p 2^{i_u} \cdot d_{i_u} + \sum_{u=1}^q 2^{j_u} \cdot (1 - d_{j_u})\right) \cdot s \\ & \qquad \equiv z + r \cdot \left(\sum_{u=1}^p 2^{i_u} \cdot d_{i_u} + \sum_{u=1}^q 2^{j_u} \cdot d_{j_u}\right) - \left(\sum_{u=1}^p 2^{i_u} \cdot d_{i_u} + \sum_{u=1}^q 2^{j_u} - \sum_{u=1}^q 2^{j_u} \cdot d_{j_u}\right) \cdot s \\ & \qquad \equiv \sum_{u=1}^p 2^{i_u} (r - s) \cdot \htmlStyle{color: yellow;}{d_{i_u}} + \sum_{u=1}^q 2^{j_u} (r + s) \cdot \htmlStyle{color: yellow;}{d_{j_u}} + z - \sum_{u=1}^q 2^{j_u} \quad (\text{mod}\ n) \qquad\qquad [\dagger'] \end{aligned}\]

Part II: LLL FTW (as always)⌗

Since $[\dagger']$ is affine, we can write it as

\[a_0 \cdot \htmlStyle{color: yellow;}{d_0} + a_1 \cdot \htmlStyle{color: yellow;}{d_1} + ... + a_{255} \cdot \htmlStyle{color: yellow;}{d_{255}} + b \equiv 0 \quad (\text{mod}\ n), \qquad\qquad [\dagger'']\]

where $a_0, a_1, ..., a_{255}, b$ are all known constants.

Although the size of unknown is reduced from 512 bits to 256 bits, it is not enough for us to recover those $d_i$'s because we only have 256 bits of information.

In reality, we have six pairs of $(z, r, s)$. This is equivalent to $256 \times 6 = 1536$ bits of information. At the same time, they shares the same unknowns $d_0, d_1, ..., d_{255}$, which is only 256 bits. Thus for $i = 0, 1, ..., 5$, we have the below equations (based on $[\dagger'']$):

\[a_{i,0} \cdot \htmlStyle{color: yellow;}{d_0} + a_{i,1} \cdot \htmlStyle{color: yellow;}{d_1} + ... + a_{i,255} \cdot \htmlStyle{color: yellow;}{d_{255}} + b_i \equiv 0 \quad (\text{mod}\ n)\]

Since we have much more information than the unknown and the relation is affine, we can use LLL to find those $d_i$'s. Anyway this is the lattice we used to LLL:

\[A = \left[\begin{array}{ccc|ccc|c} a_{0,0} & & a_{5,0} & 1 & & & \\ & \ddots & & & \ddots & & 0 \\ a_{0,255} & & a_{5,255} & & & 1 & \\ \hline b & \dots & b & & 0 & & 1 \\ \hline n & & & & & & \\ & \ddots & & & 0 & & 0 \\ & & n & & & & \\ \end{array}\right]\]

It would span to the vector $\left[\begin{array}{ccc|ccc|c}0 & \dots & 0 & d_0 & \cdots & d_{255} & 1 \end{array}\right]$ because

\[ \left[\begin{matrix} 0 \\ \vdots \\ 0 \\ \hline d_0 \\ \vdots \\ d_{255} \\ \hline 1 \end{matrix}\right] = A^T \left[\begin{matrix} d_0 \\ \vdots \\ d_{255} \\ \hline 1 \\ \hline \psi_0 \\ \vdots \\ \psi_5 \end{matrix}\right]. \]

Here each $\psi_i$ is just a number that allow the expression to take "$\text{mod}\ n$", and we don't care about what that is. We can write $[\dagger'']$ (again!) to show what $\psi_i$ is:

\[a_0 \cdot \htmlStyle{color: yellow;}{d_0} + a_1 \cdot \htmlStyle{color: yellow;}{d_1} + ... + a_{255} \cdot \htmlStyle{color: yellow;}{d_{255}} + b + n \cdot \htmlStyle{color: yellow;}{\psi_i} = 0\]

We have d = 0xfadda15bda82cc9f8779bff57fb23e3a6b5d0e50dfd809249d36c1af0ed258f4 from LLL. Now we have the AES key. We are almost done!

Part III: Recovering the flag from AES-CTR⌗

Now we have d. The last few lines of their challenge.py lies the last problem yet to be solved. It must be straight forward!

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()))

During the contest, I was very puzzled since I was unable to recover the flag with the below snippet:

cipher = AES.new(key, AES.MODE_CTR)
print(cipher.decrypt(c))

Of course I don't! From the documentation of PyCryptodome, a 8-byte nonce will be generated whenever the nonce parameter is not present.

I thought that exhausting a 8-byte nonce is infeasible. Sarcastically, this is not the first time I have such thoughts. I even DMed @maple3142 to ask if the setting is correct... Of course that is!

Well, as we have the first 16 bytes of the message (Congrats! This i), we can get the first 16 bytes of the keystream. We have nonce || counter by simply decrypting the keystream. We have the key to decrypt stuffs, after all...

After fixing the stupid mistakes those I made, we have the flag:

TSJ{who_needs_gaussian_elimination_when_you_have_LLL?_https://github.com/jonasnick/ecdsaPredictableNonce}

Solution script⌗

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

def xor(a, b):
    return bytes([u^^v for u, v in zip(a, b)])

q = CURVE.q

sigs = [
    [68628903551760154000300039815420920736833607628328728397865761689137575263983, 15443603266495080692405049373908575802334630966756172054216234269624270469394, 22981409647080659483954459639297160899607455746832364780169145673684744217331],
    [78718753887900409677937247756515988306958319672631190519685073607080826418294, 54276644149626679124071775426283215897696024493497440097979013953212408253734, 55041549251920287655053310452444903772819013365729781587201778245299568302064],
    [76095801129518609512809073275431964691465208338605553566026645469843430112342, 13243268453692556572476611015151647125720859921369299900977957389460914346512, 36340755739784353369950946724334315371788689739091478499529319569139128625422],
    [14730727965324371353827007106163274690512416783313793290093026161256262981745, 61155679185854480315452772506628842842531730179984684102346013415628266033721, 23105235892108839369406685343889200404631332972108556923344303689260664287078],
    [1873902112306026140517260545900147482389676444908353863350522632481552764819, 7259111370509779279520618531388517380717524647694957730980169106713190467749, 47964977855256430218836508671575141052659514288194710563910728384541064927004],
    [82140969634605912978034198684963146226227701184998942661897478141366806021323, 83925169940944825117018170424384235795850122118608830570830266120233738605795, 18779900738289102423955738918979596192495903397022523360371032408971788920887],
]
c0 = b'\xd8n\x81\xcfrN=\xa8\xda\xa0pIR\xdb8\x98\xdb.s;\xecOG\xe2\x07\x99\x93\x1ah\x08G\xb2\x82\xe5\xef2\xe9\x92\x8b\xfaA\x8f\xa3\xa5\xcc8\x90\x95\xff?\xef\x1c\xfd\xffL(\xb46H\x0e/z/\xfe\x9eh[\xb3\xc6Y\x0e\x90\xe5\xdaU\xcc\x84\xed\x81\xcb\x1d<`]\xd2E\xd9\xa3\xa5u\xa3/b\xf3qz\x19\xfa\x8e$\xa3S\xac{,\xbcYIZ\xa9Z\xd6M-\x06Io>\xb2\xa35\x97=\x10]\xb36\xf6\xb2.\x8c\xd48\xe4'

# Note: d is the secret key
# d = d0 + 2 * d1 + ... + 2^255 * d255
# we can know each k in terms of d because if
#   zi = 0 then ki = di, and zi = 1 then ki = 1-di

# s * (k0 + 2 k1 + ... + 2^255 k255) = z + r * (d0 + 2 d1 + ... + 2^255 d255) (mod q)

P = PolynomialRing(Zmod(q), [f'd{k}' for k in range(256)])
ds = P.gens()

A = Matrix(ZZ, 6+1+256)

print('[!] Defining the matrix')
for j, (z, r, s) in enumerate(sigs):
    zs = [(z>>i)&1 for i in range(256)]
    
    ks = []
    for zi, di in zip(zs, ds):
        if zi == 0: ks.append(di)
        else:       ks.append(1 - di)

    # f = s * k - (z + r * d)
    f  = s * sum([2**i * ki for i, ki in enumerate(ks)])
    f -= z + r * sum([2**i * di for i, di in enumerate(ds)])

    for i in [0]:
        A[i,   j] = f.constant_coefficient()
    for i in range(256):
        A[i+1, j] = f.coefficient({ ds[i]: 1 })
    for i in [j+257]:
        A[i,   j] = q

for i in range(257):
    A[i, i+6] = 1
print('[*] Defining the matrix: Done')

print('[!] Running LLL')
A = A.LLL()
print('[*] Running LLL: Done')

for row in A:
    if row[6] < 0: row = -row
    if row[6] != 1: continue

    if min(row[:6]) < 0: continue
    if max(row[:6]) > 0: continue
    
    if min(row[7:]) < 0: continue
    if max(row[7:]) > 1: continue

    ds = row[7:]
    d = int(sum(2**i * di for i, di in enumerate(ds)))
    
    key = hashlib.sha256(str(d).encode()).digest()[:16]
    cipher = AES.new(key, AES.MODE_ECB)
    m1 = cipher.decrypt(xor(b'Congrats! This is your flag: TSJ', c0[:32]))

    cipher = AES.new(key, AES.MODE_CTR, nonce=m1[:8])
    m0 = cipher.decrypt(c0)

    print(f'[*] {d = }')
    print(f'[*] {key = }')
    print(f'[*] {m1 = }')
    print(f'[*] {m0 = }')

'''
[!] Defining the matrix
[*] Defining the matrix: Done
[!] Running LLL
[*] Running LLL: Done
[*] d = 113469799004661487320247409448796883146298153010773207076143627146899378821364
[*] key = b"\xc4\xb1\x8d\xdc\xa2#\xa0\xc6\xe5\xa3'\x89,\xd0S\xd2"
[*] m1 = b'\xb7\x8f\x8a\xd1\x07\x1b\x1e?\x00\x00\x00\x00\x00\x00\x00\x00\xb7\x8f\x8a\xd1\x07\x1b\x1e?\x00\x00\x00\x00\x00\x00\x00\x01'
[*] m0 = b'Congrats! This is your flag: TSJ{who_needs_gaussian_elimination_when_you_have_LLL?_https://github.com/jonasnick/ecdsaPredictableNonce}'
'''