Blind

Is this what people mean by “message blinding”?

Challenge contributed by CryptoHack

Challenge files:

• output.txt
• blind.sage

Análisis del código fuente

Se nos proporciona un script largo de SageMath que usa ECDSA para firmar la clave que cifra la flag (en realidad, una clave utilizada para derivar una clave AES con 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 En la función anterior es _k en main, y está firmado con ECDSA, donde $x$ es la clave privada e $Y = -x \cdot G$ es la clave pública ($G$ es un punto generador de la curva elíptica):

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)

Aparte de esta firma (r, z), tenemos 9999 valores aleatorios que están ahí para ocultar esta firma. Nuestro objetivo es encontrar la firma entre los valores aleatorios y determinar _k para descifrar la flag.

El algoritmo de firma funciona de la siguiente manera:

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)

Se aplican algunas funciones hash al mensaje m y la salida es m1. Luego, se calcula un número aleatorio $\omega$ y $r$ es el XOR entre $(\omega \cdot G)_\mathrm{x}$ y m1 como bytes. Después, $c$ es la salida de otra función hash y $z = \omega + c \cdot x \mod{p}$, donde $x$ es la clave privada y $p$ es el orden de $G$.

Las funciones hash son estas:

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

Todas dependen de esta función Hash:

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]

Además, sabemos que k1 = 320 y k2 = 128.

Solución

Imaginemos que tenemos la firma válida. Entonces, tenemos $r$ y $z$. Dado que tenemos $r$, podemos calcular $c$, ya que c = int.from_bytes(H(r), "big"). Y también sabemos que $z = \omega + c \cdot x \mod{p}$. Aquí, no sabemos $\omega$ ni $x$, pero conocemos la clave pública de ECDSA: $Y = -x \cdot G$. Entonces, si multiplicamos por $G$ (verificación de firma), obtenemos:

$$ \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*} $$

Entonces tenemos el valor de $\omega \cdot G$. Nos interesa $(\omega \cdot G)_\mathrm{x}$ porque

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

Por lo tanto, podemos encontrar fácilmente m1. Luego, recordemos que

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

es solo una concatenación de cadena. Por lo tanto, podemos identificar fácilmente F1(m) y xor(F2(F1(m)), m). Es fácil calcular F2(F1(m)) porque tenemos F1(m), aY así podemos encontrar m ya que conocemos F2(F1(m)) y xor(F2(F1(m)), m).

Como resultado, tenemos una forma de obtener la clave _k siempre que conozcamos los valores válidos r, z.

Ahora, necesitamos una forma de determinar si el _k es correcto o no. Una forma sería derivar la clave con bcrypt.kdf y tratar de descifrar la flag con AES, pero llevará mucho tiempo ya que bcrypt.kdf es muy lenta.

Otra forma de ver si _k es correcto es calcular F1(_k) y comparar con el valor de F1(_k) encontrado anteriormente. Si coincide, entonces todo es correcto.

Otro matiz, la curva elíptica del reto se da en forma de Twisted Edwards, y debemos convertirla a forma de Weierstrass. Esta es solo una conversión sin sentido, pero el reto lo requiere. Además, se nos dan funciones para convertir de una forma a otra, por lo que no hay dificultad añadida en este paso.

Flag

Después de un poco de tiempo, el script mostrará la flag:

$ sage solve.sage
ECSC{3xtr4ct1ng_messages_fr0m_s1gnatur3s_on_a_goldilocks_curv3_is_just_right_a84d4a6a}  

El script completo se puede encontrar aquí: solve.sage.