Put a ring on it

4 minutes to read

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

We are given an implementation of a ring signature protocol, which is supposed to be an algorithm where a set of parties can validate signed messages but cannot determine who has signed it, providing anonymity to the signatures.

Source code analysis

There is a file that contains functions for Ed25519 elliptic curve (ed25519.py), and the main challenge file (chal.py). There is a lot of code to analyze, but a subtle bug that can be exploited to decrypt the flag.

In short, the main function of the challenge script is 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()

Basically, for each level, a ring of 16 parties is generated, and the one who executed the script is one of them. We need to find my_key, which is the index of his/her public key. Once we have those, for every level, we will be able to find the AES key and decrypt the 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)

For each level, we will be given the signature and the public keys of all 16 parties (my_key field is deleted afterwards):

    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)

This is 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

Where random_scalar and public_key are:

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


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

This ring signature algorithm works with Ed25519 elliptic curve, so the private key is a random integer, and the public key is a curve generator point $G$ times the private key. Notice how my_key is a random number between 0 and 15, which determines which public key is the one we are interested in. Then, the script uses its own private key to sign the message:

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

This function might seem overwhelming, but it is not that hard to understand.

The bug

First of all, the private key is “hashed” with key_image:

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

Then, two lists sigc and sigr are initialized and filled with some values. The key here is that sigr[i] = q and outside the for loop, sigr[my_index] is updated to (q - sigc[my_index] * my_privkey) % ed25519.l.

The oracle

If my_index is not 15, then we know that sigr[15] is q, so we can try to find my_privkey iterating through the values of sigc and checking with image, which should be key_image(my_privkey). If none of the values of sigc works, then we know that my_index must be 15.

Flag

After implementing the above oracle, we find the flag:

$ python3 solve.py
ECSC{thx_Vinc0682_4_inspiration}

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