MeePwnCTF 2017 Crypto600: justpad Writeup

題目提供了一個 encryption oracle。第一層是 Proof of Work,目的是為了拖延時間,所以就不寫了。這個 encryption oracle 利用 RSA 加密,每次會產生不同的 public key:兩個質數 \(p, q\) 最多為 512 bits,而 \(e\) 是從 3, 5, 7, 11 跟 13 裡面隨機抽出來的。

然後可以對這個 oracle 輸入最多三個 \(x\) (\(x^e\geq n\)):它會算出 \((\kappa + x)^e (\text{mod }n)\) 的值。這裡的 \(\kappa<2^{352}\) 是跟 flag 有關的,現在的目標是取得 \(\kappa\)。

如果 \(e = 3\),\(x_1 = 2^{400}\) 和 \(x_2 = 2^{400} + 1\) 分別會被加密成 \(c_1 \equiv (\kappa + 2^{400})^3 (\text{mod }n)\) 和 \(c_2 \equiv (\kappa + 2^{400} + 1)^3 (\text{mod }n)\)。相減得出 \(c_2 – c_1 \equiv 3(\kappa + 2^{400})^2 + 3(\kappa + 2^{400}) + 1 (\text{mod }n)\)。

如存在整數 \(M\) 使得 \(nM \leq c_1, c_2 < n(M+1)\) 的話,\(c_2 – c_1 = 3(\kappa + 2^{400})^2 + 3(\kappa + 2^{400}) + 1\) (不只是同餘,而是相等)。由於 \(c_2 – c_1 \approx 2^{802}\) 的關係,這個條件是非常容易產生的。所以我們只需要解這道二次方程即可取得 \(\kappa\)。

以下是取得 \(c_2 – c_1\) 的程式碼。


要從 \(\kappa\) 取回 flag,必須理解 \(\kappa\) 的產生方法:flag 是 55 bytes 的,把它分成 11 個 5 bytes 的字串,分別用 CRC32 hash 過去。

例如 MeePwnCTF{ 會變成  507FDCD463C00FB9 (因為 CRC32('MeePw') = 0x507FDCD4 及 CRC32('nCTF{') = 0x63C00FB9。)

由於我不了解 CRC32 實際的計算方法,只知道 CRC 系統都是仿射變換 (affine transformation),並有  CRC(a xor b) = CRC(a) xor CRC(b) xor CRC(0) 這個關係,所以這次我用了 meet-in-the-middle 的攻擊手法:

由於每個 message block 只有 5 bytes (40 bits),首先窮舉右邊的 20 bits,記錄成表:

由於 CRC32 是仿射的,所以有以下關係:

對於所有 hashed block (0x507FDCD4、0x63C00FB9 等等),窮舉左邊的 20 bits,算出  CRC32(left) xor CRC32(message) xor CRC32(0x0000000000)。如果上表內有這個紀錄,則這是其中一個可能性。

例如以下是第一個 hashed block 的表:

可以看到兩個表都有  0xB433BC3D,所以第一個 hashed block 的原訊息可能是  0x4D65655077 (MeePw)

寫了一段程式碼讓上述過程自動化:

把程式運行一次,可以得出 flag:

Simple?不敢苟同。


發表迴響