Post

L3akCTF 2025

Write-up for L3akCTF 2025

Posted Updated
By Dang Minh Tu
19 min read
L3akCTF 2025

Vừa qua mình có tham gia giải L3akCTF 2025, đây là các bài mình đã làm được ^^

Basic LLL

Source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def generate():
    p = random_prime(2^1024, lbound=2^1023)
    x=randint(1,2^16)
    y=randint(1,2^256)
    a=randint(2^1023,2^1024)
    q=random_prime(2^1024)
    n=p*q
    return x,a,y,n,p

x,a,y,n,p = generate()
k = x * y + a * p
e=65537
print(f"x = {x}")
print(f"a = {a}")
print(f"n = {n}")
print(f"k = {k}")

m = b'L3AK{<Redacted>}'
flag = int.from_bytes(m, byteorder='big')
c= pow(flag, e, n)
print(f"c = {c}")

'''
x = 54203
a = 139534605978199350449870348663594126359773246906906418074945064315708552206952695156472923968554408862426942537522569163756593332601739006413404986641247624386522169136633429464195370373009454673819688653512479919153332504769835621608305089536245284458011218876474599059184828911301976396971466368457267831713
n = 12909957208634846878337953184362917609451224905637563117148705894888627434882610771803126452504238664471840340722310690445704139825753660053450331966698205860077330083433391290469454571152366284661640391190008258576947840075212180965738595761925516686689797153224716140447515370184846067654512660266993573880775530634588475842083212670090415716860925772115834314563453955681012820960922892736520042799257599331942717963921797157341454739255402633419216921702659541513141028779948257696746810146033667942181244847983610429227387863821351416689099862418820999250005071861968501333899759899513283613946626413863922604073
k = 24474689179117620559916890529357882261493825442019850679598519081287156822984032786458479363048845076078220151760752906879055457682971398809768604333650029141164831566127754715775782823279839766009120238777348170982471623193652714921064243946655726118484337862412275391615166714375745390409664610412156281691721978732319253694004232933156865189917761521085635692596755802274763409871937618659197646864593743015558828475450200247766980008744319676783526158213931581034209356092026748307730083927225249093712227456855972520574747646873074625455900058136458828591335711677741591552501530047335481073272381631524755666119
c = 11185314040721202177044508537272244264288033276739579716599246665772965854249656943282002695659011960313245796587834222078633141747802754149848079632693280265262199729548775879612614113828267471629389698999657686858047585254549801752634049341009476489652456620836030696102393122618822021082792763848220677651608135328630551380537642144416978955966827336280510774254681264136102268730343853559751471313539810499170669215479225898738527316798768622089152851154959800113070358637984124299357803777453137311143202502153552192970732744885328421213081964363890280109214401691255867427694709196120824176729643585687319321473
'''

Bài này yêu cầu ta phải giải phương trình 2 ẩn:

\[x * y + a * p = k\]

biết x, a, k. Đây là một bải giải phương trình cơ bản cổ điển sử dụng thuật toán LLL. Mọi người tham khảo các build ma trận ở đây.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

from sage.all import *
from Crypto.Util.number import *

x = 54203
a = 139534605978199350449870348663594126359773246906906418074945064315708552206952695156472923968554408862426942537522569163756593332601739006413404986641247624386522169136633429464195370373009454673819688653512479919153332504769835621608305089536245284458011218876474599059184828911301976396971466368457267831713
n = 12909957208634846878337953184362917609451224905637563117148705894888627434882610771803126452504238664471840340722310690445704139825753660053450331966698205860077330083433391290469454571152366284661640391190008258576947840075212180965738595761925516686689797153224716140447515370184846067654512660266993573880775530634588475842083212670090415716860925772115834314563453955681012820960922892736520042799257599331942717963921797157341454739255402633419216921702659541513141028779948257696746810146033667942181244847983610429227387863821351416689099862418820999250005071861968501333899759899513283613946626413863922604073
k = 24474689179117620559916890529357882261493825442019850679598519081287156822984032786458479363048845076078220151760752906879055457682971398809768604333650029141164831566127754715775782823279839766009120238777348170982471623193652714921064243946655726118484337862412275391615166714375745390409664610412156281691721978732319253694004232933156865189917761521085635692596755802274763409871937618659197646864593743015558828475450200247766980008744319676783526158213931581034209356092026748307730083927225249093712227456855972520574747646873074625455900058136458828591335711677741591552501530047335481073272381631524755666119
c = 11185314040721202177044508537272244264288033276739579716599246665772965854249656943282002695659011960313245796587834222078633141747802754149848079632693280265262199729548775879612614113828267471629389698999657686858047585254549801752634049341009476489652456620836030696102393122618822021082792763848220677651608135328630551380537642144416978955966827336280510774254681264136102268730343853559751471313539810499170669215479225898738527316798768622089152851154959800113070358637984124299357803777453137311143202502153552192970732744885328421213081964363890280109214401691255867427694709196120824176729643585687319321473
e = 65537

W = 2**2024
M = Matrix(ZZ, [[x * W, 1, 0, 0],
                [a * W, 0, 1, 0],
                [k * W, 0, 0, W]])
M = M.LLL()

for row in M.rows():
    if row[-1 ] == W:
        p = abs(row[2])
        q = n // p
        phi = (p - 1) * (q - 1)
        d = inverse(e, phi)
        m = pow(c, d, n)
        print(long_to_bytes(m))

# L3AK{u_4ctu4lly_pwn3d_LLL_w1th_sh0rt_v3ct0rs_n1c3}

Shiro Hero

Source code: ecc.py prng.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

from secrets import randbits
from prng import xorshiro256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from ecc import ECDSA
from Crypto.Util.number import bytes_to_long, long_to_bytes
import hashlib
flag = open("flag.txt", "rb").read()
state = [randbits(64) for _ in range(4)]
prng = xorshiro256(state)
leaks = [prng.next_raw() for _ in range(4)]
print(f"PRNG leaks: {[hex(x) for x in leaks]}")
Apriv, Apub = ECDSA.gen_keypair()
print(f"public_key = {Apub}")
msg = b"My favorite number is 0x69. I'm a hero in your mother's bedroom, I'm a hero in your father's eyes. What am I?"
H = bytes_to_long(msg)
sig = ECDSA.ecdsa_sign(H, Apriv, prng)
print(f"Message = {msg}")
print(f"Hash = {H}")
print(f"r, s = {sig}")
key = hashlib.sha256(long_to_bytes(Apriv)).digest()
iv = randbits(128).to_bytes(16, "big")
cipher = AES.new(key, AES.MODE_CBC, iv)
ciphertext = iv.hex() + cipher.encrypt(pad(flag, 16)).hex()
print(f"ciphertext = {ciphertext}")
with open("output.txt", "w") as f:
    f.write(f"PRNG leaks: {[hex(x) for x in leaks]}\n")
    f.write(f"public_key = {Apub}\n")
    f.write(f"Message = {msg}\n")
    f.write(f"Hash = {H}\n")
    f.write(f"r, s = {sig}\n")
    f.write(f"ciphertext = {ciphertext}\n")

Ta thấy rằng, nonce trong phần ecdsa_sign được tính dựa trên prng(). Và ta đã được cung cấp 4 output liên tiếp của prng. Vì tất cả các phép biến đổi trong next_raw() đều chỉ là phép xor và dịch bit nên ta có thể biểu diễn chúng thành các phương trình toán học và dùng Z3 để tìm lại 4 trạng thái ban đầu s0, s1, s2, s3.

Sau khi tìm được state ban đầu rồi thì ta tiếp tục sinh ra 4 state tiếp theo, sau đó ta sẽ tìm được k.

\[s = k^{-1}*(h + dr) \pmod p \\ \Rightarrow d = r^{-1}*(sk-h) \pmod p\]

Thay số và phương trình và tìm được d. Sau đó giải mã AES-CBC để lấy FLAG.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

from z3 import *

MASK64 = (1 << 64) - 1

def rotl(x, k):
    return ((x << k) | LShR(x, 64 - k)) & MASK64

leaks = [0x785a1cb672480875, 0x91c1748fec1dd008, 0x5c52ec3a5931f942, 0xac4a414750cd93d7]

s0 = BitVec('s0', 64)
s1 = BitVec('s1', 64)
s2 = BitVec('s2', 64)
s3 = BitVec('s3', 64)

def next_raw(state):
    s0, s1, s2, s3 = state
    t = (s1 << 17) & MASK64

    s2 ^= s0
    s3 ^= s1
    s1 ^= s2
    s0 ^= s3
    s2 ^= t
    s3 = rotl(s3, 45)

    return s1, [s0, s1, s2, s3]

solver = Solver()
state = [s0, s1, s2, s3]

for i in range(4):
    out, state = next_raw(state)
    solver.add(out == leaks[i])

if solver.check() == sat:
    model = solver.model()
    recovered = [model[v].as_long() for v in [s0, s1, s2, s3]]
    print("Found state:", recovered)

from secrets import randbits
from prng import xorshiro256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from ecc import ECDSA
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Util.number import *
import hashlib

state = [4632343889369999961, 10793220881798324403, 12527397580889080479, 11809022490152434257]
prng = xorshiro256(state)
leaks = [prng.next_raw() for _ in range(4)]
print(f"PRNG leaks: {[hex(x) for x in leaks]}")
k = prng()
r, s = (54809455810753652852551513610089439557885757561953942958061085530360106094036, 42603888460883531054964904523904896098962762092412438324944171394799397690539)
h = 9529442011748664341738996529750340456157809966093480864347661556347262857832209689182090159309916943522134394915152900655982067042469766622239675961581701969877932734729317939525310618663767439074719450934795911313281256406574646718593855471365539861693353445695
d = inverse(r, ECDSA.n) * (s * k - h) % ECDSA.n

key = hashlib.sha256(long_to_bytes(d)).digest()
ciphertext = '404e9a7bbdac8d3912d881914ab2bdb924d85338fbd1a6d62a88d793b4b9438400489766e8e9fb157c961075ad4421fc'
iv = bytes.fromhex(ciphertext[:32])
ciphertext = bytes.fromhex(ciphertext[32:])
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ciphertext)
print(flag)

# L3AK{u_4r3_th3_sh1r0_h3r0!}

Dumber

Source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

from Crypto.Util.number import  bytes_to_long, long_to_bytes
from sage.all import *

a,b,p = ?,?,?

pt1="L3AK{test_"
pt2="flag}"

E = EllipticCurve(Zmod(p), [a, b])
p,q=E.random_element(),E.random_element()
u=bytes_to_long(pt1.encode())*p
v=bytes_to_long(pt2.encode())*q

# I will help u <3
print(p,u,q,v)


# (103905521866731574234430443362297034336 : 116589269353056499566212456950780999584 : 1)
# (171660318017081135625337806416866746485 : 122407097490400018041253306369079974706 : 1)
# (161940138185633513360673631821653803879 : 167867902631659599239485617419980253311 : 1)
# (95406403280474692216804281695624776780 : 109560844064302254814641159241201048462 : 1)

Để giải quyết bài này, việc đầu tiên phải làm đó là khôi phục lại các hệ số của đường cong Elliptic a, b, p. Ta đã được cho 4 điểm nằm trên đường cong nên chúng thỏa mãn:

\[y_i^2 = x_i^3+ax_i+b \pmod p \\ \Rightarrow y_i^2 - x_i^3 = ax_i + b \pmod p \\ \Rightarrow A_i := y_i^2-x_i^3 = ax_i+b \pmod p\]

Vì $a, b$ là các hằng số nên ta có hệ 4 phương trình tuyến tính theo $a, b$ modulo $p$:

\[\begin{cases} A_1 = ax_1 + b \pmod p \\ A_2 = ax_2 + b \pmod p \\ A_3 = ax_3 + b \pmod p \\ A_4 = ax_4 + b \pmod p \\ \end{cases}\]

Nếu trừ 2 phương trình bất kì cho nhau thì sẽ triệt tiêu được $b$, khi đó:

\[A_i - A_j \equiv a(x_i - x_j) \pmod p \\ \Rightarrow a \equiv \frac{A_i-A_j}{x_i-x_j} \pmod p \\ \Rightarrow \frac{A_i-A_j}{x_i-x_j} \equiv \frac{A_k-A_l}{x_k-x_l} \pmod p \\ \Rightarrow (A_i-A_j)(x_k-x_l) \equiv (A_k-A_l)(x_i-x_j) \pmod p \\ \Rightarrow (A_i-A_j)(x_k-x_l) - (A_k-A_l)(x_i-x_j) \equiv 0 \pmod p \\\]

Vậy, với mỗi hoán vị của 4 điểm trên, ta sẽ tính được một giá trị mà nó đồng dư với $0$ modulo $p$. Khi đó, chỉ cần lấy $GCD$ của các giá trị đó là ta sẽ tìm được $p$.

Ta có:

\[\begin{cases} y_P^2 \equiv x_P^3+ax_P+b \pmod p \\ y_Q^2 \equiv x_Q^3+ax_Q+b \pmod p \end{cases}\]

Trừ phương trình trên cho phương trình dưới ta được:

\[y_P^2-y_Q^2 \equiv x_P^3-x_Q^3 + a(x_P - x_Q) \pmod p \\ \Rightarrow a \equiv \frac{y_P^2-y_Q^2-(x_P^3 - x_Q^3)}{x_P-x_Q} \pmod p \\ \Rightarrow b \equiv y_P^2 - x_P^3 - ax_P \pmod p\]

Như vậy ta đã khôi phục lại được đường cong $E$ ban đầu. Mình kiểm tra thử thì nhận thấy order của cả 2 điểm $P, Q$ đều bằng $p$. Tức là đây là đường cong dị thường. Sử dụng Smart attack để giải.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

from sage.all import *
from Crypto.Util.number import *
from itertools import *

P = (103905521866731574234430443362297034336, 116589269353056499566212456950780999584)
U = (171660318017081135625337806416866746485, 122407097490400018041253306369079974706)
Q = (161940138185633513360673631821653803879, 167867902631659599239485617419980253311)
V = (95406403280474692216804281695624776780, 109560844064302254814641159241201048462)

points = [P, U, Q, V]
A = [point[1]**2 - point[0]**3 for point in points]
res = []
for i, j, k, l in permutations([0, 1, 2, 3]):
    res.append((A[i] - A[j]) * (points[k][0] - points[l][0]) - (A[k] - A[l]) * (points[i][0] - points[j][0]))
p = gcd(res)

a = (P[1]**2 - Q[1]**2 - (P[0]**3 - Q[0]**3)) * pow(P[0] - Q[0], -1, p) % p
b = (P[1]**2 - P[0]**3 - a*P[0]) % p

E = EllipticCurve(GF(p), [a, b])
P, U, Q, V = [E(point) for point in points]

assert P.order() == p and Q.order() == p

def _lift(E, P, gf):
    x, y = map(ZZ, P.xy())
    for point_ in E.lift_x(x, all=True):
        _, y_ = map(gf, point_.xy())
        if y == y_:
            return point_
def attack(G, P):
    E = G.curve()
    gf = E.base_ring()
    p = gf.order()
    assert E.trace_of_frobenius() == 1, f"Curve should have trace of Frobenius = 1."

    E = EllipticCurve(Qp(p), [int(a) + p * ZZ.random_element(1, p) for a in E.a_invariants()])
    G = p * _lift(E, G, gf)
    P = p * _lift(E, P, gf)
    Gx, Gy = G.xy()
    Px, Py = P.xy()
    return int(gf((Px / Py) / (Gx / Gy)))

nA = attack(P, U)
nB = attack(Q, V)

flag = long_to_bytes(nA).decode() + long_to_bytes(nB).decode()
print(flag)

# L3AK{5m4rt1_1n_Th3_h00000d!!!}

Mersenne Mayhem

Source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#!/usr/bin/python3

from random import SystemRandom
from math import gcd
from Crypto.Util.number import inverse
from Crypto.Random import get_random_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from hashlib import sha3_256
m_prime = 11213
xi1 = 0.31
xi2 = 0.69
w = 10

rand = SystemRandom()

def hamming_weight(a):
    return a.bit_count()

def get_number(n, h):
    if not (1 <= h <= n):
        raise ValueError(f"Cannot set {h} bits in {n}-bit number")
    low_positions = rand.sample(range(n - 1), h - 1)
    positions = low_positions + [n - 1]
    a = 0
    for pos in positions:
        a |= 1 << pos
    return a

def gen_params(n, w, xi1, xi2, af=1):
    p = 2**n - 1
    bf = int(n * xi1)
    bg = int(n * xi2 * af)
    f = get_number(bf, w)
    g = get_number(bg, w)
    while gcd(f, g) != 1:
        g = get_number(bg, w)
    h = inverse(g, p) * f % p
    return p, f, g, h

def main():
    p, f, g, h = gen_params(m_prime, w, xi1, xi2)
    secret = (f * g ) % p
    secret_bytes = secret.to_bytes((secret.bit_length() + 7)//8, byteorder='big')
    flag = open('flag.txt', 'rb').read()
    key = sha3_256(secret_bytes).digest()
    iv = get_random_bytes(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext_raw = iv +cipher.encrypt(pad(flag, 16))
    ciphertext_hex = ciphertext_raw.hex()
    print(f"Ciphertext = {ciphertext_hex}")
    print(f"p   = {p}")
    print(f"h   = {h}")
    print(f"xi1 = {xi1}")
    print(f"xi2 = {xi2}")
    print(f"w   = {w}")

if __name__ == "__main__":
    main()

Mục tiêu của ta là recover lại $f, g$ sao cho:

\[f = h *g \pmod p \\ \Rightarrow f - hg = 0 \pmod p \\ \Rightarrow f - hg = kp \ \ \ \ ,k \in \mathbb{Z} \\ \Rightarrow f = hg + kp\]

Biểu diễn phương trình trên dưới dạng tổ hợp tuyến tính của các vector ta được:

\[g * \begin{bmatrix} 1 \\ h \end{bmatrix} + k * \begin{bmatrix} 0 \\ p \end{bmatrix} = \begin{bmatrix} g \\ f \end{bmatrix} \\ \Rightarrow \begin{bmatrix} 1 \ \ 0 \\ h \ \ p \end{bmatrix} * \begin{bmatrix} g \\ k \end{bmatrix} = \begin{bmatrix} g \\ f \end{bmatrix}\]

Ta thấy rằng, vector $(g, f)$ là một tổ hợp tuyến tính của cơ sở $B$. Đến đây ta sẽ dùng thuật toán LLL để giải quyết. Ở đây, ta nhân hệ số $W = 2^{bg-bf}$ vào $h, p$ để đảm bảo rằng khi thực hiện LLL sẽ tìm thấy được vector $(g, f)$ chính xác nhất.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

from sage.all import *
from Crypto.Util.number import *
from math import gcd
from Crypto.Util.number import inverse
from Crypto.Random import get_random_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from hashlib import sha3_256

m_prime = 11213
ct = '41b53384d92de5c678a2138a0da552d174d77c420591b29ccb7c7610310bf82bcb58f903a423d7d257e3ee4ae2c4da69'
p   = 2814112013697373133393152975842584191818662382013600787892419349345515176682276313810715094745633257074198789308535071537342445016418881801789390548709414391857257571565758706478418356747070674633497188053050875416821624325680555826071110691946607460873056965360830571590242774934226866183966309185433462514537484258655982386235046029227507801410907163348439547781093397260096909677091843944555754221115477343760206979650067087884993478012977277878532807432236554020931571802310429923167588432457036104110850960439769038450365514022349625383665751207169661697352732236111926846454751701734527011379148175107820821297628946795631098960767492250494834254073334414121627833939461539212528932010726136689293688815665491671395174710452663709175753603774156855766515313827613727281696692633529666363787286539769941609107777183593336002680124517633451490439598324823836457251219406391432635639225604556042396004307799361927379900586400420763092320813392262492942076312933268033818471555255820639308889948665570202403815856313578949779767046261845327956725767289205262311752014786247813331834015084475386760526612217340579721237414485803725355463022009536301008145867524704604618862039093555206195328240951895107040793284825095462530151872823997171764140663315804309008611942578380931064748991594407476328437785848825423921170614938294029483257162979299388940695877375448948081108345293394327808452729789834135140193912419661799488795210328238112742218700634541149743657287232843426369348804878993471962403393967857676150371600196650252168250117793178488012000505422821362550520509209724459895852366827477851619190503254853115029403132178989005195751194301340277282730390683651120587895060198753121882187788657024007291784186518589977788510306743945896108645258766415692825664174470616153305144852273884549635059255410606458427323864109506687636314447514269094932953219924212594695157655009158521173420923275882063327625408617963032962033572563553604056097832111547535908988433816919747615817161606620557307000377194730013431815560750159027842164901422544571224546936793234970894954668425436412347785376194310030139080568383420772628618722646109707506566928102800033961704343991962002059794565527774913883237756792720065543768640792177441559278272350823092843683534396679150229676101834243787820420087274028617212684576388733605769491224109866592577360666241467280158988605523486345880882227855505706309276349415034547677180618296352866263005509222254318459768194126727603047460344175581029298320171226355234439676816309919127574206334807719021875413891580871529049187829308412133400910419756313021540478436604178446757738998632083586207992234085162634375406771169707323213988284943779122171985953605897902291781768286548287878180415060635460047164104095483777201737468873324068550430695826210304316336385311384093490021332372463463373977427405896673827544203128574874581960335232005637229319592369288171375276702260450911735069504025016667755214932073643654199488477010363909372005757899989580775775126621113057905717449417222016070530243916116705990451304256206318289297738303095152430549772239514964821601838628861446301936017710546777503109263030994747397618576207373447725441427135362428360863669327157635983045447971816718801639869547525146305655571843717916875669140320724978568586718527586602439602335283513944980064327030278104224144971883680541689784796267391476087696392191
h   = 1420555256339029007623997813064646001269162517128321148445315195505239735275630861823661566974806499472047280215484592996005803648513302169629626127099758282515738821101977445273485022910246569722391022977450955342222836145985252124058212342529128780170990021228730988558665064173954220322773988555167710669068750665776903981634200337373777404012466927646596680586333670581651645526694895600877689342038116459849183193823872501035663586605107067192354044210531807251755452156351983674662886645745394856941265207731156473167231778757731819787611903442134906892597442296936233823840108134806009542341564017395586357285132443867104900170964829691269535011088959513758953200725927512241315102588162307625667497293774446856607793870742116890747893541277522373302165118962976053575406705355764971195021874784514615007411950628751457901414286417358960010967221053822454908696424925405704175995633020493142678213202614937742894400381343076316089897622795515556015286002072322759700438579099970591676839009309031769399502594275266218377682472239872586976705452556133518395328415914503518652542017532651647731241407171312901187911076641932472943264583606924316675349565466488903831076073348850535782518384829652304040155890590587188783695482711889391210316569992875826864203896074373913044155630807488027391070097591354568591831261212998547450723243648908349081702648981754965087366716012704456844050856945098481648381066456654298504766274287677173531407712216638604928122194203916328841926799970191645315242073698356237463109990735562385573707846536974481579821301372474435457099406760484280999724263427442692583436069170036373949813257024671755403669821456270665060921956691382969799591246457852441573272563366612307625286201260042625086965961053006988659415151285688613563697564208949796608132657497688137512977726996868089866737746050625960033949688003905344289968553237468369562275970721124808922797498954729192402174080310105048553480796371124861551154608423542660872024811406457451424253705687979915395138199662324871095873255085721494088182389344068642956910343125988440788281536821574417589504214561018112652377091738873567384795002650440795826732903483284697533314215503203322729252515102929675782158033940939707173384735831945973131378767145549237414530035857282428664740004024186722896592693839808003379490048051781800528316131147063192114353380299163535474170148552078839155797722939143164848128170591789817861428901096912042379655572487529983245927123870716371357517142431645561532273325783362132723664729122853387243023889022825534772304668999948890306453633124290070865560117725343418936602004343258378292218254184989796563841886060342528155126255491479519793234521554762270234424568183556174229507271089194135988143493032829906811846783521409480751862383365285419925324896562580231684692411694312251240562954259361596977465804532938260753882101880890334741978448410119591665004422790211098229717537610959221523324756588024738544068846236205437760843840319798491939909330547143199854608585823646613660809454152858803614876632067827324289956927912056108902075641611668181460557770913959037715741018607941206784764550084749008826004455090269295539665469266276760215529247213893160911919455625283080509926624966775395334197154212462026901783136821516237970556846369147663455890608535960863730071819706481755582989771193307683239283077479511187437689338027648438450206074052
xi1 = 0.31
xi2 = 0.69
w   = 10

n = m_prime
bf = int(n * xi1)
bg = int(n * xi2)

W = 2**(bg - bf)
M = Matrix(ZZ, [[1, W * h],
                [0, W * p]])
M = M.LLL()

for g, f in M.rows():
    g, f = abs(g), abs(f // W)
    secret = (f * g) % p
    secret_bytes = secret.to_bytes((secret.bit_length() + 7)//8, byteorder='big')
    key = sha3_256(secret_bytes).digest()
    iv = bytes.fromhex(ct[:32])
    ciphertext_raw = bytes.fromhex(ct[32:])

    cipher = AES.new(key, AES.MODE_CBC, iv)
    flag = cipher.decrypt(ciphertext_raw)

    print("Flag:", flag)

# L3ak{4jp2_n0t_s0_str0ng}

Magical Oracle

Source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

#!/usr/bin/env python3
# Author: supasuge | https://github.com/supasuge
# Difficulty: Medium
import sys
import os
import time
import signal
import random
import hashlib
import base64
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import getPrime
from secrets import randbelow

PRIME_BITS       = 256
SESSION_TIMEOUT  = int(os.getenv('TIMEOUT', 60))

def timeout_handler(signum, frame):
    print("\n⏰ Session timeout! The Magical Oracle retreats.")
    sys.exit(1)

signal.signal(signal.SIGALRM, timeout_handler)
signal.alarm(SESSION_TIMEOUT)

class MagicalOracle:
    def __init__(self, connection_id=None):
        self.p = getPrime(PRIME_BITS)
        self.n = self.p.bit_length()
        self.k = int(self.n**0.5) + self.n.bit_length() + 1
        self.d = 2 * int(self.n**0.5) + 3
        self.alpha = randbelow(self.p - 1) + 1

        self.queries_used = 0
        self.max_queries  = self.d
        self.start_time   = time.time()
        self.solved       = False

    def _msb_oracle(self, x):
        threshold = self.p >> (self.k + 1)
        time.sleep(0.05)
        for _ in range(1000):
            z = random.randrange(1, self.p)
            if abs(x - z) < threshold:
                return z

        return (x + random.randint(-threshold//2, threshold//2)) % self.p

    def banner(self):
        return f"""
╔{'═'*65}╗
║              🧙‍♂️ Welcome to the Magical Oracle! 🧙‍♀️              ║
╟{'─'*65}╢
║  Prime (p): {self.p:<52}║
║  Bit length (n): {self.n:<49}║
║  MSB leak (k): {self.k:<50}║
║  Max queries: {self.max_queries:<48}║
║  Timeout: {SESSION_TIMEOUT}s{' '*(44-len(str(SESSION_TIMEOUT)))}║
╚{'═'*65}╝
"""

    def menu(self):
        rem = max(0, SESSION_TIMEOUT - int(time.time() - self.start_time))
        return f"""
📋 Magical Oracle — time remaining: {rem}s
Queries used: {self.queries_used}/{self.max_queries}

1) Query MSB oracle
2) Show encrypted data
3) Show parameters
4) Get a hint
5) Exit

Choose option: """

    def query(self):
        if self.queries_used >= self.max_queries:
            return "❌ No queries left!"
        t = random.randrange(1, self.p)
        leak = self._msb_oracle((self.alpha * t) % self.p)
        self.queries_used += 1
        return f"Oracle #{self.queries_used}: t={t}, z={leak}"

    def encrypt_flag(self):
        raw = open('/home/team/CodePy/L3akCTF/Magical Oracle/flag.txt','rb').read().strip()
        key = hashlib.sha256(str(self.alpha).encode()).digest()
        cipher = AES.new(key, AES.MODE_CBC)
        ct = cipher.iv + cipher.encrypt(pad(raw, AES.block_size))
        return base64.b64encode(ct).decode()

    def show_encrypted(self):
        blob = self.encrypt_flag()
        return f"Flag: {blob}"

    def show_params(self):
        return (f"Prime p = {self.p}\n"
                f"Bit length n = {self.n}\n"
                f"MSB leak k = {self.k}\n"
                f"Max queries d = {self.max_queries}\n"
                f"Queries used = {self.queries_used}\n")

    def hint(self):
        tips = [
            "Use magic, bro...",
            "I just work here"
        ]
        return "💡 Hint: " + tips[min(self.queries_used//3, len(tips)-1)]

if __name__ == '__main__':
    oracle = MagicalOracle()
    print(oracle.banner())
    while True:
        try:
            choice = input(oracle.menu()).strip()
        except KeyboardInterrupt:
            print("\n👋 Bye-bye!")
            break
        if choice == '1':
            print(oracle.query(), flush=True)
        elif choice == '2':
            print(oracle.show_encrypted(), flush=True)
        elif choice == '3':
            print(oracle.show_params(), flush=True)
        elif choice == '4':
            print(oracle.hint(), flush=True)
        elif choice == '5':
            print("👋 Oracle fading away...")
            sys.stdout.flush()
            break
        else:
            print("❌ Choose 1–5, mortal!")
            sys.stdout.flush()
            sys.exit(1)

Tóm tắt bài toán: bài này yêu cầu ta tìm lại giá trị $\alpha$, ta có quyền thực hiện các truy vấn để biết thêm thông tin về $\alpha$, server sẽ tính $t_i*\alpha$ sau đó làm nhiễu giá trị đó bằng cách cộng hoặc trừ thêm các giá trị $e_i$ với $(e_i \leq threshold)$.

Sau khi đọc và phân tích kĩ code của server thì ta dễ dàng nhận thấy đây là bài toán Hidden Number Problem. Server cho ta các cặp $(t_i, z_i)$ thỏa mãn:

\[t_i\alpha = z_i + e_i \pmod p \\ \Rightarrow e_i - t_i\alpha + z_i = 0 \pmod p\]

Với $e_i \leq threshold = (p » k + 1)$. Cách mình xây dựng ma trận là như này:

alt text

Các điều kiện của thuật toán BaBai đều đã được thỏa mãn trong source code.

Code sử dụng (Closet Vector Problem):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

from pwn import *
import hashlib
import base64
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import getPrime
from secrets import randbelow
from sage.all import *

io = remote('34.59.96.214', 11000, level='debug')
# io = process(['python3', '/home/team/CodePy/L3akCTF/Magical Oracle/chal.py'], level='debug')

# Show parameters
io.sendlineafter(b'Choose option: ', b'3')
io.recvline()
p = int(io.recvline().decode().strip().split('=')[-1])
n = int(io.recvline().decode().strip().split('=')[-1])
k = int(io.recvline().decode().strip().split('=')[-1])
d = int(io.recvline().decode().strip().split('=')[-1])


# Show encrypted flag
io.sendlineafter(b'Choose option: ', b'2')
io.recvline()
enc_flag = io.recvline().decode().strip().split(': ')[-1]
enc_flag = base64.b64decode(enc_flag)

# Get query
ts, zs = [], []
for _ in range(d):
    io.sendlineafter(b'Choose option: ', b'1')
    io.recvline()
    query = io.recvline().decode().strip().split(': ')[-1]
    query = query.split(', ')
    t = int(query[0].split('=')[-1])
    leak = int(query[1].split('=')[-1])
    ts.append(t)
    zs.append(leak)

M = Matrix(QQ, d + 1, d + 1)
for i in range(d):
    M[i, i] = p
    M[d, i] = ts[i]
M[d, d] = QQ(1) / QQ(p)

def babai_cvp(B, t, perform_reduction=True):
    if perform_reduction:
        B = B.LLL(delta=0.75)

    G = B.gram_schmidt()[0]
    b = t
    for i in reversed(range(B.nrows())):
        c = ((b * G[i]) / (G[i] * G[i])).round()
        b -= c * B[i]

    return t - b

u = babai_cvp(M, vector(zs + [0]))
alpha = int((u[-1] * p).round()) % p

iv = enc_flag[:16]
ct = enc_flag[16:]
key = hashlib.sha256(str(alpha).encode()).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
print(flag)

# L3AK{hnp_BBB_cvp_4_the_w1n}

Ngoài cách sử dụng CVP để giải quyết thì mình còn code thêm cách sử dụng SVP. Chi tiết cách build ma trận:

alt text

Code sử dụng (Shortest Vector Problem):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

from pwn import *
import hashlib
import base64
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import getPrime
from secrets import randbelow
from sage.all import *

io = remote('34.59.96.214', 11000, level='debug')
# io = process(['python3', '/home/team/CodePy/L3akCTF/Magical Oracle/chal.py'], level='debug')

# Show parameters
io.sendlineafter(b'Choose option: ', b'3')
io.recvline()
p = int(io.recvline().decode().strip().split('=')[-1])
n = int(io.recvline().decode().strip().split('=')[-1])
k = int(io.recvline().decode().strip().split('=')[-1])
d = int(io.recvline().decode().strip().split('=')[-1])


# Show encrypted flag
io.sendlineafter(b'Choose option: ', b'2')
io.recvline()
enc_flag = io.recvline().decode().strip().split(': ')[-1]
enc_flag = base64.b64decode(enc_flag)

# Get query
ts, zs = [], []
for _ in range(d):
    io.sendlineafter(b'Choose option: ', b'1')
    io.recvline()
    query = io.recvline().decode().strip().split(': ')[-1]
    query = query.split(', ')
    t = int(query[0].split('=')[-1])
    leak = int(query[1].split('=')[-1])
    ts.append(t)
    zs.append(leak)

B = p >> k + 1
M = Matrix(QQ, d + 2, d + 2)
for i in range(d):
    M[i, i] = QQ(p)
    M[d, i] = QQ(ts[i])
    M[d + 1, i] = QQ(zs[i])
M[d, d] = QQ(B) / QQ(p)
M[d + 1, d + 1] = QQ(B)

M = M.LLL()
for row in M:
    if row[-1] == B:
        alpha = int((-row[-2] * QQ(p) / QQ(B)).round()) % p
    if row[-1] == -B:
        alpha = int((row[-2] * QQ(p) / QQ(B)).round()) % p

iv = enc_flag[:16]
ct = enc_flag[16:]
key = hashlib.sha256(str(alpha).encode()).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
print(flag)

# L3AK{hnp_BBB_cvp_4_the_w1n}

Continue …

CTF Write-up
Lattice ECC
This post is licensed under CC BY 4.0 by the author.