<- HACK.LU CTF

Spooky Safebox

9 minutes to read

We are given source code of the server in Python. This is app.py:

#!/usr/bin/env python3

import secrets
import os, sys, hmac
import cryptod
from proofofwork import challenge_proof_of_work

FLAG = os.environ.get("FLAG", "flag{FAKE_FLAG}") if "flag" in os.environ.get("FLAG","") else "flag{FAKE_FLAG}"


 
def main():
    print("Welcome to the Spooky Safebox!")
    if not challenge_proof_of_work():
        return
    kpriv, kpub = cryptod.make_keys()
    order = cryptod.get_order()
    encrypted_flag = cryptod.encrypt(kpub, FLAG)
    print("Here is the encrypted flag:", encrypted_flag)
    print("You've got 9 signatures, try to recover Satoshi's private key!")
    for i in range(9):
        msg_ = input("Enter a message to sign: >")
        msg = hmac.new(cryptod.int_to_bytes(kpub.point.x() * i), msg_.encode(), "sha224").hexdigest()
        checksum = 2**224 + (int(hmac.new(cryptod.int_to_bytes(kpriv.secret_multiplier) , msg_.encode(), "sha224").hexdigest(), 16) % (order-2**224))  
        nonce = secrets.randbelow(2 ** 224 - 1) + 1 + checksum
        sig = kpriv.sign(int(msg, 16) % order, nonce)
        print("Signature",(cryptod.int_to_bytes(int(sig.r)) + bytes.fromhex("deadbeef") + cryptod.int_to_bytes(int(sig.s))).hex())
    
    print("Goodbye!")

if __name__ == '__main__':
    try:
        main()
    except EOFError:
        pass
    except KeyboardInterrupt:
        pass

And this is cryptod.py:

import ecdsa, ecdsa.ecdsa
from cryptography.hazmat.primitives.kdf.kbkdf import (
   CounterLocation, KBKDFHMAC, Mode
)
from cryptography.hazmat.primitives import hashes
import secrets
from Crypto.Cipher import ChaCha20_Poly1305

def get_order(): return ecdsa.NIST256p.generator.order()
def encrypt_sym(input_bytes: bytes, key:bytes):

    cipher = ChaCha20_Poly1305.new(key=key)
    ciphertext, tag = cipher.encrypt_and_digest(input_bytes)
    return ciphertext + tag + cipher.nonce

def derive_symkey(inp:bytes):
    kdf = KBKDFHMAC(
        algorithm=hashes.SHA3_256(),
        mode=Mode.CounterMode,
        length=32,
        rlen=4,
        llen=4,
        location=CounterLocation.BeforeFixed,
        label=b"safu",
        context=b"funds are safu",
        fixed=None,
    )
    return kdf.derive(inp)
    
def make_keys():
    gen = ecdsa.NIST256p.generator
    secret = secrets.randbelow(gen.order()-1) + 1
    pub_key = ecdsa.ecdsa.Public_key(gen, gen * secret)
    priv_key = ecdsa.ecdsa.Private_key(pub_key, secret)
    return priv_key, pub_key

def int_to_bytes(n: int) -> bytes:
    return n.to_bytes((n.bit_length() + 7) // 8, 'big') or b'\0'  

def encrypt(kpub_dest:ecdsa.ecdsa.Public_key, msg:str):
    gen = ecdsa.NIST256p.generator
    r = secrets.randbelow(gen.order()-1) + 1
    R = gen * r
    S = kpub_dest.point * r
    key = derive_symkey(int_to_bytes(int(S.x())))
    cp = encrypt_sym(msg.encode(), key).hex() 
    return cp + "deadbeef" + R.to_bytes().hex()

Source code analysis

The code is difficult to read, but after a bit of time, we can figure out what it does. The server uses an ECC and ECDSA on the curve P256.

The flag is encrypted with ChaCha20 and the key is derived from a curve point $S$ (actually, from $S_x$). This point $S$ is just $r \cdot Q$, where $r$ is a random value and $Q$ is the public key. This public key is $Q = x \cdot G$, where $x$ is the private key and $G$ is a generator of the curve.

All of these facts are present in cryptod.py. The encrypted data is the ChaCha20 ciphertext and the point $R = r \cdot G$. Notice that if we had the private key $x$, then $S = r \cdot Q = r \cdot (x \cdot G) = x \cdot (r \cdot G) = x \cdot R$. Therefore, we need to find the private key $x$ to be able to decrypt the flag.

In main.py, after passing the proof of work, we are given the encrypted data and we are allowed to enter 9 messages that will be signed with ECDSA in a weird way:

    for i in range(9):
        msg_ = input("Enter a message to sign: >")
        msg = hmac.new(cryptod.int_to_bytes(kpub.point.x() * i), msg_.encode(), "sha224").hexdigest()
        checksum = 2**224 + (int(hmac.new(cryptod.int_to_bytes(kpriv.secret_multiplier) , msg_.encode(), "sha224").hexdigest(), 16) % (order-2**224))  
        nonce = secrets.randbelow(2 ** 224 - 1) + 1 + checksum
        sig = kpriv.sign(int(msg, 16) % order, nonce)
        print("Signature",(cryptod.int_to_bytes(int(sig.r)) + bytes.fromhex("deadbeef") + cryptod.int_to_bytes(int(sig.s))).hex())

Our input message is hashed with HMAC using $i \cdot Q_x$ as key, where $i$ is the iteration variable. Since the public key $Q$ is not given to us, we will only know the HMAC key for the first message, since the key will be $0 \cdot Q_x = 0$. Moreover, it uses SHA224 as hash function.

After that, this hash is used to generate a checksum value using another SHA224-HMAC and $x$ as key.

Then, the nonce $k$ is just a random number below $2^{224} + 1$ plus the checksum, which is a 225-bit integer. Therefore, the nonces are 225-bit integers.

And finally, the server signs with ECDSA and outputs $r$ and $s$.

ECDSA implementation

The code for the ECDSA is almost correct (more information here). We have this equation for $i \in \{0, \dots, 8\}$:

$$ s_i = k_i^{-1} \cdot \left(h_i + x \cdot r_i\right) \mod{n} $$

Where $n$ is the order of the curve, $k_i$ are the nonces, $h_i$ are the message digests, $x$ is the private key and $(r_i, s_i)$ are the signature pairs.

The security flaw

The problem here is that the server generates nonces $k$ wrongly. Notice that $k$ are random 225-bit integers, whereas the curve P256 has a 256-bit order.

As a result, we can use a lattice-based attack and LLL to solve the Hidden Number Problem. I found this technique in this website, which points to section 4 of this paper.

Hidden Number Problem

The HNP is usually defined as:

$$ t_i \cdot \alpha + a_i \equiv b_i \pmod{p} $$

Where $\alpha$ is the hidden number and both $t_i$ and $a_i$ are known, given $i$ equations. We can apply the ECDSA signature formula to this format:

$$ s_i \equiv k_i^{-1} \cdot \left(h_i + x \cdot r_i\right) \pmod{n} $$

$$ s_i k_i \equiv h_i + x \cdot r_i \pmod{n} $$

$$ r_i \cdot x + h_i \equiv s_i k_i \pmod{n} $$

$$ (s_i^{-1} r_i) \cdot x + (s_i^{-1} h_i) \equiv k_i \pmod{n} $$

We can define a lattice that contains the solution for the HNP. In the definition, we can use the lattice spanned by the columns of:

$$ M = \begin{pmatrix} p & & & & t_1 & a_1 \\ & p & & & t_2 & a_2 \\ & & \ddots & & \vdots & \vdots \\ & & & p & t_i & a_i \\ & & & & X / p & \\ & & & & & X \\ \end{pmatrix} $$

Where $X$ is an upper bound for the $b_i$ values. Notice that the vector $(b_1, \dots, b_i, \alpha, X \alpha / p, X)$ is in the lattice:

$$ \begin{pmatrix} p & & & & t_1 & a_1 \\ & p & & & t_2 & a_2 \\ & & \ddots & & \vdots & \vdots \\ & & & p & t_i & a_i \\ & & & & X / p & \\ & & & & & X \\ \end{pmatrix} \cdot \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_i \\ \alpha \\ 1 \end{pmatrix} = \begin{pmatrix} c_1 p + \alpha t_1 + a_1 \\ c_2 p + \alpha t_2 + a_2 \\ \vdots \\ c_i p + \alpha t_i + a_i \\ X \alpha / p \\ X \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_i \\ X \alpha / p \\ X \end{pmatrix} $$

Observe that $c_i$ are just arbitrary integer numbers, they are irrelevant because we are working $\mod{p}$. The target vector is supposed to be short, so that it can be found in the reduced lattice after applying LLL.

If we apply this procedure on the ECDSA equations we have, we will try to find the vector $(k_1, \dots, k_i, X x / n, X)$. We know this is a likely to be a short vector within the lattice since all $k_i$ are at most 225-bit numbers and the lattice is defined over a 256-bit order.

Finding the public key

In order to apply the HNP to this biased nonces situation, we need to know the digests $h_i$. We only know the first one because it is the output of SHA224-HMAC with key $0$. As a result, we get the equation:

$$ s_0 = k_0^{-1} \cdot \left(h_0 + x \cdot r_0\right) \mod{n} $$

It is possible to extract the public key $Q$ from $(r_0, s_0)$. We can follow the steps in Wikipedia:

$$ Q = r_0^{-1} \cdot (s_0 P - h_0 G) $$

Where $P$ is a point in the curve such that $P_x = r_0$. Notice that there are two points that satisfy this condition, so we will have to try both of them.

Implementation

Let’s start by defining some helper functions:

def sign(m: bytes) -> Tuple[int, int]:
    io.sendlineafter(b'Enter a message to sign: >', m)
    io.recvuntil(b'Signature ')
    r, s = map(lambda x: int(x, 16), io.recvline().decode().split('deadbeef'))
    return r, s


def decrypt_sym(ct: bytes, key: bytes, nonce: bytes, tag: bytes) -> bytes:
    return ChaCha20_Poly1305.new(key=key, nonce=nonce).decrypt_and_verify(ct, tag)

Now, let’s pass the proof of work (the challenge source code already includes a proofofwork.py to solve this):

io = get_process()

io.recvuntil(b'Please provide a string that starts with ')
challenge = io.recvuntil(b' and whose sha256 hash starts with', drop=True).decode()  
prefix = io.recvline().decode().strip()

result = solve_pow(challenge, prefix)

io.sendlineafter(b'POW: >', result.encode())

Then, let’s sign the first message and try to get the public key $Q$. In order to verify which of the two possibilities is correct, we will sign a second message:

io.recvuntil(b'Here is the encrypted flag: ')
enc_data = bytes.fromhex(io.recvline().decode())

m0 = b'asdf0'
r0, s0 = sign(m0)
h0 = int(hmac.new(b'\0', m0, 'sha224').hexdigest(), 16)

m1 = b'asdf1'
r1, s1 = sign(m1)

for P in E.lift_x(Fp(r0), all=True):
    Q = pow(r0, -1, n) * (s0 * P - h0 * G)
    h1 = int(hmac.new(long_to_bytes(int(Q[0])), m1, 'sha224').hexdigest(), 16)  

    if (pow(s1, -1, n) * (h1 * G + r1 * Q))[0] == r1:
        break
else:
    io.failure('Failed to find public ECDSA key')
    exit(1)

io.info(f'Public ECDSA key: {Q}')
h, r, s = [h0, h1], [r0, r1], [s0, s1]

Now that we have the public key $Q$, we can obtain all digests $h_i$ and also collect $(r_i, s_i)$:

h, r, s = [h0, h1], [r0, r1], [s0, s1]

for i in range(2, 9):
    mi = f'asdf{i}'.encode()
    ri, si = sign(mi)
    hi = hmac.new(long_to_bytes(int(Q[0]) * i), mi, 'sha224').hexdigest()  
    h.append(int(hi, 16))
    r.append(ri)
    s.append(si)

At this point, we can model and solve the HNP using LLL as follows ($9$ samples are enough):

p = n
a = list(map(lambda s_i, h_i: pow(s_i, -1, p) * h_i % p, s, h))  
t = list(map(lambda r_i, s_i: pow(s_i, -1, p) * r_i % p, r, s))

X = 2 ** 225

raw_matrix = []

for i in range(len(a)):
    raw_matrix.append([0] * i + [p] + [0] * (len(a) - i + 1))

raw_matrix.append(t + [X / p, 0])
raw_matrix.append(a + [0, X])

M = Matrix(QQ, raw_matrix)
L = M.LLL()

Once we have the reduced lattice basis, we need to check which vector is the target one. We can do this by checking if the upper bound $X$ is presend in the vector. Then, we will take the private key $x$ and try to decrypt the flag by deriving the symmetric key from the point $S = x \cdot R$ and decrypting the ciphertext with ChaCha20:

enc_flag, R_bytes = enc_data.split(b'\xde\xad\xbe\xef')
R_mpz = ellipticcurve.Point.from_bytes(NIST256p.curve, R_bytes)
R = E(R_mpz.x(), R_mpz.y())
ct, tag, nonce = enc_flag[:-28], enc_flag[-28:-12], enc_flag[-12:]

for row in L.rows():
    if row[-1] == X:
        k = list(map(int, row[:-2]))
        x = (s[0] * k[0] - h[0]) * pow(r[0], -1, p) % p
        io.info(f'Private key: {x}')
        S = x * R
        key = derive_symkey(long_to_bytes(int(S[0])))

        try:
            io.success(f'Flag: {decrypt_sym(ct, key, nonce, tag).decode()}')  
            exit(0)
        except ValueError:
            io.failure('MAC check failed')
            continue

Flag

If we run the script, we will get the flag:

$ python3 solve_safebox.py flu.xxx 10030
[+] Opening connection to flu.xxx on port 10030: Done
[*] Public ECDSA key: (2632898350580737258169039806927386431504104360833563771125317252526522550904 : 77026766777862121462475060111493786243486512461424268224672289571158997563209 : 1)  
[*] Private key: 103023634815621571102628370470165979788796885143680181972239572475026982389573
[+] Flag: flag{s4tosh1s_Funds_4re_safu_safeB0x_isnt}
[*] Closed connection to flu.xxx port 10030

The full script can be found in here: solve.py.