SatokiCTF 報告書
SatokiCTFをチーム「脆弱エンジニア(full_weak_engineer)」で参加してきました。
2位でした！
なお、asusnの得点は1点です。
チームメンバーのsirumaさんは100倍、tchenは1000倍も得点しています。すごい！
SatokiCTFのここがすごい
開催中のネタバレOK
SatokiCTFは、開催中のYouTube配信OKの異例の大会です。
というわけで、YouTube配信しながら問題を解いていました。
チームメンバーや、大会参加者などが見ながら、コメントでwaiwaiしてくれました。
運営が現れて「その問題やばい」と助言してくれたり、あまりにも違うところを深掘りしようとすると、それは〇〇しているだけです、みたいなガイドをしてくれて、助かりました。
（↓本記事のzzzの項目で配信の切り抜き動画あり）
賞品が豪華
賞品が 大喜利 豪華です！
誰でも賞品を提供していいよ！という状態でした。ありがたい。
Satokiがチームに参戦!?
チームのパスワードをWelcome_Satokiにしていたおかげか、Satoki(本人)がチームに参戦してくれました！
でも得点0点です。もう少し頑張って欲しかったです。
チームメンバーのWriteup
Web全完まであと1問だったtchenのWriteupはこちら！
解けた？問題
zzz (Misc)
問題
sshで接続すると、一生sleepし続けてしまうシステムがある。
#!/bin/bash
echo "I'm going to sleep for a while. I will give you the flag when I wake up. Oyasumi!"
sleep infinity
cat /flag.txt
sshd_configで上記のスクリプトを実行しているという状態。
RUN echo 'ForceCommand "/app/zzz.sh"' >> /etc/ssh/sshd_config
この状態でflag.txtを見れないかという問題。
解法
以下を試したのですが、上手くいかず。
- scpでファイルを持ってこようとする
- sshのオプションで
/etc/ssh/sshd_configを無効にしようとする - pwntoolsで中断するコマンドを送信しようとする
そんな中、配信中に救世主が現れる！
キーボードをガチャガチャしたらいけた
振り返り
解きたかった問題を解説してきます。
enmusubi (Crypto)
問題
DSAのような署名アルゴリズムが与えられ、検証を突破できてしまうような署名を求めろという問題
from Crypto.Util.number import isPrime, getRandomRange
from hashlib import sha256
FLAG = "flag{*****REDACTED*****}"
p = 1151151150115115115115115115115011511511511501151151151151151151151151151150110011511511501151151151151151151150115115115115011511511511511511511511511511501100115115115011511511511511511511501151151151150115115115115115115115115115115011001151151150115115115115115115115011511511511501151151151151151151151151151150110115115115011511511511511511511501151151151150115115115115115115115115115115011011511511501151151151151151151150115115115115011511511511511511511511511511501101151151150115115115115115115115011511511511501151151151151151151151151151150110011511511501151151151151151151150115115115115011511511511511511511511511511501101
q = 115115115011511511511511511511501151151151150115115115115115115115115115115011
assert isPrime(p)
assert isPrime(q)
assert p%q == 1
h = 115
g = pow(h, (p-1)//q, p)
assert g > 1
print('g =', g)
x = getRandomRange(1, q)
y = pow(g, x, p)
print('y =', y)
def verify(m, r, s):
assert r%q != 0
assert s%q != 0
z = int(sha256(m).hexdigest(), 16)
w = pow(s, -1, q)
return (pow(g, z*w, p) * pow(y, r*w, p) - r) % p == 0
print('Give me the signature of "flag"')
r = int(input('r = '))
s = int(input('s = '))
if verify(b'flag', r, s):
print('Congratulation! The flag is', FLAG)
解法
ほぼほぼDSAなので、実際の実装と見比べていきます。
どうやら検証部分が甘そうです。
- 問題のverify：
(pow(g, z*w, p) * pow(y, r*w, p) - r) % p == 0 - 実際のverify：
(pow(g, z*w, p) * pow(y, r*w, p)) %p % q == r
自分が気づいたDSAと違うところ
-
z*w,r*wの計算に(mod q)していない - 左辺を
(mod q)していない - 右辺
rを左辺で引いているところがなんか怪しい
DSAについても英語のWikipediaで調べます。
pow(g, q, p) = 1 や pow(y, q, p) = 1 などが使えそうです。
しかし、いくら考えてもこれらを満たすrとsを作るのは無理では？？？と諦めてしまいました。
ヒント
しばらくしたら、ヒントが与えられました。
DSAっぽいアルゴリズムが実装されています。正しいDSAの署名検証アルゴリズムとどこが違うか見比べてみましょう。 sの値を決め打って(例えばs=1など)、verifyが通るrの値を構築してみてください。 素数p,qが115115...の形であることは解法に関係ありません。
s=1と固定して良さそうです。s=1とすると、w=1となり、検証部分以下のようにシンプルにできます。
(pow(g, z, p) * pow(y, r, p) - r) % p == 0
それでも、rについて冪乗と一次式で方程式を解くのが無理そうだったので、作者の解答を見ました。
g^(zw)y^(rw) modpのmodqを取っていないところも違いますが、最初の0<r<qのチェックがr%q!=0のみになっている点がポイントです。
大きいrで作ることを考えて、例えばr=aq+1としてみると、g^(zw)y^(rw) modpは一定なので、aを調整することでg^(zw)y^(rw)=r modpにできます。
もっと疑うところがあったんですね！
圧倒的にDSAと違うところ
- rのチェックが
0<r<qでなくr%q!=0
解答をもとに、(pow(g, z*w, p) * pow(y, r*w, p)) % p が一定になることついて考えていきます。
右側(pow(y, r*w, p))について
pow(y, q, p) = 1なので、pow(y, a*q+1, p) = yとなります。
これをw乗しても、pow(y, (a*q+1)*w, p) = pow(y, w, p)となり、aによらず一定です。(wすなわちsを固定した場合)
左側(pow(g, z*w, p))について
pow(g, q, p) = 1なので、pow(g, z*w, p)は、aによらず一定です。(wすなわちsを固定した場合)
よって、(pow(g, z*w, p) * pow(y, r*w, p)) % pは、sを固定すれば、aによらず一定とできます。
確かに一定ですね！
rの調整
sは何でも良さそうなので、ご縁がありますように115に固定します。
pow(g, z*w, p) * pow(y, r*w, p) = r (mod p)となるようにaを求めます。
一定となる左辺pow(g, z*w, p) * pow(y, r*w, p)をdとすると、d = a * q + 1 (mod p)となればよく、aについて解けばよいです。
よって、以下のようにrとsを定めればflagが得られました！
s = 115 # なんでもよい
w = pow(s, -1, q)
z = int(sha256(b'flag').hexdigest(), 16)
d = pow(g, z*w, p) * pow(y, w, p)
a = (d - 1) * pow(q, -1, p) # d = a * q + 1 を満たす a
r = a * q + 1
賞品 GCP Credit $100 の使い道
今回、チームで2位だったため、task4233さんよりGoogle Cloud PlatformのCredit $100 をいただきました。ありがとうございます！
チームとしては初の入賞なので、嬉しい限りです。
GCP Creditは、ASUSN CTF2のインフラとして使ったり、何か常設のサイトを作れたらいいなと考えています。
おわりに
チーム「脆弱エンジニア(full_weak_engineer)」では、SECCON CTF決勝進出を目指してCTFに参加しています！
チームでCTFをやりたいメンバーを常に募集していますので、YouTubeの概要欄にあるDiscordリンクから、気軽にご参加ください！
Pwn担当大歓迎（切実）（定期）
TODO: Satokiにご飯を奢らせていただく
Discussion