They Were Eleven - BSides Ahmedabad CTF 2021 author's writeup

この記事はCTF Advent Calendar 2021の7日目の記事です。昨日はptr-yudaiのBest Pwnable Challenges 2021でした。私もBest Crypto Challenges 2021をやりたい気持ちはあるけど、未だ暗号分野に明るくなく、見たことない・知らないテクニックを使う問題がたくさんあり、それらはすべて良い問題に見えるので難しいですね

また、この記事ははてなエンジニアアドベントカレンダーの7日目の記事でもあります。昨日はid:yutailang0119さんのXcodeテーマを自作しませんか？でした。私は普段Vimを使っているのですが、theoremoon/cryptohack-color.vimというcryptohack/sublime-themeをVim用にポートしたカラースキームを使っています。意外とめちゃくちゃ見やすいので密かにおすすめです。

本題
まとめ

本題

以前zer0ptsというチームでBSides Ahmedabad CTF 2021というCTFを開催しました*1。そのときにThey Were Elevenという暗号問題を出題したのですが、思ったより解かれなかった上にwriteupもなく悲しいので供養と知見の共有を兼ねてauthor's writeupを書きます。これまで出題した問題はauthor's writeupを書いていたんだけどどうして今回は書いてなかったんだろう 🤔

問題

非常にシンプルです。私は問題のソースコードは短ければ短いほど良いと思っています。

以下は実際に出題したときのソースコードそのままですが、実際にはこのプログラムの実行結果も一緒に配布しています。こちらはhttps://gitlab.com/zer0pts/bsides-ahmedabad-ctf-2021/-/tree/master/crypto/they_were_eleven/distfilesで公開していますので、考えて解いてみたいという方はぜひご参照ください。

import os
from Crypto.Util.number import getPrime, getRandomRange

with open("flag.txt", "rb") as f:
    m = f.read().strip()
    m += os.urandom(111 - len(m))
    m = int.from_bytes(m, "big")

xs = []
for i in range(11):
    p = getPrime(512)
    q = getPrime(512)
    n = p * q

    c = m**11 * getRandomRange(0, 2**11) % n

    xs.append((c, n))

print(xs)

観察

教科書的なRSAとの差異がいくらかあります。

同一の平文 $m$ が異なる $e$ 個の剰余のRSAで暗号化されているため、一見するとHåstad's Broadcast Attackが適用可能かのように思えます。しかし単に中国剰余定理を用いようとしても、 $e$ 乗のあとに掛けられている $r_i$ が邪魔をして適切な $m^{e}$ を復元することができません。これが問題の根幹です。

また、追加情報として $m$ は111バイト以下であり十分小さことが分かります。 $m$ がそれ以上の長さになるとos.urandom(111 - len(m))が負の値を受け取って例外を吐くからです。

考察

$e$ 個の剰余と暗号文の組が与えられている以上、この問題は何らかの工夫を用いてHåstad's Broadcast Attackを変形して適用することで解くことができると考えられます。そのためには、どうにかして雑音 $r_i$ を除去したいです。

そこで次のような式を考えます。

$R = \prod r_i$ として $(R / r_i)c_i = (R/r_i)*(r_i m^e) = Rm^e$ が各 $i \in {1, \dots, e}$ について成り立ちますから、中国剰余定理を用いて

$\sum \lambda_i * (R / r_i) * c_i \equiv R*m^e$

です。ここで $\lambda_i$ はCRT coefficientと呼ばれる係数*2で、 $\mod n_i$ をとると1、それ以外の $\mod n_{j (\ne i)}$ では0になるような値です。

この式を変形して、次の等式を考えます。ただし $B$ は $m^e \lt B$ となるような値です。また、 $t$ は適当な整数です。

$(R/r_1, R/r_2, \dots, R/r_e, t) \begin{pmatrix} 1 & & & & \lambda_1 c_1 / B \\ & 1 & & & \lambda_2 c_2 / B \\ & & \ddots & & \vdots \\ & & & 1 & \lambda_e c_e / B \\ & & & & N / B \\ \end{pmatrix} = (R/r_1, R/r_2, \dots, R/r_e, Rm^e / B)$

このとき、右辺は左辺の行列で表される基底が張る格子の十分小さいベクトルになっています。つまり、LLLアルゴリズムを用いてSVPを解くことで中央の行列から右辺のベクトルを得ることができます。

右辺を得られればGCDなどを用いて $Rm^e/B$ から $m^e$ を得ることができるので、あとは $e$ 乗根を計算することで平文 $m$ が手に入り、フラグが手に入ります

エクスプロイト

以上の考察をコードに落とすとこうなります。エクスプロイトも簡潔にかけると嬉しいですね。

import ast
with open("output.txt") as f:
    xs = ast.literal_eval(f.read())

B = 2**(111 * 8 * 11)
c, n = [list(z) for z in zip(*xs)]

N = product(n)
k = len(xs)

l = [CRT_list([0]*i + [1] + [0]*(k-i-1), n) for i in range(k)]

M = matrix(QQ, k + 1, k + 1)
for i in range(k):
    M[i,i] = 1

for i in range(k):
    M[i,k] = l[i] * int(c[i]) / B
M[k,k] = N / B

L = M.LLL()

for row in L:
    try:
        z = []
        for i in range(k):
            z.append(B * row[k] / row[i])
        z = gcd(z)
        m = z.nth_root(11)
        print(bytes.fromhex(hex(m)[2:]))
    except:
        pass

まとめ

BSides Ahmedabad CTF 2021に出題したThey Were Elevenの簡易writeupでした。この問題は共通の値に対して小さい雑音が乗じられた値ががいくつか与えられている場合に、LLLを用いることでそれを除去できるという部分が本質です。このテクニックを用いた他の問題が出題されることももしかしたらあるかもしれませんから、憶えておけるとお得ですね。

宇宙船白号に送り込まれたタダたちも、うまくLLLを使いこなすことができれば隠れた11人目をあぶり出すことができたかもしれません*3。

CTF Advent Calendar 2021の明日の担当はﾈｺﾁｬﾝ、はてなエンジニアアドベントカレンダーの明日の担当はid:cockscombさんです。いずれも楽しみですね

また、CTF Advent Calendar 2021にはまだ若干の空き枠があります。この機会に皆さんの知見を集めてみんなで最強になりましょう。みなさんのご参加を心待ちにしています。

それでは