TJCTF 2024¶
Một ngày đẹp trời 20/05/20xx ...
Đề bài của CTF này có nhiều câu rất dài nên mình không để ở đây. Các bạn có thể tải đề từ github của cuộc thi tại đây.
weird-crypto¶
Đây là một bài RSA cơ bản và không may là lúc thi mình không vào được factordb, nhưng oops đủ nhỏ để bruteforce nên cũng không hề gì.
accountleak¶
Bài này cần tìm subs để recover lại p và q. Tương tự bài trên, subs cũng đủ nhỏ để mình bruteforce đến khi nào tìm được cặp p và q là hai số nguyên tố và decrypt my_password.
from sage.all import *
from pwn import process, context, remote
import re
context.log_level = 'Debug'
pr = process(["python3", "server.py"])
# pr = remote("tjc.tf", 31601)
pr.recvline()
c, n = list(map(int, re.findall(r'\d+', pr.recvline().strip().decode())))
pr.recvline()
pr.recvline()
pr.sendlineafter(b'<You>', b'yea')
pr.recvline()
dont_leak_this = int(re.findall(r'\d+', pr.recvline().strip().decode())[0])
print(f"c = {c}")
print(f"n = {n}")
print(f"dont_leak_this = {dont_leak_this}")
for sub in range(1, 2**20):
if (n + sub**2 - dont_leak_this) % sub != 0: continue
s = (n + sub**2 - dont_leak_this) // sub
PR = PolynomialRing(ZZ, 'x')
x = PR.gen()
f = x**2 - s*x + n
roots = f.roots()
if len(roots) == 0: continue
p, q = roots[0][0], roots[1][0]
assert p * q == n
d = pow(65537, -1, (p-1) * (q-1))
my_password = pow(c, d, n)
pr.recvline()
pr.recvline()
pr.sendlineafter(b"<You>", str(my_password).encode())
pr.recvline()
pr.recvline()
print(pr.recvline())
pr.close()
assume¶
Ở bài này mình chỉ cần kiểm tra xem if hay else được thực thi bằng việc kiểm tra message thứ 5 của mỗi đoạn có bằng (g^a)^b không.
with open("log.txt") as f:
lines = [line.strip() for line in f.readlines()]
p = int(lines[0])
msg = lines[1:]
g = 6
flag = ""
pos = 0
for ln in range(0, len(msg), 6 * 20):
for i in range(ln, ln + 6 * 20, 6):
ga = int(msg[i].split(" ")[-1])
b = int(msg[i+1].split(" ")[-1])
gb = int(msg[i+2].split(" ")[-1])
c = msg[i+3].split(" ")[-1]
guess = int(msg[i+4].split(" ")[-1])
if pow(ga, b, p) == guess:
flag += c
pos += 1
break
print(flag)
print(flag)
iodomethane¶
Ở bài này, nếu gọi \(K\) là khóa thì \(K\) là ma trận \(3 \times 3\). Giả sử flag gồm các bytes \(f_0 f_1 \ldots f_{n}\) thì kết quả output là phép nhân ma trận
Với flag format là tjctf{, mình đã biết \(6\) ký tự đầu của flag, mình chỉ cần bruteforce thêm \(3\) ký tự nữa là có thể kết hợp với output để tìm \(K\). Ở đây \(K\) cần thỏa mãn là ma trận khả nghịch và khi decrypt mỗi dòng của flag (trừ dòng cuối) phải cho kết quả nằm trong alphabet.
Code giải mình để ở solve.py.
alkane¶
Bài này mình giải ra sau cùng do một số nhầm lẫn.
Giả sử gọi dòng \(i\) của schedule là \(S^{(i)} = ( s^{(i)}_0, s^{(i)}_1, \ldots, s^{(i)}_{63} )\).
Gọi key là \(K = k_0 k_1 \ldots k_{128}\). Khi đó mảng arr sẽ được tạo bằng cách
Ý tưởng của mình là xem phép tính trên như một tích vô hướng của hai vector \(\bar{a}_i = (a_0, \ldots, a_{127})\) và \(K\), với \(a_j = 1\) nếu \(j\) nằm trong \(S^{(i)}\), ngược lại thì \(a_j = 0\).
Khi mình xây dựng ma trận \(M\) gồm các dòng là các vector \(\bar{a}_i\) như trên thì mình không decrypt ra được. Mãi về sau mình mới phát hiện rằng trong \(S^{(i)}\) có một số phần tử trùng nhau chứ không hoàn toàn là \(64\) phần tử phân biệt.
Khi đó mình cần xem số lần mỗi phần tử xuất hiện trong \(S^{(i)}\) là chẵn hay lẻ.
Một vấn đề khác là ma trận \(M\) có rank bằng 127, không phải full rank. Do đó để tìm tất cả nghiệm của hệ phương trình mình cần cộng với tất cả tổ hợp tuyến tính của các vector trong kernel.
from sage.all import *
m = b'yellow submarine'
c = b'\xb7\x8e\xb3\xd9\xfd\xf2\x1f\xa2\xeaz\xe3\x0f\x00xj\x08'
assert len(m) == len(c)
def xor(a, b):
return bytes(x^y for x, y in zip(a, b))
def get_bit(b, n):
byte = b[n // 8]
return (byte >> (7 - (n % 8))) & 1
def set_bit(b, n, v):
byte = b[n // 8]
byte &= ~(v << (7 - (n % 8)))
byte |= v << (7 - (n % 8))
b[n // 8] = byte
return b
def rrot(x1, n):
arr = bytearray(x1)
for i in range(len(x1)):
arr[(i + n) % len(x1)] = x1[i]
return arr
def lrot(x1, n):
arr = bytearray(x1)
for i in range(len(x1)):
arr[i] = x1[(i + n) % len(x1)]
return arr
out = xor(m, c)
M = matrix(GF(2), 128, 128)
from challenge import schedule
for i in range(128):
for bit_loc in schedule[i]:
M[i, bit_loc] += 1
arr = vector(GF(2), [get_bit(out, i) for i in range(128)])
try:
sol = M.solve_right(arr)
except: exit(0)
ker = M.right_kernel()
assert len(ker.basis()) == 1
sol_ = sol + ker.basis()[0]
assert M * sol == arr and M * sol_ == arr
key = bytearray(b"\x00" * 16)
for i in range(128):
set_bit(key, i, int(sol[i]))
print(b"tjctf{" + key + b"}")
key_ = bytearray(b"\x00" * 16)
for i in range(128):
set_bit(key_, i, int(sol_[i]))
print(b"tjctf{" + key_ + b"}")
lightweight-crypto-guard-system¶
Đây là một bài LCG cũng không quá phức tạp.
Với seed ban đầu \(x_0\), chuỗi sẽ được sinh theo công thức \(x_{i+1} = (a x_i + b) \bmod m\). Ở đây cả \(a\), \(b\) và \(m\) đều không biết.
Có nhiều hướng dẫn mình tham khảo để tìm lại modulo \(m\) và \(a\), \(b\) (mình lười :v). Ví dụ như ở link.
Nhưng vấn đề ở bài này là chúng ta được cho một đoạn liên tục \(x_0, x_1, x_2, \ldots\) mà thay vào đó là \(x_1\), \(x_{1+n}\), \(x_{2n+1}\) (tổng có 6 số).
Thực ra cách giải vẫn giống nhau. Đầu tiên mình recover modulo \(m\). Sau đó để ý rằng
Cứ tương tự vậy mình có \(x_{i+n} = (A x_n + B) \bmod m\),
với \(A = a^n \bmod m\) và \(B = \dfrac{a^n - 1}{a - 1} \cdot b \bmod m\).
Như vậy mình có một LCG mới và giải ra được \(A\), \(B\).
Sau đó mình recover lại \(a\) và \(b\). Như vậy là mình sinh được toàn bộ dãy.
hulksmash¶
Với hint là file keysmashes.txt thì các dòng trong file sẽ giúp mình tìm key.
Để ý rằng mỗi dòng chỉ gồm các ký tự fjdlska; (\(8\) ký tự, mỗi ký tự xuất hiện hai lần).
Để ý thêm xíu nữa, mình phát hiện ra mỗi ký tự xuất hiện hai lần vào vị trí hoặc đều chẵn, hoặc đều lẻ. Cụ thể là các ký tự fdsa sẽ ở vị trí chẵn còn jlk; ở vị trí lẻ.
Như vậy mình bruteforce tất cả tổ hợp như vậy và thử decrypt ...
from Crypto.Cipher import AES
from itertools import combinations
with open("keysmashes.txt") as rf:
lines = [line.strip() for line in rf.readlines()]
alphabet = list(b"fjdlska;")
assert len(alphabet) == 8
ct = bytes.fromhex('ed05f1440f3ae5309a3125a91dfb0edef306e1a64d1c5f7d8cea88cdb7a0d7d66bb36860082a291138b48c5a6344c1ab')
odd = set([1, 3, 5, 7, 9, 11, 13, 15])
even = set([0, 2, 4, 6, 8, 10, 12, 14])
for x1, x2 in combinations(odd, 2):
ox = odd.difference([x1, x2])
for y1, y2 in combinations(ox, 2):
oy = ox.difference([y1, y2])
for z1, z2 in combinations(oy, 2):
t1, t2 = oy.difference([z1, z2])
assert set([x1, x2, y1, y2, z1, z2, t1, t2]) == odd
for a1, a2 in combinations(even, 2):
ea = even.difference([a1, a2])
for b1, b2 in combinations(ea, 2):
eb = ea.difference([b1, b2])
for c1, c2 in combinations(eb, 2):
d1, d2 = eb.difference([c1, c2])
key = [0] * 16
key[x1] = key[x2] = ord('j')
key[y1] = key[y2] = ord('l')
key[z1] = key[z2] = ord('k')
key[t1] = key[t2] = ord(';')
key[a1] = key[a2] = ord('f')
key[b1] = key[b2] = ord('d')
key[c1] = key[c2] = ord('s')
key[d1] = key[d2] = ord('a')
aes = AES.new(bytes(key), AES.MODE_ECB)
try:
print(aes.decrypt(ct).decode())
except:
pass
Tiếp theo mình sẽ trình bày các bài mình làm sau khi giải kết thúc (có tham khảo writeup).
c-8¶
Đề bài cho mình các file enc.py, dec.py, re_plaus, plausibly.deniable. Với hint là affine cipher và modulo n = 18446744073709551629 mình cần khôi phục lại bốn file trên.
Do \(n\) có \(65\) bit nên việc mã hóa theo mã affine sẽ mã hóa \(8\) bytes một lần ra \(9\) bytes của ciphertext. Các bạn cũng có thể thấy rằng byte đầu của mỗi đoạn \(9\) bytes các file trên là 0x00 hoặc 0x01.
Mã affine có dạng \(y = ax + b \bmod n\) với \(a\) và \(b\) là hai số chưa biết cần đi tìm. Mình đã có \(y\) và cần dự đoán \(x\) nào sẽ mã hóa ra \(y\) tương ứng. Đoạn đầu của các file mã hóa với Python thường sẽ dùng các thư viện như pycryptodome. Mình thử một loạt các kiểu import và tìm ra phần đầu sẽ là
from Crypto.Cipher import AES
Mình chỉ cần \(16\) bytes ở trên thôi là được. Dựa vào đó mình khôi phục lại \(a\) và \(b\) rồi decrypt bốn file ban đầu.
u-235¶
Lát viết.
titanium-isopropoxide¶
Bài này mã hóa bằng file C++ với thuật toán khá phức tạp.
Bug ở bài này là key được tạo ra từ S-box không đủ mạnh. Sử dụng known-plaintext là flag format tjctf{ và XOR với \(6\) bytes đầu của ciphertext của hai file mình:
flag2 = open("flag2.txt.enc", "rb").read()
flag3 = open("flag3.txt.enc", "rb").read()
def xor(a, b):
return bytes(x^y for x, y in zip(a, b))
known_plaintext = b"tjctf{"
key = xor(flag2, known_plaintext)
f2 = []
f3 = []
for i in range(len(flag2)):
f2.append(key[i % len(key)] ^ flag2[i])
f3.append(key[i % len(key)] ^ flag3[i])
print(bytes(f2))
print(bytes(f3))
Ở kết quả thu được từ đoạn code, mình thấy rằng flag2 khá giống với đoạn văn có nghĩa. Sau dấu { là từ this (vì có sẵn chữ is), sau dấu _ là cube. Như vậy, mình XOR đoạn tjctf{this_cube thì sẽ thấy được key:
b'<U\xed\x18\xed\x18\xed\x18\xed\x18\xed\x18\xf7\x1e\xed'
Mình thấy rằng key bắt đầu bởi <U và lặp lại cặp byte `\xed\x18. Do đó mình có thể decrypt ra flag.
flag2 = open("flag2.txt.enc", "rb").read()
def xor(a, b):
return bytes(x^y for x, y in zip(a, b))
known_plaintext = b"tjctf{"
key = xor(flag2, known_plaintext)
while len(key) != 70:
key += b"\xed\x18"
f2 = []
for i in range(len(flag2)):
f2.append(key[i % len(key)] ^ flag2[i])
print(bytes(f2))
lithium-stearate¶
Sau khi giải kết thúc một pro đã hint cho mình: Slide attack.
Bài này mình được cho \(20\) cặp plaintext-ciphertext cùng với ciphertext của flag. Thông tin về cipher:
độ dài block là \(16\) bits (\(2\) bytes);
độ dài khóa là \(64\) bits (\(8\) bytes);
số vòng thực hiện là \(100000\) vòng.
Hàm mã hóa:
Word encrypt(Word in, Key k)
{
Word out = in;
for (int i = 0; i < rounds; i++)
{
out = r(out, ksch(k, i));
}
return out;
}
Trong đó rounds = 100000 và ksch là key schedule sinh ra subkey cho mỗi vòng.
round function¶
Round function là hàm r với cấu trúc như sau:
Word r(Word in, RKey kin)
{
RKey k = kin;
in ^= (k & 0xffff) ^ ((k >> 16) & 0xffff);
return P_f(S_f(in));
}
Trong đó, P_f và S_f là hai hàm:
Word S_f(Word in)
{
return (Sbox[in >> 8] << 8) | Sbox[in & 0xff];
}
Word P_f(Word in)
{
int r = 3;
Word out = 0;
out |= (in >> 8) & 0xff;
out |= (in & 0xff) << 8;
out ^= out >> 8;
Word out2 = 0;
out2 |= out >> r;
out2 |= out << (16 - r);
return out2;
}
Như vậy, S_f là hàm sử dụng S-box cho trước, và P_f là hàm hoán vị. Mình kí hiệu hai hàm này là \(S_f\) và \(P_f\).
Như vậy round function có dạng \(out = P_f(S_f(out \oplus k))\), trong đó \(r\) là số \(16\) bits và \(k\) cũng là số \(16\) bits. Ở đây lưu ý rằng tham số thứ hai của r là số \(32\) bits nhưng thực chất là lấy nửa đầu XOR nửa cuối, như vậy key được dùng có \(16\) bits.
key schedule¶
Thuật toán sinh khóa ksch lấy đầu vào là khóa ban đầu \(8\) bytes và vòng hiện tại \(i\) để sinh ra khóa \(k_i\). Khi thử in ra tất cả \(1000000\) khóa khi mã hóa một plaintext bất kì thì chúng ta có thể thấy rằng chỉ có đúng bốn subkey xoay vòng.
Kết hợp với lúc nãy mình chỉ ra, mỗi round function lấy vào key \(32\) bits nhưng thực chất chỉ là \(16\) bits. Như vậy nếu bruteforce cả bốn vòng với bốn subkeys thì sẽ cần \(16 \times 4 = 64\) bits. À thì nó cũng chả khác việc key ban đầu có \(64\) bits :))) nên chúng ta sẽ không bruteforce kiểu này.
Chúng ta sẽ xem kỹ hơn hàm sinh khóa con ksch.
RKey ksch(Key k, int i)
{
// .............
k |= 0xff << 24;
k |= 0xffULL << (24 + 32);
// .............
}
Đoạn trên cho thấy rằng, sau một hồi biến đổi, hàm ksch sẽ set bit thứ \(3\) và thứ \(7\) của biến k thành 0xff, nghĩa là k lúc này có dạng 0xff------ff------ (\(64\) bits).
RKey ksch(Key k, int i)
{
// .............
if (i == 0)
{
r = k & 0xffffffff;
r ^= 1162466901;
r ^= r >> 16;
r *= 3726821653;
}
if (i == 1)
{
r = ((k >> 32) & 0xffffffff) ^ (k & 0xffffffff);
r ^= 3811777446;
r = (r * 1240568533);
}
if (i == 2)
{
r = ((k >> 32) & 0xffffffff) ^ (k & 0xffffffff);
r ^= 3915669785;
r = (r * 1247778533);
}
if (i == 3)
{
r = ((k >> 32) & 0xffffffff) ^ (k & 0xffffffff);
r ^= 3140176925;
r = (r * 1934965865);
}
return r;
}
Ở phần kế của hàm ksch có \(3/4\) trường hợp r là XOR của \(32\) bits cao và \(32\) bits thấp. Ở trên mình đã phân tích rằng bytes thứ \(3\) và thứ \(7\) của k sẽ là 0xff nên khi XOR như vậy sẽ triệt tiêu byte đầu tiên của r, nên r chỉ còn \(24\) bits và chúng ta sẽ bruteforce ở đây.
Trong trường hợp i = 0 thì chương trình cũng chỉ lấy \(32\) bits thấp nên chúng ta có thể bỏ qua. Lý do sẽ được trình bày ở phần sau.
slide attack¶
Giới thiệu qua loa: slide attack là phương pháp tấn công block cipher thông qua việc chọn các cặp plaintext-ciphertext \((P, C)\) và \((P', C')\) mà \(P' = F(P)\) và \(C' = F(C)\) với \(F(x)\) là hàm nào đó. Khi thỏa mãn các điều kiện trên thì ta có thể thực hiện slide attack.
Để tìm hàm \(F(x)\) như vậy thì phụ thuộc vào cipher nào. Thông thường hàm \(F(x)\) sẽ chứa một hoặc nhiều round, trong đó chứa tất cả khóa con của cipher.
Ví dụ. Xét mô hình cipher đơn giản sau:
Như vậy hàm \(F(x)\) ở đây sẽ chứa hai subkey là \(K_0\) và \(K_1\). Do đó sơ đồ của \(F\) sẽ là:
Giả sử với một cặp plaintext-ciphertext khác là:
hay tương đương là
Slide attack lúc này sẽ hoạt động nếu \(P' = O_2 = F(P)\) và \(C' = F(C)\). Khi vẽ ra sẽ có dạng:
Quay lại bài lithium-stearate này, do chỉ có bốn subkeys nên có thể xem hàm \(F\) ở trên có dạng:
Trong đó \(K\) là khóa ban đầu \(64\) bits và mỗi \(K_i\) là khóa con \(32\) bits. Hàm \(G(x, k) = P_f(S_f(x \oplus k))\) là round function.
Như vậy chiến thuật để giải bài này là:
Tìm trong \(20\) cặp plaintext-ciphertext đề cho các cặp \((P, C)\) và \((P', C')\) sao cho \(F(P, K) = P'\) và \(F(C, K) = C'\).
Từ hai cặp plaintext-ciphertext trên khôi phục khóa \(K\).
Tuy nhiên việc này khó khăn vì không có khóa \(K\) thì không kiểm tra được điều kiện \(F(P, K) = P'\). Do đó chúng ta sẽ làm ngược lại.
Như ở trên đã phân tích, \(K_1\), \(K_2\) và \(K_3\) được sinh ra từ một k có \(24\) bits, do đó chúng ta bruteforce các k như vậy và tính ra \(K_1\), \(K_2\) và \(K_3\) tương ứng.
Với mỗi hai plaintext \(P_i\) và \(P_j\) ta tính \(K_0\) theo \(K_0 = S_f^{-1}(P^{-1}(T)) \oplus P\), với
Khi đã có đủ \(K_0\), \(K_1\), \(K_2\) và \(K_3\), mình sẽ kiểm tra điều kiện \(C' = F(C, K)\). Nếu thỏa mãn thì mình có được một cặp slid pair và sẽ thử mã hóa hai cặp plaintext-ciphertext bất kì để xem việc mã hóa với khóa có đúng không.
Khi tìm được khóa rồi thì mình giải mã lại flag.
Sau khi chạy findkey.cpp thì mình tìm được key là \(11892\), \(8704\), \(3384\), \(38922\). Sau đó mình decrypt ra flag. Ở đây mình compile với flag -O3 và openmp vì mình không có nhiều kinh nghiệm dùng GCC lắm. :))) Code cũng sẽ chạy nhanh hơn nếu sử dụng các flag khác, cũng như C++ khác như 11, ...
Lệnh compile:
g++ -O3 findkey.cpp -o findkey -fopenmp
Cuối cùng chúng ta giải mã với file decrypt.cpp.
Mình dành hẳn một phần cho một bài vì bài này khá dài và phức tạp.
Đây cũng là bài viết đầu tiên của mình về một phương pháp tấn công cực kì phổ biến là differential attack (phá mã vi sai).
tetraethyllead¶
Đây là một cipher sử dụng mô hình Feistel để mã hóa. Mô hình Feistel thường xuyên bị tấn công theo phương pháp differential, có thể kể đến như: DES, GOST, hay các phiên bản nhỏ hơn của chúng.
Do đó yêu cầu chống lại differential attack (cũng như người anh em khác của nó là linear attack) trở thành tiêu chuẩn để xây dựng block cipher hiện nay.
Mô hình Feistel¶
Trong mô hình Feistel, mỗi block của plaintext sẽ được chia đôi thành hai nửa trái phải - \(P = L_0 \Vert R_0\).
Ở bài này, plaintext có \(8\) bytes và key cũng có \(8\) bytes.
Trong mô hình Feistel chuẩn, ở mỗi vòng \(i+1\), sẽ thực hiện biến đổi sau:
Trong đó:
\(K_{i+1}\) là khóa ở vòng \(i+1\) với \(i = 0, 1, \ldots\)
\(F\) được gọi là round function. Hàm \(F\) phụ thuộc vào cipher là loại nào. Ví dụ thuật toán DES thì \(F\) là các phép biến đổi Expand, P-box và S-box. Hoặc đối với thuật toán GOST thì \(F\) gồm cộng modulo \(2^{32}\), S-box và dịch \(11\) bit sang trái.
Ở mô hình Feistel bên trên (cũng là mô hình chuẩn) thì hàm \(F\) cố định cho mỗi vòng. Tuy nhiên ở bài này thì round function ở mỗi vòng khác nhau. Cụ thể thì ở vòng một dùng S-box r2, ở vòng thứ hai là S-box r1, các vòng sau thì dùng hàm r345.
Mình có thể viết quá trình biến đổi như sau:
Vòng \(1\) |
\(L_1 = R_0\) |
\(R_1 = L_0 \oplus r_2(R_0, S_2)\) |
Vòng \(2\) |
\(L_2 = R_1\) |
\(R_2 = L_1 \oplus r_1(R_1, S_1)\) |
Vòng \(3\) |
\(L_3 = R_2\) |
\(R_3 = L_2 \oplus r_{345}(R_2, k_2, 3)\) |
Vòng \(4\) |
\(L_4 = R_3\) |
\(R_4 = L_3 \oplus r_{345}(R_3, k_2, 4)\) |
Vòng \(5\) |
\(L_5 = R_4\) |
\(R_5 = L_4 \oplus r_{345}(R_4, k_1 \oplus k_2, 5)\) |
Vòng \(6\) |
\(L_6 = R_5\) |
\(R_6 = L_5 \oplus r_{345}(R_5, k_1, 6)\) |
Vòng \(7\) |
\(L_7 = L_6 \oplus r_{345}(R_6, k_2, 7)\) |
\(R_7 = R_6 \oplus L_7 = R_6 \oplus r_{345}(R_6, k_2, 7)\) |
Lưu ý rằng vòng cuối hơi khác một tí.
Differential attack¶
Differential là gì???
Định nghĩa. Xét hàm \(S\) từ \(\mathbb{F}_2^n\) tới \(\mathbb{F}_2^m\). Với mỗi cặp vector \(\boldsymbol{a}, \boldsymbol{b} \in \mathbb{F}_2^n\) thì ta nói \(\boldsymbol{a} \oplus \boldsymbol{b}\) là input differential và \(S(\boldsymbol{a}) \oplus S(\boldsymbol{b})\) là output differential ứng với hàm \(S\).
Hàm \(S\) thường là các S-box trong block cipher. Các S-box thường không tuyến tính, nghĩa là ta không có \(S(\boldsymbol{a} \oplus \boldsymbol{b}) = S(\boldsymbol{a}) \oplus S(\boldsymbol{b})\).
Differential dựa trên quan sát rằng khi \(\boldsymbol{a} \oplus \boldsymbol{b}\) cố định thì output differential \(S(\boldsymbol{a}) \oplus S(\boldsymbol{b})\) phân bố không đều. Giả sử mình có S-box như sau:
Nếu mình duyệt qua tất cả cặp \(\boldsymbol{a}, \boldsymbol{b} \in \mathbb{F}_2^4\) thì mình sẽ có quan sát sau:
Nếu input vi sai là \(0\) thì output vi sai là \(0\) với xác suất \(1\).
Nếu input vi sai là \(1\) thì output vi sai là \(13\) với xác suất \(6 / 16\).
Nếu input vi sai là \(4\) thì output vi sai là \(7\) với xác suất \(6 / 16\).
Nếu input vi sai là \(8\) thì output vi sai là \(5\) với xác suất \(6 / 16\).
Nếu input vi sai là \(15\) thì output vi sai là \(14\) với xác suất \(6 / 16\).
Đây là những output differential với xác suất cao nhất ứng với mỗi input differential cố định \(\boldsymbol{a} \oplus \boldsymbol{b}\).
Điều đó có nghĩa là cứ trung bình \(16\) cặp \(\boldsymbol{a} \oplus \boldsymbol{b}\) cho kết quả là \(1\) thì có \(6\) cặp cho output differential là \(13\).
Tận dụng điều này, chúng ta sẽ giải bài tetraethyllead.
Giả sử \((P, C)\) và \((P', C')\) là hai cặp plaintext-ciphertext sao cho khi input differential \(P \oplus P'\) cố định thì xác suất xảy ra của output differential \(C \oplus C'\) cao nhất. Khi tìm được input và output differential như vậy, ta mã hóa nhiều plaintext khác nhau và khả năng (xác suất) xuất hiện ciphertext tương ứng thỏa mãn differential đó sẽ cao.
Giả sử \(P = (L_0, R_0)\) và \(P' = (L'_0, R'_0)\) là hai nửa trái phải tương ứng với \(P\) và \(P'\).
Đặt \(\Delta L_{in} = L_0 \oplus L'_0\) và \(\Delta R_{in} = R_0 \oplus R_0\) là input differential trước khi mã hóa.
Đặt \(\Delta L_{out} = L_7 \oplus L'_7\) và \(\Delta_{in} = R_7 \oplus R'_7\) là output differential sau khi mã hóa.
Chúng ta sẽ đi qua từng hàm để xem với input-output differential nào thì khả năng xảy ra là cao nhất.
Differential vòng 1¶
Sau vòng \(1\) ta có:
\(L_1 = R_0\) và \(R_1 = L_0 \oplus r_2(R_0, S_2)\).
\(L'_1 = R'_0\) và \(R'_1 = L'_0 \oplus r_2(R'_0, S_2)\).
Khi đó differential ở vòng \(1\) là:
Như vậy \(\Delta R_1\) phụ thuộc vào vi sai của hàm \(r_2\).
def r2(i, box):
out = []
i = long_to_bytes(i)
for byte in i:
out.append(box[byte])
for idx in range(len(out) - 2, -1, -1):
out[idx] ^= out[idx + 1]
return bytes_to_long(b"".join([long_to_bytes(l) for l in out]))
Giả sử bốn bytes đầu vào của \(r_2\) là \(a \Vert b \Vert c \Vert d\). Tiếp theo ta thay thế bốn bytes này bởi giá trị S-box của nó là \(S_2(a) \Vert S_2(b) \Vert S_2(c) \Vert S_2(d)\). Vòng lặp thứ hai XOR chồng các bytes lên nhau để có kết quả:
Như vậy nếu \(R_0 = a \Vert b \Vert c \Vert d\) và \(R'_0 = a' \Vert b' \Vert c' \Vert d'\) thì:
Dễ thấy rằng nếu chúng ta chọn \(d = d'\) thì byte cuối triệt tiêu.
Tiếp theo chọn \(c = c'\) thì byte kế cuối cũng triệt tiêu.
Tiếp theo chọn \(b = b'\) thì byte thứ ba (từ phải sang trái) cũng triệt tiêu.
Khi đó vi sai sẽ là
Bằng một cách ảo ma nào đó thì output differential \(S_2(a) \oplus S_2(a') = 0x80\) có xác suất xảy ra cao nhất khi input differential là \(0x80\). Cái này writeup nói nhưng chúng ta cũng có thể kiểm tra phân bố vi sai của \(r_2\).
Đi ngược lên trên thì \(a \Vert b \Vert c \Vert d \oplus a' \Vert b' \Vert c' \Vert d' = 80 \Vert 00 \Vert 00 \Vert 00\). Đây chính là vi sai cho \(R_0 \oplus R_0'\).
Như vậy \(\Delta L_1 = 0x80000000\) (với xác suất là \(1\)) và \(\Delta R_1 = L_0 \oplus L_0' \oplus 0x80000000\) (với xác suất cao).
Differential vòng 2¶
Tương tự, đối với \(r_1\) chúng ta cũng dùng phương pháp tương tự.
Sau vòng \(2\) ta có:
\(L_2 = R_1\) và \(R_2 = L_1 \oplus r_1(R_1, S_1)\);
\(L'_2 = R'_1\) và \(R'_2 = L'_1 \oplus r_1(R'_1, S_1)\).
Khi đó differential ở vòng \(2\) là:
với xác suất cao.
Tương tự
Khi này, \(R_1 \oplus R_1'\) rất khó kiểm soát nên chúng ta sẽ khiến \(R_1 = R_1'\). Khi đó \(r_1(R_1, S_1) \oplus r_1(R_1', S_1) = 00\) với xác suất bằng \(1\).
Nếu \(R_1 = R_1'\) thì quay ngược lên trên, \(\Delta R_1 = 00 = L_0 \oplus L_0' \oplus 0x80000000\) nên \(L_0 \oplus L_0' = 0x80000000\).
Như vậy mình đã tìm được input differential cho cả hàm mã hóa là \(L_0 \oplus L_0' = 0x80000000\) và \(R_0 \oplus R_0' = 0x80000000\).
Lúc này, differential ở vòng \(2\) có xác suất xảy ra cao nhất là \(L_2 \oplus L_2' = 0x00000000\) và \(R_2 \oplus R_2' = 0x80000000\).
Tiếp theo, mình cần biết output differential nào của toàn bộ hàm encrypt sẽ có khả năng xảy ra nhất đối với input differential này.
Hàm z345¶
def r345(word, k, rnum):
word ^= rrot(word, -463 + 439 * rnum + -144 * rnum**2 + 20 * rnum**3 - rnum**4) ^ lrot(word, 63 + -43 * rnum + 12 * rnum**2 + -rnum**3)
word = (4124669716 + word * bytes_to_long(k))**3
word ^= word << 5
word ^= word << 5
word ^= rrot(word, -463 + 439 * rnum + -144 * rnum**2 + 20 * rnum**3 - rnum**4) ^ lrot(word, 63 + -43 * rnum + 12 * rnum**2 + -rnum**3)
return rrot(word, -504 + 418 * rnum -499 * rnum**2 + -511 * rnum**3 + 98 * rnum**4) & 0xffffffff
Khi thay các giá trị rnum vào thì mình thấy có \(3\) vòng rrot và lrot ngược nhau (rrot(word, 17) và lrot(word, 15) trên \(32\) bit) nên ở những vòng này rrot và lrot sẽ triệt tiêu nhau do đa thức.
Tiếp theo, word ^= word << 5 sẽ không làm thay đổi differential \(0x80\). Lấy ví dụ với \(8\) bit \(\bar{a} = a_0 a_1 a_2 a_3 a_4 a_5 a_6 a_7\) và \(\bar{b} = b_0 b_1 b_2 b_3 b_4 b_5 b_6 b_7\). Giả sử \(\bar{a} \oplus \bar{b} = 0x80\) thì:
Cuối cùng, phép nhân modulo \(2^{32}\) có \(50\%\) duy trì differential \(0x80000000\) và do đó differential này vẫn có xác suất cao cho cả z345.
Giải¶
Chiến thuật để giải bài này là:
Gửi lên các cặp plaintext sao cho \(\Delta L_{in} = 0x80000000\) và \(\Delta R_{in} = 0x80000000\).
Nhận các cặp ciphertext tương ứng thỏa mãn \(\Delta L_{out} \oplus R_{out} = 0x80000000\).
Các cặp plaintext, ciphertext như trên sẽ giúp ta khôi phục lại khóa.
Note. Để thuận tiện thì mình sẽ cố định khóa trong server.py và chỉ cần tìm ra khóa là xong. Ở trong giải thì sau khi request đủ \(1024\) lần encrypt server cũng không đặt timeout nên chúng ta có thể để script chạy bao lâu tùy ý.
File solve.py sau đây tương tác với server.py để lấy về các cặp plaintext, ciphertext thỏa mãn điều kiện trên.
Sau đó sử dụng thư viện SHA256 từ project SHA256 (gồm file SHA256.h và SHA256.cpp).
Chúng ta cần viết solve.h chứa định nghĩa các hàm sẽ dùng để tìm khóa.
Đầu tiên chúng ta sẽ khôi phục k2 đi ngược từ ciphertex lên. Chúng ta nhận các khóa thỏa mãn \(\Delta L_6 \oplus \Delta R_6 = 0x80000000\) (vòng \(6\)). Để tìm k2 thì hàm main sẽ là:
int main()
{
std::vector<uint32_t> key2 = bruteforce_k2();
for (int i = 0; i < key2.size(); i++)
std::cout << std::hex << key2[i] << std::endl;
return 0;
}
Sau đó với mỗi k2 chúng ta bruteforce các k1 và kiểm tra k = k1 || k2 nào sẽ encrypt đúng. Ở đây do mình đã cố định khóa ở server.py nên mình biết k2 nào là đúng để tiết kiệm thời gian viết lại writeup. Sau đó thì chỉ cần bruteforce k1 thôi.
int main()
{
uint8_t k2[] = { 0xef, 0x13, 0x37, 0xff };
get_sbox(k2, sbox2);
uint64_t p = 2194090266659289430ULL;
uint64_t c = 5313144679078469543ULL;
#pragma omp for
for (uint64_t k1 = 0; k1 < 0xffffff; k1++)
{
uint64_t key = (k1 << 32) | 0xef1337ff;
if (encrypt(p, key) == c)
{
std::cout << "Found key: " << std::hex << key << std::endl;
}
}
return 0;
}
Cám ơn các bạn đã đọc writeup dài lê thê của mình.