Blind

Is this what people mean by “message blinding”?

Challenge contributed by CryptoHack

Challenge files:

• output.txt
• blind.sage

Source code analysis

We are given a large SageMath script that uses ECDSA to sign the key to encrypt the flag (actually, a key used to derive an AES key with bcrypt.kdf):

def encrypt_flag():
    k = secrets.token_bytes(k2//8)
    key = bcrypt.kdf(k, b"ICC_CHALLENGE", 16, 31337)  
    cipher = AES.new(key, AES.MODE_CTR, nonce=b"")
    with open("flag.txt", "rb") as f:
        flag = f.read().strip()
    return k, cipher.encrypt(flag)

So, the value k in the above function is _k in main, and it is signed with ECDSA, where $x$ is the private key and $Y = -x \cdot G$ is the public key ($G$ is a generator point of the elliptic curve):

def main():
    Y, x = keygen()
    _k, ct = encrypt_flag()

    print(f"Y = {to_twistededwards(*Y.xy())}")
    print(f"ct = {ct.hex()}")
    sigs = []
    sigs.append(sign(_k, x))
    for _ in range(10000 - 1):
        sigs.append((secrets.token_bytes((k1 + k2)//8).hex(), secrets.randbelow(p)))  
    random.seed(secrets.token_bytes(16))
    random.shuffle(sigs)
    print(sigs)

Appart from this signature (r, z), we have 9999 random values that are there to hide this signature. Our objective is to find the signature among the random values and determine _k to decrypt the flag.

The signature algorithm works as follows:

def sign(m, x):
    m1 = F1(m) + xor(F2(F1(m)), m)
    ω = secrets.randbelow(p)
    r = xor(int((ω * G)[0]).to_bytes((k1 + k2)//8, "big"), m1)  
    c = int.from_bytes(H(r), "big")
    z = (ω + c * x) % p
    return (r.hex(), z)

The message m is hashed with some functions and the output is m1. Then, a random number $\omega$ is computed and $r$ is just the XOR between $(\omega \cdot G)_\mathrm{x}$ and m1 as bytes. After that, $c$ is the output of another hash function and $z = \omega + c \cdot x \mod{p}$, where $x$ is the private key and $p$ is the order of $G$.

The hash functions are these ones:

F1 = lambda x: Hash(x, k2, k1, b"1")
F2 = lambda x: Hash(x, k1, k2, b"2")
H = lambda x: Hash(x, k1+k2, k, b"H")  

All of them depend on this Hash function:

def Hash(x, nin, n, div):
    assert nin % 8 == n % 8 == 0
    nin //= 8
    n //= 8
    assert len(x) == nin
    r = b""
    i = 0
    while len(r) < n:
        r += hashlib.sha256(x + b"||" + div + int(i).to_bytes(8, "big")).digest()  
        i += 1
    return r[:n]

Moreover, we know that k1 = 320 and k2 = 128.

Solution

Imagine that we have the valid signature. Then, we have $r$ and $z$. Since we have $r$, we can compute $c$, because c = int.from_bytes(H(r), "big"). And we also know that $z = \omega + c \cdot x \mod{p}$. Here, we don’t know $\omega$ and $x$, but we know the public key of ECDSA: $Y = -x \cdot G$. So, if we multiply by $G$ (signature verification), we get:

$$ \begin{align*} z = \omega + c \cdot x \mod{p} & \iff z \cdot G = \omega \cdot G + c \cdot x \cdot G \\ & \iff z \cdot G = \omega \cdot G - c \cdot Y \\ & \iff \omega \cdot G = z \cdot G + c \cdot Y \end{align*} $$

So we have the value of $\omega \cdot G$. We are interested in $(\omega \cdot G)_\mathrm{x}$ because

    r = xor(int((ω * G)[0]).to_bytes((k1 + k2)//8, "big"), m1)  

Therefore, we can easily find m1. Then, recall that

    m1 = F1(m) + xor(F2(F1(m)), m)  

which is just a string contatenation. Hence, we can easily identify F1(m) and xor(F2(F1(m)), m). It is easy to compute F2(F1(m)) because we have F1(m), and thus we can find m because we know F2(F1(m)) and xor(F2(F1(m)), m).

As a result, we have a way to get the key _k provided that we know the valid r, z values.

Now, we need a way to tell if the _k is correct or not. One way would be deriving the key with bcrypt.kdf and trying to decrypt the flag with AES, but it will take a lot of time since bcrypt.kdf is very slow.

Another way to see if _k is correct is to compute F1(_k) and compare it with the value F1(_k) found previously. If it matches, then everyting is correct.

Another nuance, the elliptic curve of the challenge is given in Twisted Edwards form, and we must convert it to Weierstrass form. This is just a non-sense conversion, but the challenge requires so. Plus, we are given functions to convert from one form to the other, so there is no difficulty on this.

Flag

After a bit of time, the script will show the flag:

$ sage solve.sage
ECSC{3xtr4ct1ng_messages_fr0m_s1gnatur3s_on_a_goldilocks_curv3_is_just_right_a84d4a6a}  

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