2024年９月２１日〜２２日に開催されたIERAE CTF 2024に参加しました。
Crypto
Weak PRNG
Mersenne Twister の問題。
1.問題の理解
配布されたchallenge.pyを読み、出題サーバは以下の動きをすると理解した。
- 乱数生成器（random, MT19937ベースの決定論的疑似乱数生成器）を、暗号学的乱数（secrets.randbits()）で初期化する。
- 乱数生成器（random）から 32bit乱数を取り出し、secretとして保存
- nc経由のアクセスで、リクエストがあれば32bit乱数を１６個出力してあげる。いくらでも教えてあげる。
- ncの向こう側の人が、secretをわかって入力したら、FLAGを教えてあげる。
つまり、解答者としては、
乱数列から、最初に出してくれた乱数の１個前の乱数を推定すれば良い、
と理解した。
2. Mersenne Twister の理解
ググった。素晴らしい記事があった。
Google検索のキーワード：Mersenne twister 過去 推定
Mersenne Twister (MT19937) で未来と過去の乱数列を予測してみる【Python】
ざっくりいうと、Mersenne Twisterの疑似乱数生成器は以下のように振る舞う。
- 内部状態として32bitがN=624個並んでいる。
- 乱数リクエストがあると、１個32bitをtemperingして出力する。
- 次のリクエストでは、次の32bitをtemperingして出力する。
- 624個使い切ったら、内部状態を更新する。そのときに624個がandやorやxorやbitshiftでいい感じに混ぜる。
私が説明しても言葉足らずになるので、上記ページを見てほしい。
2. 解く
上記の
https://zenn.dev/hk_ilohas/articles/mersenne-twister-previous-state
には、まさに過去に出力された乱数の推定法（計算法）も書いてあった。
- 乱数列を集める。
ncで出題サーバにつなぎ1、Enterの順にキーボードを叩くと、16個ずつ32bit乱数を出力してくれる。624個ほしいので、38回以上1とEnterを叩く必要がある。
どうしても自動化できなかったので、teeでファイルに出力しつつ、1とEnterを40回ほど叩いた。
$ nc 35.201.xx.xx 19937 |tee hoge
hogeには出力された乱数以外にも「何しますか？」みたいな不要な行があるので、grepで適当にきれいにする（3桁以下の乱数が提示されていたらやり直すつもりで雑にやった）。
grep -o '[0-9]\{3,\}' hoge >input.txt
テスト用には、1行目をanswer.txtにでもコピーして、その行はinput.txtから消しておく。
- 過去の出力を推定する
https://zenn.dev/hk_ilohas/articles/mersenne-twister-previous-state
に書いてあるとおり。
temperingの逆は、untempering。そのまま使えば良い。
内部状態の過去へのさかのぼりは、直前の1個だけほしいので、
get_prev_state()のiのfor loopを回す必要はない。
i=624と思って、state[396], state[397], state[623], state[624]から計算すれば良い。
（もとのコードでは、i=623から0までiのループを回していき、state[623]から順番に後ろ向きに埋めていくのだけれど、私のコードでは、state[624]を、与えられたstate[396], state[397], state[623]で更新するイメージ。配列のアクセスはindexが624のmoduloになるので、i=624と思ってもi=0と思っても実質的に同じ。
出力してもらった乱数が、state[1]をtemperingしたもの,state[2]をtemperingしたもの...となっていて、state[624]を更新すると、state[0]になる。）
コードを書いた。
prng.awk
#!/usr/bin/gawk -f
function temper(y){
y=xor(y, rshift(y, 11));
y=xor(y, and(lshift(y, 7), 0x9d2c5680));
y=xor(y, and(lshift(y, 15), 0xefc60000));
y=xor(y, rshift(y, 18));
return y;
}
function unBitshiftRightXor(x, shift){
i=1;
y=x;
while ( i*shift < 32 ){
z=rshift(y,shift);
y=xor(x,z);
i=i+1;
}
return y;
}
function unBitshiftLeftXor(x, shift, mask){
i=1;
y=x;
while ( i*shift < 32 ){
z=lshift(y,shift);
y=xor(x, and(z, mask));
i=i+1;
}
return y;
}
function untemper(x){
x=unBitshiftRightXor(x, 18);
x=unBitshiftLeftXor(x, 15, 0xefc60000);
x=unBitshiftLeftXor(x, 7, 0x9d2c5680);
x=unBitshiftRightXor(x, 11);
return x
}
function get_prev(state396,state397,state623,state624){
result=0;
tmp=state624;
tmp=xor(tmp, state397);
if(and(tmp,0x80000000) == 0x80000000){
tmp = xor(tmp, 0x9908b0df);
}
result=and(lshift(tmp,1), 0x80000000);
tmp=state623;
tmp=xor(tmp,state396);
if(and(tmp, 0x80000000) == 0x80000000){
tmp = xor(tmp, 0x9908b0df);
result = or(result, 1);
}
result = or(result, and( lshift(tmp, 1), 0x7fffffff));
return result;
}
BEGIN{
}
{
if(NR==396) state396=untemper($0);
if(NR==397) state397=untemper($0);
if(NR==623) state623=untemper($0);
if(NR==624) state624=untemper($0);
}
END{
print(temper(get_prev(state396,state397,state623,state624)))
}
多少のデバッグをして、テストがうまく行ったので、もう一度ncで問題サーバにつないで1とEnter Keyを40回押してコードを走らせて回答を入力したら、FLAGが表示された！