MeePwnCTF 2017 Writeup

目錄

  1. Crypto 100: Simpler than RSA?
  2. Crypto 100: |\/|/-\T|-|
  3. Crypto 650: Justpad
  4. Misc 850: Find me!
  5. Web 432: Br0kenMYSQL v1-v3


Crypto100: Simpler than RSA?

0x00. 背景

題目提供了一個密碼系統還有一組 ciphertext,要求我們從中找出 flag。

Key generation:

  • 生成兩個 90 bits 的質數:\(p, q\), 並設 \(n = p^2 q\)
  • 生成一個亂數 \(g\) 使得 \(1 \leq g \leq n\)
  • 算出 \(h \equiv g^n (\text{mod }n)\)
  • 傳回 \((n, g, h)\)

加密 (\(m\rightarrow c\)):

  • 把所有字元一個一個字傳換成 ASCII code (\(m = m_1 m_2 … m_k\)、\(0 \leq m_i < 256\))
  • 逐個按以下算法加密:
    • 生成亂數 \(r\) 使得 \(1 \leq r \leq n\)
    • 算出 \(c_i \equiv g^{m_i} h^r (\text{mod }n)\)
    • 傳回 \(c_i\)、即 \(m_i\) 加密後的結果

解密:

題目作者用這個算法給出了一組 public key:

0x01. 思路與解法

首先看出了兩個問題:

  1. 質數太小,每個只有 90 bits。把數字丟到 FactorDB 就直接得出了它的因數:
  2. 訊息空間 (message space) 太小,它只加密 0 到 255 這堆數字。

基於 Euler’s theorem,\(g^{p(p-1)(q-1)}\equiv 1 (\text{mod }n)\)。如果計算 \(c_i^{(p-1)(q-1)} \equiv g^{m_i(p-1)(q-1)} (\text{mod }n)\),可以把 \(r\) 的效果取消。

所以只要把密文的 \(g^0, g^{(p-1)(q-1)}, g^{2(p-1)(q-1)}, …, g^{255(p-1)(q-1)}\) 分別取代為 \(0, 1, 2, …, 255\) 就可以得到 flag: MeePwnCTF{well_is_fact0rizati0n_0nly_w4y_to_s0lve_it?}

代碼如下:


Crypto 100: |\/|/-\T|-|

0x00. 背景

以下是這道題目所提供的東西:

簡單概括一下,題目提供了一個加密算法 (\(m\rightarrow c\)):

  • 算出 \(p=\text{MD5}(m)\) [*]
  • 把字元變成 ASCII:\(m = m_1 m_2 … m_k\)
  • 算出 \(c = (p\times m_1 + p)\times m_2 + p) \times …)\times m_k\) [**]

例如 \(m = \text{‘ABC’}\),\(p = 100\),那 \(c = ((100 \times  65 + 100) \times 66 + 100) \times 67 = 65666700\)。(這裡的 \(p\neq\text{MD5}(m)\),只是方便舉例用。)

給定 \(c = 64364485357060434848865708402537097493512746702748009007197338675\),已知 \(m\) 的長度為 14 字元,把 \(m\) 回復。

0x01. 思路與題解

這題目主要是 Harry 解出來的,我只負責裝茶倒水,順便寫一下 writeup:

首先發現由於 \(c\) 可以被 \(p\) 整除,所以可以先找出 \(p\) 的可能值。因數分解 \(c\) 得出:

由於 \(c\) 的因數不多於 5000 個,我們把所有因數都找列了出來。Harry 用了一個加速的方法:由於 MD5 是一個 128-bit 的字元,所以他篩選出所有在 \(2^{120}\) 跟 \(2^{128}\) 之間的因數。

然後對於每個 \(p\) 找出符合上式 [**] 的對應的 \(m\),如有,再用 [*] 檢查是否正確。

寫了個 Python 程式自動檢查,得出 flag: MeePwnCTF{d0y0ul1keM@TH?}


Crypto 600: Justpad

0x00. 背景

題目提供了一個 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\)。

0x01. 思路與題解

如果 \(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?不敢苟同。


Misc 850: Find me!

0x00. 背景

題目給定疑似 UIT-HCM 的首頁代碼,利用 DiffChecker 發現大部份的變動都是在轉換 tag 的次序。

0x01. 思路與解法

想到大約是在 tag 裡面的隱寫,上網找了之後發現 Deogol (https://hord.ca/projects/deogol/intro.html) 這個工具。下載之後運行

得出 flag: MeePwnCTF{W3lc0m3_T0_U1T_!}


Web 499: Br0kenMYSQL (v1-v3)

0x00. 背景

這三道 web 題的原始碼都差不多,在此只提供 v1 的。

看到任務的目標是 人格分裂 在同一次訪問裡,首先登入成 guest,然後登入為 admin。

0x00. 思路與題解

整個順利的過程大約如下:

  1. SELECT username FROM users WHERE id = $id,需要輸出  guest
  2. INSERT INTO logs VALUES('$ip')
  3. SELECT username FROM users WHERE id = $id,需要輸出  admin

等一下 - $ip 也有經過過濾,感覺有甚麼不妥。原來它會先檢查  $_SERVER['HTTP_X_FORWARDED_FOR'] 這個可以被人修改的變數,如果不為空就把它當成 IP。所以我的 IP 也可以換成 HAHAHA 了,哈哈哈。

言歸正傳,我們可以怎樣才可以成功地取得 flag 呢?

我們直接設:

當中的 “T0x1c K3n” 可以被取代成其他 payload,只需要一段基本上不會在 log 裡面存在的字。

因為第一次 “T0x1c K3n” 不在 logs 裡面,所以輸出了 guest ;而在 INSERT 那一步把 “T0x1c K3n” 放到了 logs 裡面,所以後面那一個 query 會輸出 admin 。

得出第一個 flag: MeePwnCTF{_b4by_tr1ck_fixed}

然後出現了 v2,更新了不多,就改變了以下兩行:

好吧,他把 select、from、括號都過濾掉了,那意味著所有函數都用不了。

這時思路開始奇怪:用 @@timestamp。只要第一次和第二次傳回的時間分別是 @@timestamp >t@@timestamp < t就可以了。

寫了一段代碼來找這個 \(t\),然後就得到第二個 flag: MeePwnCTF{_I_g1ve__uPPPPPPPP}

最後是 v3,這次作者連 time、date、sec 和 day 也過濾掉了。這次用了一個異常簡單的手段來得到 flag:

我們運用了自定義變數解決了問題:如果 @omg 是存在的,輸出 2 (guest 的 id);否則輸出 1 (admin 的 id)。由於 @omg  本身不存在,所以在第一次 query 會傳回 guest。

在 insert logs 的時候我們把 @omg 設成 5,所以在第二次 query 的時候會出現 admin。

得出第三個 flag: MeePwnCTF{_I_g1ve__uPPPPPPPP_see_you_next_Year}


發表迴響