Signature Studio

Category: Crypto

Description

Welcome to the Signature Studio, where no signature appears twice.

Challenge by Eli Kaski

Sources were attached.

Solution

We are given a service that signs and verifies messages using ECDSA on the standard NIST P-256 curve.

from collections import namedtuple
from hashlib import sha256
import binascii
import random

Point = namedtuple("Point", "x y")
O = 'Infinity'

def sign(private_key, G, message, k=None):
    if k is None:
        k = random.randrange(n)
    hash = bytes_to_long(sha256(message.encode()).digest())
    r = point_multiplication(G, k).x % n
    s = pow(k, -1, n) * (hash + r * private_key) % n
    return number_to_string(r) + number_to_string(s)

def verify(public_key, G, message, signature):
    signature = bytes.fromhex(signature)
    l = p.bit_length() // 8
    if len(signature) != 2*l:
        return False
    r = string_to_number(signature[:l])
    s = string_to_number(signature[l:])
    if r < 1 or r > n - 1 or s < 1 or s > n-1:
        return False
    hash = bytes_to_long(sha256(message.encode()).digest())
    u1 = (hash * pow(s, -1, n)) % n
    u2 = (r * pow(s, -1, n)) % n
    P = point_addition(
        point_multiplication(G, u1), 
        point_multiplication(public_key, u2)
        )
    return P.x % n == r

# Signature cache logic:
SIGNATURES_CACHE = set()
def add_signature(signature):
    SIGNATURES_CACHE.add(signature)
def is_signature_known(signature):
    return signature in SIGNATURES_CACHE

The Rules:

We can ask the server to Sign any message.
We can ask the server to Verify a message + signature pair.
The Goal: We need to verify the specific message: "can i haz flag?".
The Catch: The server caches every signature it generates. If we try to verify a signature that is already in the SIGNATURES_CACHE, it rejects us with “I already knew that…”.

Since we need the server to sign the flag message first (to get a valid signature), we immediately hit the cache problem. We need a way to generate a new, valid signature for the same message without knowing the private key.

This is a textbook example of Transaction Malleability (a property that famously plagued Bitcoin in its early days).

In ECDSA, a signature consists of a pair of integers (r, s). The verification equation involves checking a point P derived from $s^{-1}$.

Due to the symmetry of the elliptic curve, for every valid signature (r, s), the signature (r, -s (mod n)) is also valid for the exact same message.

Original: (r, s)
Forged: (r, n - s)

The Logic Flaw

The server treats the signature as a raw hex string and stores it in a Python set:

SIGNATURES_CACHE.add(signature)
# ... later ...
if signature in SIGNATURES_CACHE:
    send("I already knew that...")

The mathematical value s and n-s are distinct integers, so their hex string representations are different.

We get the server to sign "can i haz flag?". It stores the signature S_orig in the cache.
We calculate the malleable twin S_new = (r, n-s).
We submit S_new.
The server checks the cache: S_new != S_orig. Pass.
The server verifies the math: S_new is valid. Pass.
We get the flag.

Solution Script

from pwn import *

# Challenge Parameters
# 'n' (Order of the curve) from source code
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551

def solve():
    # Connect to the challenge
    conn = remote('0.cloud.chals.io', 27412)
    
    target_message = "can i haz flag?"
    print(f"[*] Target Message: {target_message}")

    # 1. Sign the target message to get a valid (r, s)
    conn.sendlineafter(b'3 - Exit\n', b'1')
    conn.sendlineafter(b'Enter a message to sign:\n', target_message.encode())
    
    conn.recvuntil(b'Signature: ')
    sig_hex = conn.recvline().strip().decode()
    print(f"[*] Original Signature: {sig_hex}")

    # Parse r and s (64 hex chars each = 32 bytes)
    r_hex = sig_hex[:64]
    s_hex = sig_hex[64:]
    r = int(r_hex, 16)
    s = int(s_hex, 16)

    # 2. Calculate the malleable signature s' = n - s
    s_prime = n - s
    
    # Format back to 64-char hex strings
    r_new_hex = f"{r:064x}"
    s_new_hex = f"{s_prime:064x}"
    new_sig_hex = r_new_hex + s_new_hex
    
    print(f"[*] Malleable Signature: {new_sig_hex}")

    # 3. Verify the target message using the NEW signature
    conn.sendlineafter(b'3 - Exit\n', b'2')
    conn.sendlineafter(b'What is your message?\n', target_message.encode())
    conn.sendlineafter(b'What is your signature?\n', new_sig_hex.encode())

    # 4. Receive Flag
    response = conn.recvline().decode()
    print(f"\n[+] SERVER RESPONSE: {response}")
    
    conn.close()

if __name__ == '__main__':
    solve()

[*] Original Signature: 64e2...
[*] Malleable Signature: 64e2...[different_s]

[+] SERVER RESPONSE: Cool, here's the flag: BSidesTLV2025{m4ll3ab1l1ty_1s_a_f34tur3_n0t_a_bug}