Crypto CTF 2021¶

Chào mọi người, lại một mùa Crypto CTF nữa đã qua và lần này mình có khá khẩm hơn năm ngoái một chút, và sau đây là writeup các challenge mình đã làm được

Source code đề và bài giải của mình ở đây.

Farm¶

Đề bài cho mình F tạo các đa thức trên \(\mathrm{GF}(2^6)\), maptofarm để lấy đa thức tương ứng với chỉ số của ký tự trong alphabet, và encrypt để mã hóa chuỗi base64, bằng cách là ký tự base64 m sẽ thành ALPHABET[F.index(pkey * maptofarm(chr(m)))].

Ok, vì key chỉ nằm trong \(\mathrm{GF}(2^6)\), mình chỉ việc bruteforce thôi (nằm trong \(\mathrm{GF}(2^6)\) nên độ dài là \(14\) hay bao nhiêu cũng không quan trọng). Làm ngược lại quá trình mã hóa mình có flag.

Flag: CCTF{EnCrYp7I0n_4nD_5u8STitUtIn9_iN_Fi3Ld!}.

KeyBase¶

Bài này cho mình một hệ thống sử dụng AES mode CBC (key và iv giống nhau suốt một phiên kết nối) để làm hai việc:

đưa flag đã bị mã hóa;
mã hóa một đoạn input \(32\) byte bất kì và trả lại key (dạng hex) với \(2\) byte cuối bị ẩn, và ciphertext với \(14\) byte ở giữa bị ẩn.

Do mode CBC có tính chất \(C_{i+1} = E_k(C_i \oplus P_{i+1})\), với \(P_0 = iv\). Do đó nếu mình chọn \(P\) và \(P'\) là hai plaintext có \(16\) bytes đầu giống nhau còn \(16\) bytes cuối khác nhau thì mình có \(C_1 = C_1' = E_k(iv \oplus P_1)\) còn \(C_2 = E_k(C_1 \oplus P_2)\) và \(C_2' = E_k(C_1' \oplus P_2')\).

Từ đây mình có \(C_1 \oplus P_2 \oplus C_1' \oplus P_2' = D_k(C_2) \oplus D_k(C_2')\), mà \(C_1 = C_1'\) rồi nên mình cần lấy ciphertext nào mà \(16\) bytes cuối không bị ẩn đi để có thể bruteforce \(2\) byte cuối của key và decrypt, tức là mình phải có \(P_2 \oplus P_2' = D_k(C_2) \oplus D_k(C_2')\).

Bây giờ tìm iv, mình chỉ cần đưa lên server \(32\) bytes \0 là xong và cũng tương tự trên, chỉ lấy ciphertext nào mà \(16\) bytes cuối không bị ẩn. Vì \(C_2 = E_k(C_1) = E_k(E_k(iv))\) (do xor với dãy toàn 0). Decrypt mình có lại iv.

Giờ thì giải mã flag thôi.

Flag: CCTF{h0W_R3cOVER_7He_5eCrET_1V?}.

Rima¶

Bài này không dùng biến chữ để chạy loop và dùng dấu gạch dưới của python nên lúc đầu mình thấy hơi rắc rối.

Đầu tiên flag được chuyển sang dạng nhị phân và thêm 1 bit 0 ở đầu được dãy \(f\). Kế tiếp với mỗi \(i = 0, \ldots, \mathrm{len}(f) - 2\) thì \(f_i = f_i + f_{i+1}\).

Kế tiếp hai số \(a\) và \(b\) được tạo là hai số nguyên tố kế tiếp tính từ \(\mathrm{len}(f)\) là độ dài \(f\).

Sau đó, \(g\) và \(h\) là hai list tạo ra từ việc lặp \(f\) lần lượt với \(a\) và \(b\) lần. Như vậy độ dài của \(g\) là \(a \cdot \mathrm{len}(f)\) và độ dài của \(h\) là \(b \cdot \mathrm{len}(f)\).

Tiếp theo, \(c\) là số nguyên tố kế tiếp tính từ \(\mathrm{len}(f) \gg 2\). Thêm \(c\) bit 0 vào đầu \(g\) và thực hiện \(g_i = g_i + g_{i+c}\) với \(i = 0, 1, \ldots, \mathrm{len}(f) - c - 1\). Làm tương tự với \(h\).

Cuối cùng là chuyển \(g\) và \(h\) sang số int base \(5\) và viết lên file dưới dạng byte. Nên đầu tiên mình sẽ làm ngược lại và tìm được \(g\) và \(h\), sau đó mình bruteforce \(\mathrm{len}(f)\) để tìm \(a\), \(b\) và \(c\) và xem thử bộ nào thỏa \(a \cdot \mathrm{len}(f) + c = \mathrm{len}(g)\) và \(b \cdot \mathrm{len}(f) + c = \mathrm{len}(h)\).

Sau đó là làm ngược lại quá trình, với \(i = \mathrm{len}(f) - c - 1, \ldots, 0\) thì \(g_i = g_i - g_{i+c}\). Tương tự với \(h\). Có thể kiểm chứng cách đúng nếu đầu \(g\) có đúng \(c\) số 0. :)))

Giờ thì, lấy \(\mathrm{len}(f)\) số đầu của \(g\) và tiếp tục làm ngược lại sẽ ra các bit của flag.

Flag: CCTF{_how_finD_7h1s_1z_s3cr3T?!}.

Maid¶

Ở bài này server cung cấp cho mình các chứng năng sau:

encrypt một số bất kì không vượt quá \(2^{2048 - 2}\) bits;
decrypt một số bất kì (hàm decrypt bị giấu đi);
lấy flag bị mã hóa.

Key là một cặp khóa công khai-bí mật \((pubkey, privkey)\), trong đó \(pubkey = p^2q\) còn \(privkey = p^2\), với \(p\) và \(q\) là hai số nguyên tố \(1024\) bits và đồng dư \(3\) modulo \(4\).

Hàm encrypt thực hiện mã hóa số \(m\) bằng cách trả về \(m^2 \pmod{pubkey}\). Còn hàm decrypt thực hiện giải mã chỉ cần \(privkey\).

Kì cục ..............

Thế quái nào ..............

Mà encrypt cần cả \(p\) và \(q\) còn decrypt chỉ cần \(p\)?

Thật ra là vì nếu \(c \equiv m^2 \pmod{pubkey}\) thì \(c \equiv m^2 \pmod{p^2}\), như vậy giải thích cho việc \(m\) không được vượt quá \(2048-2\) bits và việc giải mã chỉ cần \(p\). Như vậy cách attack của mình như sau:

Chọn ngẫu nhiên các ciphertext, gửi lên để server decrypt và nhận lại các plaintext tương ứng. Ta biết rằng \(c \equiv m^2 \pmod{p^2}\) nên \(p^2 = \gcd(m_1^2 - c_1, m_2^2 - c_2)\), từ đó lấy căn bậc hai là có \(p\).
Tiếp theo, chọn ngẫu nhiên các plaintext, gửi lên server encrypt và nhận lại ciphertext tươngg ứng. Do

\[c \equiv m^2 \pmod{pubkey} \equiv m^2 \pmod{p^2q},\]

khi đó \(p^2q = \gcd(m_1^2 - c_1, m_2^2 - c_2)\). Việc này ngược lại quá trình trên vì như nãy mình đã nói, encrypt sử dụng \(p^2q\) còn decrypt thì chỉ cần \(p^2\);
và bây giờ \(p\) và \(q\) đã có đủ, ta decrypt và có flag thôi.

Flag: CCTF{___Ra8!N_H_Cryp70_5YsT3M___}.

Tuti¶

Ở đây \(x\) và \(y\) là nửa đầu và nửa sau của flag, \(k\) là một số cho trước thỏa mãn

\[(x^2+1)(y^2+1)-2(x-y)(xy-1) = 4(k+xy).\]

Biến đổi một tí mình có

\[\begin{split} \begin{array}{cccc} & x^2 y^2 + x^2 + y^2 + 1 - 2(x-y)xy+2(x-y)-4xy & = & 4k \\ \Leftrightarrow & x^2 y^2 + (x^2 + y^2 + 1 + 2(x-y) - 2xy) - 2(x-y+1)xy & = & 4k \\ \Leftrightarrow & x^2 y^2 + (x-y+1)^2 - 2(x-y+1)xy & = & 4k \\ \Leftrightarrow & (xy - x + y - 1)^2 & = & 4k. \end{array}\end{split}\]

Như vậy \(xy-x+y-1=\sqrt{4k}\) mà \(xy-x+y-1=(x+1)(y-1)\) nên mình chỉ cần factor số này là tìm được \(x\) và \(y\). Do có thể có nhiều cách chọn nên mình tìm cái "hợp lí" nhất.

Flag: CCTF{S1mPL3_4Nd_N!cE_Diophantine_EqUa7I0nS!}.

Improve¶

Ở bài này khá có khá nhiều thứ linh tinh nhưng chung quy lại là mình cần nhập vào hai số khác nhau \(m_1\) và \(m_2\) khác \(n\) sao cho kết quả hàm improve với hai số này là giống nhau.

Các tham số sẽ là \(n\) làm chặn trên cho hai số nhập vào (không vượt quá \(n^2\), và \(f\) có tính chất quan trọng là luôn chẵn, đây là tiền đề để mình giải bài này.

Hàm improve mình để ý rằng \(L\) được tạo ra sau vài biến đổi từ \(e = m^f \pmod{n^2}\), mà mình cần hai số \(m\) cho cùng \(L\), vậy chỉ cần cho ra cùng \(e\) là xong. Như hồi nãy mình có đề cập là \(f\) luôn chẵn, vậy chỉ cần chọn \(m\) và \(n^2-m\) là xong. :))

Flag: CCTF{Phillip_N0W_4_pr0b4b1liStiC__aSymM3Tr1C__AlGOrithM!!}.

Onlude¶

Bài này mình giải trước khi hết thời gian 1 tiếng và là bài cuối cùng mình giải được. Hàm prepare chuyển flag thành ma trận \(A\), key là bộ ba ma trận \(R\), \(L\) và \(U\). Ma trận \(S=L U\).

Việc mã hóa như sau:

với \(R\), \(L\) và \(U\) như trên, tính \(S = LU\);
tính \(X = A + R\), \(Y = S X\) và ciphertext là \(E = L^{-1} Y\).

Đề cho mình bốn ma trận:

\(E\) là ciphertext, với một chút biến đổi mình có \(E = U (A+R)\);
ma trận \(L U L\);
ma trận

\[L^{-1} S^2 L = L^{-1} (LU)^2 L = L^{-1}LULUL=(UL)^2,\]

mình đặt là \(T\);

ma trận \(R^{-1}S^8\), mình đặt là \(W\).

Lấy \(LUL\) nhân với \(T\) mình có \(LUL \cdot (UL)^2 = L(UL)^3\).

Khi đó

\[T^2 [L(UL)^3]^{-1} = (UL)^4 \cdot (UL)^{-3} \cdot L^{-1} = UL \cdot L^{-1} = U.\]

Vậy là mình có \(U\) rồi. :))

Quay lại \(E = U (A + R)\), khi đó \(R = U^{-1} E - A\), nhân bên phải của hai vế với \(W\) thì

\[R \cdot R^{-1} S^8 = (U^{-1} E - A) W = S^8 = (LU)^8.\]

Quay lại một chút,

\[(LUL) \cdot T^3 = (LUL) \cdot (L^{-1}S^6L) = (LU)^7 \cdot L,\]

suy ra \((LUL) \cdot T^3 \cdot U = (LU)^8\).

Từ đó mình dễ dàng tìm lại được \(A = U^{-1}E - (LU)^8 W^{-1}\).

Thực hiện tương tự hàm prepare mình có được flag.

Flag: CCTF{LU__D3c0mpO517Ion__4L90?}.

Writeup đến đây là hết, cám ơn các bạn đã đọc.