Log Jam

The brief

Someone forgot to shred their logs. We caught an encrypted transmission leaving an adversary's network. The recovery was messy, but everything we salvaged is in params.json. Find the key. Read the message.

• logjam.zip, 998 B

In short

A Diffie Hellman public key on a 71 bit safe prime guarded an AES GCM message. A Pollard rho collision search recovered the private exponent after about 41 billion steps, and the AES key was the SHA-256 of that exponent.

Diffie Hellman on a tiny prime

The file params.json holds a public key h = g^x mod p and a message sealed with AES GCM. The prime p has only 71 bits, where groups in real use have 2,048 or more. The name points at Logjam, the attack on weak Diffie Hellman groups.

No shortcut, only the square root

The prime is safe. p minus 1 is 2 times q, a 70 bit prime, and g and h both sit in the subgroup of order q. Nothing splits into small pieces, so x takes a generic attack on the order of the square root of q, about 34 billion steps.

Walks that wait for a collision

The lab wrote Pollard rho in C. Each walk hops through values g^a h^b with known a and b and stores rare distinguished points. Two threads ran at about 80 million steps a second.

41 billion steps, one collision

After about 41 billion steps, 9 minutes of running, two walks reached the same point. Their exponent pairs give x = 471,774,559,909,450,042,061, and g^x mod p equals h exactly.

The key is a hash of x

The AES key is the SHA-256 of x written as decimal text. With the 12 byte nonce, AES GCM opens the 50 byte message and the tag verifies, so the plaintext is authentic.

The insight

A 71 bit prime gives Diffie Hellman no cover. A square root attack needs about 34 billion steps, and the key was only a hash of the exponent.

The flag

hiCTF{W0W1_y0u_4ctu4a11y_s01v3d_1t_ju$t_L1k3_tH4t}