[Purple Pill Challenge 2023] Bank / Winterfell

 2023-10-13

Bank (aka. Winterfell) was a cryptography challenge from this year’s Purple Pill Challenge. The challenge featured an ECDSA oracle that could sign any message (except the string ‘Winterfell’) and verify any (message, signature) pair. The aim was of course to get the server to verify our signature for the string ‘Winterfell’. The challenge source code is available here.

TL;DR

Just like for the psychic signatures vulnerability, we can send a null signature to sign the message.

Source code analysis

The implementation of the signing part is sane but the verifier function, shown below, isn’t.

def ecdsa_verify(msg, s, r):
    h = int(sha1(msg).hexdigest(), 16)
    u1 = h * modinv(s, q) % q
    u2 = r * modinv(s, q) % q
    T = u1 * G + u2 * P
    print(T)
    x = int(T.x() or 0)
    if x == r:
        return True
    return False

The function deviates from the specification shown below by not verifying the values of s and r. How can we abuse this ?

Psychic signatures

Since s and r are not validated, what would happen if they were both 0 (ie. what would happen if we sent a null signature) ? This is the idea behind the psychic signatures vulnerability in Java’s implementation of ECDSA.

def ecdsa_verify(msg, r, s):
    h = int(sha1(msg).hexdigest(), 16)
    u1 = h * modinv(s, q) % q       <=>       h * 0 % q       <=>       0
    u2 = r * modinv(s, q) % q       <=>       0 * 0 % q       <=>       0
    T = u1 * G + u2 * P             <=>       0 * G + 0 * P   <=>       0 # T is the zero point (a point at infinity)
    print(T)
    x = int(T.x() or 0)                                                   # T.x() is None so x == r == 0
    if x == r:
        return True
    return False

Solve script

import pwn

pwn.context.log_level = "INFO"

# r = pwn.remote("34.244.254.13", 50004)
r = pwn.process(["python3", "winterfell.py"])

r.sendline(b"2")
r.sendline(b'Winterfell'.hex().encode())
r.sendline(b'{"s":"0", "r":"0"}')
r.interactive()

"""
[+] Starting local process '/usr/bin/python3': pid 8522
[*] Switching to interactive mode
[1] - Sign
[2] - Verify
[3] - Exit
> Insert your msg (in hex) : Insert your signature : infinity
Welcome, Sir. Here is your flag flag{debug_flag}

[1] - Sign
[2] - Verify
[3] - Exit
> $
"""