ISITDTU Quals 2022

Glitch in the matrix

Đề bài các bạn có thể xem ở chall.py.

Bài này mình re-writeup từ hint của của một idol. :))))

Thử thách ở đây là cần đoán một token hex độ dài \(64\) bit với secret key là SECRET_BASIS.

Gọi token hex có \(64\) bit là \((m_1, m_2, \cdots, m_{64})\). Với SECRET_BASIS là ma trận trên \(\mathbb{F}_2\) kích thước \(128 \times 128\), ta thực hiện encrypt như sau:

  • random một chuỗi \(64\) bit C;

  • nếu \(m_i = 1\) thì thực hiện f(SECRET_BASIS[:64], C), nếu là \(0\) thì f(SECRET_BASIS[64:], C);

  • nghĩa là secret key được chia thành hai nửa trái phải theo chiều dọc.

Hàm \(f\) thực hiện như sau:

  • Với C là một chuỗi \(64\) bit, đặt \(C = (c_1, c_2, \cdots, c_{64})\);

  • Nếu \(c_i = 1\) thì dòng \(i\) được xor vào kết quả;

  • Hay viết dưới dạng vector sẽ là

\[c_1 \cdot (m_{1,1}, m_{1,2}, \cdots m_{1,128}) + \cdots + c_{64} \cdot (m_{64,1}, m_{64,2}, \cdots, m_{64,128}).\]

Ý tưởng để làm bài này là mình lấy thật nhiều ciphertext tương ứng với một plaintext (password). Do từng bit của plaintext được mã hóa riêng nhau nên mình sẽ tìm mối liên hệ giữa hai block mã hóa để xem chúng có cùng thuộc nửa trái (hoặc nửa phải) của secret key hay không.

Vì \(64\) bit plaintext được mã hóa thành \(64 \times 128\) bit của ciphertext, mình chia mỗi ciphertext thành \(64\) block. Giả sử mình lấy \(n\) ciphertext, mỗi ciphertext cũng được chia thành \(64\) block thì mình sẽ có 64 ma trận \(n \times 128\).

Nếu hai ma trận có chung base (cùng thuộc nửa trái hoặc nửa phải) thì hiệu của chúng sẽ có cùng rank với ma trận đầu. Do đó mình giả sử bit đầu là \(0\), vậy thì những block thứ \(2\) tới \(64\) (tương ứng bit thứ \(2\) tới \(64\)) nếu có cùng rank thì sẽ mang bit \(0\), không thì mang bit \(1\). Do đó mình cần lấy \(n\) ciphertext đủ lớn để block đầu có rank là \(64\) (max).

Lưu ý rằng do mình giả sử bit đầu là \(0\), nên nếu bit đầu của plaintext là \(1\) thì sẽ không giải ra. Do đó xác suất cách làm này là \(1/2\).

Code giải của mình ở solve.py.