ふるつき

v(*'='*)v かに

RTACTF (SECCON Speedrun Challenge) 感想

完走失敗したので完走した感想はありません!!!!!!!

2021年12月19日(日) 15:40〜 SECCON電脳会議のコンテンツとしてRTACTF、あるいはSECCON Speedrun Challengeと名打ったライブ配信が行われていました。これはSECCONの作問者やSECCONで上位だったプレイヤーが如何に短い時間で問題を解けるかを競うものです。私はSECCON CTFで作問をしていたこともあり、この企画でcryptoの問題のspeedrunに挑戦する走者として参加しましたので、本記事では感想・振り返り・競技中に解いた問題のwriteupなどを書いていこうと思います。

そもそも

そもそもこの企画はSpeedrunとあるようにできるだけ高速に、限られた時間で何かを達成しようとする、いわゆるRTAというやつなのですが、RTAがよく行われているジャンルであるゲームとは異なり、プレイヤーは問題について全く未知の状態で早時に挑戦することになります*1。これは企画として非常に挑戦的で、どれくらいの時間で解けるのか――そもそも走者がちゃんと問題を解くことができるのかさえ不透明な状態でのライブ配信となりました。

どのような結果になったかは、こちらのアーカイブから実際の様子をたどることができるのでぜひご覧ください。

ご覧くださいとは書いたものの、一言でまとめてしまえば概ね成功、という形に収まったのではないでしょうか。十分な準備を重ねてきたとは言えない状態での開催でしたから多少のわちゃわちゃはあるものの、大きなトラブルなく、当初描いていたような放送を実現することができたのではないかと思います。企画の立案から実現までの波乱万丈はいいだしっぺかつ最大級の功労者であるrexさんが書いてくださることと思いますので期待してお待ち下さい。

スコアサーバ

書きました。ptr-yudaiがいじれるようにめちゃくちゃ素朴なやつを書いたけど結局特にいじられることはなかった(完)。めちゃくちゃ雑につくったのでRTACTFが大人気になるとサーバが落ちる危険性もありました。結果として人気にならなくて良かった(?)あとLMTの面々には無理言ってサーバ緊急で用意してもらいました。ありがとう……

本番

一口 writeup + 一口感想です

Sexy RSA (163.75 sec)

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

def getSexyPrime(n=512):
    # Sexy prime: https://en.wikipedia.org/wiki/Sexy_prime
    while True:
        p = getPrime(n)
        if isPrime(p+6):
            return p, p+6

if __name__ == '__main__':
    # Plaintext (FLAG)
    m = int.from_bytes(os.getenv("FLAG", "FAKE{sample_flag}").encode(), 'big')

    # Generate key
    p, q = getSexyPrime()
    n = p * q
    e = 65537

    # Encryption
    c = pow(m, e, n)

    # Information disclosure
    print(f"n = 0x{n:x}")
    print(f"e = 0x{e:x}")
    print(f"c = 0x{c:x}")

ひと目ですね、セクシー素数という言葉には聞き覚えがあったので、問題の +6 という部分だけみてすぐ実装した……と思います

with open("output.txt") as f:
    n = int(f.readline().strip().split(" = ")[1], 16)
    e = int(f.readline().strip().split(" = ")[1], 16)
    c = int(f.readline().strip().split(" = ")[1], 16)

PR.<x> = ZZ[]
f = x*(x + 6) - n
p = int(f.roots()[0][0])
q =  n // p

d = int(pow(e, -1, (p-1)*(q-1)))
m = pow(c, d, n)
print(bytes.fromhex(hex(int(m))[2:]))

Proth RSA (465.36 sec)

from Crypto.Util.number import getRandomInteger, getPrime, isPrime
import os

def getProthPrime(n=512):
    # Proth prime: https://en.wikipedia.org/wiki/Proth_prime
    while True:
        k = getRandomInteger(n)
        p = (2*k + 1) * (1<<n) + 1
        if isPrime(p):
            return p, k

if __name__ == '__main__':
    # Plaintext (FLAG)
    m = int.from_bytes(os.getenv("FLAG", "FAKE{sample_flag}").encode(), 'big')

    # Generate key
    p, k1 = getProthPrime()
    q, k2 = getProthPrime()
    n = p * q
    e = 65537
    s = (k1 * k2) % n

    # Encryption
    c = pow(m, e, n)

    # Information disclosure
    print(f"n = 0x{n:x}")
    print(f"e = 0x{e:x}")
    print(f"s = 0x{s:x}")
    print(f"c = 0x{c:x}")

 p = (2k+1)*(2^{n}) + 1 という形になっていて、 s = k_1 * k_2 \mod nが与えられています。 k_1 * k_2 \lt nなので剰余をとっている意味はなく、 k_1, k_2という2変数に関して、 n, sの2式あるので適当に式変形を解けるはずです。というわけでグレブナー基底を使ってドン

with open("output.txt") as f:
    n = int(f.readline().strip().split(" = ")[1], 16)
    e = int(f.readline().strip().split(" = ")[1], 16)
    s = int(f.readline().strip().split(" = ")[1], 16)
    c = int(f.readline().strip().split(" = ")[1], 16)

PR.<u,v> = QQ[]
p = (2*u + 1) * (1<<512) + 1
q = (2*v + 1) * (1<<512) + 1

polys = [
    p*q - n,
    u*v - s,
]
I = Ideal(polys)
ans = I.variety(ring=ZZ)[0]
u, v = ans[u], ans[v]

p = (2*u + 1) * (1<<512) + 1
q = (2*v + 1) * (1<<512) + 1

d = int(pow(e, -1, (p-1)*(q-1)))
m = pow(c, d, n)

print(bytes.fromhex(hex(m)[2:]))

本番ではscを読む順番を取り違えて解けなくて焦っていました

Leaky RSA

解けませんでした。今にして思えばこれが解けないのは精進が不足していますね。うーん配信で緊張していたから……という言い訳も通用しなさそうですね。反省です。それにしたって良い問題ですね

Neighbor RSA (791.75 sec)

import os

# Plaintext (FLAG)
plaintext = os.getenv("FLAG", "FAKE{sample_flag}").encode()
plai  = plaintext[:len(plaintext)//2]
ntext = plaintext[len(plaintext)//2:]
m1 = int.from_bytes(plai  + os.urandom(128), 'big')
m2 = int.from_bytes(ntext + os.urandom(128), 'big')

# Generate key
e = 65537
p = random_prime(1<<2048)
q = random_prime(1<<512)
r = random_prime(1<<512)
n1 = p * q
n2 = next_prime(p) * r
assert m1 < n1 and m2 < n2

# Encryption
c1 = pow(m1, e, n1)
c2 = pow(m2, e, n2)

# Information disclosure
print(f"e = {hex(e)}")
print(f"n1 = {hex(n1)}")
print(f"n2 = {hex(n2)}")
print(f"c1 = {hex(c1)}")
print(f"c2 = {hex(c2)}")

 n_1 = pq,  n_2 = (p + \alpha)r = pr + \alpha rです。 \alphaはごく小さい値なので \alpha rは512〜bit程度です。こうしてみるとひと目Approximate GCD Problemですね。本番でもひとめそう見えたので高速に解きました。高速に解いた……はずですが負けてしまいました。なぜ……🤔

ちなみにApproximate GCD Problemについては以前記事にしました。これを書いたおかげでみんな解けたものと思いたいですね

furutsuki.hatenablog.com

with open("output.txt") as f:
  e = int(f.readline().strip().split(" = ")[1], 16)
  n1 = int(f.readline().strip().split(" = ")[1], 16)
  n2 = int(f.readline().strip().split(" = ")[1], 16)
  c1 = int(f.readline().strip().split(" = ")[1], 16)
  c2 = int(f.readline().strip().split(" = ")[1], 16)



# e = 65537
# p = random_prime(1<<2048)
# q = random_prime(1<<512)
# r = random_prime(1<<512)
# p2 = next_prime(p)
# 
# n1 = p * q
# n2 = p2 * r

K = 2**512
M = matrix(ZZ, [
  [K, 0, n1],
  [0, K, -n2],
])

L = M.LLL()
for row in L:
  zs = [int(abs(x//K)) for x in row]
  for r in zs:
    if r == 0 or r == 1:
      continue
    if n2 % r != 0:
      continue

    p2 = n2 // r
    print(r, p2)
    p = previous_prime(p2)
    q = n1 // p

    print(p, q, r)

    d1 = int(pow(e, -1, (p-1)*(q-1)))
    d2 = int(pow(e, -1, (p2-1)*(r-1)))

    m1 = pow(c1, d1, n1)
    m2 = pow(c2, d2, n2)

    print(hex(m1)[2:] + hex(m2)[2:])   

タイムロス要素は2048bitの素数を生成するのに時間がかかったこと、previous_primeのことを忘れていたことですね

総括

負けて悔しい花いちもんめ。またやりたいですね。みんなつよい

*1:ゲームでいうと初見RTAみたいなものですか?

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-themeVim用にポートしたカラースキームを使っています。意外とめちゃくちゃ見やすいので密かにおすすめです。

本題

以前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が111バイトになるようにランダムなパディングが付与されていること
  • 同じ平文 mがそれぞれ異なる n_1, \dots, n_{11}のもとで、public exponent  e = 11を用いて暗号化されていること
  • 暗号文 c_i m^{e_i}にランダムな値 r_i \leftarrow \lbrack 0, 2^{11} \rbrackが掛けられたうえで \mod n_iをとった形になっていること

同一の平文 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にはまだ若干の空き枠があります。この機会に皆さんの知見を集めてみんなで最強になりましょう。みなさんのご参加を心待ちにしています。

それでは

*1:開催記はhttps://furutsuki.hatenablog.com/entry/2021/11/07/143907

*2:良い日本語訳を知りません

*3:

Crypto CTFプレイヤーにおすすめのVim Plugin 1選

こんにちは。今回はCTFで暗号問題を解いている && Vimを使っている方へのお得情報です。

昨今の暗号問題では多変数剰余多項式の小さい解を求めたいことや、連立した不等式の解を求めたいことが多くあります。そしてこれらの問題についてはそれぞれdefund/coppersmithrkm0959/Inequality Solving with CVPという非常に洗練されたライブラリが存在しますから、これらを利用したいことは多いですよね。

こういったときに煩わしく感じるのがライブラリの利用方法です。これらのライブラリはSageMathという処理系用のプログラム(Sageという言語?)で記述されていますが、Sage自体にはパッケージマネージャのような仕組みはありませんから、毎回プログラムをGitHubからコピー&ペーストする必要があります。

Sageにはloadという関数があり、これでSageの外部プログラムを読み込むこと自体はできますが、これを使う場合にもプログラムをwgetなりcurlなりでダウンロードしてくるひと手間が必要になります。

今回はこんな時に便利なVim Pluginであるtheoremoon/CTF.vimを紹介します。動作にはcurlが必要です。

このプラグインを読み込むとDefund, Rkmというコマンドが定義され、これを実行するとそれぞれdefund/coppersmith, rkm0959/Inequality Solving with CVPのプログラムを編集中のファイルに展開してくれます。defund/coppersmithを使いたい問題に出会ったときにサッと:tabnew defund.sage :Defund :wq load("./defund.sage") と入力すれば良いので便利です。また、ファイルを分けずにそのまま埋め込むと解法とライブラリと、ライブラリのGitHubへのURLが近い位置にまとまって、Gistなどにwriteupを上げるときに非常に便利です。

これが実際どのくらい便利なのかは↓をご覧ください。便利ですね

ところでVim:r!<command> とすることで<command>の実行結果を編集中のファイルに流し込めるのでわざわざvim pluginにしなくてもcurlスクリプトの上手なエイリアスにパスが通っていればそれで良いですね。


この記事はCTF Advent Calendar 2021の5日目の記事です。こんなよくわからない記事にAdvent Calendarの貴重な枠が消費されてしまって悲しいですね。もっと良い知見を集めるためにCTFプレイヤーの皆様は高速に空いている枠を抑えてください。よろしくおねがいします

adventar.org