<h1 style="text-align:center; color:#96811d">
PicoCTF Walkthrough: Part 3
</h1>
Dưới đây là các lời giải cho một số thử thách của **picoCTF** mà mình cảm thấy thú vị và hữu ích.
Phần này tiếp tục là những bài với độ khó **Hard**, tuy nhiên lần này ta sẽ giải những bài có ít lời giải hơn một chút so với những bài trước nên độ khó cũng sẽ cao hơn một chút.
## Double DES
:::spoiler <b>ddes.py</b>
```python=
#!/usr/bin/python3 -u
from Crypto.Cipher import DES
import binascii
import itertools
import random
import string
def pad(msg):
block_len = 8
over = len(msg) % block_len
pad = block_len - over
return (msg + " " * pad).encode()
def generate_key():
return pad("".join(random.choice(string.digits) for _ in range(6)))
FLAG = open("flag").read().rstrip()
KEY1 = generate_key()
KEY2 = generate_key()
def get_input():
try:
res = binascii.unhexlify(input("What data would you like to encrypt? ").rstrip()).decode()
except:
res = None
return res
def double_encrypt(m):
msg = pad(m)
cipher1 = DES.new(KEY1, DES.MODE_ECB)
enc_msg = cipher1.encrypt(msg)
cipher2 = DES.new(KEY2, DES.MODE_ECB)
return binascii.hexlify(cipher2.encrypt(enc_msg)).decode()
print("Here is the flag:")
print(double_encrypt(FLAG))
while True:
inputs = get_input()
if inputs:
print(double_encrypt(inputs))
else:
print("Invalid input.")
```
:::
Bài này về cơ bản sẽ dùng mã hóa **flag** của chúng ta bằng hai lần <a href="https://en.wikipedia.org/wiki/Data_Encryption_Standard"><b>DES</b></a> với hai loại khóa khác nhau, chúng ta có thể gửi bất kỳ văn bản rõ nào cho **server** để nhận về văn bản mã tương ứng.
Để giải bài này, chúng ta sẽ tiến hành thực hiện tấn công xen giữa (<a href="https://en.wikipedia.org/wiki/Man-in-the-middle_attack"> man-in-the-middle attack</a>). Ta để ý rằng không gian khóa không quá lớn (số phần tử của tập không gian khóa $\mathcal{K}$ là $|\mathcal{K}| = 10^6$), vì vậy ta sẽ tiến hành thu thập một cặp văn bản rõ và văn bản mã tương ứng, sau đó tiến hành **brute-force** cho đến khi ta tìm được hai cặp khóa `KEY1` và `KEY2` mà server đã sử dụng là được.
Nếu ta brute-force ngây thơ, tức là mỗi `KEY1` ta brute-force, ta lại tiến hành brute-force hết `KEY2` thì ta sẽ mất $(10^{6})^2 = 10^{12}$ lần lặp tất cả, điều này khiến cho việc tìm kiếm rất là lâu và không thực tế trong các cuộc thi CTF. Do đó, chúng ta sẽ brute-force một cách thông minh hơn, đó là kết hợp với **tìm kiếm trùng khớp**!
Cụ thể, theo đề bài ta có công thức:
$$
C = E_{K_2}(E_{K_1}(P)) \Leftrightarrow D_{K_2}(C) = E_{K_1}(P).
$$
Nhìn qua thì tưởng chừng chỉ là một biến đổi tương đương đơn giản nhưng nó đã cho chúng ta một cách brute-force thông minh hơn với số lần lặp chỉ còn khoảng $10^6$.
Cụ thể, chúng ta sẽ brute-force một `key` duy nhất, với mỗi key, ta sẽ lưu lại giá trị của $D_K(C)$ vào một **dictionary** `encrypt_list` và giá trị của $E_K(P)$ vào một **dictionary** `decrypt_list`. Sau đó, ta sẽ tiến hành tìm ra những giá trị trùng nhau của `encrypt_list` và `decrypt_list`. Trong những giá trị trùng nhau này, chúng ta lại lấy ra $K_1$ và $K_2$ từ hai **dictionary** và tiến hành tìm $\text{flag} = D_{K_1}(D_{K_2}(C_{\text{flag}}))$, và chúng ta đã tìm ra **flag** 🥳.
Dưới đây là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#96811d">solution.py</b>
```python=
from pwn import remote
from tqdm import trange
from Crypto.Cipher import DES
def pad(msg):
block_len = 8
over = len(msg) % block_len
pad = block_len - over
return (msg + " " * pad).encode()
HOST = "mercury.picoctf.net"; PORT = 29980
connection = remote(HOST, PORT)
connection.recvuntil(b"Here is the flag:\n")
encrypted_flag = bytes.fromhex(connection.recvline().strip().decode())
connection.recvuntil(b"What data would you like to encrypt? ")
chosen_plaintext = b"0160ca14"
connection.sendline(f"{chosen_plaintext.hex()}".encode())
ciphertext = bytes.fromhex(connection.recvline().strip().decode())
connection.close()
encrypt_list = {}; decrypt_list = {}
for key in trange(10**6, desc="Collecting keys..."):
KEY = pad(f"{key:06}")
cipher = DES.new(KEY, DES.MODE_ECB)
encrypt_plaintext = cipher.encrypt(pad(chosen_plaintext.decode()))
encrypt_list[encrypt_plaintext] = KEY
decrypt_ciphertext = cipher.decrypt(ciphertext)
decrypt_list[decrypt_ciphertext] = KEY
encrypt_set = set(encrypt_list.keys())
decrypt_set = set(decrypt_list.keys())
intermediate_set = encrypt_set.intersection(decrypt_set)
for intermediate_text in intermediate_set:
KEY1, KEY2 = encrypt_list[intermediate_text], decrypt_list[intermediate_text]
cipher1 = DES.new(KEY1, DES.MODE_ECB)
cipher2 = DES.new(KEY2, DES.MODE_ECB)
flag = cipher1.decrypt(cipher2.decrypt(encrypted_flag))
if(flag.isascii()):
print("[!] Got flag:", flag.strip().decode())
break
# [!] Got flag: 45d6631b0c4d52b801a0fa7f6d3bda3c
```
:::
:::success
**Flag: 45d6631b0c4d52b801a0fa7f6d3bda3c**
:::
## Clouds
:::spoiler <b>clouds.py</b>
```python=
#!/usr/bin/python2 -u
import binascii
ROUNDS = 5
BLOCK_LEN = 8
HEX_BLOCK_LEN = BLOCK_LEN * 2
MAX_NOTES = 2048
MAX_NOTE_LEN = 512
def pad(p):
if len(p) % BLOCK_LEN != 0:
return p + "\0" * (BLOCK_LEN - (len(p) % BLOCK_LEN))
else:
return p
def g(i):
b = bin(i).lstrip("0b").rstrip("L").rjust(BLOCK_LEN * 8, "0")
return int(b[::-1], 2)
def encrypt_block(b):
k = open("./key").read().rstrip()
assert (len(b) * ROUNDS) == len(k)
result = int(binascii.hexlify(b), 16)
for i in range(ROUNDS):
key = int(binascii.hexlify(k[i * BLOCK_LEN:(i + 1) * BLOCK_LEN]), 16)
key_odd = key | 1
result ^= key
result = g(result)
result = (result * key_odd) % (1 << 64)
return hex(result).lstrip("0x").rstrip("L").rjust(HEX_BLOCK_LEN, "0")
def encrypt(msg):
plain = pad(msg)
result = ""
for i in range(0, len(plain), BLOCK_LEN):
result += encrypt_block(plain[i:i + BLOCK_LEN])
return result
def menu(n):
notes = n
print("""
1) Store
2) Retrieve
Anything else to quit
""")
ui = raw_input("Selection? ").rstrip()
if ui == "1":
if len(notes) >= MAX_NOTES:
print("Max capacity")
return notes
ui = raw_input("Give me a note to encrypt: ").rstrip()
try:
msg = binascii.unhexlify(ui)
except:
print("Invalid input.")
return notes
if len(msg) > MAX_NOTE_LEN:
print("Invalid input.")
else:
notes.append(encrypt(msg))
elif ui == "2":
ui = raw_input("What index would you like to read? ").rstrip()
try:
index = int(ui)
except:
print("Invalid index.")
return notes
if index >= 0 and index < len(notes):
print(notes[index])
else:
print("Invalid index.")
else:
return None
return notes
art = """
.
|
. /
\ I
/
\ ,g88R_
d888(` ). _
- --== 888( ).=-- .+(` )`.
) Y8P( '`. :( . )
.+(`( . ) .-- `. ( ) )
(( (..__.:'-' .=( ) ` _` ) )
`. `( ) ) ( . ) ( ) ._
) ` __.:' ) ( ( )) `-'.:(` )
) ) ( ) --' `- __.' :( ))
.-' (_.' .') `( ) ))
(_ ) ` __.:'
--..,___.--,--'`,---..-.--+--.,,-,,..._.--..-._.-a:f--.
"""
print(art)
print("I love cloud watching, so I made a place to store all my notes about them.")
flag = open("./flag").read().rstrip()
notes = [encrypt(flag)]
notes = menu(notes)
while notes:
notes = menu(notes)
```
:::
Nhìn qua đề bài thì thấy đây là một mã hóa khối kỳ lạ, sau khi tìm kiếm trên mạng thì mình phát hiện đây là mã hóa khối **Nimbus**, được tạo ra bởi **Alexis Machado** vào năm 2000. Đây là trang web wikipedia nói ngắn gọn về mã hóa này [ở đây](https://en.wikipedia.org/wiki/Nimbus_(cipher)).
Tiếp theo, ta chú ý về phần tham khảo, ở mục số 2 có một file trông khá hay nên ta sẽ thử tìm kiếm nó trên mạng thử xem. Sau một hồi tìm kiếm, mình đã tìm được bài báo đó [Tại đây](https://link.springer.com/content/pdf/10.1007/3-540-45473-x_16.pdf).
Đọc qua bài báo này thì nó giống hệt như mã hóa của file thử thách này! Hơn hết nữa, nó còn trình bày các phá mã đối với loại mã hóa khối này, tuy nhiên vì chúng quá phức tạp nên mình lấy luôn đoạn mã [**ở đây**](https://dhrumilp15.medium.com/cracking-the-nimbus-cipher-with-differential-cryptanalysis-picoctf-21-clouds-e3c92406bb73) (đường link này cũng giải thích chi tiết về lời giải nên bạn nào muốn tìm hiểu sâu hơn thì có thể vào đây để đọc) và giải quyết chúng nhanh gọn lẹ luôn.
Bài này chỉ giành cho những ai thiên hướng nghiên cứu mật mã học nên mình cũng không mặn mà tìm hiểu sâu về nó cho lắm.
Dưới đây là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#96811d">solution.py</b>
```python=
from __future__ import division
from __future__ import print_function
import binascii
import random
from collections import Counter
from itertools import repeat
from pwn import *
from termcolor import cprint
from tqdm import trange
ROUNDS = 5
BLOCK_LEN = 8
HEX_BLOCK_LEN = BLOCK_LEN * 2
MAX_NOTES = 2048
MAX_NOTE_LEN = 512
def pad(p):
'''Output item of size 8, 0s at the end if necessary'''
if len(p) % BLOCK_LEN != 0:
return p + b"\0" * (BLOCK_LEN - (len(p) % BLOCK_LEN))
else:
return p
def g(i):
'''reverses binary number, outputs 64-digit binary number'''
b = bin(i).lstrip("0b").rstrip("L").rjust(BLOCK_LEN * 8, "0")
return int(b[:: -1], 2) # 64-digit number
def encrypt_block(b):
k = open("./key").read().rstrip()
assert (len(b) * ROUNDS) == len(k) # len(k) == 40
result = int(binascii.hexlify(b), 16)
for i in range(ROUNDS):
key = int(binascii.hexlify(
k[i * BLOCK_LEN: (i + 1) * BLOCK_LEN].encode()), 16)
key_odd = key | 1
result ^= key
result = g(result)
result = (result * key_odd) % (1 << 64)
return hex(result).lstrip("0x").rstrip("L").rjust(HEX_BLOCK_LEN, "0")
def encrypt(msg):
plain = pad(msg)
result = ""
assert len(plain) == BLOCK_LEN
for i in range(0, len(plain), BLOCK_LEN):
result += encrypt_block(plain[i: i + BLOCK_LEN])
return result
def comp(msg, index):
'''Complements the value at index in msg. Returns a list'''
msg[index] = '1' if msg[index] == '0' else '0'
return msg
def egcd(a, b):
x, y, u, v = 0, 1, 1, 0
while a != 0:
q, r = b//a, b % a
m, n = x-u*q, y-v*q
b, a, x, y, u, v = a, r, u, v, m, n
gcd = b
return gcd, x, y
def condition1(ciphertexts):
'''
Takes ciphertexts directly from the remote connection
Returns hex ciphertexts that pass the condition
'''
precandidates = []
thirdLSBis1 = 0
thirdLSBis0 = 0
for ctext in ciphertexts:
ci0, ci1 = map(int, ctext, repeat(16))
cxor = ci0 ^ ci1
cb0 = f'{ci0:064b}'
cb1 = f'{ci1:064b}'
cbxor = f'{cxor:064b}'
if cbxor[-2:] != '10' or cb0[-1] != '0' or cb1[-1] != '0':
continue
precandidates.append(ctext)
if cbxor[-3] == '1':
thirdLSBis1 += 1
else:
thirdLSBis0 += 1
candidates = [] # GOOD VALUES
noncandidates = [] # BAD VALUES
# THE 3rd LSB OF GOOD VALUES SHOULD BE THE MODE OF THE 3rd LSBs
if thirdLSBis1 >= thirdLSBis0:
defining3rdlsb = '1'
else:
defining3rdlsb = '0'
for pre in precandidates:
ci0, ci1 = map(int, pre, repeat(16))
cxor = ci0 ^ ci1
cbxor = f'{cxor:064b}'
if cbxor[-3] == defining3rdlsb:
candidates.append(pre)
else:
noncandidates.append(pre)
return candidates, noncandidates
n = 64
sdiff = list('0' + '1' * (n - 2) + '0') # 011110 <-- (n - 2) 1's
diff = int(''.join(sdiff), 2) # 011110 <-- (n - 2) 1's
assert diff == 2**63 - 2
def create_plaintexts():
plaintexts = []
for i in range(32):
binp = ['0']
for i in range(62):
binp.append(str(random.randint(0, 1)))
binp.append('0')
p = ''.join(binp) # binary string of plaintext
xorp = int(p, 2) ^ diff
bxorp = list(f'{xorp:064b}')
# plaintext, plaintext xor diff
plaintexts.append([p, ''.join(bxorp)])
# plaintext, complement MSB of plaintext
binp = comp(binp, 0)
bxorp = comp(bxorp, 0)
plaintexts.append([''.join(binp), ''.join(bxorp)])
# plaintext, complement MSB AND LSB of plaintext
binp = comp(binp, -1)
bxorp = comp(bxorp, -1)
plaintexts.append([''.join(binp), ''.join(bxorp)])
# plaintext, complement LSB of plaintext
binp = comp(binp, 0)
bxorp = comp(bxorp, 0)
plaintexts.append([''.join(binp), ''.join(bxorp)])
return plaintexts
connection = remote("mercury.picoctf.net", 24402)
counter = 1
def encryptp(msg):
global connection, counter
connection.sendlineafter(b"Selection? ", b"1")
connection.sendlineafter(b"Give me a note to encrypt: ", msg.encode())
connection.sendlineafter(b"Selection? ", b"2")
connection.sendlineafter(b"What index would you like to read? ", str(2 - (counter % 2)).encode())
counter += 1
receive = connection.recvline().rstrip().decode()
print(f"{counter - 1:<3}", receive)
return receive
def get_ciphertexts(plaintexts, online=True):
global connection
ciphertexts = []
for plain in plaintexts:
fin = []
for idx in range(len(plain)):
p = plain[idx]
assert len(p) == 64
p = ''.join([f"{int(p[i : i+BLOCK_LEN], 2):02x}"
for i in range(0, len(p), BLOCK_LEN)])
assert len(p) == 16
if online:
fin.append(encryptp(p))
else:
p = binascii.unhexlify(p)
fin.append(encrypt(p))
ciphertexts.append(fin)
connection.close()
connection = remote("mercury.picoctf.net", 24402)
assert len(ciphertexts) == len(plaintexts)
return ciphertexts
def rev_multiply(ciphertexts):
candidates, noncandidates = condition1(ciphertexts)
gcdd, key_scaler, _ = egcd(diff, 1 << 64)
keycounter = Counter()
for cand in candidates:
ci1, ci2 = map(int, cand, repeat(16))
if (ci1 + ci2) % 2 != 0 or ci1 ^ ci2 == diff:
continue
kodd = (((ci1 + ci2) // gcdd) * key_scaler) % (1 << 64)
kcomp = int(''.join(comp(list(f'{kodd:064b}'), 0)), 2)
keycounter[kodd] += 1
keycounter[kcomp] += 1
return keycounter.most_common(1)
def crack_subkey(ciphertexts):
k_pair = rev_multiply(ciphertexts)
if len(k_pair) < 1:
return None
k_odd, conf = k_pair[0]
# Cracking the subkey is a deterministic process
# If the confidence in the calculated subkey is too low, we have to try
# different keys
if conf <= 1:
return None
kcomp = int(''.join(comp(list(f'{k_odd:064b}'), 0)), 2)
return [k_odd, kcomp, k_odd ^ 1, kcomp ^ 1]
def recurse(plaintexts, ciphertexts, kcands, keyers=[], depth=1):
if depth > 5:
return None, None
for k in kcands:
dciphertexts = ciphertexts[:]
# DECRPYT CIPHERTEXTS WITH THE CURRENT KEY
for pair in trange(len(dciphertexts)):
ci1, ci2 = map(int, dciphertexts[pair], repeat(16))
# undo modular multiplication by odd-ed key, reversal,
# xor by guessed key
ci1 = g((ci1 * pow(k | 1, -1, 1 << 64)) % (1 << 64)) ^ k
ci2 = g((ci2 * pow(k | 1, -1, 1 << 64)) % (1 << 64)) ^ k
dciphertexts[pair] = [hex(ci1)[2:], hex(ci2)[2:]]
# If the decrypted ciphertexts are the same as the plaintext, we're done!
if all([int(dciphertexts[i][j], 16) == int(plaintexts[i][j], 2)
for j in range(0, 2) for i in range(len(dciphertexts))]):
return dciphertexts, [k] + keyers
# SOLVE FOR THE NEXT ODD-ED KEY
dkcands = crack_subkey(dciphertexts)
if dkcands is None:
continue
v = recurse(plaintexts, dciphertexts,
dkcands, [k] + keyers, depth + 1)
if v is not None:
return v
def attack(online=True):
while True:
# creating plaintexts is a random process
plaintexts = create_plaintexts()
assert len(plaintexts) == 128
ciphertexts = get_ciphertexts(plaintexts, online)
assert len(ciphertexts) == 128
kcands = crack_subkey(ciphertexts)
if kcands is None:
continue
break
dciphertexts, keyers = recurse(plaintexts, ciphertexts, kcands)
if dciphertexts is not None and keyers is not None:
return keyers
def decrypt(ciphertext, keys):
result = ""
for i in range(0, len(ciphertext), HEX_BLOCK_LEN):
block = int(ciphertext[i: i + HEX_BLOCK_LEN], 16)
# undo modular multiplication by odd-ed key, reversal, xor by guessed key
for k in keys[::-1]:
block = (g(((block % (1 << 64)) * (pow(k | 1, -1, 1 << 64) %
(1 << 64))) % (1 << 64)) ^ k) % (1 << 64)
result += hex(block)[2:]
return result
connection.sendlineafter(b"Selection? ", b"2")
connection.sendlineafter(b"What index would you like to read? ", b'0')
flag = connection.recvline().rstrip().decode()
cprint(f"Encrypted Flag: {flag}", 'red')
keyers = attack()
cprint("Subkeys: " + str(keyers), 'blue')
fullkey = []
for k in keyers:
hexkey = hex(k)[2:]
for hc in range(0, len(hexkey) - 1, 2):
fullkey.append(chr(int(hexkey[hc:hc+2], 16)))
fullkey = ''.join(fullkey)
cprint("Full key: " + fullkey, 'blue')
cprint("Plaintext: " + bytearray.fromhex(decrypt(flag, keyers)).decode(), 'green')
connection.close()
# Subkeys: [4990608929225721186, 7297316171674891571, 7008498656364217668, 3617857495015437926, 7221599192469485877]
# Full key: EB4a7dEbeEFe2e53aC0e5dED25696a6fd8F41d95
# Plaintext: 89bd63caf70f3c58375571b8a91313bb
```
:::
:::success
**Flag: 89bd63caf70f3c58375571b8a91313bb**
:::
## PowerAnalysis: Warmup
:::spoiler <b>encrypt.py</b>
```python=
#!/usr/bin/env python3
import random, sys, time
with open("key.txt", "r") as f:
SECRET_KEY = bytes.fromhex(f.read().strip())
Sbox = (
0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)
# Leaks one bit of information every operation
leak_buf = []
def leaky_aes_secret(data_byte, key_byte):
out = Sbox[data_byte ^ key_byte]
leak_buf.append(out & 0x01)
return out
# Simplified version of AES with only a single encryption stage
def encrypt(plaintext, key):
global leak_buf
leak_buf = []
ciphertext = [leaky_aes_secret(plaintext[i], key[i]) for i in range(16)]
return ciphertext
# Leak the number of 1 bits in the lowest bit of every SBox output
def encrypt_and_leak(plaintext):
ciphertext = encrypt(plaintext, SECRET_KEY)
ciphertext = None # throw away result
time.sleep(0.01)
return leak_buf.count(1)
pt = input("Please provide 16 bytes of plaintext encoded as hex: ")
if len(pt) != 32:
print("Invalid length")
sys.exit(0)
pt = bytes.fromhex(pt)
print("leakage result:", encrypt_and_leak(pt))
```
:::
Nhìn đề thì cũng dễ hiểu, ta sẽ mã hóa văn bản rõ bằng cách cho chúng làm phép **XOR** với **key**, sau đó hoán vị bằng một **S-box** (substitution-box). Cuối cùng server sẽ trả về cho chúng ta số lượng bit $1$ cuối cùng của từng byte trong văn bản mã (ta gọi là số lượng rò rỉ).
Đây là một bài liên quan đến **side-channel attack** (tấn công bên kênh), ban đầu thì mình cũng chả biết làm gì nhưng sau đó nhờ thu thập thông tin trên mạng thì mình phát hiện một hướng giải rất thú vị.
Ta sẽ tạo một plaintext mà trong đó ngoài byte thứ $i$, các byte khác sẽ là $00$ hết. Riêng byte thứ $i$, ta sẽ tiến hành brute-force nó với giá trị từ $0$ đến $255$ và thu thập các số lượng rò rỉ mà server trả về cho ta.
Gọi $\text{LSB}(b)$ là bit ít quan trọng nhất của $b$, theo cách gửi văn bản rõ của chúng ta thì server sẽ tính số lượng rò rỉ theo công thức (tượng trưng, hơi sai về mặt toán học) sau:
$$
\text{leakage}(p_i, k_i) = \sum_{u = 0}^{i - 1} \text{LSB}(\text{S-box}[0 \oplus k_i]) + \text{LSB}(\text{S-box}[p_i \oplus k_i]) + \sum_{v = i+1}^{15} \text{LSB}(\text{S-box}[0 \oplus k_i]) \hspace{5pt} (1)
$$
Đặt: $\displaystyle
C = \sum_{u = 0}^{i - 1} \text{LSB}(\text{S-box}[0 \oplus k_i]) + \sum_{v = i+1}^{15} \text{LSB}(\text{S-box}[0 \oplus k_i])$, ta thấy giá trị này luôn là hằng số với mọi $p_i = \overline{0, 255}$.
Khi đó đẳng thức $(1)$ trở thành:
$$
\begin{align*}
\text{leakage}(p_i, k_i) &= \text{LSB}(\text{S-box}[p_i \oplus k_i]) + C \\[5pt]
\Leftrightarrow C &= \text{leakage}(p_i, k_i) - \text{LSB}(\text{S-box}[p_i \oplus k_i]) \hspace{20pt} (2)
\end{align*}
$$
Như vậy, ta thấy với $k_{right} = k_i$, thì đẳng thức $(2)$ luôn đúng với mọi $p_i = \overline{0, 255}$. Đến đây, ta sẽ thực hiện tấn công bằng cách brute-force byte thứ $i$ của **key** là $k_{\text{guess}}$ mang giá trị từ $0$ đến $255$ và tính giá trị:
$$
C_{\text{guess}} = \text{leakage}(p_i, k_i) - \text{LSB}(\text{S-box}[p_i \oplus k_{\text{guess}}]) \hspace{20pt} (3)
$$
Ta sẽ kiểm tra như sau: Nếu sau 255 lần ta thu về cùng một giá trị $C_{\text{guess}}$ thì ta có thể chắc chắn $k_{\text{guess}}$ này là đúng, còn nếu xuất hiện nhiều giá trị $C_{\text{guess}}$ khác nhau thì ta loại bỏ trường hợp này và tiếp tục brute-force.
Vế đầu đúng đơn giản là vì từ đẳng thức $(2)$ ta suy ra $C_{\text{guess}} = C$ và $k_{\text{guess}} = k_i$.
Còn vế sau thì phức tạp hơn một chút, nó đúng vì nếu $k_{\text{guess}} \neq k_i$ thì $\text{LSB}(\text{S-box}[p_i \oplus k_{\text{guess}}]) \neq \text{LSB}(\text{S-box}[p_i \oplus k_{i}])$ với một vài giá trị của $p_i$ nào đó. Do đó từ $(2)$ và $(3)$ ta sẽ suy ra $C_{\text{guess}}$ không phải lúc nào cũng bằng $C$ được, từ đây ta kết luận rằng $C_{\text{guess}}$ sẽ mang nhiều giá trị khác nhau!
Vậy là ta đã đưa ra được chiến lược để giải bài này rồi, dưới đây là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#96811d">solution.py</b>
```python=
from pwn import remote
from tqdm import trange
def recover_key_byte(index: int, HOST: str, PORT: int):
Sbox = (
0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)
observed_leak_list = []
for byte in trange(256, desc="Collecting leakages..."):
connection = remote(HOST, PORT)
connection.recvuntil(b"Please provide 16 bytes of plaintext encoded as hex: ")
plaintext = "00"*index + f"{byte:02x}" + "00"*(15 - index)
connection.sendline(plaintext.encode())
connection.recvuntil(b"leakage result: ")
observed_leak_list.append(int(connection.recvline().strip().decode()))
connection.close()
for key_guess in trange(256):
constant = observed_leak_list[0] - (Sbox[0 ^ key_guess] & 1)
is_correct_key = True
for byte in range(1, 256):
if(observed_leak_list[byte] != (Sbox[byte ^ key_guess] & 1) + constant):
is_correct_key = False
break
if(is_correct_key):
key_byte = key_guess
break
return key_byte
HOST = "saturn.picoctf.net"; PORT = 53731
# # Thực tế mỗi instance chỉ tồn tại trong 15 phút nên ta phải khôi phục từng byte của key chứ không dùng vòng lặp for thoải mái như thế này được (vì vậy mình đã dislike bài này 😆)
# partial_key = []
# for i in range(16):
# partial_key.append(recover_key_byte(i, HOST, PORT))
# print(partial_key)
key = [31, 8, 65, 173, 109, 121, 218, 107, 173, 152, 44, 65, 163, 207, 138, 127]
flag = "picoCTF{" + bytes(key).hex() + '}'
print("[!] Got flag:", flag)
# [!] Got flag: picoCTF{1f0841ad6d79da6bad982c41a3cf8a7f}
```
:::
:::success
**Flag: picoCTF{1f0841ad6d79da6bad982c41a3cf8a7f}**
:::
## PowerAnalysis: Part 1
Đây là mô tả khi ta mở **instance**:
Thử thách này không có file đề bài, và mô tả của nó liên quan đến tấn công bên kênh.
Chi tiết hơn một chút, thử thách này liên quan đến cuộc tấn công kênh phụ kinh điển có tên là **Phân tích Tương quan Công suất (Correlation Power Analysis - CPA)**. Ý tưởng cốt lõi là tìm ra mối tương quan thống kê giữa **mức tiêu thụ điện năng thực tế** mà server trả về và **mức tiêu thụ điện năng giả định** mà chúng ta tự tính toán dựa trên từng key đoán. Key đoán nào tạo ra sự tương quan cao nhất chính là key đúng.
Để giải được bài này, đầu tiên ta sẽ thu thập một bộ dữ liệu lớn gồm nhiều cặp `(plaintext, power_trace)`. Tấn công CPA dựa trên thống kê, vì vậy chúng ta cần đủ mẫu (ở đây là 150) để nhiễu ngẫu nhiên bị triệt tiêu và tín hiệu thật sự nổi bật lên.
Tiếp theo chúng ta sẽ sử dụng thư viện [`scared`](https://pypi.org/project/scared/) để thực hiện cuộc tấn công này (Thư viện này rất nhảm khi bắt chúng ta xài một phiên bản từ đời tống của `numpy` để có thể tương thích). Sau khi sử dụng cái thư viện kỳ lạ đó xong, mình có trực quan hóa bằng đồ thị để có thể hình dung về kết quả của cuộc tấn công.
Sau đó, mình chỉ đơn giản trích xuất **key đoán có điểm cao nhất** mà thôi, vì nó tuân thủ giống với lý thuyết nhất với số mẫu lớn như vậy nên khả năng gần như tuyệt đối là nó chính là **key** mà ta cần tìm!
Dưới đây là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#96811d">solution.py</b>
```python=
from pwn import remote
import json, numpy as np, scared, os
from tqdm import trange
from estraces import read_ths_from_ram
import matplotlib.pyplot as plt
# def plot_attack(attack, byte):
# """Plot attack results for the given byte."""
# fig, axes = plt.subplots(1, 2, figsize=(20, 3))
# axes[0].plot(attack.results[:, byte].T)
# axes[0].set_title('CPA results', loc='left')
# axes[1].plot(attack.convergence_traces[:, byte].T)
# axes[1].set_title('Scores convergence', loc='right')
# plt.suptitle(f'Attack results for byte {byte}')
# plt.show()
def crawl_data(HOST, PORT, samples = 150):
plaintext_list = []
result_list = []
for i in trange(samples):
connection = remote(HOST, PORT)
connection.recvuntil(b"Please provide 16 bytes of plaintext encoded as hex: ")
plaintext = np.random.randint(0, 256, 16, dtype='uint8')
connection.sendline(plaintext.tobytes().hex().encode())
connection.recvuntil(b"power measurement result: ")
power_measurement_result = json.loads(connection.recvline())
connection.close()
plaintext_list.append(plaintext)
result_list.append(power_measurement_result)
ths = read_ths_from_ram(samples=np.array(result_list), plaintext=np.array(plaintext_list))
return ths
HOST = "saturn.picoctf.net"; PORT = 56968
ths = crawl_data(HOST, PORT)
attack = scared.CPAAttack(selection_function=scared.aes.selection_functions.encrypt.FirstSubBytes(),
model=scared.HammingWeight(),
discriminant=scared.maxabs,
convergence_step=50)
attack.run(scared.Container(ths))
# plot_attack(attack, 0)
found_key = np.nanargmax(attack.scores, axis=0).astype('uint8')
flag = "picoCTF{" + found_key.tobytes().hex() + '}'
print("[!] Got flag:", flag)
# [!] Got flag: picoCTF{4999139026d84bf29a279e48d4edec53}
```
:::
:::success
**Flag: picoCTF{4999139026d84bf29a279e48d4edec53}**
:::
>[!note] Thông tin
>Các bài liên quan đến tấn công bên kênh quan trọng nhất là kết nối nhưng mà có vẻ picoCTF không làm tốt việc này khi mà kết nối cứ gặp lỗi liên tục và mỗi lần mở kết nối chỉ tồn tại trong 15 phút.
>Hơn thế nữa, các tham số `selection_function` được chọn trong bài này chỉ đúng vì bài này hoạt động giống như mô tả trong file thử thách của bài [**PowerAnalysis: Warmup**](https://hackmd.io/@0160ca14/HyNWNEwRel#PowerAnalysis-Warmup).
## PowerAnalysis: Part 2
Bài này giống hệt bài trước, nhưng thay vì chỉ có kết nối thì ta lại được $100$ file chứa thông tin về cặp `(plaintext, power_trace)`, vậy nên cách giải cũng y hệt bài trước thôi.
:::spoiler <b>traces.py</b> (gồm 100 file nhỏ bên trong)
:::
Dưới đây là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#96811d">solution.py</b>
```python=
from pwn import remote
import json, numpy as np, scared, os
from tqdm import trange
from estraces import read_ths_from_ram
import matplotlib.pyplot as plt
import re
# def plot_attack(attack, byte):
# """Plot attack results for the given byte."""
# fig, axes = plt.subplots(1, 2, figsize=(20, 3))
# axes[0].plot(attack.results[:, byte].T)
# axes[0].set_title('CPA results', loc='left')
# axes[1].plot(attack.convergence_traces[:, byte].T)
# axes[1].set_title('Scores convergence', loc='right')
# plt.suptitle(f'Attack results for byte {byte}')
# plt.show()
def crawl_data(path, file_count = 100):
plaintext_list = []
power_trace_list = []
for i in trange(file_count):
with open(path + f"\\trace{i:02}.txt", "r") as file:
line1 = file.readline()
plaintext = bytes.fromhex(re.search(r"([0-9a-f]+){4,}", line1).group())
line2 = file.readline()
power_trace = json.loads(re.search(r"\[.+\]", line2).group())
plaintext_list.append(np.frombuffer(plaintext, dtype=np.uint8))
power_trace_list.append(power_trace)
ths = read_ths_from_ram(samples=np.array(power_trace_list), plaintext=np.array(plaintext_list))
return ths
ths = crawl_data("traces", 100)
attack = scared.CPAAttack(selection_function=scared.aes.selection_functions.encrypt.FirstSubBytes(),
model=scared.HammingWeight(),
discriminant=scared.maxabs,
convergence_step=10)
attack.run(scared.Container(ths))
# plot_attack(attack, 0)
found_key = np.nanargmax(attack.scores, axis=0).astype('uint8')
flag = "picoCTF{" + found_key.tobytes().hex() + '}'
print("[!] Got flag:", flag)
# [!] Got flag: picoCTF{a8c43ca617250fd48d5f101b889f34de}
```
:::
:::success
**Flag: picoCTF{a8c43ca617250fd48d5f101b889f34de}**
:::
## college-rowing-team (No Explanation)
:::spoiler <b>encrypt.py</b>
```python=
#!/usr/bin/env python3
import random
from Crypto.Util.number import getPrime, bytes_to_long
with open('flag.txt', 'rb') as f:
flag = f.read()
msgs = [
b'I just cannot wait for rowing practice today!',
b'I hope we win that big rowing match next week!',
b'Rowing is such a fun sport!'
]
msgs.append(flag)
msgs *= 3
random.shuffle(msgs)
for msg in msgs:
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 3
m = bytes_to_long(msg)
c = pow(m, e, n)
with open('encrypted-messages.txt', 'a') as f:
f.write(f'n: {n}\n')
f.write(f'e: {e}\n')
f.write(f'c: {c}\n\n')
```
:::
:::spoiler <b>encrypted-messages.txt</b>
```text!
n: 12426348204210593270343924563278821305386892683425418957350363905840484905896816630189546938112358425679727243103082954824537007026886458498690134225705484501535835385800730412220192564706251228021192115494699150390312107794005569764411063907390563937247515046052549753641884721864426154021041082461015103337120756347692245843318676049947569653604616584167536958803278688355036036887022591104659059883622072052793378468850702811804337808760402077376453702190206077039468600466511349923882037572540505571672225260106649075841827340894515208811788428239691505001675042096850318994923571686175381862745049100863883977473
e: 3
c: 5065488652323342174251548936130018278628515304559137485528400780060697119682927936946069625772269234638180036633146283242714689277793018059046463458498115311853401434289264038408827377579534270489217094049453933816452196508276029690068611901872786195723358744119490651499187556193711866091991489262948739533990000464588752544599393
n: 19928073532667002674271126242460424264678302463110874370548818138542019092428748404842979311103440183470341730391245820461360581989271804887458051852613435204857098017249255006951581790650329570721461311276897625064269097611296994752278236116594018565111511706468113995740555227723579333780825133947488456834006391113674719045468317242000478209048237262125983164844808938206933531765230386987211125968246026721916610034981306385276396371953013685639581894384852327010462345466019070637326891690322855254242653309376909918630162231006323084408189767751387637751885504520154800908122596020421247199812233589471220112129
e: 3
c: 86893891006724995283854813014390877172735163869036169496565461737741926829273252426484138905500712279566881578262823696620415864916590651557711035982810690227377784525466265776922625254135896966472905776613722370871107640819140591627040592402867504449339363559108090452141753194477174987394954897424151839006206598186417617292433784471465084923195909989
n: 13985338100073848499962346750699011512326742990711979583786294844886470425669389469764474043289963969088280475141324734604981276497038537100708836322845411656572006418427866013918729379798636491260028396348617844015862841979175195453570117422353716544166507768864242921758225721278003979256590348823935697123804897560450268775282548700587951487598672539626282196784513553910086002350034101793371250490240347953205377022300063974640289625028728548078378424148385027286992809999596692826238954331923568004396053037776447946561133762767800447991022277806874834150264326754308297071271019402461938938062378926442519736239
e: 3
c: 86893891006724995283854813014390877172735163869036169496565461737741926829273252426484138905500712279566881578262823696620415864916590651557711035982810690227377784525466265776922625254135896966472905776613722370871107640819140591627040592402867504449339363559108090452141753194477174987394954897424151839006206598186417617292433784471465084923195909989
n: 19594695114938628314229388830603768544844132388459850777761001630275366893884362012318651705573995962720323983057152055387059580452986042765567426880931775302981922724052340073927578619711314305880220746467095847890382386552455126586101506301413099830377279091457182155755872971840333906012240683526684419808580343325425793078160255607072901213979561554799496270708954359438916048029174155327818898336335540262711330304350220907460431976899556849537752397478305745520053275803008830388002531739866400985634978857874446527750647566158509254171939570515941307939440401043123899494711660946335200589223377770449028735883
e: 3
c: 5065488652323342174251548936130018278628515304559137485528400780060697119682927936946069625772269234638180036633146283242714689277793018059046463458498115311853401434289264038408827377579534270489217094049453933816452196508276029690068611901872786195723358744119490651499187556193711866091991489262948739533990000464588752544599393
n: 12091176521446155371204073404889525876314588332922377487429571547758084816238235861014745356614376156383931349803571788181930149440902327788407963355833344633600023056350033929156610144317430277928585033022575359124565125831690297194603671159111264262415101279175084559556136660680378784536991429981314493539364539693532779328875047664128106745970757842693549568630897393185902686036462324740537748985174226434204877493901859632719320905214814513984041502139355907636120026375145132423688329342458126031078786420472123904754125728860419063694343614392723677636114665080333174626159191829467627600232520864728015961207
e: 3
c: 301927034179130315172951479434750678833634853032331571873622664841337454556713005601858152523700291841415874274186191308636935232309742600657257783870282807784519336918511713958804608229440141151963841588389502276162366733982719267670094167338480873020791643860930493832853048467543729024717103511475500012196697609001154401
n: 19121666910896626046955740146145445167107966318588247850703213187413786998275793199086039214034176975548304646377239346659251146907978120368785564098586810434787236158559918254406674657325596697756783544837638305550511428490013226728316473496958326626971971356583273462837171624519736741863228128961806679762818157523548909347743452236866043900099524145710863666750741485246383193807923839936945961137020344124667295617255208668901346925121844295216273758788088883216826744526129511322932544118330627352733356335573936803659208844366689011709371897472708945066317041109550737511825722041213430818433084278617562166603
e: 3
c: 38999477927573480744724357594313956376612559501982863881503907194813646795174312444340693051072410232762895994061399222849450325021561935979706475527169503326744567478138877010606365500800690273
n: 13418736740762596973104019538568029846047274590543735090579226390035444037972048475994990493901009703925021840496230977791241064367082248745077884860140229573097744846674464511874248586781278724368902508880232550363196125332007334060198960815141256160428342285352881398476991478501510315021684774636980366078533981139486237599681094475934234215605394201283718335229148367719703118256598858595776777681347337593280391052515991784851827621657319164805164988688658013761897959597961647960373018373955633439309271548748272976729429847477342667875183958981069315601906664672096776841682438185369260273501519542893405128843
e: 3
c: 38999477927573480744724357594313956376612559501982863881503907194813646795174312444340693051072410232762895994061399222849450325021561935979706475527169503326744567478138877010606365500800690273
n: 11464859840071386874187998795181332312728074122716799062981080421188915868236220735190397594058648588181928124991332518259177909372407829352545954794824083851124711687829216475448282589408362385114764290346196664002188337713751542277587753067638161636766297892811393667196988094100002752743054021009539962054210885806506140497869746682404059274443570436700825435628817817426475943873865847012459799284263343211713809567841907491474908123827229392305117614651611218712810815944801398564599148842933378612548977451706147596637225675719651726550873391280782279097513569748332831819616926344025355682272270297510077861213
e: 3
c: 38999477927573480744724357594313956376612559501982863881503907194813646795174312444340693051072410232762895994061399222849450325021561935979706475527169503326744567478138877010606365500800690273
n: 21079224330416020275858215994125438409920350750828528428653429418050688406373438072692061033602698683604056177670991486330201941071320198633550189417515090152728909334196025991131427459901311579710493651699048138078456234816053539436726503461851093677741327645208285078711019158565296646858341000160387962592778531522953839934806024839570625179579537606629110275080930433458691144426869886809362780063401674963129711723354189327628731665487157177939180982782708601880309816267314061257447780050575935843160596133370063252618488779123249496279022306973156821343257109347328064771311662968182821013519854248157720756807
e: 3
c: 301927034179130315172951479434750678833634853032331571873622664841337454556713005601858152523700291841415874274186191308636935232309742600657257783870282807784519336918511713958804608229440141151963841588389502276162366733982719267670094167338480873020791643860930493832853048467543729024717103511475500012196697609001154401
n: 22748076750931308662769068253035543469890821090685595609386711982925559973042348231161108618506912807763679729371432513862439311860465982816329852242689917043600909866228033526990181831690460395726449921264612636634984917361596257010708960150801970337017805161196692131098507198455206977607347463663083559561805065823088182032466514286002822511854823747204286303638719961067031142962653536148315879123067183501832837303731109779836127520626791254669462630052241934836308543513534520718206756591694480011760892620054163997231711364648699030108110266218981661196887739673466188945869132403569916138510676165684240183111
e: 3
c: 5065488652323342174251548936130018278628515304559137485528400780060697119682927936946069625772269234638180036633146283242714689277793018059046463458498115311853401434289264038408827377579534270489217094049453933816452196508276029690068611901872786195723358744119490651499187556193711866091991489262948739533990000464588752544599393
n: 15211900116336803732344592760922834443004765970450412208051966274826597749339532765578227573197330047059803101270880541680131550958687802954888961705393956657868884907645785512376642155308131397402701603803647441382916842882492267325851662873923175266777876985133649576647380094088801184772276271073029416994360658165050186847216039014659638983362906789271549086709185037174653379771757424215077386429302561993072709052028024252377809234900540361220738390360903961813364846209443618751828783578017709045913739617558501570814103979018207946181754875575107735276643521299439085628980402142940293152962612204167653199743
e: 3
c: 301927034179130315172951479434750678833634853032331571873622664841337454556713005601858152523700291841415874274186191308636935232309742600657257783870282807784519336918511713958804608229440141151963841588389502276162366733982719267670094167338480873020791643860930493832853048467543729024717103511475500012196697609001154401
n: 21920948973299458738045404295160882862610665825700737053514340871547874723791019039542757481917797517039141169591479170760066013081713286922088845787806782581624491712703646267369882590955000373469325726427872935253365913397944180186654880845126957303205539301069768887632145154046359203259250404468218889221182463744409114758635646234714383982460599605335789047488578641238793390948534816976338377433533003184622991479234157434691635609833437336353417201442828968447500119160169653140572098207587349003837774078136718264889636544528530809416097955593693611757015411563969513158773239516267786736491123281163075118193
e: 3
c: 86893891006724995283854813014390877172735163869036169496565461737741926829273252426484138905500712279566881578262823696620415864916590651557711035982810690227377784525466265776922625254135896966472905776613722370871107640819140591627040592402867504449339363559108090452141753194477174987394954897424151839006206598186417617292433784471465084923195909989
```
:::
Cách giải tương tự như [bài này](https://hackmd.io/@0160ca14/SJkH2skCel#Crack-the-Power-No-Explanation), chỉ là nó thêm thắt một chút cho phức tạp thôi.
Dưới đây là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#96811d">solution.py</b>
```python=
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes
from tqdm import trange
import re
with open("encrypted-messages.txt", "r") as file:
for i in trange(12):
n = int(re.search(r"[0-9]+", file.readline()).group())
e = int(re.search(r"[0-9]+", file.readline()).group())
c = int(re.search(r"[0-9]+", file.readline()).group())
flag_found = False; k = 0
while(True):
expression = c + k*n
m, exact = iroot(expression, e)
if exact:
flag = long_to_bytes(m).decode()
if("picoCTF{" in flag): flag_found = True
break
if(flag_found):break
file.readline()
print("[!] Got flag:", flag)
# [!] Got flag: picoCTF{1_gu3ss_p30pl3_p4d_m3ss4g3s_f0r_4_r34s0n}
```
:::
:::success
**Flag: picoCTF{1_gu3ss_p30pl3_p4d_m3ss4g3s_f0r_4_r34s0n}**
:::
## Sequences
:::spoiler <b>sequences.py</b>
```python=
import math
import hashlib
import sys
from tqdm import tqdm
import functools
ITERS = int(2e7)
VERIF_KEY = "96cc5f3b460732b442814fd33cf8537c"
ENCRYPTED_FLAG = bytes.fromhex("42cbbce1487b443de1acf4834baed794f4bbd0dfe2d6046e248ff7962b")
# This will overflow the stack, it will need to be significantly optimized in order to get the answer :)
@functools.cache
def m_func(i):
if i == 0: return 1
if i == 1: return 2
if i == 2: return 3
if i == 3: return 4
return 55692*m_func(i-4) - 9549*m_func(i-3) + 301*m_func(i-2) + 21*m_func(i-1)
# Decrypt the flag
def decrypt_flag(sol):
sol = sol % (10**10000)
sol = str(sol)
sol_md5 = hashlib.md5(sol.encode()).hexdigest()
if sol_md5 != VERIF_KEY:
print("Incorrect solution")
sys.exit(1)
key = hashlib.sha256(sol.encode()).digest()
flag = bytearray([char ^ key[i] for i, char in enumerate(ENCRYPTED_FLAG)]).decode()
print(flag)
if __name__ == "__main__":
sol = m_func(ITERS)
decrypt_flag(sol)
```
:::
Bài này nếu tính theo file thử thách thì sẽ không thể nào chạy ra trong kiếp này được, vì vậy chúng ta cần phải biến đổi về mặt toán học sao cho file này giảm thời gian chạy về mặt tính toán nhiều nhất có thể.
Xét dãy số ${\{u_n\}}_{n = 0}^{+ \infty}$ là dãy số tượng trưng cho hàm `m_func` trong file chương trình của thử thách. Khi đó ta có công thức truy hồi như sau:
$$
\begin{align*}
&u_n = 55692u_{n-4} - 9549u_{n-3} + 301u_{n-2} + 21u_{n-1}, ~~ \forall n = 4, 5,\ldots \\
\Leftrightarrow &u_n - 21u_{n-1} - 301u_{n-2} + 9549u_{n-3} - 55692u_{n-4} = 0, ~~ \forall n = 4, 5,\ldots
\end{align*}
$$
Vì đây là phương trình sai phân bậc $4$ thuần nhất nên ta chỉ cần xét phương trình đặc trưng như sau:
$$
\begin{align*}
&\lambda^4 - 21\lambda^3 - 301\lambda^2 + 9549\lambda -55692 = 0 \\
\Leftrightarrow &(\lambda - 17)(\lambda - 13)(\lambda -12)(\lambda +21) = 0 \\
\Leftrightarrow &
\left[
\begin{aligned}
\lambda &= 17 \\
\lambda &= 13 \\
\lambda &= 12 \\
\lambda &= -21
\end{aligned}
\right.
\end{align*}
$$
Do đó dãy số ${\{u_n\}}_{n = 0}^{+ \infty}$ có dạng:
$$
u_n = A(-21)^n + B\cdot12^n + C\cdot13^n + D\cdot17^n, ~~ \forall n = 0, 1, 2, \ldots
$$
Mặt khác từ file thử thách ta có $\begin{cases}
u_0 = 1 \\
u_1 = 2 \\
u_2 = 3 \\
u_3 = 4
\end{cases}$ nên ta có hệ phương trình sau:
$$
\begin{cases}
A + B + C + D &= 1 \\
-21\cdot A + 12\cdot B + 13\cdot C + 17\cdot D &= 2 \\
441\cdot A + 144\cdot B + 169\cdot C + 289\cdot D &= 3 \\
-9261\cdot A + 1728\cdot B + 2197\cdot C + 4913\cdot D &= 4
\end{cases} \Leftrightarrow
\begin{cases}
A &= \frac{403}{10659} \\
B &= \frac{760}{33} \\
C &= -\frac{1727}{68} \\
D &= \frac{253}{76}
\end{cases}
$$
Như vậy công thức tổng quát của dãy ${\{u_n\}}_{n = 0}^{+ \infty}$ là:
$$
\begin{align*}
u_n &= \frac{403}{10659}(-21)^n + \frac{760}{33}\cdot12^n -\frac{1727}{68}\cdot13^n + \frac{253}{76}\cdot17^n, ~~ \forall n = 0, 1, 2, \ldots \\
42636u_n &= 1612(-21)^n + 981920\cdot12^n -1082829\cdot13^n + 141933\cdot17^n, ~~ \forall n = 0, 1, 2, \ldots
\end{align*}
$$
Thay $n$ bởi $m = 2\cdot 10^7$ vào công thức, ta được:
$$
42636u_m = 1612\cdot21^m + 981920\cdot12^m -1082829\cdot13^m + 141933\cdot17^m
$$
Đến đây với $a = 10^{10000}$ thì ta có thể tính $42636u_m \bmod{a}$ rất nhanh bằng thuật toán [**thuật toán lũy thừa bằng bình phương**](https://en.wikipedia.org/wiki/Exponentiation_by_squaring), cụ thể ta sẽ tính như sau:
$$
42636u_m \bmod{a} = \left(1612(21^m \bmod{a})+ 981920(12^m \bmod{a}) - 1082829(13^m \bmod{a}) + 141933(17^m \bmod{a})\right) \bmod{a}
$$
Đặt: $b = 1612(21^m \bmod{a})+ 981920(12^m \bmod{a}) - 1082829(13^m \bmod{a}) + 141933(17^m \bmod{a})$ , khi đó ta chỉ cần giải phương trình để tìm lại được $u_m$:
$$
42636u_m \equiv b \pmod{a}
$$
Như vậy sau khi tìm được $u_m$ (khả năng sẽ có nhiều giá trị thỏa mãn), ta chỉ thử từng cái và tiến hành giải mã để ra **flag**.
>[!Tip]
>Thay vì nháp tay, bạn nên sử dụng **sagemath** hoặc các công cụ lập trình toán học để tự động hóa và tránh sai sót trong quá trình tính toán.
Dưới đây sẽ là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#96811d">solution.py</b>
```python=
import hashlib
from sage.all import inverse_mod, Integer, ZZ
# Giải phương trình đồng dư ax ≡ b (mod n)
def solve_linear_congruence(a,b,n):
from math import gcd
a=ZZ(a); b=ZZ(b); n=ZZ(n)
d = gcd(a, n)
if b % d != 0:
return [] # không có nghiệm
a1 = a//d; b1 = b//d; n1 = n//d
inverse = inverse_mod(a1, n1) # bây giờ gcd(a1,n1)=1
x0 = (inverse * b1) % n1
solutions = [Integer((x0 + k*n1) % n) for k in range(d)]
return solutions
def decrypt_flag(iterations = 0, modulo = 10**10000):
remain = (1612*pow(-21, iterations, modulo) + 981920*pow(12, iterations, modulo) - 1082829*pow(13, iterations, modulo) + 141933*pow(17, iterations, modulo)) % modulo
solutions = solve_linear_congruence(42636, remain, modulo)
for solution in solutions:
solution = int(solution) % (10**10000)
solution = str(solution)
sol_md5 = hashlib.md5(solution.encode()).hexdigest()
if sol_md5 != VERIF_KEY: continue
key = hashlib.sha256(solution.encode()).digest()
flag = bytearray([char ^ key[i] for i, char in enumerate(ENCRYPTED_FLAG)]).decode()
return flag
ITERS = int(2e7)
VERIF_KEY = "96cc5f3b460732b442814fd33cf8537c"
ENCRYPTED_FLAG = bytes.fromhex("42cbbce1487b443de1acf4834baed794f4bbd0dfe2d6046e248ff7962b")
flag = decrypt_flag(ITERS)
print("[!] Got flag:", flag)
# [!] Got flag: picoCTF{b1g_numb3rs_689693c6}
```
:::
:::success
**Flag: picoCTF{b1g_numb3rs_689693c6}**
:::
>[!Note] Thông tin thêm
>Ngoài cách này ra, còn một cách sử dụng chéo hóa ma trận vuông (cũng là lời giải chính cho thử thách này), tuy nhiên vì đã có nhiều write-up trên mạng nói về nó nên mình cũng không trình bày cách này nữa.
>Còn cách giải này là do cách giải này mình tự nghĩ ra, dựa vào kiến thức của phần dãy số khi ôn HSG toán cấp 3.
## Summary
Trên đây là các lời giải cho những bài khó mà khá ít người giải được trên **picoCTF**, các bài này đều có kiến thức rất mới lạ và phong phú. Về độ khó, các bài này cũng ở một tầm cao hơn khi mà phải tư duy nhiều hơn mới có thể giải ra được.
Xin chào và hẹn gặp lại các bạn ở phần tiếp theo (và có lẽ là phần cuối trong năm nay vì không còn nhiều bài **picoCTF** ở mảng cryptography nữa) 👋.
Sign in with Wallet
Connect another wallet