SECCON Beginners CTF 2023 Writeup - あめんばーどのバーチャル日記

部長が書いてたので解法だけ

VRC競プロ部でCTF出ようぜ！って話があったのでノリで無言で参加したWriteup

ぜんぜんわからんわー。

あめんばーさんはエンジニアとしてはやってきたことが偏ってて一般的な知識はめちゃくちゃ持ち合わせていません。いろんなことを数学と泥臭いプログラミング基礎知識のみでやってきましたって感じなのが露呈してしまいcrypto以外は読んでも「何言ってるの？」って感じでした。

cryptoだけはプログラミングに対する数学や実装での暗号解読って感じだったので「それならなんとか……」って感じでやったところ全完。

チーム内で素数にめちゃくちゃ詳しい人がいたのでだいぶ助けられました

Welcome

ディスコにあった文字列をコピっただけ。初めての参加だったのでとりあえずここでやり方とどういう文字列が来るのか把握

CoughingFox2

(flag[i]+flag[i+1])の二乗+iを格納した後にシャッフルした。

値の衝突が発生するような文字は来ていないと仮定してしまい、平方根の整数を取った後にもう一度二乗をして差を取ればiがいくつかわかるので、シャッフルもなくせる。あとは1文字目はcとわかっているのでドミノ倒しで決まる。

import sys
cipher=[省略]
ans=list()
li=list()
for v in cipher:
    vv = int(v**0.5)
    i=v-vv*vv
    li.append((i,vv))
li.sort()

ans.append(ord('c'))

for i,v in li:
    ans.append(v-ans[-1])

for v in ans:
    sys.stdout.write(chr(v))

捕捉

今回は幸いなことに衝突一切ナシだったが文字数が多いと絶対衝突する。衝突が発生した場合は文字数に対するマッチング問題になるのである程度までならグラフ問題に帰着できると思う。文字コードの範囲が32～127なので、二つの和の範囲は64～254。10万文字くらいあるとフル衝突が発生するので頑張る感じになりそう。ただ二乗と言う性質上、グラフのパスを結ぶ場所の幅は狭義単調増加的に増えるはずなのでランダム配置ならループは多くは発生しなさそう。どちらかというと全く同じ数値が現れるという~~悪意のある~~配置が一番つらくなりそうだが、そんなに巨大な事にもならなさそう。

Conquer

ROLは全部のビットを左にNシフトしている関数。左端のは右端に移動する。 keyがランダムで与えられた後に

下記を32回
- flagとkeyをxor
- keyを3シフト
最後にkeyとflagを出力

ROLがなにしているかわかれば逆算するだけで済む

length=max(cipher.bit_length(),key.bit_length())+1

def LOR(bits, N):
    for _ in range(N):
        bits = ((bits&1)<<(length-1)) | (bits>>1)
    return bits

for i in range(32):
    cipher^=key
    key=LOR(key,pow(cipher,3,length))    
cipher ^=key

ans = long_to_bytes(cipher)

Choice

むずかしかった。

問題文

RSA用の素数 $p,q,r$ が与えられる。素数とは言ったか知らんがたぶん素数。あと暗号 $m$ に対して次の値は最初から与えられる。 $n$ 以外はmod nでの値になる

$n:=pqr$
$s:=pq+qr+rp$
$c:=m^{65537}$

あとサーバー側に要求して $n\le a$ において次の値を知る事ができる

$f(a)=p^{a}+q^{a}+r^{a}$

$m$ を求めよ

方針

RSA暗号の鉄板で $c^{x}=m^{65537x}\equiv m$ になる $x$ が出せれば終わり。

フェルマーの小定理からこの累乗は $(p-1)(q-1)(r-1)=pqr-pq-qr-rp+p+q+r-1$ でループする。

$n$ と $s$ が揃ってる以上 $t:=p+q+r$ が死ぬほど知りたい

最初に考えたこと

$p+q+r=a$
$p^{2}+q^{2}+r^{2}=b$
$p^{3}+q^{3}+r^{3}=c$

これで $p,q,r$ を求めるのは結構鉄板のグレブナー基底の方針。なのでちょっと変えて

$p^{n}+q^{n}+r^{n}=b$
$p^{2n}+q^{2n}+r^{2n}=b$
$p^{3n}+q^{3n}+r^{3n}=c$

このクエリを要求すればなんかいい感じのことになりそうって思った。

三乗根が求められないので大ハズレだった上に、結構これでハマってしまった

辿り着いた式

定数倍ではなく $f(n)t-f(n+1)=p^{n}q+pq^{n}+p^{n}q+pq^{n}+p^{n}q+pq^{n}$ なので、それでいろいろできないかもちょこちょこ考えた。ただこれはあんまりうまくいかったが最終的にたどり着いたのがコレ

$f(n)s+f(n+2)\equiv f(n+1)t$

つかってなかった $s$ を活用して $pqr$ の項を作り出してmodで消してしまおうとう算段。気づいた時にあまりにも美しく感じてしまった。

最後に

さっきも言った式を変数で表すと $n-s+t-1$ でループすると言えるため、あとは $t$ にくっついてる $f(n+1)$ がジャマである。だったら $f(n+1)n-f(n+1)s+f(n+1)t-f(n+1)$ でもループするよね、としたところ失敗。よくよく考えたら $f(n+1)t$ はmod nの余りを出す必要があるくらい大きな値なので、 $n-s+t-1$ はmodを取ってないことを考えると狂ってる。

逆元を求めるには $n-s+t-1$ の繰り返し二乗法で求めるには $t$ が知らないから無理じゃねーか、と十分くらい考えた後に自分でブログに書いた拡張ユークリッド互除法を使っても普通に求まるじゃんかと気づく。失態。

終了。

def ect(a,b):
    if b==0:
        return a,1,0
    g,x,y=ect(b,a%b)
    return g,y,x-y*(a//b)

n=初期条件
s=初期条件
fn0=クエリで聞いたやつ
fn1=クエリで聞いたやつ
fn2=クエリで聞いたやつ
fn1t=fn0*s+fn2
_,rfn1,_=ect(fn1,n)
t=fn1t*rfn1%n
v=1
mod=n-s+t-1
for i in range(65537):
    if v%65537==0:
        x=v//65537
        break
    v+=mod
ans=pow(c,x,n)

switchable_cat

LFSRをネコちゃん三匹分動かした後にLFSRをさらに働かせてだしたコードです。

LFSR

01のコードが有限にある。今回は128ビット。一番右の0か1でクエリを取得する。新規クエリを現在のコードに対する線形式で新しく作成して左に追加することで128に収めつつもランダムにいろいろクエリを獲得できる。うまい線形式を定義すれば $2^{length}-1$ と、全部ゼロ以外のビットパターンが網羅できるらしい。

ネコちゃん

ネコちゃん3匹と言っているが、ネコちゃんの文字コードは128008なので、要はLFSRを $128008^{3}$ 回動かした後に最後に文字コードに処理をする。さっきは $2^{length}-1$ でループすると言ったが、別にその約数が出てくるってわけでもないっぽい。

解法

ただ所詮128ビットの線形式なので行列の掛け算が可能。ネコちゃん三匹分の $10^{18}$ 以上の処理だとしても繰り返し二乗法で問題ない。

こんな感じの行列式を用意して繰り返し二乗法して

[s1]=[0,1,0,0][s0]
[s2]=[0,0,1,0][s1]
[s3]=[0,0,0,1][s2]
[s4]=[線形式][s3]

どうせXORなのでもう一回計算すれば戻るので同じことをする

seed=与えられたやつからネコちゃん三匹分の行列かけたやつ

class LFSR:
  同じなので省略

cipher = 与えられた奴
for l in range(1024):
    lfsr = LFSR()
    key = lfsr.gen_randbits(l * 8)
    ans = key ^ cipher
    aa = long_to_bytes(ans)
    try:
        print(aa.decode('utf-8'))
    except:
        pass

cooking

出題側のミスじゃなければただのギャグである解法

問題ちゃんと詳細

サーバーに接続する

meat(2048ビット),salt(64ビット)の値がランダムに伏せて作成される
ユーザー側が $2^{128}$ 以上 $2^{2048}$ 未満の素数pを用意する
$meat^{3}$ がmod pで与えられる
ユーザーが $2^{128} \le g \lt p$ の値を与えると $(g^{3}(meat\ \text{xor}\ salt))^{meat+g^{3}}$ $+g(meat\ \text{xor}\ salt)^{3}$ の値をmod pで教えてくれる
16回聞いた後にmeatはいくつか当てるとフラグゲット

ギャグ解法

一緒にやっていた水色の方が素数にとても詳しい方だったのだが、クソデカ素数を用意する方法を教えてもらえる。

というわけで「3で割って2あまるクソデカ素数」を用意する。具体的には $2^{2048}-2543$ が用意できた。そうするとこのmod pは $p-1$ でループする。そうすると3とは互いに素なので都合よく $m^{3x} \equiv m$ な $x$ が取れる。取る。

とはいえ、あくまでこの値は $mod\ p$ の中の候補の一つなので、その中から都合のいいものをリクエスト16回で当てていくのがいいのだろう。

ただし用意した素数があまりにもデカすぎるので候補の1つとか言ってもそれしか候補がない確率の方がずっと高いので、それを答えて終わり

p=クソデカ素数
m3=与えられたm^3
print(p%3)
x=1
while True:
   if x%3==0:
       x//=3
       break
   x+=p-1 
g,pp,_=ect(3,p)
m=pow(m3,x,p)

感想

cryptが全完できたということで初めてにしてはすごくいい成績を収められたと思うし、参加したVRC競プロ部も20/778位に入ることができました（結構すごいのでは？）

普段の競プロが $10^{18}$ 程度までの数しか扱わないのに $10^{1800}$ とか普通に扱う問題が出てきてなかなか新鮮でした。というかpythonとlinux使えるように頑張っててよかった。（水色あたりまではどっちも全然できなかった）

とはいっても本気でcrypt以外がなにを読んでもさっぱりわからない。エンコードもわからない、webもわからない、gpt…もそこまでわからない、やっぱり自分って数学とかアルゴリズムとか好きなだけでエンジニアとしての知識はほとんど持ってないんだなぁと思いました。その辺りはしっかり伸ばしていきたいと思っています。いまとりあえずWebアプリをお試しで作るヤツもやってるのでそれは完結したいわね。

でもクソ楽しかったのでヨシ。数学遊びはいくらあってもよい。