2024 Cyber Apocalypse: Russian Roulette

Challenge Information

Summary

Russian Roulette is a blockchain challenge involving a weak Diffie-Hellman key exchange implementation. The vulnerability lies in using a 32-bit prime modulus (0xdd6cc28d), which is small enough to be factored or brute-forced. The challenge provides public keys A and B, allowing an attacker to recover the private keys and compute the shared secret to decrypt the flag.

Analysis

The challenge implements Diffie-Hellman key exchange with the following vulnerable characteristics:

1. Small Prime Modulus: Uses a 32-bit prime (0xdd6cc28d) instead of a cryptographically secure large prime
2. Published Parameters: Public keys A and B are provided in the output
3. AES Encryption: The shared secret is hashed with SHA256 and used as an AES-256-CBC key
4. Predictable IV: The IV is hardcoded (b’\xc1V2\xe7\xed\xc7@8\xf9\\xef\x80\xd7\x80L*‘)

Solution

Step 1: Recover Private Keys

Since the modulus p is small, we can recover the private keys using modular inverse:

from Crypto.Util.number import inverse

# Known values from output.txt
p = 0xdd6cc28d
g = 0x83e21c05
A = 0xcfabb6dd
B = 0xc4a21ba9

# Find 'a' (private key for Alice)
a = pow(g, -1, p) * A % p

# Find 'b' (private key for Bob)
b = pow(g, -1, p) * B % p

print(f'a = {a}')  # 2766777741
print(f'b = {b}')  # 1913706799

Step 2: Compute Shared Secret

Using the recovered private key ‘a’ or ‘b’, compute the shared secret:

# Using private key 'a' and public key 'B'
C = pow(B, a, p)

# Verify it matches the other computation
assert C == pow(A, b, p)

The shared secret is: C = 1739735275

Step 3: Derive AES Key

Hash the shared secret and extract the key:

from Crypto.Util.number import long_to_bytes
from hashlib import sha256

# Derive key from shared secret
hash_obj = sha256()
hash_obj.update(long_to_bytes(1739735275))
key = hash_obj.digest()[:16]  # First 16 bytes for AES-256

# Known IV from source code
iv = b'\xc1V2\xe7\xed\xc7@8\xf9\\\xef\x80\xd7\x80L*'

Step 4: Decrypt the Flag

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

ciphertext = b'\x94\x99\x01\xd1\xad\x95\xe0\x13\xb3\xacZj{\x97|z\x1a(&\xe8\x01\xe4Y\x08\xc4\xbeN\xcd\xb2*\xe6{'

cipher = AES.new(key, AES.MODE_CBC, iv)
decrypted_data = unpad(cipher.decrypt(ciphertext), 16)

flag = decrypted_data.decode('utf-8')
print(flag)  # HTB{99%_0f_g4mbl3rs_quit_b4_bigwin}

Key Takeaways

• Key Size Matters: Diffie-Hellman requires large primes (typically 2048+ bits) for security
• Small Moduli Risk: 32-bit primes can be compromised through simple mathematical operations
• Parameter Validation: Always validate cryptographic parameters before deployment
• Defense in Depth: Relying solely on key exchange algorithm without proper parameter selection is insufficient