Tuwaiq Nights Ctf L3aks

L3aks — Crypto

Category: Crypto
Difficulty: Easy
Author: Flagyard

Challenge Summary

The challenge implements a Diffie–Hellman key exchange and then derives an AES key from the shared secret.
However, the server leaks partial information about the secret twice. By exploiting this leak we can recover the full secret and decrypt the flag.

---

Diffie–Hellman Setup

The server generates:

• a strong prime p
• generator g = 2
• secret values a and b

Then computes:

A = g^a mod p
B = g^b mod p

The shared secret becomes:

s = B^a mod p = g^(ab) mod p

The AES key is derived from s:

key = SHA1(str(s))[:16]

The flag is encrypted using AES-CBC.

---

First Information Leak

The server prints:

mask = ((1 << 256) - 1 << 256) + (1 << 255)
r1 = s & mask

This means we learn the most significant bits of the shared secret.

We can write:

s = r1 + x

where

0 ≤ x < 2^255

---

Second Information Leak

Later the server computes:

AC = g^(a + c)
s2 = AC^b
r2 = s2 & mask

So we also know the high bits of another value s2.

We write:

s2 = r2 + y

with

0 ≤ y < 2^255

---

Relationship Between the Secrets

From the definitions:

s  = g^(ab)
s2 = g^((a+c)b)

Expanding:

s2 = g^(ab + bc)

Which equals:

s2 = g^(ab) * g^(bc)

Since:

g^(bc) = (g^b)^c = B^c

Therefore:

s2 = s * B^c mod p

Let:

k = B^c mod p

Then:

s2 ≡ k * s (mod p)

---

Substituting the Leaks

Since:

s = r1 + x
s2 = r2 + y

Substitute into the equation:

r2 + y ≡ k(r1 + x) mod p

Rearrange:

k x - y ≡ r2 - k r1 (mod p)

Let:

D = r2 - k*r1

Then:

k x - y ≡ D (mod p)

Which implies:

n*p + kx + D = y

Because x and y are small (< 2\^255), we can solve this with LLL lattice reduction.

---

Lattice Construction

We build the lattice matrix:

[p   0   0]
[k  -1   0]
[D   0   X]

where

X = 2^255

Running LLL reveals a short vector containing x and y.

---

Solver Script (Sage)

from sage.all import *
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

p  = 13243062138526201284447970770448985497487835935046195151033172870362190226263571343026139270696938219188495760269911620417720944383208589957958028917476379
B  = 12804907211022889015278628012415679960043121396540707259624421939419807646452519300380372940419262121964832208229011315629370674083955124625987102911578414
r1 = 760378900730138567523985812784164677484768378525866553519207455906967297645062813186975476419680956655829496837046596277141393914017271133326426899480576
c  = 10514128938118845773883292289080487620886740574448840718981396583099184943396464503944071765146807497504664152156644409092109452724863376568702011718657467
r2 = 2997362278023140488456292886638406002550622618115848944703928922011753356376940947542648823845754235109234595450483225545693777310720402100337903455436800

ct_hex = "ee7af60d97f400747d8a7cf609ab64c823b7fb2870fc5dc740927344f223a96837c260731d66b56d8f7206b6de5404f1"
iv_hex = "0f098017c38cffaba366c9a4b9caff79"

X = 2^255

k = power_mod(B, c, p)
D = r2 - k*r1

M = Matrix(ZZ, [
    [p,0,0],
    [k,-1,0],
    [D,0,X]
])

L = M.LLL()

for row in L:
    print(row)

---

Recovering the Shared Secret

Running the solver yields:

s = 760378900730138567523985812784164677484768378525866553519207455906967297645087986355760841037730606778245244662827166878771596680226596338163713703910418

---

Decrypting the Flag

The AES key is:

key = SHA1(str(s))[:16]

Using the provided IV and ciphertext, we decrypt the flag.

---

Final Flag

FlagY{37c37f30fc67f98f376a1c30b25b3969}