Amateurs CTF 2023¶
Minimalaestic¶
Đề bài ở aes.py.
Phân tích hiện trường¶
Đây là một bài AES nhưng trên ma trận \(2 \times 2\). Ma trận đầu vào có dạng
Các động tác cơ bản giống với AES gốc, bao gồm: add round key, shift rows, mix columns và sub bytes. Đối với vòng cuối sử dụng một biến thể của sub byte, shift rows và add round key. Ở bài này có 100 vòng biến đổi bình thường và 1 vòng cuối sử dụng các biến thể trên.
Sub Bytes và Final Sub Bytes¶
SBox được sử dụng trong bài là SBox của AES gốc. Do đó mình cũng không nghĩ rằng sẽ khai thác được gì ở đây. Ở đây có một điều mình cần nhớ là Sub Bytes biến đổi trên cột đầu, và Final Sub Bytes biến đổi trên cột sau.
Đối với Sub Bytes thì
Đối với Final Sub Bytes thì
Shift Rows và Final Shift Rows¶
Đối với Shift Rows thay đổi vị trí 2 bytes ở cột (?) đầu.
Đối với Final Shift Rows thay đổi vị trí 2 bytes ở cột (?) sau.
Mình thấy rằng phép biến đổi ngược đối với shift rows và final shift rows cũng là chính nó.
Mix Columns¶
Đối với Mix Columns, cột đầu mới sẽ là cột đầu cũ XOR với cột sau.
Tương tự shift rows, phép biến đổi ngược của mix columns cũng là chính nó.
Add Round Keys¶
Phép Add Round Keys ở bài này khá thú vị (mặc dù mình cũng không khai thác từ đó).
def add_round_key(s, k):
for i in range(2):
for j in range(2):
s[i][j] ^= k[k[k[k[i*2+j]%4]%4]%4]
Đối với final add round keys thì chỉ thực hiện phép XOR trên cột sau.
Okay, tới đây thì việc phân tích mã hóa của bài này đã tạm xong và mình cũng không thấy điểm nào có thể dùng để khai thác (hoặc chưa thấy). Điều làm mình quan tâm là hàm schedule_key.
Key Schedule¶
def schedule_key(k):
for i in range(4):
for j in range(2*ROUNDS):
k[i] = pow(pow(sbox[sbox[sbox[((((k[i] << 4) ^ k[i]) << 4) ^ k[i]) % 256]]], pow(k[i], k[i]), 256),
pow(sbox[k[i]], sbox[k[i]]),
256)
def final_schedule(k):
for i in range(4):
k[i] = sbox[k[i]]
Hàm sinh khóa con khá lạ. Do đó mình thử in ra khóa con ở các vòng với một chút điều chỉnh ở hàm encrypt với các khóa được random.
def encrypt(p, k):
ciphertext = b""
for i in split_blocks(p):
key = k.copy()
i = bytes2matrix(i)
add_round_key(i, key)
for j in range(ROUNDS):
schedule_key(key)
print(f"{j}, {key}")
sub_bytes(i)
shift_rows(i)
mix_columns(i)
add_round_key(i, key)
final_schedule(key)
print(f"100, {key}")
final_sub(i)
final_shift(i)
final_add(i, key)
ciphertext += matrix2bytes(i)
return ciphertext
pt = b"haha"
for _ in range(1000):
key = [random.choice(range(256)) for _ in range(4)]
encrypt(pt, key)
Các khóa con trong các vòng từ 0 tới 99 đều có vẻ như nằm trong một tập hợp nhất định là \(\{ 0, 1, 175 \}\). Từ đó khóa con ở vòng 100 (vòng final) cũng nằm trong một tập hợp nhất định do đã đi qua hàm sbox (final_schedule) và kết quả là tập \(\{99, 121, 124 \}\).
Truy tìm đầu mối¶
Nơi cryptanalysis bắt đầu¶
Chiến thuật của mình là tìm khóa trước khi đi vào vòng lặp với known-plaintext là format của flag. Chú ý rằng ở đây không cần phải tìm khóa ban đầu mà chỉ cần tìm khóa trước khi vào vòng lặp, tức là khóa tham gia vào phép XOR add_round_key đầu tiên.
def encrypt(p, k):
ciphertext = b""
for i in split_blocks(p):
key = k.copy()
i = bytes2matrix(i)
add_round_key(i, key)
# Find intermediate key used in add_round_key #
for j in range(ROUNDS):
schedule_key(key)
sub_bytes(i)
shift_rows(i)
mix_columns(i)
add_round_key(i, key)
final_schedule(key)
final_sub(i)
final_shift(i)
final_add(i, key)
ciphertext += matrix2bytes(i)
return ciphertext
Để tìm khóa ở điểm được đánh dấu, mình sẽ đi ngược từ ciphertext lên. Mình bruteforce các khóa con dùng trong vòng lặp (\(3^4 = 81\) trường hợp). Ứng với mỗi khóa con cho vòng lặp mình có một khóa con cho vòng cuối cùng (final). Kết hợp hai khóa đó và ciphertext mình sẽ tìm được state trước khi vào vòng lặp. Cuối cùng mình XOR kết quả đó cho known-plaintext thì sẽ được khóa ở điểm được đánh dấu.
Từ nhận xét bên trên, 100 vòng (0 tới 99) sử dụng cùng một khóa con, mình đặt là \(k_1\). Ở vòng final sử dụng một khóa con, mình đặt là \(k_2\). Quan hệ giữa chúng là k_2 = final_schedule(k_1).
Man-In-The-Middle¶
Với mỗi block \(4\) bytes ciphertext và known-plaintext tương ứng, mình đi ngược từ dưới lên để tìm key trung gian. Lưu ý rằng mình chỉ cần xây dựng bảng inv_sbox vì các phép biến đổi khác có phép biến đổi ngược là chính nó.
final_add(ciphertext, k2_)
final_shift(ciphertext)
inv_final_sub(ciphertext)
for j in range(ROUNDS):
add_round_key(ciphertext, k1_)
mix_columns(ciphertext)
shift_rows(ciphertext)
inv_sub_bytes(ciphertext)
pt = matrix2bytes(plaintext)
ct = matrix2bytes(ciphertext)
key = xor(pt, ct)
Với format flag là amateursCTF{ có 12 bytes tương ứng 3 block, mình thực hiện biến đổi trên với 12 bytes ciphertext tương ứng. Với mỗi block mình sẽ tìm ra được tập hợp các key tương ứng với các \(k_1\) (và \(k_2\) tương ứng với \(k_1\)). Sau đó mình giao các tập hợp key lại sẽ được key ban đầu.
Nói cách khác
candidates1 = set()
candidates2 = set()
candidates3 = set()
for k1 in product(K1, repeat=4):
k2 = final_schedule_(list(k1))
k1_ = list(k1).copy()
k2_ = list(k2).copy()
# Phase 1
plaintext = bytes2matrix(flag[:4])
ciphertext = bytes2matrix(ctx[:4])
final_add(ciphertext, k2_)
final_shift(ciphertext)
inv_final_sub(ciphertext)
for j in range(ROUNDS):
add_round_key(ciphertext, k1_)
mix_columns(ciphertext)
shift_rows(ciphertext)
inv_sub_bytes(ciphertext)
pt = matrix2bytes(plaintext)
ct = matrix2bytes(ciphertext)
key = xor(pt, ct)
candidates1.add(bytes(key))
# Phase 2
plaintext = bytes2matrix(flag[4:8])
ciphertext = bytes2matrix(ctx[4:8])
final_add(ciphertext, k2)
final_shift(ciphertext)
inv_final_sub(ciphertext)
for j in range(ROUNDS):
add_round_key(ciphertext, k1_)
mix_columns(ciphertext)
shift_rows(ciphertext)
inv_sub_bytes(ciphertext)
pt = matrix2bytes(plaintext)
ct = matrix2bytes(ciphertext)
key = xor(pt, ct)
candidates2.add(bytes(key))
# Phase 3
plaintext = bytes2matrix(flag[8:12])
ciphertext = bytes2matrix(ctx[8:12])
final_add(ciphertext, k2_)
final_shift(ciphertext)
inv_final_sub(ciphertext)
for j in range(ROUNDS):
add_round_key(ciphertext, k1_)
inv_mix_columns(ciphertext)
inv_shift_rows(ciphertext)
inv_sub_bytes(ciphertext)
pt = matrix2bytes(plaintext)
ct = matrix2bytes(ciphertext)
key = xor(pt, ct)
candidates3.add(bytes(key))
key = list(candidates1.intersection(candidates2).intersection(candidates3))
print(key)
Kết quả khi giao ba tập hợp chỉ có đúng một key b'\x00**\x00'. Quá tốt!!!
Ờ mà khoan, từ từ đã :)))) Có gì đó không đúng lắm. Cụ thể là khi mình encrypt hai block plaintext đầu thì nó không ra đúng ciphertext. Cụ thể hơn nữa, encrypt ra đúng ở vị trí 0 và 2, sai ở vị trí 1 và 3 cho mỗi block (?!?!).
Sửa chữa lỗi lầm¶
Mình mất cả ngày để tìm lỗi sai nhưng thất bại. Và mình đã chuyển sang tấn công cưỡng ép. Vì encrypt đúng ở vị trí 0 và 2 còn sai ở vị trí 1 và 3 nên mình kết luận được là \(k_2\) có vấn đề, tức là key ở bước final_add.
Mình thử in ra \(k_1\) và \(k_2\) tương ứng với khóa tìm được bên trên b'\x00**\x00'.
for k1 in product(K1, repeat=4):
k2 = final_schedule_(list(k1))
k1_ = list(k1).copy()
k2_ = list(k2).copy()
# Phase 1
plaintext = bytes2matrix(flag[:4])
ciphertext = bytes2matrix(ctx[:4])
final_add(ciphertext, k2_)
final_shift(ciphertext)
inv_final_sub(ciphertext)
for j in range(ROUNDS):
add_round_key(ciphertext, k1_)
mix_columns(ciphertext)
shift_rows(ciphertext)
inv_sub_bytes(ciphertext)
pt = matrix2bytes(plaintext)
ct = matrix2bytes(ciphertext)
key = xor(pt, ct)
candidates1.add(bytes(key))
if bytes(key) == b'\x00**\x00':
print(k1, k2)
Hai trường hợp có thể xảy ra cho cặp \((k_1, k_2)\) là \(([1, 0, 0, 1], [124, 99, 99, 124])\) và \(([1, 0, 175, 1], [124, 99, 121, 124])\). Mình chỉ cần xét trường hợp 1 là được.
Khi nhìn vào hàm final_add thì mình biết chắc rằng k[k[k[k[i*2+1]]] chắc chắn nằm trong [124, 99] nên mình bốc đại \(k_2 = [124, 124, 124, 124]\), và nó đã thành công (????).
Hàm decrypt mình fix cứng \(k_1\) và \(k_2\) luôn, và decrypt ra toàn bộ flag ban đầu.
def decrypt(c, k):
plaintext = b""
for i in split_blocks(c):
key = k.copy()
k1, k2 = [1, 0, 0, 1], [124, 124, 124, 124]
i = bytes2matrix(i)
final_add(i, k2)
final_shift(i)
inv_final_sub(i)
for j in range(ROUNDS):
add_round_key(i, k1)
mix_columns(i)
shift_rows(i)
inv_sub_bytes(i)
plaintext += bytes(xor(matrix2bytes(i), key))
return plaintext
# b'amateursCTF{th1s_1s_wh4t_bad_k3y_sch3dul1ng_d03s_t0_a_p3rson_109bcd1f}\x02\x02.
Nếu bạn nhìn thấy được điểm sai nào đó trong bài làm của mình dẫn tới tấn công cưỡng ép thì có thể nói cho mình biết. Thực sự thì mình không biết mình đang lag chỗ nào :confused:
Owo Time Pad¶
Đề bài ở file main.py.
Bài này sẽ random một key có độ dài là số nguyên tố cùng nhau với độ dài của plaintext. Đặt \(l\) là độ dài plaintext và \(n\) là độ dài key. Chương trình tạo key mới bằng cách lặp lại key cũ \(l\) lần, tương tự plaintext mới sẽ là plaintext cũ lặp lại \(n\) lần. Chú ý rằng \(\gcd(l, n) = 1\), điều này rất quan trọng giải bài này.
Khi factor độ dài của ciphertext thì mình thấy có hai khả năng xảy ra của độ dài key là 32 hoặc 79. Mình giải với \(n = 79\) (sai thì quay lại làm 32 :v).
Như một thói quen, để xử lý các bài toán với số lớn mình thường xem xét những trường hợp số nhỏ để xem mối liên hệ giữa chúng.
Giả sử \(l = 5\) và \(n =3\). Đặt key là \(\bm{k} = (k_0, k_1, k_2)\) và \(\bm{P} = (p_0, p_1, p_2, p_3, p_4)\).
Khi đó ciphertext sẽ được ghép cặp XOR như sau
Nhìn vào \(k_0\), mình thấy rằng \(k_0\) tác động lần lượt lên \(p_0\), \(p_3\), \(p_1\), \(p_4\) và \(p_2\), tương ứng với các ciphertext \(c_0\), \(c_3\), \(c_6\), \(c_9\) và \(c_{12}\). Như vậy mình chỉ cần sắp xếp lại \(p_0\), \(p_3\), ... về đúng vị trí của nó là được.
Vì \(\gcd(l, n) = 1\) nên mình nhớ tới một tính chất mà chúng ta hay dùng để chứng minh định lý Wilson hoặc Euler là nếu \(\{ g_1, g_2, \ldots, g_{\phi(n)} \}\) là hệ thặng dư thu gọn modulo \(n\) và \(a\) là số sao cho \(\gcd(a, n) = 1\) thì tập
cũng là hệ thặng dư thu gọn modulo \(n\). Nói cách khác hai tập hợp
là hoán vị của nhau.
Mình thử như sau:
với \(i = 0\) thì \(0 \cdot 3 = 0 \bmod 5\);
với \(i = 1\) thì \(1 \cdot 3 = 3 \bmod 5\);
với \(i = 2\) thì \(2 \cdot 3 = 1 \bmod 5\);
với \(i = 3\) thì \(3 \cdot 3 = 4 \bmod 5\);
với \(i = 4\) thì \(4 \cdot 3 = 2 \bmod 5\).
Nhìn chuỗi \((0, 3, 1, 4, 2)\) quen quen. Đó chính là \(p_0\), \(p_3\), \(p_1\), \(p_4\), \(p_2\) ở trên.
Như vậy mình có công thức tổng quát là \(p_{i \cdot 3 \bmod 5} = c_{i \cdot 3}\), hay tổng quát hơn \(p_{i \cdot n \bmod l} = c_{i \cdot n}\) với \(i = 0, 1, \ldots, l-1\).
Sau đó mình chỉ cần bruteforce 256 trường hợp \(k_0\) nữa. Ở đây mình thấy với \(k_0 = 165\) thì có chuỗi PNG (?).
Như vậy XOR với \(165\) sẽ có flag. Code giải mình để ở main.py.
Okay vậy là xong bài.