ASCIS 2023

Đây là write-up nhỏ cho 1 bài crypto trong svattt vừa qua của mình

Challenge

from Crypto.Random.random import getrandbits
from Crypto.Util.number import bytes_to_long

nbits = 128
while True:
    mul = getrandbits(nbits)
    add = getrandbits(nbits)
    modulus = getrandbits(nbits)
    if mul < modulus and add < modulus:
        break

def gen_num(bits):
    truncate = bits
    seed = getrandbits(511)
    gen_num = 41

    xx = []
    yy = [] 
    
    for _ in range(gen_num):
        seed = (mul * seed + add) % modulus
        xx.append(seed)
        yy.append(seed >> (nbits-truncate))
    return xx, yy

_, ee = gen_num(18)
_, ff = gen_num(20)

a = ee[-1]
b = ff[-1]
c = getrandbits(1024)
p = next_prime(a * c + getrandbits(512))
q = next_prime(b * c + getrandbits(512))

flag = '<REDACTED>'
N = p * q
e = 65537
m = bytes_to_long(flag.encode())
enc = pow(m, e, N)

print(f'enc = {enc}')
print(f'N = {N}')
print(f'ee = {ee[:-1]}')
print(f'ff = {ff[:-1]}')
print(f'a = {mul}')
print(f'c = {add}')
print(f'm = {modulus}')

Overview

Đây là một bài RSA, vuln nằm ở cách đề bài gen 2 số $p$ và $q$, cụ thể là: $p = ac + d_1$ và $q = bc + d_2$. Trong đó:

$a$ và $b$ lần lượt là $18$ bits và $20$ bits đầu tiên của state cuối cùng của LCG

$c, d_1, d_2$ là các số 1024 bits, 512 bits và 512 bits

Chúng ta có $enc$ là ciphertext, $N = pq$, $ee$ là dãy 18 bit đầu tiên của các state trong lần gen số đầu tiên từ LCG (trừ state cuối cùng chính là a), tương tự với $ff$ nhưng là 20 bit đầu tiên, mul, add và modulus là các tham số của LCG

Solution

Step 1: Break truncated LCG

Note: mình sẽ gọi các biến số như script print ra output (a là mul, vv…) để tránh tên dài dòng

Từ truncated LCG, chúng ta có thể tìm lại state như sau:

Gọi $x_i$ là state thứ $i$, ta có $x_{i + 1} \equiv ax_i + c \pmod{m}$ $(i \geq0)$. Ví dụ $i=1$ ta sẽ có

\[\begin{aligned} x_2 &\equiv ax_1 + c &\pmod{m}\\ &\equiv a(ax_0 + c) + c &\pmod{m}\\ &\equiv a^2x_0 + ac + c &\pmod{m} \end{aligned}\]

Nhận thấy phần $ac + c$ chính là output $state_1$ của LCG nếu như $state_0 = c$.

Vậy ta hoàn toàn có thể loại bỏ đi phần hằng số, để thu được dãy $x’$ có mối quan hệ $x’_{i+1} \equiv ax’_i \pmod{m}$.

Ta dễ dàng nhận thấy $x’_i \equiv a^i x’_0 \pmod{m}$ tức $a^i x’_0 - x’_i \equiv 0 \pmod{m}$.

Mục tiêu của ta sẽ là đi tìm $x_{40}$ sau đó lấy $18$ bit đầu tiên, đó chính là $ee_{40}$ mà ta cần tìm.

Ta xét một lattice $L$ được tạo ra bởi basis $\textbf{B}$ (đồng thời ta cũng thực hiện LLL trên $\textbf{B}$) như sau:

\[\begin{aligned} \textbf{B} = \left(\begin{array}{cc} m & 0 & 0 & \dots & 0 \\ a & -1 & 0 & \dots & 0 \\ a^2 & 0 & -1 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a^{39} & 0 & 0 & \dots & -1 \\ \end{array}\right) \end{aligned}\]

Đồng thời ta xét một vector \(\textbf{x'} = (x'_0, x'_1, \dots, x'_{39})\)

Ta có:

\[\textbf{B} \textbf{x'} = (mx'_0, ax'_0 - x'_1, \dots, a^{39}x'_0 - x'_{39}) = \textbf{vm}\equiv 0 \pmod{m}\]

Trong đó $\textbf{v}$ là một vector nào đấy. Nhớ lại rằng đề bài cho chúng ta các $ee_i$ chính là $18$ bit đầu của các $x_i$, vậy ta có $x_i = 2^{128 - 18}ee_i + y_i$ hay nếu ta loại bỏ đi phần hằng số ở hai vế ta thu được $x’_i = 2^{128 - 18}ee_i + y’_i$, viết lại theo dạng vector ta có $\textbf{x’} = 2^{128 - 18}\textbf{ee} + \textbf{y’}$. Từ đây:

\[\begin{aligned} \textbf{B} \textbf{x'} &= \textbf{B}(2^{128-18}\textbf{ee} + \textbf{y'}) \\ &= \textbf{B}2^{128-18}\textbf{ee} + \textbf{B}\textbf{y'} \\ &= \textbf{vm} \\ \Rightarrow \textbf{By'} &= \textbf{vm} - \textbf{B}2^{128-18}\textbf{ee} \end{aligned}\]

Do $\textbf{By’}$ bé $\Rightarrow$ $\textbf{vm} - \textbf{B}2^{128-18}\textbf{ee}$ cũng bé, vậy ta có thể cho $v_i = \bigg\lfloor\dfrac{\textbf{B}2^{128-18}ee_i}{m}\bigg\rceil$. Từ đây ta có thể solve tìm lại $\textbf{y’}$ và tìm lại $\textbf{x} = 2^{128 - 18}\textbf{ee} + \textbf{y’} + \textbf{const}$ với $\textbf{const}$ là phần hằng số mà ta đã trừ để tìm $\textbf{x’}$ từ $\textbf{x}$. Vậy là ta đã tìm được $(x_0, x_1, \dots, x_{39})$, Ta dễ dàng tìm được $ee_{40}$. Ta làm tương tự với $ff_{40}$, điều khác biệt duy nhất là thay vì $18$ bits thì ta làm $20$ bits.

def recover_state(y, bits, trunc, a, c, m):
    k = len(y) 
    M = [[m] + [0] * (k - 1)]
    M += [[a^i] + [0] * (i - 1) + [-1] + [0] * (k - 1 - i) for i in range(1, k)]
    M = matrix(ZZ, M)
    B = M.LLL()

    add = c
    for i in range(k):
        y[i] = (y[i] << (bits - trunc)) - add
        add = (a * add + c) % m 
    
    y = vector(ZZ, y)

    T1 = B * y 
    T2 = vector([round(RR(x) / m) * m - x for x in T1])

    add = c 
    x = list(B.solve_right(T2))

    for i, z in enumerate(x):
        x[i] = ZZ(y[i] + z + add)
        add = (a * add + c) % m 

    return x 

lcg1 = recover_state(ee, nbits, 18, a, c, m)
lcg2 = recover_state(ff, nbits, 20, a, c, m)

ee40 = ((a * lcg1[-1] + c) % m) >> (nbits - 18)  
ff40 = ((a * lcg2[-1] + c) % m) >> (nbits - 20) 

Step 2: Tìm $p$ và $q$

Đây là lúc não mình ngừng hoạt động và thế là mình đã không solve được bài này lúc thi :(

Ý tưởng để tìm $p$ và $q$ như sau:

Ta có $p = ee_{40}c + d_1$ và $q = ff_{40}c + d_2$. Ta dễ dàng thấy được $ff_{40}p \approx ee_{40}q$ (ít nhất là đúng được hơn $1024$ bits). Từ đây ta có

\[\begin{aligned} ff_{40}p^2 &\approx ee_{40}N \\ \\ p^2 &\approx \dfrac{ee_{40}N}{ff_{40}}\\ \\ p &\approx \bigg\lfloor{\sqrt{\dfrac{ee_{40}N}{ff_{40}}}}\bigg\rceil \\ \end{aligned}\]

Hmm… liệu rằng cái này sẽ đúng được bao nhiêu bits nhỉ? Hãy cùng mình gen số test nhé

from sympy import sqrt 

test_p = int(sqrt(N * a // b))

print(f"Real p: {p}")

print(f"Test p: {test_p}")

print(f"Error: {(p - test_p).bit_length()}")

(sage) elita@tehoang:/mnt/d/CTF/2023/ASCISQuals$ python3 testchall2.sage.py
Real p: 17288797107137857954337722293793042596729237196867565238391344955858651917652025365344505335491140708298160953339354317475316795116413867790503578862574619739130746127695891901466640981104833198915489240964392845014351397642738560273922781066499822265015446922494055756321507939778949079907799443470654725917351033
Test p: 17288797107137857954337722293793042596729237196867565238391344955858651917652025365344505335491140708298160953339354317475316795116413867790503578862574619739130070065346001983778907474714702655095504543128598073226082257715626472878481071547590364691526398449687047064468475656310637815279399654493410472517779759
Error: 508
(sage) elita@tehoang:/mnt/d/CTF/2023/ASCISQuals$ python3 testchall2.sage.py
Real p: 3470180433422260214015965781769334259695303840679331631802932796225990512313145377100336151891559883495672965915422754699790143118187658058812855193365384674470020341683606609236050196393871259495526686001867294626831230009388804221892796093736590587069780325309790475906173292803174154725624293842908599830109023
Test p: 3470180433422260214015965781769334259695303840679331631802932796225990512313145377100336151891559883495672965915422754699790143118187658058812855193365384674467714203502033916988938927690186374575063737866005435099817111719352127492549113135707211349319968311662813563500128607833805357995797946850739611128948566
Error: 510
(sage) elita@tehoang:/mnt/d/CTF/2023/ASCISQuals$ python3 testchall2.sage.py
Real p: 15145430561250893683271533135419282315697586814345184768592577422300025803960792632645909175107004905793953688090906740296219754246247695069423587500832381551419793787314527121738963788632550223185515795192408504188718427648388056475154809559307185855781796795765206914018962835303278206333236434882699208972223103
Test p: 15145430561250893683271533135419282315697586814345184768592577422300025803960792632645909175107004905793953688090906740296219754246247695069423587500832381551419796686063857330771092673231032870661524852962270921140540906149172608373621475305952510526393288278712147722047343979686815536093424689045272573423246675
Error: 500
(sage) elita@tehoang:/mnt/d/CTF/2023/ASCISQuals$ python3 testchall2.sage.py
Real p: 1111911821841105821886181307092596857438195715041452539191463389096299300641647993558052843335165644055857687482706107671844354250039569468144738360176451589933342773565074727483504231783934866950569174195980700073051634743044309859880954692898722253511582979677887011874142417549610876237080769805938502630572031
Test p: 1111911821841105821886181307092596857438195715041452539191463389096299300641647993558052843335165644055857687482706107671844354250039569468144738360176451589933235153279233017467588052716465382172449745268569283965149532999837785552118879869072329786622664885005321793420023112337515667802958321624536596403740202
Error: 506

Bằng một cách nào đó nó đúng hơn $1/2$ số bits của $p$, lúc này ta có thể làm tương tự với $q$, vậy là ta đã tìm được $1/2$ số bits của N, rồi ta dùng coppersmith là có thể tìm lại được $p$ và $q$ lmaoooooooo

Ta xét phương trình $f(x, y) = (p’ + x) (q’ + y)$ với $p’$ và $q’$ lần lượt là $p$, $q$ mà ta xấp xỉ được từ cách trên, $x$, $y$ sẽ dao động từ $500$ tới $520$ bits

Vì là có tận 2 biến số nên mình không thể sử dụng small_roots của sage mà mình sẽ sử dụng coppersmith của defund

from sympy import sqrt

PR.<x, y> = PolynomialRing(Zmod(N))

testp = int(sqrt(ee40 * N / ff40)) 
testq = int(sqrt(ff40 * N / ee40))

f = (testp + x) * (testq + y)
bounds = [2^515, 2^515]
roots = small_roots(f, bounds, m = 4)

if roots != []:
    p = testp + roots[0][0]
    q = testq + roots[0][-1]
    
assert N % p == 0 

Step 3: Lấy flag thui lmao

e = 0x10001 
d = pow(e, -1, (p-1) * (q-1))

print(long_to_bytes(pow(enc, d, N)).decode())

ASCIS{S0rry_1_caNt_make_a_b3tt3r_Crypt0_ch4ll}