2023 Business CTF: Vitrium Stash

Challenge Information

Summary

An old signing panel rumored to contain crucial information about valuable vitalium resources is guarded by DSA signatures. As the war comes to an end, you must exploit the signing system to reveal the locations of these strategic assets.

Analysis

The system implements DSA signing with a Vitalium Storage Panel:

def sign(message):
    m = bytes_to_long(message)
    k = randbelow(p)
    r = pow(g, k, p) % q
    s = (inverse(k, q) * (m + x*r)) % q
    return r, s

def verify(message, r, s):
    m = bytes_to_long(message)
    w = pow(s, -1, q)
    u1 = (m * w) % q
    u2 = (r * w) % q
    v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
    return r == v

The panel allows:

1. Getting the public key (p, q, g, y)
2. Creating accounts (returns signed messages with admin=False)
3. Viewing coordinates (requires admin=True signature)

Vulnerability: The DSA implementation may be susceptible to attacks if:

• Random values (k) are weak or reused
• Parameter extraction from signed messages
• Signature forgery via parameter manipulation

Solution

The attack involves forging a DSA signature for a message with admin=True:

1. Request a legitimate signature: Create an account to get a valid (r, s) pair for a known message

2. Analyze the signature parameters: Extract information from the signature that may reveal patterns in k or other secrets

3. Forge the signature:

   • Calculate the target message hash for {"username": "attacker", "admin": true}
   • Forge a signature (r, s) that will verify against this message
   • This might involve:
     • Finding a k value that produces the same r
     • Mathematical manipulation of the signature equation
     • Exploiting weak random number generation in k

4. Submit forged credentials:

   # Use the forged (r, s) to authenticate as admin
   r = <forged_r>
   s = <forged_s>
   message = {"username": "attacker", "admin": true}

5. Retrieve the flag: Once verified as admin, the system reveals the vitalium stash coordinates

Key Takeaways

• DSA security depends critically on random k values
• Each signature must use a unique, unpredictable k
• If k is reused or weakly generated, private key extraction is possible
• Parameter validation in signature verification is essential
• Administrative access should never rely solely on cryptographic signatures
• Always use modern cryptographic standards like ECDSA over DSA when possible