SECCON CTF 2022 Quals Writeups

SECCON CTF 2022 Quals にチーム TSG で参加し、this_is_not_lsb と noiseccon (実装パートのみ; アイデアは mikit さんから) の 2 問を解きました。以下はその writeup です。

this_is_not_lsb

Tired of difficult problems? Ok, I give you a simple LSB Padding Oracle problem. Ah, my magic has exploded... Sorry

問題概要

  • N …… 2 つの 512 bit 素数 p, q の積
  • e=65537
  • flag_length …… flag のビット長
  • c …… 暗号文

上の情報に加えて、任意の暗号文を復号した結果の1014～1023ビット目が 0011111111 かどうかをサーバーから得られる。そこから flag を推測すればよい。

解法

通常の LSB Padding Oracle problem では復号結果の下位 1 bit を得られるが、この問題では代わりに上位 10 bit のパターンが 0011111111 かどうか知ることができる。

以下、平文を m とする。 LSB が与えられる通常の問題と同様に、本問題も Ke c を復号して得られる Km の性質から解ける。 この問題の場合は Km が 0b0011111111<<1014 以上 0b0100000000<<1014 未満かどうか知ることができるので、これを満たすような K の下界を二分探索し、そこから m を計算すればよい。

flag の形式が SECCON{[\x20-\x7e]+} であることを利用して適切に二分探索の探索範囲を絞っておくと、K の値の上界を気にせず探索できる。

SECCON{WeLC0me_t0_tHe_MirRoR_LaNd!_tHIs_is_lSb_orAcLe!}

▶ソルバー（クリックで展開） gist.github.com

noiseccon

Noise! Noise! Noise!

問題概要

サーバーに scaleX, scaleY の 2 種類の値を渡すと、サーバーはランダムなシードで生成された 2 次元パーリンノイズの中から (offsetX, offsetY) を左上端とした 12.8×12.8 の領域を切り抜き、 256×256 ピクセルへと 20 倍に引き延ばして返す。

なお、offsetX, offsetY は index.js 内で以下のように定義されている。

const offsetX = div(flagInt, scaleX);
const offsetY = div(flagInt, scaleY);

また div は以下の通り実装されている。要するに div(x,y) は浮動小数点演算 x/y の結果から小数点以下を 4 bit、上を 32 bit だけ残して返す関数である。

const div = (x, y) => {
  const p = 4;
  return Number(BigInt.asUintN(32 + p, (x * BigInt(1 << p)) / y)) / (1 << p);
};

ここから flagInt を推測すればよい。

解法

アイデア

パーリンノイズは格子点を基準にテクスチャを生成するため、格子点には何らかの特徴がある。この特徴をもとに、サーバーが返す画像から格子点の位置を復元できれば offsetX, offsetY の小数点以下が分かる。

各オフセットは小数点 4 bit の情報を残しているので、scaleX, scaleY の両方を適切に設定すると 1 枚の画像からフラグ 1 文字分の情報を得られそうである。

実装

1 枚の画像からフラグの i 文字目を得るためには、offsetY, offsetX の小数点以下 4 bit (以下、hi, lo とする) がそれぞれ i 文字目の上位/下位 4 bit を表すようにすればよく、以下のように scaleX, scaleY を設定するとよい。

scaleX = 1 << (8 * (total_length - pad_length - idx) - 4)
scaleY = 1 << (8 * (total_length - pad_length - idx))

index.js の実装より、パーリンノイズの格子点に相当するピクセルの色はすべて #808080 になっているはずである。 (hi, lo) = (0, 0), (0, 1), ... , (15, 15) とそれぞれ仮定を置き、その場合の格子点の推定位置のピクセルの色が #808080 からどれだけ離れているかを残差平方和で表すと、この残差平方和を最小にするような (hi, lo) の組が求めたい情報になっている。

SECCON{p3RLin_W0r1d!}

フラグ 0 文字目を得るためのノイズ画像 (左)、そこから推測した (hi, lo) (右)

▶ソルバー（クリックで展開） gist.github.com