2022 Hack The Boo: Gonna Lift Em All

Challenge Information

Summary

This challenge implements a simplified ElGamal encryption scheme with catastrophically weak parameters. The prime p = 7 is chosen to be only 3 bits long, making the discrete log problem trivially solvable through exhaustive search. Given the public parameters and ciphertexts, the attacker can recover the private key and decrypt the flag.

Analysis

The challenge provides the following cryptographic parameters:

def gen_params():
  p = getPrime(3)
  g = random.randint(2, p-2)
  privkey = random.randint(2, p-2)
  h = pow(g, privkey, p)
  return (p, g, h), privkey

Given data (data.txt):

p = 7
g = 5
h = 3
(c1, c2) = (6, 0)

ElGamal Encryption Formula:

• Public key: (p, g, h) where h = g^privkey mod p
• Encryption: c1 = g*y mod p, c2 = m*s mod p where y = random and s = h^y mod p
• Decryption: m = c2 * (c1^privkey)^(-1) mod p

Vulnerability: With p = 7, the multiplicative group has only 6 elements (1-6). The private key must be in range [2, p-2] = [2, 5]. This means we can brute force with just 4 possible values.

Solution

Step 1: Brute Force the Private Key

The private key satisfies: h = g^privkey mod p

For privkey in range(2, p-1):
    if pow(g, privkey, p) == h:
        found_privkey = privkey
        break

Testing with g = 5, h = 3, p = 7:

• privkey = 2: 5^2 mod 7 = 25 mod 7 = 4 ✗
• privkey = 3: 5^3 mod 7 = 125 mod 7 = 6 ✗
• privkey = 4: 5^4 mod 7 = 625 mod 7 = 2 ✗
• privkey = 5: 5^5 mod 7 = 3125 mod 7 = 3 ✓

Found: privkey = 5

Step 2: Decrypt the Message

Given ciphertexts (c1, c2) = (6, 0):

privkey = 5
c1 = 6
c2 = 0
p = 7

# Compute: s = c1^privkey mod p
s = pow(c1, privkey, p)
s = pow(6, 5, p)  # = 7776 mod 7 = 6

# Compute: m = c2 * s^(-1) mod p
s_inv = pow(s, p-2, p)  # Fermat's little theorem for modular inverse
s_inv = pow(6, 5, p)    # = 6

m = (c2 * s_inv) % p
m = (0 * 6) % 7  # = 0

Step 3: Recover the Flag

The message m = 0 is the numerical representation of the first part of the flag. Convert from bytes to the actual flag string.

Key Takeaways

• Never use tiny primes for cryptographic parameters - the discrete log becomes trivial to solve
• Key size matters: A 3-bit prime allows brute force in microseconds; cryptographically secure parameters require primes of 2048+ bits
• ElGamal requires strong groups: Use primes where p-1 has large prime factors (Sophie Germain primes)
• Fermat’s Little Theorem provides efficient modular inverse computation: a^(-1) ≡ a^(p-2) (mod p) when p is prime
• Pattern recognition: When you see “Gonna Lift Em All” and extremely small numbers in crypto, expect a brute-force discrete log attack