<h1 style="text-align:center;">Pseudo Random Number Generator</h1>
Trong mật mã hiện đại, bộ sinh số giả ngẫu nhiên (**Pseudo-Random Number Generators – PRNGs**) có vai trò vô cùng quan trọng, nó có thể tạo khóa bí mật, sinh nonce, hoặc xây dựng hệ thống bảo mật dựa trên entropy. Tuy nhiên, không phải mọi PRNG đều được thiết kế an toàn – một số tồn tại lỗ hổng nghiêm trọng, khiến cho attacker có thể dự đoán hoặc khôi phục toàn bộ **trạng thái** (state) bên trong chỉ từ một vài đầu ra.
Trong blog này, ta sẽ tập trung tìm hiểu ba loại PRNG tiêu biểu: **Linear Congruential Generator** (LCG), **Linear Feedback Shift Register** (LFSR), và **Dual_EC_DRBG** – một PRNG từng được chuẩn hóa nhưng sau đó bị cáo buộc có "backdoor". Ta cũng sẽ đi sâu vào một số kỹ thuật khôi phục **state** từ đầu ra, bao gồm:
> **LCG**: Parameter recovery, state recovery và state recovery từ truncated outputs.
**LFSR**: Tìm hiểu thuật toán **Berlekamp-Massey**.
**Dual_EC_DRBG**: Là ví dụ điển hình về một PRNG tưởng như an toàn nhưng lại tiềm ẩn nguy cơ nghiêm trọng.
Song song với lý thuyết, ta cũng sẽ làm một số Challenge liên quan đến các thuật toán đã học ở trên trong phần **Misc** của **CryptoHack** để củng cố kiến thức.
# Linear Congruential Generator (LCG)
## Nguyên lý hoạt động
**Linear Congruential Generator (LCG)** là một trong những bộ sinh số giả ngẫu nhiên (**PRNG**) nổi tiếng nhất, lý do là vì nó đơn giản, không yêu cầu quá nhiều nền tảng toán học, dễ hiểu dễ triển khai và đặc biệt là chạy rất nhanh khi modulus $m$ là dạng $2^k$.
**LCG** hoạt động dựa trên công thức đệ quy tuyến tính sau:
$$X_{n+1} = a.X_n + c \mod m$$
> Trong đó:
- $X_n$ là số ngẫu nhiên giả được sinh ra ở bước thứ $n$
- $m$ là modulus.
- $a$ là hệ số nhân.
- $c$ là hệ số cộng.
- $X_0$ sẽ là **seed** hay giá trị khởi đầu.
Để tính giá trí tiếp theo là $X_{n+2}$, ta sẽ gán $X_n = X_{n+1}$ và thực hiện lại công thức trên:
$$X_{n+2} = a.X_{n+1} + c \mod m$$
> Ta cứ lặp đi lặp lại công thức trên là có thể tính được một chuỗi các số nhìn có vẻ ngẫu nhiên nhưng lại hoàn toàn có thể xác định được.
++**Ví dụ:**++ Vì LCG khá đơn giản nên ta có thể minh họa trong **python** như sau:
```python=
from random import randint
class LCG:
def __init__(self, seed, a, c, m):
self.state = seed
self.a = a
self.c = c
self.m = m
def next(self):
self.state = (self.a * self.state + self.c) % self.m
return self.state
if __name__ == "__main__":
a = 1664525
c = 1013904223
m = 2**32
seed = randint(0, m)
lcg = LCG(seed, a, c, m)
print("10 số ngẫu nhiên từ LCG:")
for _ in range(10):
print(lcg.next())
```
Ta sẽ được một dãy số mà nhìn thoạt ra không có bất kỳ quy luật nào cả:
```p!
625251826 424344745 308944372 1620422851 193044294 89124333 2523887208 3647825575 3828528090 2532634993
```
---
Bằng cách chọn seed ($X_0$) và các tham số $(a,c,m)$ phù hợp, LCG có thể sinh ra một dãy số trông có vẻ ngẫu nhiên và có **chu kỳ** dài với bất kỳ seed nào. Điều kiện đủ để LCG đạt được chu kỳ tối đa (tức là dãy sinh ra lặp lại sau $m$ bước) là:
- $\text{GCD}(c, m) = 1$
- $a-1$ chia hết cho các ước nguyên tố của $m$.
- $m \equiv a-1 \equiv 0 \pmod 4$
> Nếu không thỏa mãn điều kiện trên thì dãy sinh ra sẽ bị lặp lại trước bước thứ $m$.
++**Ví dụ:**++ Chọn $(a,c,m) = (8, 12,21)$, ta thấy rằng $\text{GCD}(12, 21) \neq 1$, $m$ và $a-1$ không chia hết cho $4$, và $a-1$ chỉ chia hết cho ước $7$ của $m$, chứng tỏ chu kỳ của LCG sẽ không thể nào bằng $m$ được:
```python=
from random import randint
class LCG:
def __init__(self, seed, a, c, m):
self.state = seed
self.a = a
self.c = c
self.m = m
def next(self):
self.state = (self.a * self.state + self.c) % self.m
return self.state
if __name__ == "__main__":
a = 8
c = 12
m = 21
seed = randint(0, m)
lcg = LCG(seed, a, c, m)
for _ in range(21):
print(lcg.next(), end=" ")
```
Ta được dãy số sau:
```python!
15 6 18 9 0 12 3 15 6 18 9 0 12 3 15 6 18 9 0 12 3
```
> Có thể thấy rằng dãy số do LCG sinh ra chỉ có chu kỳ là $7$ `(15 6 18 9 0 12 3)`.
---
## Attack
LCG rất đơn giản, mà đơn giản nên sinh ra nhiều hạn chế, chỉ cần một vài **output** liên tiếp bị lộ, Hacker có thể tính được state tiếp theo và dự đoán tương lai một cách chính xác, thậm chí có thể khôi phục state trước đó, vô cùng nguy hiểm. Vì thế trong thực tế người ta sẽ không để lộ **output** (state) và các **tham số** (parameter), nếu có tiết lộ thì cũng chỉ để lộ **msb** hoặc **lsb** thôi. Sau đây chúng ta sẽ đi tìm hiểu một số cách để khôi phục tham số **(a,c,m)** và **state** khi được cung cấp đủ output nhé, nội dung được mình tham khảo trong ([**link1**](https://msm.lt/posts/cracking-rngs-lcgs/), [**link2**](https://hackmd.io/@nhatviet/SkUT_IlkA#shuffle), [**link3**](https://crypto.stackexchange.com/questions/87220/cryptographically-secure-linear-congruential-generator-is-it-possible)).
### khôi phục state khi đã có (a,c,m)
Khi ta được cung cấp đầy đủ tham số $(a,c,m)$ thì việc tính state kế tiếp hay khôi phục state trước đó là vô cùng đơn giản.
Giả sử ta đã có $(a,c,m)$ và $X_0$, để tính $X_1$ ta chỉ cần áp dụng công thức của LCG thôi:
$$X_{n+1} = a.X_n+c \mod m$$
Còn khi có $(a,c,m)$ và $X_{n+1}$, nếu $\text{GCD}(a,m)=1$ thì công thức để khôi phục $X_n$ là:
$$X_n = \frac{X_{n+1}-c}{a} \mod m$$
> Nhưng đối với các bài **CTF** thì thường họ sẽ giấu đi các tham số như $a$ và $c$ và thậm chí $(a,c,m)$, vì vậy ta phải biết cách khôi phục chúng trong các trường hợp nhất định.
---
### Khôi phục tham số (a,c,m) trong các trường hợp cụ thể
#### ++Trường hợp 1:++ Khôi phục c khi đã có (a,m) và 2 outputs liên tiếp.
Đây là trường hợp đơn giản nhất khi các giá trị quan trọng đã được biết, ta biểu diễn công thức của LCG như sau:
$$X_{n+1} = a.X_n+c \mod m$$
Cô lập $c$, ta được công thức của $c$ là:
$$c = X_{n+1}-a.X_{n} \mod m$$
---
#### ++Trường hợp 2:++ Khôi phục a và c khi đã có m và 3 outputs liên tiếp.
Giả sử ta có $3$ output liên tiếp là $X_n, X_{n+1}, X_{n+2}$. Khi này ta có hai phương trình modulo:
$$
\begin{align}
X_{n+1} &\equiv a.X_n + c \pmod m \hspace{5mm} (1)\\
X_{n+2} &\equiv a.X_{n+1} + c \pmod m \hspace{5mm} (2)
\end{align}
$$
Lấy $(2)-(1)$ ta được:
$$X_{n+2}-X_{n+1} \equiv a.(X_{n+1}-X_n) \mod m$$
$$\Leftrightarrow a \equiv \frac{X_{n+2}-X_{n+1}}{X_{n+1}-X_n} \pmod m$$
Có $a$, ta thay vào công thức $(1)$ là có được $c$
$$c \equiv X_{n+1}-a.X_{n} \pmod m$$
---
#### ++Trường hợp 3:++ Khôi phục a, c và m khi có ≥4 outputs liên tiếp
Khi cả $3$ tham số đều bị giấu thì ta cần tìm modulus $m$ đầu tiên, tối thiểu cần $4$ output liên tiếp và để chắc chắn thì cần $5$ output trở lên, ta thực hiện như sau:
Đặt $4$ outputs liên tiếp là $X_n,X_{n+1},X_{n+2},X_{n+3}$, ta có 3 phương trình modulo như sau:
$$
\begin{align}
X_{n+1} &\equiv a.X_n + c &\pmod m\\
X_{n+2} &\equiv a.X_{n+1} + c &\pmod m \\
X_{n+3} &\equiv a.X_{n+2} + c &\pmod m\\
\end{align}
$$
Đặt:
$$
\begin{align}
T_o &\equiv X_{n+1} - X_{n} &\pmod m \\
T_1 &\equiv X_{n+2}-X_{n+1} \equiv a.(X_{n+1}-X_n) \equiv a.T_0 &\pmod m \\
T_2 &\equiv X_{n+3} - X_{n+2} \equiv a.(X_{n+2}-X_{n+1}) \equiv a.T_1 &\pmod m
\end{align}
$$
Lấy $T_2$ chia $T_1$ ta có:
$$\frac{T_2}{T_1} \equiv \frac{T_1}{T_0} \pmod m$$
$$
\begin{align}
\Leftrightarrow T_1^2 - T_2.T_0 &\equiv 0 \pmod m \\
\Rightarrow T_1^2 - T_2.T_0 &= k_1.m
\end{align}
$$
Nếu ta đủ may mắn thì $k_1$ sẽ bằng $1$ và ta sẽ có được giá trị $m$. Nhưng thực tế điều này rất rất khó xảy ra. Thay vào đó chỉ cần có thêm **một** output nữa thôi, xác suất tìm được $m$ sẽ tăng lên thành $60\%$, ta đặt output tiếp theo là $X_{n+4}$, khi này ta có:
$$X_{n+4} \equiv a.X_{n+3} + c \pmod m $$
Đặt $T_3 \equiv X_{n+4}-X_{n+3} \equiv a.(X_{n+3} - X_{n+2}) \equiv a.T_2 \pmod m$
Lấy $T_3$ chia $T_2$ ta có:
$$\frac{T_3}{T_2} \equiv \frac{T_2}{T_1} \pmod m$$
$$
\begin{align}
\Leftrightarrow T_2^2 - T_3.T_1 &\equiv 0 \pmod m \\
\Rightarrow T_2^2 - T_3.T_1 &= k_2.m
\end{align}
$$
Bây giờ chỉ cần tính $\text{GCD}(T_2^2 - T_3.T_1;\hspace{2mm}T_1^2 - T_2.T_0)$ là có được $\text{GCD}{(k_1,k_2)}.m$ rồi.
> Theo định lý [**dirichlet**](https://vi.wikipedia.org/wiki/Số_nguyên_tố_cùng_nhau#Xác_suất_hai_số_nguyên_tố_cùng_nhau) thì xác suất để hai số ngẫu nhiên nguyên tố với nhau là $\frac{6}{\pi^2} \approx 0.608 \approx 61\%$
Vậy sẽ có xác suất $61\%$ để $\text{GCD}{(k_1,k_2)} =1$ và ta sẽ tìm được $m$ từ $5$ output.
Còn khi tăng lên thành $6$ output thì sao? Đặt output thứ $6$ là $X_{n+5}$, ta có:
$$X_{n+5} \equiv a.X_{n+4} + c \pmod m$$
Đặt $T_4 \equiv X_{n+5}-X_{n+4} \equiv a.(X_{n+4} - X_{n+3}) \equiv a.T_3 \pmod m$
Lấy $T_4$ chia $T_3$ ta có:
$$\frac{T_4}{T_3} \equiv \frac{T_3}{T_2} \pmod m$$
$$
\begin{align}
\Leftrightarrow T_3^2 - T_4.T_2 &\equiv 0 \pmod m \\
\Rightarrow T_3^2 - T_4.T_2 &= k_3.m
\end{align}
$$
Tính $\text{GCD}(T_2^2 - T_3.T_1;\hspace{2mm} T_1^2 - T_2.T_0;\hspace{2mm} T_3^2 - T_4.T_2)$ là có được $\text{GCD}{(k_1,k_2,k_3)}.m$, khi này xác suất tìm được $m$ lên đến $83\%$.
> Còn với $7$ output xác suất tìm được $m$ là $92\%$, gần như chắc chắn sẽ tìm được $m$.
Có modulus $m$, ta tìm lại $a,c$ tương tự như trường hợp $2$:
$$a \equiv \frac{X_{n+2}-X_{n+1}}{X_{n+1}-X_n} \pmod m$$
$$c \equiv X_{n+1}-a.X_{n} \pmod m$$
Ta có thể xây dựng một hàm `attack` khôi phục lại tham số $(a,c,m)$ trong python như sau:
```python=
https://github.com/jvdsn/crypto-attacks/blob/master/attacks/lcg/parameter_recovery.py
from math import gcd
from sage.all import Zmod
def attack(y, m=None, a=None, c=None):
if m is None:
assert len(y) >= 4, "At least 4 outputs are required to recover the modulus"
for i in range(len(y) - 3):
d0 = y[i + 1] - y[i]
d1 = y[i + 2] - y[i + 1]
d2 = y[i + 3] - y[i + 2]
g = d2 * d0 - d1 * d1
m = g if m is None else gcd(g, m)
gf = Zmod(m)
if a is None:
assert len(y) >= 3, "At least 3 outputs are required to recover the multiplier"
x0 = gf(y[0])
x1 = gf(y[1])
x2 = gf(y[2])
a = int((x2 - x1) / (x1 - x0))
if c is None:
assert len(y) >= 2, "At least 2 outputs are required to recover the multiplier"
x0 = gf(y[0])
x1 = gf(y[1])
c = int(x1 - a * x0)
return m, a, c
```
Thử nghiệm với `a = 1664525, c = 1013904223, m = 2^32` và $7$ output liên tiếp là:
```python
y = [1233263650, 2391928089, 3317756836, 4082281139, 857731190, 174271837, 3047182104]
```
Ta được kết quả là:
```python=
print(attack(y[:4])) # (28668253865771008, 18776750911219213, 23424580847596383)
print(attack(y[:5])) # (4294967296, 1664525, 1013904223)
print(attack(y[:6])) # (4294967296, 1664525, 1013904223)
print(attack(y[:7])) # (4294967296, 1664525, 1013904223)
```
> Chỉ cần cung cấp $\geq5$ ouput liên tiếp thì xác suất recover lại đúng $(a,c,m)$ là rất cao rồi.
---
# Linear Feedback Shift Register (LFSR)
**LFSR** (Linear Feedback Shift Register) là một loại **mạch logic** vật lí hoặc một **thuật toán** đơn giản được sử dụng để sinh các chuỗi bit giả ngẫu nhiên. Nó hoạt động dựa trên một thanh ghi dịch (**shift register**) kết hợp với một hàm phản hồi tuyến tính (**linear feedback**), thường là phép **XOR** của một số bit tại vị trí xác định, các vị trí đó được gọi là **Taps**.
Mỗi lần cập nhật, LFSR dịch toàn bộ bit trong thanh ghi sang **trái** (hoặc phải), và bit mới được thêm vào là kết quả của phép **XOR** giữa các bit tại các vị trí các taps.
LFSR được sử dụng trong nhiều lĩnh vực như mã hóa dòng (stream cipher), mô phỏng phần cứng, phát hiện lỗi và đôi lúc cũng xuất hiện trong các bài CTF Crypto.
Tuy nhiên, do tính tuyến tính của hàm phản hồi, LFSR có thể bị phá vỡ dễ dàng bằng các kỹ thuật như **Berlekamp-Massey** nếu attacker có đủ số bit đầu ra. Do đó, LFSR không còn được xem là an toàn trong mật mã hiện đại, nhưng vẫn là công cụ tuyệt vời để giảng dạy và làm ví dụ cho **PRNG**.
## Nguyên lý hoạt động
++**Thuật toán**++: Gọi trạng thái ban đầu là một dãy bit dạng $s=[s_0,s_1,s_2,...,s_{n-1}]$ và Tap của ta là các vị trí $t_1,t_2,...,t_k$, giả sử thanh ghi hoạt động bằng cách dịch sang **bên trái** thì nguyên lý tạo bit ngẫu nhiên diễn ra như sau:
++**Bước 1**++ (Lấy bit để xuất ra): Vì thanh ghi dịch sang bên trái nên ta đặt bit đầu tiên ($s[0]$) làm bit đầu ra.
++**Bước 2**++ (Tính bit mới): Ta tiến hành tính bit mới bằng cách **XOR** các bit ở vị trí **Tap**, tức:
$$s_{new} = s_{t_1} \oplus s_{t_2} \oplus ...\oplus s_{t_k}$$
++**Bước 3**++ (Dịch bit): Ta dịch toàn bộ thanh ghi sang bên **trái**, khi này $s[0]$ sẽ bị văng ra khỏi thanh ghi và ta sử dụng nó làm bit ngẫu nhiên. Khi này bit cuối cùng của thanh ghi sẽ bị trống, ta tiến hành thêm $s_{new}$ vào cuối để lắp đầy thanh ghi. Sau đó ta lặp lại **bước 1** để bất đầu quá trình tạo bit mới.
> ++**Ví dụ:**++ Trạng thái ban đầu của thanh ghi là **s=[1,0,0,1,0,1,0]**, đặt các Taps nằm ở vị trí **t=[0,1,2,6]**. Giả sử thanh ghi hoạt động bằng cách dịch sang trái, ta có thể mô phỏng nó như sau:
*Lần 1:* $s[0] = 1, s_{new} = s[0] \oplus s[1] \oplus s[2] \oplus s[6] = 1\oplus0\oplus0\oplus0 = 1$
nên sau khi dịch sang trái, ta được kết quả là: **s=[0,0,1,0,1,0,1]**.
*Lần 2:* $s[0] = 0, s_{new} = s[0] \oplus s[1] \oplus s[2] \oplus s[6] = 0\oplus0\oplus1\oplus1 = 0$
Sau khi dịch trái ta được **s=[0,1,0,1,0,1,0]**.
*Lần 3:* $s[0] = 0, s_{new} = s[0] \oplus s[1] \oplus s[2] \oplus s[6] = 0\oplus1\oplus0\oplus0 = 1$
Sau khi dịch trái ta được **s=[1,0,1,0,1,0,1]**.
Vậy sau $3$ vòng lặp thì LFSR tạo được $3$ bit là `100`.
++**Code**++:
```python=
class LFSR:
def __init__(self, seed_bits: list[int], taps: list[int]):
self.state = seed_bits[:]
self.taps = taps[:]
def clock(self) -> int:
new_bit = 0
for t in self.taps:
new_bit ^= self.state[t]
output_bit = self.state[0]
self.state = self.state[1:] + [new_bit]
return output_bit
def stream(self, length: int) -> list[int]:
return [self.clock() for _ in range(length)]
RNG = LFSR(seed_bits=[1,0,0,1,0,1,0], taps=[0,1,2,6])
print(RNG.stream(3))
# [1, 0, 0]
```
++**Định nghĩa**++ (Feedback polynomial): là cách biểu diễn toán học của quá trình Feedback trong LFSR, hay hiểu đơn giản hơn nó là đa thức biểu diễn vị trí của các Taps.
>++**Biểu diễn**++: Giả sử thanh ghi có chiều dài $n$, Tap nằm ở vị trí $[t_1,t_2,...t_k]$ thì đa thức của ta sẽ có dạng:
$$f = x^n + x^{t_k} +...+ x^{t_2} + x^{t_1} + 1$$
$x^n$ và $1$ sẽ luôn có mặt vì chúng đại diện cho bit input và bit output của LFSR.
❕Nếu Feedback polynomial là **Primitive Polynomial** tức đa thức không thể bị phân tích (factored) thì chu kỳ của **LFSR** sẽ có giá trị lớn nhất là $(2^n-1)$ với $n$ là chiều dài của thanh ghi.
++**Định nghĩa**++ (Chu kỳ): Chu kỳ của một LFSR là độ dài của dãy bit được sinh ra trước khi nó bắt đầu lặp lại chính nó. Chu kỳ của một LFSR phụ thuộc rất lớn vào việc chọn vị trí các taps, ta có một bảng để tham khảo như sau:
> Có thể nói Feedback polynomial là trái tim của LFSR, nó điều khiển cách LFSR hoạt động và kiểm soát chu kỳ, vì thế nó luôn được **giấu kín** vì nếu bị tính toán được thì Hacker có thể tính được toàn bộ dãy LFSR — cả về sau lẫn ngược về trước.
---
## Thuật toán Berlekamp-Massey
>**Berlekamp-Massey** là một thuật toán giúp tìm lại công thức của **feedback polynomial** từ một dãy bit đầu ra.
++**Code**++:
```python=
# https://github.com/thewhiteninja/lfsr-berlekamp-massey/blob/master/berlekamp_massey.py
class BerlekampMassey:
def __init__(self, sequence):
n = len(sequence)
s = sequence # list các giá trị nguyên 0 và 1
k = 0
for k in range(n):
if s[k] == 1:
break
self._f = {k + 1, 0}
self._l = k + 1
g = {0}
a = k
b = 0
for n in range(k + 1, n):
d = 0
for item in self._f:
d ^= s[item + n - self._l]
if d == 0:
b += 1
else:
if 2 * self._l > n:
self._f ^= set([a - b + item for item in g])
b += 1
else:
temp = self._f.copy()
self._f = set([b - a + item for item in self._f]) ^ g
self._l = n + 1 - self._l
g = temp
a = b
b = n - self._l + 1
def _get_polynomial_string(self):
result = ''
lis = sorted(self._f, reverse=True)
for i in lis:
if i == 0:
result += '1'
else:
result += 'x^%s' % str(i)
if i != lis[-1]:
result += ' + '
return result
def get_polynomial(self):
return list(self._f)
def get_polynomial_degree(self):
return self._l
def __str__(self):
return self._get_polynomial_string()
def __repr__(self):
return "<%s polynomial=%s>" % (self.__class__.__name__, self._get_polynomial_string())
```
```p!
Thử nghiệm với taps = [0,1,2,6], seed_bits=[1,0,0,1,0,1,0] và dãy bit
[1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
```
Ta truyền vào tham số như sau:
```python=
y = [1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
breaker = BerlekampMassey(sequence=y)
print(breaker._get_polynomial_string())
```
Được **Feednack Polynomial** là `x^7 + x^6 + x^2 + x^1 + 1` tương ứng với `Taps = [0,1,2,6]` và `n=7`.
# Dual_EC_DRBG
**Dual Elliptic Curve Deterministic Random Bit Generator** (Dual EC DRBG) là một bộ sinh số ngẫu nhiên được thiết kế dựa trên phép **nhân vô hướng** trên đường cong elliptic. Khác với các PRNG truyền thống như LCG hay LFSR, **Dual EC DRBG** khai thác tính **một chiều** của phép nhân vô hướng để sinh ra các chuỗi bit ngẫu nhiên. Điều này khiến nó trở thành một trong những PRNG "mang dáng dấp hiện đại" đầu tiên được tiêu chuẩn hóa bởi **NIST** (SP 800-90A).
Nhưng không lâu sau đó thì nó bị chứng minh là chứa **backdoor** (tức nó cho phép kẻ thứ ba can thiệp vào dữ liệu nhạy cảm mà người dùng không cho phép). Người ta cho rằng mục đích mà **Dual_EC_DRBG** được tạo ra là để cài cắm backdoor vào các phần mềm mà người dùng thường dùng nhằm theo dõi và đánh cắp thông tin một cách bí mật. Đến năm $2013$ thì Dual EC DRBG hưởng dương $7$ tuổi (2006-2013) vì dính quá nhiều sự chỉ trích buộc NIST phải rút nó khỏi tiêu chuẩn. Sau đây chúng ta sẽ tìm hiểu qua thuật toán PRNG tai tiếng nhất trong giới Cryptography nhé.
## Nguyên lý hoạt động
Sử dụng đường cong tiêu chuẩn **P-256**, đầu tiên ta khởi tạo một điểm sinh $P$ cố định, một điểm $Q$ cố định, một giá trị $s$ làm $\text{seed}$ và một hàm $\phi$ có tác dụng lấy tọa độ $x$ của một điểm trên đường cong.
++**Thuật toán:**++
++Bước 1++: Tính $t=\phi(s.P)$
++Bước 2++: Tính $r = \phi(t.Q)$
++Bước 3++: Cắt đi $16$ bit đầu của $r$ được $r'$, sau đó trả về giá trị của $r'$ như một giá trị ngẫu nhiên.
++Bước 4++: Đặt $s = \phi(t.P)$ và lặp lại bước $1$.
++**Sơ đồ:**++
Ta có thể minh họa trong python như sau:
```python=
from random import randint
from fastecdsa.curve import P256
from fastecdsa.point import Point
# đây là giá trị P,Q cố định trong bản tiêu chuẩn của Nist
# https://en.wikipedia.org/wiki/Dual_EC_DRBG#Details
Px = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
Py = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
Qx = 0xc97445f45cdef9f0d3e05e1e585fc297235b82b5be8ff3efca67c59852018192
Qy = 0xb28ef557ba31dfcbdd21ac46e2a91e3c304f44cb87058ada2cb815151e610046
class Dual_EC:
def __init__(self, seed):
self.s = seed
self.P = Point(Px, Py, curve=P256)
self.Q = Point(Qx, Qy, curve=P256)
def next(self):
t = (self.s * self.P).x
r = (t * self.Q).x
self.s = (t * self.P).x # đặt lại s
return (r & ((1<<240)-1)) # bỏ 16 bit đầu
if __name__ == "__main__":
seed = randint(0, P256.q-1)
PRNG = Dual_EC(seed)
print("10 số ngẫu nhiên từ Dual EC:")
for _ in range(10):
print(PRNG.next())
```
Ta được các giá trị ngẫu nhiên cực kỳ lớn như sau:
```p!
10 số ngẫu nhiên từ Dual EC:
450692808565769372859516584005105896367990617144655283378790286095059282
1319595610808025797049438303871327614289558936368431079652671980490822932
1522035218020601167967835683540452224397044365731852573954790888658070303
1355598215185675603378564966085339955333439249982901706839051724753453079
447900755851131174674745708005375848576700455031676109222188371403172794
777568794742911719658514418549939946101594088502424650204220543864132027
820500082441871042194773974521920998875591160974268820757642006834412254
1538423961648112788582037565457895332821763702512017372241162379514338026
521300582801147737160004700625231561643212169971004526055919996170530007
1217898211662646031324461433666901508142362115927467677740796699038098801
```
> Nghe có vẻ hiện đại và an toàn nhưng khi nhìn vào hai giá trị cố định $P,Q$ thì liệu bạn có đặt câu hỏi về mối quan hệ giữa chúng không?
## Scandal về việc tồn tại Backdoor
Rất nhiều nhà nghiên cứu khi nhìn vào thuật toán đã chú ý đến hai giá trị cố định là $(P,Q)$, ta đều biết $P$ là điểm sinh nhưng $Q$ thì sao? Nist không hề giải thích cho mọi người biết cách mà họ tạo ra $Q$ cũng như liệu $Q$ có bằng $d.P$ với một giá trị $d$ nào đó? Có lẽ họ biết giá trị $d$ nhưng không muốn nói cho ai biết. Dưới đây mình sẽ giải thích cách mà người nắm giữ $d$ có thể tính toán và thao túng các **state** tiếp theo như thế nào, nội dung được mình thao khảo trong ([**link1**](https://www.youtube.com/watch?v=nybVFJVXbww), [**link2**](https://rump2007.cr.yp.to/15-shumow.pdf))
Giả sử ta biết giá trị $d$ sao cho:
$$Q = d.P$$
>Khi này ta có: $P = d^{-1}.Q = e.Q$ với $e$ là nghịch đảo modulo của $d$ trong order $P$.
Đặt $s_0 = \text{seed}$, ở lần lặp đầu tiên chưa có gì đặc biệt:
$$
\begin{align}
t_0 &= s_0.P\\
r_0 &= t_0.Q\\
s_1 &= t_0.P
\end{align}
$$
Đến lần thứ hai thì xuất hiện biến số:
$$
\begin{align}
t_1 &= s_1.P = (t_0.P).P = (t_0.e.Q).P = (e.(t_0.Q)).P = (e.r_0).P\\
r_1 &= t_1.Q\\
s_2 &= t_1.P
\end{align}
$$
Nhìn vào công thức của $t_1$, ta hoàn toàn có thể tính được $t_1$ nhờ vào $r_0$ trước đó.
Khi có $t_1$ thì ta tính được state $r_1$ và $s_2$, có $s_2$ thì tính được $r_2$ và $s_3$ và cứ tiếp tục như thế ta sẽ dự đoán được toàn bộ các state sau này.
:::info
Để dễ hình dung thì khi có $r_0$, ta chỉ cần lấy $r_0.e$ là có được $s_1$ bởi vì $r_0.e=t_0.Q.e=t_0.P=s_1$.
:::
> Nhưng ta chưa có $r_0$ mà chỉ có $\text{trunc}_{r_0}$ là $r_0$ bị mất $16$ bit đầu.
$r_0$ chỉ bị mất $16$ bit đầu (65536 giá trị) nên không phải vấn đề quá phức tạp, ta sẽ có $2^{16}$ khả năng và **Brute force** như sau:
$$r_0 = i\times2^{240}+\text{trunc}_{r_0} \hspace{5mm}|0 \leq i\leq 2^{16}|$$
Sau đó ta thay từng giá trị $r_0$ tìm được vào công thức của đường cong:
$$y^2 \equiv r_0^3 + a.r_0 + b \pmod p$$
Nếu $y^2$ là **Quadratic Residue** thì ta tìm được $r_0$.
:::info
Tóm lại ta có thể Brute force để tìm được $r_0$, sau đó dùng $r_0$ để tính các state tiếp theo, phá vỡ hoàn toàn **Dual_EC_DRBG** nếu như biết được giá trị $d$.
:::
> ++**Fun fact:**++ Vào năm 2013, các tài liệu bị rò rỉ từ **Edward Snowden** tiết lộ rằng Cơ quan An ninh Quốc gia Hoa Kỳ (NSA) đã chủ động thiết kế và thúc đẩy sử dụng **Dual_EC_DRBG** với cái Backdoor to tổ chảng này, thậm chí còn trả [**10 triệu USD**](https://www.reuters.com/article/us-usa-security-rsa-idUSBRE9BJ1C220131220/) cho công ty **RSA Security** để triển khai và giấu trong các sản phẩm thương mại nhằm mục địch giám sát khách hàng, sau khi bị phanh phui thì công ty RSA Security bị chỉ trích khá dữ dội vì ưu tiên lợi ích tài chính hơn bảo mật người dùng.
# CryptoHack - Misc
## One Time Pad
### Gotta Go Fast (40 pts)
**nc socket.cryptohack.org 13372**
:::spoiler Source
```python=
#!/usr/bin/env python3
import time
from Crypto.Util.number import long_to_bytes
import hashlib
from utils import listener
FLAG = b'crypto{????????????????????}'
def generate_key():
current_time = int(time.time())
key = long_to_bytes(current_time)
return hashlib.sha256(key).digest()
def encrypt(b):
key = generate_key()
assert len(b) <= len(key), "Data package too large to encrypt"
ciphertext = b''
for i in range(len(b)):
ciphertext += bytes([b[i] ^ key[i]])
return ciphertext.hex()
class Challenge():
def __init__(self):
self.before_input = "Gotta go fast!\n"
def challenge(self, your_input):
if not 'option' in your_input:
return {"error": "You must send an option to this server"}
elif your_input['option'] == 'get_flag':
return {"encrypted_flag": encrypt(FLAG)}
elif your_input['option'] == 'encrypt_data':
input_data = bytes.fromhex(your_input['input_data'])
return {"encrypted_data": encrypt(input_data)}
else:
return {"error": "Invalid option"}
import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
"""
When you connect, the 'challenge' function will be called on your JSON
input.
"""
listener.start_server(port=13372)
```
:::
++**Solution 1**++: Challenge sử dụng thời gian hiện tại `int(time.time())` và băm nó ra bằng $\text{sha256}$ để làm **OTP** xor với Flag, khi remote tới server thì khoảng thời gian này có thể bị lệch $1-2$ giây nên ta hoàn toàn có thể ước chừng được, băm thời gian ra và đem xor với ciphertext là có **Flag**.
:::spoiler Solution
```python=
from pwn import *
import hashlib
from Crypto.Util.number import long_to_bytes
import time
from json import *
def generate_key():
current_time = int(time.time()) + 1 # bù trừ thời gian lệch
print(f'{current_time = }')
key = long_to_bytes(current_time)
return hashlib.sha256(key).digest()
while True:
io = remote("socket.cryptohack.org", 13372)
request_1 = {"option" : "get_flag"}
io.sendlineafter(b"\n", dumps(request_1).encode())
key = generate_key()
ct = bytes.fromhex(loads(io.recvline())["encrypted_flag"])
flag = xor(key[:-4], ct)
if b"crypto{" in flag:
print(flag.decode())
break
io.close()
```
:::spoiler Flag
current_time = 1750788375
**crypto{t00_f4st_t00_furi0u5}**
:::
++**Solution 2**++: Challenge cho phép ta gửi một plaintext bất kỳ để cho nó xor với **OTP** nên ta sẽ gửi plaintext là $28$ bytes NULL. Lý do là vì khoảng cách giữa hai lần mã hóa không cách nhau quá xa nên chúng sẽ chung OTP, mà chung OTP nên ta có hai kết quả sau:
$$\text{Ct}_1 = \text{Flag} \oplus \text{OTP}$$
$$\text{Ct}_2 = \text{\x00} \oplus \text{OTP}$$
$$\Rightarrow \text{Ct}_2 \oplus \text{Ct}_1 = \text{Flag} \oplus \text{\x00} = \text{Flag} $$
:::spoiler Solution
```python=
from pwn import *
from json import *
io = remote("socket.cryptohack.org", 13372)
request_1 = {"option" : "get_flag"}
io.sendlineafter(b"\n", dumps(request_1).encode())
ct1 = bytes.fromhex(loads(io.recvline())["encrypted_flag"])
request_2 = {"option" : "encrypt_data", "input_data" : "00"*28}
io.sendline(dumps(request_2).encode())
ct2 = bytes.fromhex(loads(io.recvline())["encrypted_data"])
print(xor(ct1, ct2))
```
:::spoiler Flag
current_time = 1750788375
**crypto{t00_f4st_t00_furi0u5}**
:::
---
### No Leaks (100 pts)
**nc socket.cryptohack.org 13370**
:::spoiler Source
```python=
import base64
import os
from utils import listener
FLAG = "crypto{????????????}"
def xor_flag_with_otp():
flag_ord = [ord(c) for c in FLAG]
otp = os.urandom(20)
xored = bytearray([a ^ b for a, b in zip(flag_ord, otp)])
# make sure our OTP doesnt leak any bytes from the flag
for c, p in zip(xored, flag_ord):
assert c != p
return xored
class Challenge():
def __init__(self):
self.before_input = "No leaks\n"
def challenge(self, your_input):
if your_input == {"msg": "request"}:
try:
ciphertext = xor_flag_with_otp()
except AssertionError:
return {"error": "Leaky ciphertext"}
ct_b64 = base64.b64encode(ciphertext)
return {"ciphertext": ct_b64.decode()}
else:
self.exit = True
return {"error": "Please request OTP"}
import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
"""
When you connect, the 'challenge' function will be called on your JSON
input.
"""
listener.start_server(port=13370)
#nc socket.cryptohack.org 13370
```
:::
++**Mô tả**++: Mỗi lần gửi Request đến server, server sẽ trả về cho ta kết quả: $$\text{xored} = \text{Flag} \oplus \text{OTP}$$
với điều kiện:
$$\text{Flag}[i] \neq \text{xored}[i]$$
> Nếu **một** ký tự của Flag trùng với $\text{xored}$ thì server sẽ báo lỗi **Leaky ciphertext**.
Ta nhận ra điều sau, những ký tự từng xuất hiện ở $\text{xored}[i]$ sẽ không xuất hiện trong $\text{Flag}[i]$, vì vậy ý tưởng của ta là gửi thật nhiều Request để loại dần dần từng khả năng của $\text{Flag}[i]$, đến khi còn lại $1$ khả năng thì ta nhận ký tự đó làm ký tự của Flag.
:::spoiler Solution
```python=
from pwn import *
from string import ascii_lowercase, digits
from base64 import b64decode
from json import *
def check(list):
return all(len(i) == 1 for i in list)
r = remote('socket.cryptohack.org', 13370)
# r = remote('localhost', 13370)
r.recvuntil(b"No leaks\n")
alphabet = "_" + ascii_lowercase + digits
flag = 'crypto{'
guess = [alphabet for _ in range(12)]
while True:
try:
req = dumps({"msg": "request"})
r.sendline(req.encode())
res = r.recvline()
res = loads(res.decode())
ct = b64decode(res["ciphertext"])[7:-1]
# ta sẽ loại từng ký tự trong guess
for i in range(12):
if chr(ct[i]) in guess[i]:
guess[i] = guess[i].replace(chr(ct[i]), '')
# khi mà toàn bộ guess chỉ còn một ký tự thì đó là ký tự cùa Flag
if check(guess):
print(flag + ''.join(guess) + "}")
break
except:
continue
r.close()
```
:::spoiler Flag
**crypto{unr4nd0m_07p}**
:::
## PRNGs
### Lo-Hi Card Game (120 pts)
**nc socket.cryptohack.org 13383**
:::spoiler Source
```python=
from functools import total_ordering
from Crypto.Random import random
from utils import listener
FLAG = 'crypto{?????????????????????????????}'
VALUES = ['Ace', 'Two', 'Three', 'Four', 'Five', 'Six',
'Seven', 'Eight', 'Nine', 'Ten', 'Jack', 'Queen', 'King']
SUITS = ['Clubs', 'Hearts', 'Diamonds', 'Spades']
class RNG:
mul = random.getrandbits(60)
inc = random.getrandbits(60)
mod = 2**61 - 1 # 9th mersenne prime
def __init__(self, seed):
self.state = seed
def next(self):
self.state = (self.state * self.mul + self.inc) % self.mod
return self.state
@total_ordering
class Card:
def __init__(self, value, suit):
self.value = value
self.suit = suit
def __str__(self):
return f"{self.value} of {self.suit}"
def __eq__(self, other):
return self.value == other.value
def __gt__(self, other):
return VALUES.index(self.value) > VALUES.index(other.value)
class Game:
def __init__(self):
self.rng = RNG(random.getrandbits(60))
self.deck = [Card(value, suit) for suit in SUITS for value in VALUES]
self.num_deals = self.shuffle()
def rebase(self, n, b=52):
if n < b:
return [n]
else:
return [n % b] + self.rebase(n//b, b)
def shuffle(self):
self.deals = self.rebase(self.rng.next())
return len(self.deals)
def deal_card(self):
index = self.deals.pop()
if self.deals == []:
self.num_deals = self.shuffle()
return self.deck[index]
class Challenge():
def __init__(self):
self.no_prompt = True
self.game = Game()
self.funds = 20
self.dollars = self.funds
self.round = 0
self.hidden = self.game.deal_card()
def play_round(self, msg=None):
self.round += 1
self.hand = self.hidden # move last round's hidden card to player's hand
self.hidden = self.game.deal_card() # deal new hidden card
self.shuffle_msg = ""
if self.game.num_deals: # dealer shuffled deck
self.shuffle_msg = f"I will reshuffle the deck after {self.game.num_deals} rounds. "
self.game.num_deals = None
if self.round == 1:
msg = f"Welcome to my virtual casino! You are sitting down for a game of lo-hi. {self.shuffle_msg}Your hand is the {self.hand}. Lower or higher?"
self.shuffle_msg = ""
return {
"round": self.round,
"$": self.dollars,
"hand": str(self.hand),
"msg": msg
}
def win(self):
self.dollars += 1
msg = f"Correct! Hidden card was {self.hidden}. {self.shuffle_msg}Lower or higher?"
return self.play_round(msg)
def lose(self):
self.dollars -= 2 # house edge
msg = f"Incorrect! Hidden card was {self.hidden}. {self.shuffle_msg}Lower or higher?"
return self.play_round(msg)
def challenge(self, your_input):
if self.round == 0:
return self.play_round()
elif self.dollars <= 0:
self.exit = True
return {"error": "You're broke!"}
elif self.round == 200:
self.exit = True
if self.dollars >= 130:
return {"msg": f"You pulled a 21! Here's a flag: {FLAG}"}
elif self.dollars > self.funds:
return {"msg": f"Nice, you beat the house!"}
else:
return {"msg": f"Aww, have a free drink!"}
elif not 'choice' in your_input:
self.exit = True
return {"error": "You must make a choice"}
else:
if self.hidden == self.hand:
return self.lose() # house edge
choice = your_input['choice']
if choice.lower().startswith('l'):
if self.hidden < self.hand:
return self.win()
else:
return self.lose()
elif choice.lower().startswith('h'):
if self.hidden > self.hand:
return self.win()
else:
return self.lose()
else:
self.exit = True
return {"error": "Invalid input"}
import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13383)
```
:::
++**Mô tả:**++ Challenge này là một giả lập đánh bạc khi ta phải đoán được lá của người chia bài `(hidden)` lớn hơn hay bé hơn lá ta đang cầm trong tay `(hand)` (chỉ so số chứ không so chất). Khởi đầu với `$20` trong tay nếu đoán đúng ta được `$1` còn sai thì mất `$2`. Liếm được `$130` trong **200** lần chơi thì ta có được Flag.
> Nghe có vẻ không ngon ăn vì xác suất ta đoán trúng nhiều lần liên tiếp là rất khó, thậm chí thắng chỉ được một nhưng thua lại mất hai.
Tiến hành phân tích Source code, ta giải thích từng đoạn như sau:
> Class **RNG**:
```python=
class RNG:
mul = random.getrandbits(60)
inc = random.getrandbits(60)
mod = 2**61 - 1 # 9th mersenne prime
def __init__(self, seed):
self.state = seed
def next(self):
self.state = (self.state * self.mul + self.inc) % self.mod
return self.state
```
Ta thấy rằng nó sử dụng cơ chế **LCG** để tạo state, trong đó đã biết modulus $m$, ta cần khôi phục giá trị $(a,c)$. Như lý thuyết đã tìm hiểu ở [trước](https://hackmd.io/@at20n0118/ByCdXCLExg#Trường-hợp-2-Khôi-phục-a-và-c-khi-đã-có-m-và-3-outputs-liên-tiếp) thì cần biết $3$ output liên tiếp thì mới khôi phục được.
> Class **Card**:
```python=
class Card:
def __init__(self, value, suit):
self.value = value
self.suit = suit
def __str__(self):
return f"{self.value} of {self.suit}"
def __eq__(self, other):
return self.value == other.value
def __gt__(self, other):
return VALUES.index(self.value) > VALUES.index(other.value)
```
Class này không có gì đặc biệt, đơn giản là giúp ta dễ dàng tạo các lá bài và so sánh các lá bài với nhau hơn, điểm chú ý là khi so sánh hai lá bài, nó chỉ so **số** chứ **không so chất**.
> Class **Game**:
```python=
class Game:
def __init__(self):
self.rng = RNG(random.getrandbits(60))
self.deck = [Card(value, suit) for suit in SUITS for value in VALUES]
self.num_deals = self.shuffle()
def rebase(self, n, b=52):
if n < b:
return [n]
else:
return [n % b] + self.rebase(n//b, b)
def shuffle(self):
self.deals = self.rebase(self.rng.next())
return len(self.deals)
def deal_card(self):
index = self.deals.pop()
if self.deals == []:
self.num_deals = self.shuffle()
return self.deck[index]
```
Đây là phần code quan trọng nhất của Challenge, chú ý vào hàm `shuffle()` ta thấy rằng tác dụng của nó là tạo một **state** bằng **LCG** và chuyển state đó từ **base 10 → base 52**, khi này state của ta là một dãy các Index thuộc (0-51) được sắp xếp ngẫu nhiên, ta gọi state này là `deals`.
Ở hàm `deal_card()`, nó lấy giá trị **cuối cùng** của `deals` để làm `index` và bốc ngẫu nhiên trong bộ bài một lá bài ở vị trí `index`. Nghĩa là mỗi lần gọi hàm `deal_card()` nó sẽ bốc dần dần từng index cuối trong deals để làm lá `hidden`, đến khi nào hết thì gọi hàm `shuffle()` để tạo `deals` tiếp.
> class **Challenge**
- Hàm khởi tạo `__init__`:
```python=
def __init__(self):
self.no_prompt = True
self.game = Game()
self.funds = 20
self.dollars = self.funds
self.round = 0
self.hidden = self.game.deal_card()
```
Đầu tiên nó khởi tạo một `deals` bằng Class **Game** sau đó sử dụng Index cuối cùng trong `deals` để làm lá bài `hidden` đầu tiên, ta sẽ bắt đầu đánh bạc với `funds = $20`.
- Hàm `play_round`:
```python=
def play_round(self, msg=None):
self.round += 1
self.hand = self.hidden # move last round's hidden card to player's hand
self.hidden = self.game.deal_card() # deal new hidden card
self.shuffle_msg = ""
if self.game.num_deals: # dealer shuffled deck
self.shuffle_msg = f"I will reshuffle the deck after {self.game.num_deals} rounds. "
self.game.num_deals = None
if self.round == 1:
msg = f"Welcome to my virtual casino! You are sitting down for a game of lo-hi. {self.shuffle_msg}Your hand is the {self.hand}. Lower or higher?"
self.shuffle_msg = ""
return {
"round": self.round,
"$": self.dollars,
"hand": str(self.hand),
"msg": msg
}
```
Hàm này có tác dụng là gán lá `hand` của ta thành lá `hidden` trước đó và bốc một lá khác làm lá `hidden`. Nó cũng cho ta biết khi nào đã bốc hết Index trong `deals` bằng cách trả lại thông báo:
```python!
f"I will reshuffle the deck after {self.game.num_deals} rounds. "
```
Tức khi này nó sẽ `shuffle` lại và tạo `deals` mới.
- Mấu chốt của Challenge nằm ở hai hàm:
```pyth=
def win(self):
self.dollars += 1
msg = f"Correct! Hidden card was {self.hidden}. {self.shuffle_msg}Lower or higher?"
return self.play_round(msg)
def lose(self):
self.dollars -= 2 # house edge
msg = f"Incorrect! Hidden card was {self.hidden}. {self.shuffle_msg}Lower or higher?"
return self.play_round(msg)
```
Nó trả về cho ta giá trị của lá `hidden` trước đó mỗi lần ta thắng hoặc thua. Mà như đã đề cập trước đó, các lá bài được chọn từ **Index**, mà Index được tạo ra từ **state**, suy ra nếu ta thu thập đủ Index, ta có thể chuyển nó về **Base 10** và có được State :flushed:
++**Thử nghiệm:**++ khi `deals = [0, 1, 28, 13, 35, 43, 47, 25, 44, 48, 8]`, ta thấy rằng Index của từng lá bài trong `hand` sẽ là các giá trị cuối cùng trong `deals`:
```python!
{'round': 1, '$': 20, 'hand': 'Nine of Clubs', 'msg': 'Welcome to my virtual casino! You are sitting down for a game of lo-hi. I will reshuffle the deck after 11 rounds. Your hand is the Nine of Clubs. Lower or higher?'}
{'round': 2, '$': 18, 'hand': 'Ten of Spades', 'msg': 'Incorrect! Hidden card was Ten of Spades. Lower or higher?'}
{'round': 3, '$': 19, 'hand': 'Six of Spades', 'msg': 'Correct! Hidden card was Six of Spades. Lower or higher?'}
{'round': 4, '$': 17, 'hand': 'King of Hearts', 'msg': 'Incorrect! Hidden card was King of Hearts. Lower or higher?'}
{'round': 5, '$': 18, 'hand': 'Nine of Spades', 'msg': 'Correct! Hidden card was Nine of Spades. Lower or higher?'}
{'round': 6, '$': 19, 'hand': 'Five of Spades', 'msg': 'Correct! Hidden card was Five of Spades. Lower or higher?'}
{'round': 7, '$': 17, 'hand': 'Ten of Diamonds', 'msg': 'Incorrect! Hidden card was Ten of Diamonds. Lower or higher?'}
{'round': 8, '$': 18, 'hand': 'Ace of Hearts', 'msg': 'Correct! Hidden card was Ace of Hearts. Lower or higher?'}
{'round': 9, '$': 16, 'hand': 'Three of Diamonds', 'msg': 'Incorrect! Hidden card was Three of Diamonds. Lower or higher?'}
{'round': 10, '$': 17, 'hand': 'Two of Clubs', 'msg': 'Correct! Hidden card was Two of Clubs. Lower or higher?'}
{'round': 11, '$': 18, 'hand': 'Ace of Clubs', 'msg': 'Correct! Hidden card was Ace of Clubs. I will reshuffle the deck after 11 rounds. Lower or higher?'}
```
Vì vậy chiến lược của ta là thu thập đủ số lượng các lá bài `hand`, chuyển nó thành `deals`, và từ `deals` → `state`. Khi có được $3$ `state`, ta khôi phục được $(a,c)$ của LCG, có đủ tham số và `state` ta có thể tính được state tiếp theo và dự đoán được các lá bài trong tương lai rồi.
> Chú ý là nhiều lúc không thể kiếm đủ `$130` trong vòng `200` lượt chơi đâu. Nên đừng bỏ cuộc :sunglasses: remote lại chơi tiếp là đủ.
:::spoiler Solution
```python=
from pwn import *
from json import *
FLAG = 'crypto{?????????????????????????????}'
VALUES = ['Ace', 'Two', 'Three', 'Four', 'Five', 'Six',
'Seven', 'Eight', 'Nine', 'Ten', 'Jack', 'Queen', 'King']
SUITS = ['Clubs', 'Hearts', 'Diamonds', 'Spades']
def base_52_to_10(n: list):
return sum(d * (52 ** i) for i, d in enumerate(n))
def base_10_to_52(n, b=52):
if n < b:
return [n]
else:
return [n % b] + base_10_to_52(n//b, b)
class Card:
def __init__(self, value, suit):
self.value = value
self.suit = suit
def __str__(self):
return f"{self.value} of {self.suit}"
def __eq__(self, other):
return self.value == other.value
def __gt__(self, other):
return VALUES.index(self.value) > VALUES.index(other.value)
# phải dùng while true vì đôi khi 200 lần mà không đủ $130
flag = None
found_flag = False
while True:
try:
if found_flag:
print("✅", flag)
break
# io = remote("localhost", 13383)
io = remote("socket.cryptohack.org", 13383)
DECK = [Card(value, suit) for suit in SUITS for value in VALUES]
my_deck = [(value + " of " + suit) for suit in SUITS for value in VALUES]
list_state = []
# thu thập 3 state
for _ in range(3):
deck = []
request = dumps({"choice" : "l"})
# thường thì len(deals) sẽ <= 11
for i in range(11):
feedback = loads(io.recvline())
deck.append(feedback["hand"])
if feedback["round"] >=7 and "I will reshuffle" in feedback["msg"]:
break
io.sendline(request.encode())
deck = deck[::-1]
deals = []
for i in deck:
deals.append(my_deck.index(i))
STATE = base_52_to_10(deals)
list_state.append(STATE)
# lần thứ 33 sẽ không gửi nữa
if _ < 2:
io.sendline(request.encode())
STATE1, STATE2, STATE3 = list_state
# tính lại giá trị (a,c)
m = 2**61 - 1
a = ((STATE3 - STATE2) *pow(STATE2 - STATE1, -1, m)) % m
c = (STATE3 - a*STATE2) % m
# có state3 và a,c,m là ta có thể tính được các state tiếp theo và có được deals
deals = base_10_to_52(STATE3)
hand = DECK[deals[0]] # hand sẽ là index cuối trong deals
state = STATE3
exits = False
while True:
if exits:
break
state = (a*state + c) % m
deals = base_10_to_52(state)
deals = deals[::-1]
for i in range(0, len(deals)):
hidden = DECK[deals[i]]
if hidden < hand:
request = dumps({"choice" : "l"})
io.sendline(request.encode())
elif hidden > hand:
request = dumps({"choice" : "h"})
io.sendline(request.encode())
else:
request = dumps({"choice" : "h"})
io.sendline(request.encode())
hand = DECK[deals[i]]
feedback = loads(io.recvline())["msg"]
if "You pulled a 21! " in feedback:
found_flag = True
flag = feedback
exits = True
break
elif "Nice, you beat the house!" in feedback:
print("❌ không đủ $130")
io.close()
exits = True
break
hand = DECK[deals[0]]
except:
print("❌ Hết tiền trước 33 lần")
io.close()
continue
```
:::spoiler Flag
**crypto{shuffl3_tr4ck1n6_i5_1t_l3g4l?}**
:::
### Nothing Up My Sleeve (150 pts)
**nc socket.cryptohack.org 13387**
:::spoiler Source
```python=
from fastecdsa.curve import P256
from fastecdsa.point import Point
from Crypto.Random import random
from utils import listener
FLAG = 'crypto{???????????????????}'
class RNG:
def __init__(self, seed, P, Q):
self.seed = seed
self.P = P
self.Q = Q
def next(self):
t = self.seed
s = (t * self.P).x
self.seed = s
r = (s * self.Q).x
return r & (2**(8 * 30) - 1)
class Game:
reds = {1, 3, 5, 7, 9, 12, 14, 16, 18, 19, 21, 23, 25, 27, 30, 32, 34, 36}
blacks = {2, 4, 6, 8, 10, 11, 13, 15, 17, 20, 22, 24, 26, 28, 29, 31, 33, 35}
odds = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35}
evens = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36}
def __init__(self, P, Q):
self.rng = RNG(random.getrandbits(60), P, Q)
self.num_spins = None
self.change_croupier()
def rebase(self, n, b=37):
if n < b:
return [n]
else:
return [n % b] + self.rebase(n//b, b)
def change_croupier(self):
self.spins = self.rebase(self.rng.next())
return len(self.spins)
def spin_wheel(self):
number = self.spins.pop()
if self.spins == []:
self.num_spins = self.change_croupier()
return number
class Challenge():
def __init__(self):
self.before_input = "Welcome to my virtual casino! You are sitting down for a game of roulette. This is a fair casino. We have chosen our lucky point, now you get to choose one too.\n"
self.funds = 20
self.dollars = self.funds
self.round = 0
def challenge(self, your_input):
self.round += 1
if self.round == 1:
casino_x = "0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296"
casino_y = "0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5"
P = Point(int(casino_x, 16), int(casino_y, 16), curve=P256)
player_x = your_input["x"]
player_y = your_input["y"]
Q = Point(int(player_x, 16), int(player_y, 16), curve=P256)
self.game = Game(P, Q)
croupier_msg = "Good evening, I will be your croupier for your first bets. "
return {"msg": f"{croupier_msg}The table is setup, place your bet!"}
elif self.dollars <= 0:
self.exit = True
return {"error": "You're broke!"}
elif self.round == 125:
self.exit = True
if self.dollars >= 1000:
return {"msg": f"Congratulations Mr Jarecki! Here's a flag: {FLAG}"}
elif self.dollars > self.funds:
return {"msg": f"Nice, you beat the house!"}
else:
return {"msg": f"Aww, have a free drink!"}
elif not 'choice' in your_input:
self.exit = True
return {"error": "You must make a choice"}
else:
bet = your_input["choice"]
spin = self.game.spin_wheel()
if bet == spin:
msg = "Boom, fantastic guess!"
self.dollars += 35
elif bet == "EVEN" and spin in self.game.evens:
msg = "Nice bet!"
self.dollars += 1
elif bet == "ODD" and spin in self.game.odds:
msg = "Nice bet!"
self.dollars += 1
elif bet == "RED" and spin in self.game.reds:
msg = "Nice bet!"
self.dollars += 1
elif bet == "BLACK" and spin in self.game.blacks:
msg = "Nice bet!"
self.dollars += 1
else:
msg = "Aww, try again."
self.dollars -= 1
croupier_msg = ""
if self.game.num_spins:
croupier_msg = f"Good evening, I will be your new croupier for the time being. "
self.game.num_spins = None
return {
"msg": f"{croupier_msg}The ball landed on {spin}. {msg}",
"spin": spin,
"round": self.round,
"$": self.dollars,
}
import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13387)
```
:::
++**Mô tả:**++ Challenge này mô phỏng **casino roulette game** và yêu cầu ta phải kiếm đủ `$1000` trong `125` lượt chơi thì mới có Flag. Ta có nhiều hình thức cược hơn bao gồm cược màu **(đỏ, đen)**, cược **chẵn, lẻ** và cược **số** (số mà viên bi rơi vào). Ta sẽ tập trung vào phần cược **số** vì nó cho ta nhiều tiền thưởng nhất, lên đến `$35` một lần đoán trúng, tức chỉ cần ta đoán trúng $30$ lần cược số thì ta sẽ có được Flag.
Tiến hành phân tích Challenge:
> Class **RNG**
```python=
class RNG:
def __init__(self, seed, P, Q):
self.seed = seed
self.P = P
self.Q = Q
def next(self):
t = self.seed
s = (t * self.P).x
self.seed = s
r = (s * self.Q).x
return r & (2**(8 * 30) - 1)
```
Ta thấy rằng nó sử dụng một phiên bản đơn giản hơn của **Dual_EC_DRBG** để tạo **state** và sau đó bỏ đi `16 bit` đầu của state bằng đoạn `r & (2**(8 * 30) - 1)`. Ta biết rằng **Dual_EC_DRBG** là không an toàn khi ta biết được mối quan hệ giữa $P$ và $Q$.
> Class **Game**:
```python=
class Game:
reds = {1, 3, 5, 7, 9, 12, 14, 16, 18, 19, 21, 23, 25, 27, 30, 32, 34, 36}
blacks = {2, 4, 6, 8, 10, 11, 13, 15, 17, 20, 22, 24, 26, 28, 29, 31, 33, 35}
odds = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35}
evens = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36}
def __init__(self, P, Q):
self.rng = RNG(random.getrandbits(60), P, Q)
self.num_spins = None
self.change_croupier()
def rebase(self, n, b=37):
if n < b:
return [n]
else:
return [n % b] + self.rebase(n//b, b)
def change_croupier(self):
self.spins = self.rebase(self.rng.next())
return len(self.spins)
def spin_wheel(self):
number = self.spins.pop()
if self.spins == []:
self.num_spins = self.change_croupier()
return number
```
Challenge tạo kết quả ngẫu nhiên dựa trên hàm `change_croupier()`, đầu tiên nó tạo một **state** bằng class **RNG** ra đó chuyển state từ **base 10 → base 37**, khi này state sẽ là một list các số (0-36) được sắp xếp ngẫu nhiên, ta gọi state ở base 37 là `spins`. Sau đó hàm `spin_wheel()` sẽ bốc giá trị cuối cùng của `spins` để làm kết quả mỗi lượt chơi. Tức mỗi lần gọi hàm `spin_wheel()` thì Challenge sẽ bộc số cuối cùng trong `spins`, bốc hết thì gọi hàm `change_croupier()` để tạo `spins` mới.
> Class **Challenge**:
Hàm `challenge(your_input)`:
```python=
def challenge(self, your_input):
self.round += 1
if self.round == 1:
casino_x = "0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296"
casino_y = "0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5"
P = Point(int(casino_x, 16), int(casino_y, 16), curve=P256)
player_x = your_input["x"]
player_y = your_input["y"]
Q = Point(int(player_x, 16), int(player_y, 16), curve=P256)
self.game = Game(P, Q)
croupier_msg = "Good evening, I will be your croupier for your first bets. "
return {"msg": f"{croupier_msg}The table is setup, place your bet!"}
```
Mấu chốt nằm ở đây, Challenge cho ta gửi một điểm $Q(x,y)$ vào để khởi tạo Class **Game**, đây là lỗ hổng nghiêm trọng vì khi ta gửi $Q=P$, ta sẽ có thông tin sau:
Ở lần **next** đầu tiên, không có gì đặc biệt.
$$
\begin{align}
t_0 &= \text{seed}\\
s_0 &= t_0 . P\\
\text{seed} &= s_0\\
r_0 &= s_0.Q = s_0.P
\end{align}
$$
Nhưng ở lần **next** tiếp theo thì đã xảy ra sự cố:
$$
\begin{align}
t_1 &= \text{seed} = s_0\\
s_1 &= t_1 . P= s_0.P = r_0\\
\text{seed} &= s_1 = r_0\\
r_1 &= s_1.Q = r_0.Q
\end{align}
$$
> Ta thấy rằng $s_1=r_0$, mà $s_1$ lại là seed của lần next tiếp theo, suy ra khi ta có được $r_0$ thì ta có thể tính được kết quả của lần next tiếp theo ($r_1$), mà có $r_1$ thì có được $s_2$, có $s_2$ thì có $r_2$, cứ thế ta sẽ tính được toàn bộ state sau này.
Mục tiêu của ta là tìm được $r_0$. Khi này $r_0$ bị cắt mất $16$ bit đầu, chuyển sang base 37 và được lấy làm kết quả của mỗi lượt quay, vậy ta cần thu thập đủ kết quả của các lần quay, chuyển sang base 10 là ta có được **truncated** $r_0$.
Vì ta mất đi $16$ bit đầu (tối đa **65536**) của $r_0$ nên ta phải brute force các bit đã mất để tìm lại, điều kiện dừng là khi $s_1$ bằng $r_0$ thì nó phải tạo ra được **state** $r_1$, vì vậy ta cần phải thu thập các giá trị base 37 của $r_1$ để làm đối chiếu nữa.
Có $r_0$, ta tính được $r_1 = r_0.Q$, có $r_1$ tính được $r_2=r_1.Q$, cắt $16$ bit đâu chuyển sang **base 37** là có được `spins` tiếp theo, gửi cho server là ta thắng đậm 😎.
:::spoiler Solution
```python=
from fastecdsa.curve import P256
from fastecdsa.point import Point
from pwn import *
from json import *
from tqdm import *
io = remote("socket.cryptohack.org", 13387)
# io = remote("localhost", 13387)
casino_x = "0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296"
casino_y = "0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5"
# gửi điểm P = Q
input1 = {"x": casino_x, "y": casino_y}
input1 = dumps(input1)
io.sendlineafter(b"now you get to choose one too.\n", input1.encode())
io.recvline()
def base_37_to_10(n: list):
return sum(d * (37 ** i) for i, d in enumerate(n))
def base_10_to_37(n, b=37):
if n < b:
return [n]
else:
return [n % b] + base_10_to_37(n//b, b)
# thu thập các base 37 của r0 truncated
input2 = {"choice" : "EVEN"}
input2 = dumps(input2)
spin0 = []
for i in range(60):
io.sendline(input2.encode())
feedback = loads(io.recvline())
spin = feedback["spin"]
spin0.append(spin)
if "Good evening" in feedback["msg"]:
break
spin0 = spin0[::-1]
r0 = base_37_to_10(spin0)
# thu thập các base 37 của r1 truncated
input3 = {"choice" : "EVEN"}
input3 = dumps(input3)
spin1 = []
for i in range(60):
io.sendline(input3.encode())
feedback = loads(io.recvline())
spin = feedback["spin"]
spin1.append(spin)
if "Good evening" in feedback["msg"]:
break
spin1 = spin1[::-1]
r1 = base_37_to_10(spin1)
print(f"{spin0 = }")
print(f"{spin1 = }")
print(f"r0 truncated = {r0}")
print(f"r1 truncated = {r1}")
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
class RNG:
def __init__(self, seed, P, Q):
self.seed = seed
self.P = P
self.Q = Q
def next(self):
t = self.seed
s = (t * self.P).x
self.seed = s
r = (s * self.Q).x
return r & (2**(8 * 30) - 1)
# tìm lại 16 bit của r0
Q = Point(int(casino_x, 16), int(casino_y, 16), curve=P256)
for i in trange(2, 2**16):
r = i * 2**(30*8) + r0
s = r
r_ = (s * Q).x
tmp = r_ & (2**(8 * 30) - 1)
tmp_spin = base_10_to_37(tmp)
if tmp_spin == spin1:
print(f"{r = }")
break
# có r0, có r1
s = r
r_ = (s * Q).x #r1
# có r1 là có r2
s = r_
r_ = (s * Q).x # r2
tmp = r_ & (2**(8 * 30) - 1)
tmp_spin = base_10_to_37(tmp)
spin3 = tmp_spin[::-1]
for i in spin3:
input3 = {"choice" : i}
input3 = dumps(input3)
io.sendline(input3.encode())
io.interactive()
```
:::spoiler Flag
r = 84690202611128926250199625148402487479147838419419733350849096962367529248164
73%|███████████████████████████████████████████████▌| 47930/65534 [01:04<00:23, 738.37it/s]
**crypto{No_Str1ngs_Att4ch3d}**
:::
### RSA vs RNG (150 pts)
:::spoiler Source
```python=
from Crypto.Util.number import *
import json
MOD = 2**512
A = 2287734286973265697461282233387562018856392913150345266314910637176078653625724467256102550998312362508228015051719939419898647553300561119192412962471189
B = 4179258870716283142348328372614541634061596292364078137966699610370755625435095397634562220121158928642693078147104418972353427207082297056885055545010537
FLAG = b'crypto{???????????????????????????}'
class PRNG:
def __init__(self, seed):
self.state = (seed % MOD)
def get_num(self):
self.state = (A * self.state + B) % MOD
return self.state
def get_prime(self):
p = self.get_num()
while not isPrime(p):
p = self.get_num()
return p
seed = getRandomRange(1, MOD)
rng = PRNG(seed)
P = rng.get_prime()
Q = rng.get_prime()
N = P * Q
E = 0x10001
pt = bytes_to_long(FLAG)
ct = long_to_bytes(pow(pt, E, N))
json.dump({
'N': N,
'E': E,
'ciphertext': ct.hex()
}, open('flag.enc', 'w'))
```
:::
++**Mô tả:**++ Challenge này sử dụng **LCG** để tạo hai số nguyên tố $(p,q)$ cho mã hóa **RSA**. Nhưng lỗ hổng nằm ở việc sau khi tạo số nguyên tố $p$ một cách ngẫu nhiên thì nó sử dụng $p$ để làm **seed** tính $q$.
Đặt $\text{seed} = p, M = 2^{512}$, ta có công thức của $q$ là:
$$q \equiv (((A.p + B).A + B).A+B).A+... \equiv A'.p+B' \pmod M$$
Suy ra:
$$p.q \equiv p.(A'.p+B') \pmod M$$
$$\Leftrightarrow A'.p^2 + B'.p - n \equiv 0 \pmod M$$
Ta có đây là phương trình modulo bậc $2$ và modulus có thể factor dễ dàng nên hoàn toàn có thể tìm được $p$ bằng `.roots()` trong **sagemath**.
Có $(p,q)$ thì ta có thể giải mã ciphertext để có Flag rồi.
:::spoiler Solution
```python=
from json import *
from tqdm import trange
from Crypto.Util.number import *
A =
B =
MOD = 2**512
data = loads(open("rsa.enc", "rb").read())
n = data["N"]
e = data["E"]
c = data["ciphertext"]
c = int(c, 16)
x = PolynomialRing(Zmod(MOD), "x").gen()
f = x
exit = False
for i in trange(1000):
if exit:
break
f = A*f + B
root = (x*f - n).roots(multiplicities=False)
if root:
for prime in root:
if isPrime(int(prime)) and n % int(prime) == 0:
P = int(prime)
exit = True
break
Q = n//P
d = pow(e, -1, n-P-Q+1)
print(long_to_bytes(pow(c, d, n)).decode())
```
:::spoiler Flag
18%|████████ | 180/1000 [00:00<00:03, 230.37it/s]
**crypto{pseudorandom_shamir_adleman}**
:::
### Trust Games (150 pts)
**nc socket.cryptohack.org 13396**
:::spoiler Source
```python=
from Crypto.Cipher import AES
from os import urandom
from Crypto.Util.number import bytes_to_long
from utils import listener
FLAG = 'crypto{??????????????????????}'
class LCG:
def __init__(self, a, b, m, seed):
self.a = a
self.b = b
self.m = m
self.state = seed
self.counter = 0
def refresh(self):
self.counter = 0
self.state = bytes_to_long(urandom(6))
def next_state(self):
self.state = (self.a * self.state + self.b) % self.m
def get_random_bits(self, k):
if self.counter == 16:
self.refresh()
self.counter += 1
self.next_state()
return self.state >> (48 - k)
def get_random_bytes(self, number):
bytes_sequence = b''
for i in range(number):
bytes_sequence += bytes([self.get_random_bits(8)])
return bytes_sequence
class Challenge():
def __init__(self):
a = 0x1337deadbeef
b = 0xb
m = 2**48
seed = bytes_to_long(urandom(6))
self.G = LCG(a, b, m, seed)
self.plaintext = self.G.get_random_bytes(16)
self.key = self.G.get_random_bytes(16)
self.IV = self.G.get_random_bytes(16)
self.before_input = f"Let's play a game, Player {self.G.get_random_bytes(8).hex()}. If you can encrypt the plaintext that I will give you with my secret key, you will be worthy of my trust and a reward.\n"
def challenge(self, your_input):
if your_input['option'] == 'get_a_challenge':
msg = 'Try encrypting this plaintext with the given IV and my secret key!'
self.plaintext = self.G.get_random_bytes(16)
self.key = self.G.get_random_bytes(16)
self.IV = self.G.get_random_bytes(16)
return {'msg': msg, 'plaintext': self.plaintext.hex(), 'IV': self.IV.hex()}
if your_input['option'] == 'validate':
self.exit = True
if 'ciphertext' not in your_input:
return {'msg': 'You must provide a ciphertext...'}
received_ct = bytes.fromhex(your_input['ciphertext'])
cipher = AES.new(self.key, AES.MODE_CBC, self.IV)
my_ct = cipher.encrypt(self.plaintext)
if my_ct == received_ct:
return {'msg': f'Here is a well deserved flag: {FLAG}'}
else:
return {'msg': f'The expected ciphertext was: {my_ct.hex()}. I knew you could not be trusted...'}
import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13396)
```
:::
++**Mô tả:**++ Ở Challenge này ta sẽ thực hành khôi phục **state** của **LCG** từ các truncated output. Để lấy được Flag, Challenge sẽ cho ta $IV$ và $Pt$ sau đó yêu cầu ta mã hóa $Pt$ thành $Ct$ bằng Key của server nhưng Key được random bằng thuật toán của Server và không được tiết lộ. Mục tiêu của ta là phải tìm ra **Key**.
Tiến hành phân tích Source code:
> Class **LCG**:
```python=
class LCG:
def __init__(self, a, b, m, seed):
self.a = a
self.b = b
self.m = m
self.state = seed
self.counter = 0
def refresh(self):
self.counter = 0
self.state = bytes_to_long(urandom(6))
def next_state(self):
self.state = (self.a * self.state + self.b) % self.m
def get_random_bits(self, k):
if self.counter == 16:
self.refresh()
self.counter += 1
self.next_state()
return self.state >> (48 - k)
def get_random_bytes(self, number):
bytes_sequence = b''
for i in range(number):
bytes_sequence += bytes([self.get_random_bits(8)])
return bytes_sequence
```
Chú ý vào hàm `get_random_bytes(number)`, nó tạo một chuỗi bytes dài `number` bằng cách gọi `number` lần hàm `get_random_bits()`.
Với hàm `get_random_bits()`, nó có tác dụng tạo một giá trị nguyên `k bit` từ **state** bằng cách lấy `state >> (48 - k)` và sau $16$ lần tạo bit nó sẽ khởi tạo một **seed** mới bằng hàm `refresh()`.
Có thể thấy rằng nếu biết được chuỗi bytes được tạo ra từ hàm `get_random_bytes()` thì ta chỉ biết được `k bit` **msb** của các **state** mà thôi.
> Class **Challenge**:
Giá trị khởi tạo `__init__()`:
```python=
def __init__(self):
a = 0x1337deadbeef
b = 0xb
m = 2**48
seed = bytes_to_long(urandom(6))
self.G = LCG(a, b, m, seed)
self.plaintext = self.G.get_random_bytes(16)
self.key = self.G.get_random_bytes(16)
self.IV = self.G.get_random_bytes(16)
self.before_input = f"Let's play a game, Player {self.G.get_random_bytes(8).hex()}. If you can encrypt the plaintext that I will give you with my secret key, you will be worthy of my trust and a reward.\n"
```
Nhớ rằng sau khi tạo một chuỗi dài $16$ bytes thì **seed** sẽ được đặt lại, Vì vậy khi khởi tạo **plaintext, key, IV** thì seed đã được đặt lại $3$ lần vì chúng đều dài $16$ bytes, nhưng khi khởi tạo xong tên **Player** thì seed chưa được refresh bởi vì tên Player chỉ dài $8$ bytes, chứng tỏ $8$ bytes tiếp theo sẽ chung seed với $8$ bytes của Player.
Hàm `Challenge()`:
```python=
def challenge(self, your_input):
if your_input['option'] == 'get_a_challenge':
msg = 'Try encrypting this plaintext with the given IV and my secret key!'
self.plaintext = self.G.get_random_bytes(16)
self.key = self.G.get_random_bytes(16)
self.IV = self.G.get_random_bytes(16)
return {'msg': msg, 'plaintext': self.plaintext.hex(), 'IV': self.IV.hex()}
```
Vì seed chưa được refresh nên $8$ bytes đầu của plaintext sẽ chung seed với $8$ bytes cuối của Player. Tương tự, $8$ bytes cuối của plaintext sẽ chung seed với $8$ bytes đầu của **Key** và $8$ bytes cuối của Key sẽ chung seed với $8$ bytes đầu của **IV**.
++**Minh họa**++:
Có thể thấy rằng **Key** là kết hợp của seed `125036756085320` (màu cam) và seed `248047704308531` (màu xanh dương).
> Vì vậy chỉ cần ta recover được **state cuối** của plaintext và **state đầu** của IV thì ta có thể recover được $16$ state của Key rồi.
Sử dụng tool [**này**](https://github.com/deut-erium/RNGeesus/tree/main?tab=readme-ov-file#code---lcg), truyền vào Class `Breaker` các tham số `(seed=None,a,b,n,truncation=40)` và truyền vào hàm `break_lattice` $8$ truncated output là nó sẽ trả về cho ta **seed** của các output đó.
++**Ví dụ:**++ Ta có các thông tin sau:
```!
a = 0x1337deadbeef
b = 0xb
m = 2**48
state refresh = 35433236224931
8 state cuối của Pt là [231003972601656, 153040193047891, 165273117346440, 22923680908547, 268240331761624, 150626344059571, 250489913155368, 13681270834787]
Giữ 8 bit đầu còn [210, 139, 150, 20, 243, 136, 227, 12]
```
Sử dụng tool trên ta sẽ tìm được `seed = state refresh = 35433236224931`.
```python=
from trunc_LCG import Breaker
a = 0x1337deadbeef
b = 0xb
m = 2**48
y = [210, 139, 150, 20, 243, 136, 227, 12]
seed_recover = Breaker(seed=None, a=a, b=b, n=m, truncation=48-8)
print(seed_recover.break_lattice(y))
```
> Có được seed của Pt, ta có thể tính được $8$ state đầu của key, khi có được seed của IV, ta cũng sẽ tính ngược lại được $8$ state cuối của key. Có được $16$ state của key, ta chuyển sang bytes và đem đi mã hóa Plaintext là có Flag.
:::spoiler Solution
```python=
from pwn import *
from json import *
from trunc_LCG import Breaker # lấy từ tool đã đề cập ở trên
from Crypto.Cipher import AES
a = 0x1337deadbeef
b = 0xb
m = 2**48
io = remote("socket.cryptohack.org", 13396)
# io = remote("localhost", 13396)
# lấy 8 bytes của player, cái này không có tác dụng gì
player = bytes.fromhex(io.recvline()[len("Let's play a game, Player "):].split(b". ")[0].decode())
player = [i for i in player]
# lấy pt và iv
request = dumps({"option" : "get_a_challenge"})
io.sendline(request.encode())
feedback = loads(io.recvline())
pt = bytes.fromhex(feedback["plaintext"])
iv = bytes.fromhex(feedback["IV"])
PT = [i for i in pt[8:]]
IV = [i for i in iv[:8]]
# tìm seed của pt và seed của iv
seed_recover = Breaker(seed=None, a=a, b=b, n=m, truncation=48-8)
seedPT = int(str(seed_recover.break_lattice(PT)[0]))
seedIV = int(str(seed_recover.break_lattice(IV)[0]))
# tính 8 state đầu cảu key
state_key_1 = [seedPT]
for i in range(8 + 8):
state_key_1.append((state_key_1[i] * a + b) % m)
state_key_1 = state_key_1[1+8:]
# tính ngược 8 state cuối của key
state_key_2 = [seedIV]
for i in range(7):
state_key_2.append(((state_key_2[i] - b) * pow(a, -1, m)) % m)
state_key_2 = state_key_2[::-1]
key = state_key_1 + state_key_2
key = bytes([i >> (48 - 8) for i in key])
cipher = AES.new(key, AES.MODE_CBC, iv)
ciphertext = cipher.encrypt(pt).hex()
request = dumps({"option" : "validate", "ciphertext" : ciphertext})
io.sendline(request.encode())
io.interactive()
```
:::spoiler Flag
**crypto{L4ttice_C0mpl1ant_G4m3}**
:::
## LFSR
### L-Win (120 pts)
:::spoiler Source
```python=
from Crypto.Util.number import bytes_to_long
# SECRET_T = [?, ?, ?, ?]
FLAG = b"crypto{????????????????????????????????????????}"
assert len(FLAG) == 48
class LFSR:
def __init__(self):
self._s = list(map(int, list("{:0384b}".format(bytes_to_long(FLAG)))))
for _ in range(16 * len(FLAG)):
self._clock()
def _clock(self):
b = self._s[0]
c = 0
for t in SECRET_T: c ^= self._s[t]
self._s = self._s[1:] + [c]
return b
def stream(self, length):
return [self._clock() for _ in range(length)]
c = LFSR()
stream = c.stream(2048)
print("".join(map(str, stream)))
```
:::
++**Mô tả:**++ Challenge sử dụng **Flag** làm seed ban đầu sau đó **clock** tổng cộng `16*48 + 2048` lần, nhưng chỉ có `2048` bit của `2048` lần clock sau là được in ra, vì số lượng output là khá nhiều nên ý tưởng của ta là sử dụng **Berlekamp Massey** để khôi phục **Taps**, có Taps là ta có thể đảo ngược quá trình tạo bit và tìm được giá trị **seed** là Flag.
Về **Berlekamp Massey** mình sử dụng Code này:
```python=
# https://github.com/thewhiteninja/lfsr-berlekamp-massey/blob/master/berlekamp_massey.py
class BerlekampMassey:
def __init__(self, sequence):
n = len(sequence)
s = sequence # list các giá trị nguyên
k = 0
for k in range(n):
if s[k] == 1:
break
self._f = {k + 1, 0}
self._l = k + 1
g = {0}
a = k
b = 0
for n in range(k + 1, n):
d = 0
for item in self._f:
d ^= s[item + n - self._l]
if d == 0:
b += 1
else:
if 2 * self._l > n:
self._f ^= set([a - b + item for item in g])
b += 1
else:
temp = self._f.copy()
self._f = set([b - a + item for item in self._f]) ^ g
self._l = n + 1 - self._l
g = temp
a = b
b = n - self._l + 1
def _get_polynomial_string(self):
result = ''
lis = sorted(self._f, reverse=True)
for i in lis:
if i == 0:
result += '1'
else:
result += 'x^%s' % str(i)
if i != lis[-1]:
result += ' + '
return result
def get_polynomial(self):
return list(self._f)
def get_polynomial_degree(self):
return self._l
def __str__(self):
return self._get_polynomial_string()
def __repr__(self):
return "<%s polynomial=%s>" % (self.__class__.__name__, self._get_polynomial_string())
sequence = open("output.txt", "r").read()
sequence = [int(i) for i in sequence]
c = BerlekampMassey(sequence=sequence)
print(c._get_polynomial_string())
```
Tìm được **Taps** là `x^384 + x^16 + x^15 + x^6 + 1` hay `Taps = [0,6,15,16]`.
Có Taps thì ta đảo ngược quá trình xor là có được Flag.
:::spoiler Solution
```python=
from Crypto.Util.number import *
SECRET_T = [0, 6, 15, 16]
# vì thanh ghi chỉ dài 384 nên ta chỉ lấy 384 bit thôi
with open("output.txt") as f:
output = f.readline()[:384]
s = output
decrypted = output
for _ in range(16*48):
b = 0 ^ int(s[15]) ^ int(s[14]) ^ int(s[5]) ^ int(s[-1])
s = (str(b) + s[:-1])
decrypted = str(b) + decrypted
print(long_to_bytes(int(decrypted, 2))[:48])
```
:::spoiler Flag
**crypto{minimal_polynomial_in_an_arbitrary_field}**
:::
# END
> [time=Sat, Jun 28, 2025 2:57 AM]
:::spoiler
:::
Sign in with Wallet
Connect another wallet