We’re given a weird “Diffie-Hellman-like” setup using this function:
result = 3 * result * mult
mult <<= 1
At first it looks complex, but if you break it down, each bit of the private key contributes:
[ 3^k \cdot 2^{k(k-1)/2} ]
So the public value becomes:
[ public = seed \cdot 3^A \cdot 2^B ]
Where:
- (A = \sum k)
- (B = \sum k(k-1)/2)
👉 So a 256-bit private key is basically reduced to just two numbers (A, B).
The weakness
This is the core flaw:
Instead of being 256-bit secure, the key leaks into small values
(A, B).
That makes it brute-forceable.
Step 1 – Remove seed
inv_seed = inverse(SEED, MOD)
Pa = alice_pub * inv_seed % MOD
Pb = bob_pub * inv_seed % MOD
Now:
Pa = 3^A * 2^B mod MOD
Step 2 – Recover (A, B)
We brute A, and check if what's left is a power of 2.
val = Pa * inverse(3^A) mod MOD
Using a lookup table for powers of 2, we recover:
(A_a, B_a)for Alice(A_b, B_b)for Bob
Step 3 – Get bit positions
We reverse:
[ A = \sum k,\quad B = \sum k(k-1)/2 ]
def recover_bits(A, B):
bits = []
while A > 0:
for k in reversed(range(256)):
if k <= A and (k*(k-1))//2 <= B:
bits.append(k)
A -= k
B -= (k*(k-1))//2
break
return bits
Important mistake to avoid
You can’t combine exponents like normal DH.
This function is stateful, so math shortcuts will give wrong results (you’ll get AES MAC errors).
Step 4 – Recompute shared secret
We must replay the original function:
def apply(seed, bits):
result = seed
for k in bits:
mult = 1
for i in range(k):
result = (3 * result * mult) % MOD
mult <<= 1
return result
Then:
shared = apply(bob_pub, alice_bits)
Step 5 – Decrypt
key = sha256(long_to_bytes(shared)).digest()
cipher = AES.new(key, AES.MODE_GCM, nonce=iv)
plaintext = cipher.decrypt_and_verify(ciphertext, tag)
If everything is correct:
- No MAC error
- You get a valid
FortID{...}flag