HITB GSEC CTF 2017 Writeup

目錄

  1. Crypto 377: Hashinator
  2. Crypto 881: Hack in the Card I – II

Crypto 377: Hashinator

0x00. 背景

題目從 rockyou 裡面抽取一個 password 補至 128 字元,並使用給定的 hash function 把內容拼成 hash。我們需要從 hash 「解密」得到本來的密碼。

首先提供的代碼如下:

0x01. 思路與題解

設 \(h_1, h_2, …, h_{32}\) 為 32 個 hash functions,及 \(l_0, l_1, …, l_{32}, r_0, r_1, …, r_{32}\) 為長度為 64 的字串。

如果 \((l_0, r_0)\) 為 hash function 的輸入,對於 \(k=1, 2, …, 32\),我們有:

\(l_k := l_{k-1} \oplus h_{33-k}(r_{k-1})\)\(r_k := r_{k-1} \oplus h_k(l_k)\) ---- [*]

整個 hash function 的輸出為 \((l_{32}, r_{32})\)。

問題是,如果我們知道 \(h_1, h_2, …, h_{32}\) 和 \((l_{32}, r_{32})\),怎樣可以得到 \((l_0, r_0)\)?

[*] 整理一下可得出,對於 \(k=1,2, …, 32\),我們有:

\(r_{k-1} = r_k \oplus h_k(l_k)\) 及 \(l_{k-1} := l_k \oplus h_{33-k}(r_k\oplus h_k(l_k))\)---- [**]

就是這樣,我們可以得到 \((l_0, r_0)\) 。


Crypto881: Hack in the Card I – II

0x00. 背景

這次有關 RSA 的題目都是比較經典的。題目分成兩部分:

  • 第一部份提供 oscilloscope 測量的電壓 (Voltage),明顯是 power attack;
  • 第二部分 public key 所用的 \(n\) 跟第一部份相同。由於我們得到這個 \(n\) 對應的其中一對密鑰 \(e’, d’\),我們可以因式分解 \(n = pq\),繼而得到這部分的 \(e\) 所對應的 \(d\)。

0x01. 思路與解法

第一部分

RSA 加密或者解密時都需要算出形如 \(a^k (\text{mod}n)\) 的表達式。眾所周知,沒有人會用 \(\mathcal{O}(k)\) 的算法來計算它 - 我們可以用 \(\mathcal{O}(\text{log }k)\) 把結果算出來:

計算單數的 \(k\) 時,以上算法會比計算雙數時多出一個乘法運算。有什麼分別?下圖是 oscilloscope 對於 0 和 1 的 waveform:

圖片來源:https://en.wikipedia.org/wiki/Power_analysis

由上圖所見,0 和 1 在 oscilloscope 裡分別是「高低」和「高高低」,所以我們可以把題目給定的波形轉成由 0 和 1 組成的序列。

另外,考慮上述的算法是怎樣算出 \(2^{11} (\text{mod} 37)\) 的:

記住次序是 top-down 的,所以我們得到 0-1 序列後需要把它的次序倒轉,才會得到 \(d\) 的二進制表達式。

得到了 \(d\) 後,解密是非常簡單的:

第二部分

這部分的 \(n\) 是跟第一部份的一樣。由於我們已經有一組 \((e’, d’\)),我們可以用算法找出 \(n\) 的因式分解。

得出 \(n = pq\) 後,對於 \(e\) 有 \(d \equiv e^{-1} (\text{mod}(p-1)(q-1))\)。我們用 extended Euclidean’s algorithm 即可得出 \(d\)。解密得到 flag:


發表迴響