Put a ring on it

4 minutos de lectura

Ring Signatures are used in some cryptocurrencies to provide anonymity for who has signed a transaction or sent money. Can you break the anonymity of the ring signatures?
Challenge contributed by CryptoHack
Challenge files:
ed25519.py
data.json
chal.py

Se nos proporciona una implementación de un protocolo de firma de anillo, que se supone que es un algoritmo en el que unas partes pueden validar los mensajes firmados pero no pueden determinar quién lo ha firmado, proporcionando anonimato a las firmas.

Análisis del código fuente

Hay un archivo que contiene funciones para la curva elíptica Ed25519 (ed25519.py), y el archivo principal del reto (chal.py). Hay mucho código para analizar, pero un error muy sutil que puede explotarse para descifrar la flag.

En resumen, la función principal del script de reto es gen_levels:

def gen_levels():
    levels = []
    for level in range(NUM_LEVELS):
        msg = f"Generating ring {level}"
        print(msg)
        signature, pks, my_key = gen_ring(msg)
        levels.append({
            "signature": signature,
            "public_keys": pks,
            "my_key": my_key,
        })
        print(level)

    with open("flag.txt") as f:
        flag = f.read().strip().encode()

    # First byte of each of my public keys
    aes_key = bytes.fromhex("".join([l["public_keys"][l["my_key"]][0:2] for l in levels]))  
    aes_iv = urandom(16)
    cipher = AES.new(aes_key, AES.MODE_CBC, aes_iv)
    encrypted = cipher.encrypt(flag)

    output = {
        "levels": levels,
        "iv": aes_iv.hex(),
        "enc": encrypted.hex(),
    }

    with open("data-private.json", "w") as f:
        f.write(json.dumps(output))

    for level in output["levels"]:
        del level["my_key"]
    with open("data.json", "w") as f:
        f.write(json.dumps(output))

if __name__ == "__main__":
    gen_levels()

Básicamente, para cada nivel, se genera un anillo de 16 partes, y el que ejecutó el script es uno de ellos. Necesitamos encontrar my_key, que es el índice de su clave pública. Una vez que los tengamos, para cada nivel, podremos encontrar la clave AES y descifrar la flag:

    # First byte of each of my public keys
    aes_key = bytes.fromhex("".join([l["public_keys"][l["my_key"]][0:2] for l in levels]))  
    aes_iv = urandom(16)
    cipher = AES.new(aes_key, AES.MODE_CBC, aes_iv)
    encrypted = cipher.encrypt(flag)

Para cada nivel, nos darán la firma y las claves públicas de las 16 partes (el campo my_key se elimina después):

    for level in range(NUM_LEVELS):
        msg = f"Generating ring {level}"
        print(msg)
        signature, pks, my_key = gen_ring(msg)  
        levels.append({
            "signature": signature,
            "public_keys": pks,
            "my_key": my_key,
        })
        print(level)

Esta es la función gen_ring:

def gen_ring(msg):
    public_keys = [public_key(random_scalar()) for i in range(RING_SIZE)]
    my_privkey = random_scalar()
    my_pubkey = public_key(my_privkey)
    my_index = random.randrange(0, len(public_keys))
    public_keys[my_index] = my_pubkey

    signature = ring_sign(msg, public_keys, my_privkey, my_pubkey, my_index)  

    return signature, public_keys, my_index

Donde random_scalar y public_key son:

def public_key(sk):
    return hexlify(ed25519.encodepoint(ed25519.scalarmultbase(sk)))  


def random_scalar():
    return rand.getrandbits(256)

Este algoritmo de firma de anillo funciona con la curva elíptica Ed25519, por lo que la clave privada es un entero aleatorio, y la clave pública es un punto de generador $G$ de curva multiplicado por la clave privada. Nótese cómo my_key es un número aleatorio entre 0 y 15, lo cual determina qué clave pública es la que nos interesa. Entonces, el script usa su propia clave privada para firmar el mensaje:

def ring_sign(message, public_keys, my_privkey, my_pubkey, my_index):
    image = key_image(my_privkey)

    sigc = [0 for xx in range(RING_SIZE)]
    sigr = [0 for xx in range(RING_SIZE)]

    buf = message
    sumc = 0

    for i in range(RING_SIZE):
        if i == my_index:
            q = random_scalar()
            L = public_key(q)
            R = scalarmultKeyInt(hash_to_point(my_pubkey), q)
        else:
            q = random_scalar()
            w = random_scalar()

            L = addKeys(public_key(q), scalarmultKeyInt(public_keys[i], w))  
            R = addKeys(
                scalarmultKeyInt(hash_to_point(public_keys[i]), q),
                scalarmultKeyInt(image, w)
            )

            sigc[i] = w
            sigr[i] = q
            sumc += sigc[i]

        buf += L
        buf += R
        print(f"{i+1}/{RING_SIZE}")

    c = scalar_hash(buf)

    sigc[my_index] = (c - sumc) % ed25519.l
    sigr[my_index] = (q - sigc[my_index] * my_privkey) % ed25519.l

    return image, sigc, sigr

Esta función puede parecer abrumadora, pero no es tan difícil de entender.

El error

En primer lugar, se aplica un “hash” a la clave privada con key_image:

def key_image(privkey):
    return scalarmultKeyInt(hash_to_point(public_key(privkey)), privkey)

Entonces, dos listas sigc y sigr se inicializan y se rellenan con algunos valores. La clave aquí es que sigr[i] = q y fuera del bucle for, sigr[my_index] se actualiza como (q - sigc[my_index] * my_privkey) % ed25519.l.

El oráculo

Si my_index no es 15, entonces sabemos que sigr[15] es q, por lo que podemos intentar encontrar my_privkey iterando sobre los valores de sigc y comprobando con image, que debería ser key_image(my_privkey). Si ninguno de los valores de sigc funciona, entonces sabremos que my_index tiene que ser 15.

Flag

Después de implementar el oráculo anterior, obtenemos la flag:

$ python3 solve.py
ECSC{thx_Vinc0682_4_inspiration}

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