Tokyo Westerns CTF 2017 Reverse224: Cryptal Writeup

題目有一個 binary file - 它會把輸入加密,還有一個被該 binary file 加密的密文 - flag.png.enc。

經過黑箱 作業 測試後,發現了 binary 所運行的是 fixed-key Crystalline cipher (我當時只知道它運作的原理,名字就是在 flag 裡面看到的…)

Crystalline cipher 是一個 stream cipher,其運作原理如下:

對於一個長度為 \(n\)-bits 的字串 \(\mathcal{M}\),它會生成一個固定的 \(n\)-bits 字串 \(\mathcal{S}: \{1, 2, …, n\} \rightarrow [0, 1]\),以及一個固定的排列 \(\varphi: \{1, 2, …, n\} \rightarrow\{1, 2, …, n\}\)。

設 \(\mathcal{C} = \mathcal{C}_1\mathcal{C}_2…\mathcal{C}_n\) (\(\mathcal{C}_k\in\{0, 1\}\)) 為由 \(\mathcal{M} =\mathcal{M}_1\mathcal{M}_2…\mathcal{M}_n\)(\(\mathcal{M}_k\in\{0, 1\}\)) 所加密的密文,則對於所有 \(k = 1, 2, …, n\),我們有 \(\mathcal{C}_k = \mathcal{S}_k \oplus \mathcal{M}_{\phi(k)}\)。

舉個例子,就當 \(n = 8\) 吧。假設 \(\mathcal{S} = (0, 1, 1, 0, 1, 0, 1, 1)\) 及 \(\varphi = (7, 3, 5, 4, 1, 8, 2, 6)\) 為兩個常數。

\(\mathcal{M} = (0, 1, 0, 0, 1, 1, 0, 1)\) 所對應的密文是 \(\mathcal{C} = (\mathcal{S}_1 \oplus \mathcal{M}_{\varphi(1)},\mathcal{S}_2 \oplus \mathcal{M}_{\varphi(2)}, …,\mathcal{S}_8 \oplus \mathcal{M}_{\varphi(8)})\),即 \((0, 1, 0, 0, 1, 1, 0, 0)\)。


那麼我們可以怎樣利用 encryption oracle (那個 binary 檔) 來解出 flag.png?我們知道加密後長度不變,所以得到 flag.png 本來的大小。

問題是,如何得到 \(\mathcal{S}\) 和 \(\varphi\)?得到 \(\mathcal{S}\) 是很簡單的,只需要輸入 00...0 (\(n\) 個 zero bits) 即可。

但是 \(\varphi\) 呢?

方法一

一個比較直觀的方法是輸入  10...001...0、…、 00...1,各自跟 \(\mathcal{S}\) xor 一次,得到改變了的位置。需要 query 的次數為 \(\mathcal{O}(n)\)。由於每個 query 的時間複雜度是 \(\mathcal{O}(n)\),所以整體的時間複雜度是 \(\mathcal{O}(n^2)\)。

如果 \(n = 8\),可以利用 oracle 詢問九次: 00000000 (找出 \(\mathcal{S}\))、 10000000、…、 00000001

但是我們面對的是 \(n \approx 8000\) - 這樣做好像太慢了,應該怎樣改善現有的算法呢?

方法二

我想起小學的時候看過一套 eTV:想一個 50 以內的整數,看看以下哪些「卡片」有這個數字。如果有,把左上角的數字相加。

現在我想的是 44。這個數字出現在第三、四及第六張卡片上 - 然後發現 \(4 + 8 + 32 = 44\)!

其實原理很簡單,第一張卡片寫的都是符合  n & 0b00001 == 0b00001 的數字、第二張符合  n & 0b00010 == 0b00010 等等。

但是… 這個東西跟題目有關係嗎?

再利用 \(n = 8\) 的例子,我們可以詢問 4 次就可以得到所有資訊:

我們可以得出輸入跟輸出的關係:

假如我們要解密 \(11111111\),首先把 \(11111111 \oplus \mathcal{S} = 00100111\)。我們關心的是 output bits 3, 6, 7, 8。

根據上表,他們分別對應 input bits 6, 4, 8, 7。所以解密後得出 \(00010111\)。

利用相同原理,可以得出這題的 plaintext。現在需要 query 的次數為 \(\mathcal{O}(\text{log} n)\)。

最後得出 flag: TWCTF{Cry5ta11ine_Ciph3r_with_Cryst4l}

 

 

 

 

 

最後的最後,少不了要炫耀一下!HOLLAND KING。

 


發表迴響