Một bài toán mật mã (crypto) từ deadsecCTF 2024 yêu cầu khôi phục flag từ chuỗi mã hóa được tạo bởi hàm FLAG_KILLER, với đặc điểm nổi bật: mỗi khối đầu vào chỉ gồm đúng 3 ký tự hex (tức 1.5 byte), tương đương giá trị nguyên trong khoảng [0, 4095]. Do đó, thay vì phân tích ngược thuật toán — vốn phức tạp do hàm sử dụng chuỗi phép biến đổi cơ số hỗn hợp giữa nhị phân và tam phân — cách tiếp cận hiệu quả hơn là vét cạn toàn bộ không gian đầu vào khả thi.

Cấu trúc mã hóa

Hàm encrypt thực hiện các bước sau:

• Chuyển chuỗi đầu vào sang dạng hex (ví dụ "DEAD{test}" → "444541447b746573747d").
• Cắt chuỗi hex thành các đoạn dài 3 ký tự (ví dụ "444", "541", ...), mỗi đoạn được chuyển sang số nguyên cơ số 16.
• Mỗi số nguyên này được đưa vào hàm FLAG_KILLER, trả về một giá trị nguyên khác.
• Kết quả đầu ra của FLAG_KILLER được định dạng thành chuỗi hex 5 ký tự ('%05x') và nối lại thành chuỗi mã hóa cuối cùng.

Do đó, mỗi khối 3 ký tự hex đầu vào sinh ra đúng 5 ký tự hex đầu ra. Với chuỗi mã hóa có độ dài 155 ký tự, ta suy ra có chính xác 155 ÷ 5 = 31 khối cần giải mã.

Phương pháp vét cạn hiệu quả

Vì miền giá trị đầu vào cho mỗi khối chỉ nằm trong [0, 4095], việc xây dựng bảng tra cứu trước (precomputation) hoặc duyệt tuyến tính là hoàn toàn khả thi. Dưới đây là hàm đảo ngược đơn giản nhưng đủ mạnh:

def brute_force_inverse(encoded_val):
    for candidate in range(4096):  # 0x000 to 0xFFF
        if FLAG_KILLER(candidate) == encoded_val:
            return candidate
    return None

Lưu ý rằng hàm FLAG_KILLER không phải là song ánh trên toàn bộ ℤ⁺, nhưng trên miền [0, 4095] nó đảm bảo tính đơn ánh đối với mục đích mã hóa bài toán — điều này đã được kiểm chứng thực nghiệm khi chạy thử trên các giá trị mẫu.

Quy trình giải mã đầy đủ

Sau khi tách chuỗi mã hóa thành 31 khối 5 ký tự, mỗi khối được chuyển sang số nguyên cơ số 16 rồi truyền vào hàm vét cạn ở trên. Kết quả trả về là giá trị hex 3 ký tự tương ứng. Các khối hex được nối lại thành một chuỗi duy nhất, sau đó loại bỏ phần padding dư thừa (do độ dài chuỗi gốc không chia hết cho 3) trước khi giải mã từ hex sang bytes và cuối cùng là string UTF-8.

Đoạn mã giải mã hoàn chỉnh:

from binascii import unhexlify

def decrypt(ciphertext):
    result_hex = ""
    for i in range(0, len(ciphertext), 5):
        chunk = ciphertext[i:i+5]
        encoded_num = int(chunk, 16)
        raw_val = brute_force_inverse(encoded_num)
        if raw_val is None:
            raise RuntimeError(f"No preimage found for {chunk}")
        result_hex += f"{raw_val:03x}"
    
    # Loại bỏ padding cuối nếu cần (do padding zero khi cắt khối)
    cleaned = result_hex.rstrip('0')
    # Đảm bảo độ dài chẵn để unhexlify không lỗi
    if len(cleaned) % 2 != 0:
        cleaned = cleaned[:-1]
    
    return unhexlify(cleaned).decode('utf-8', errors='ignore')

cipher = "0e98b103240e99c71e320dd330dd430de2629ce326a4a2b6b90cd201030926a090cfc5269f904f740cd1001c290cd10002900cd100ee59269a8269a026a4a2d05a269a82aa850d03a2b6b900883"
print("Flag:", decrypt(cipher))

Kết quả thu được là: