IERAE CTF 2024 Writeup - Weak PRNG

2024年９月２１日〜２２日に開催された[IERAE CTF 2024](https://ierae-ctf.com/)に参加しました。

# Crypto
## Weak PRNG
Mersenne Twister の問題。
### 1.問題の理解
配布されたchallenge.pyを読み、出題サーバは以下の動きをすると理解した。

1. 乱数生成器（random, MT19937ベースの決定論的疑似乱数生成器）を、暗号学的乱数（secrets.randbits()）で初期化する。
2. 乱数生成器（random）から 32bit乱数を取り出し、secretとして保存
3. nc経由のアクセスで、リクエストがあれば32bit乱数を１６個出力してあげる。いくらでも教えてあげる。
4. ncの向こう側の人が、secretをわかって入力したら、FLAGを教えてあげる。   

つまり、解答者としては、
乱数列から、最初に出してくれた乱数の１個前の乱数を推定すれば良い、
と理解した。

### 2. Mersenne Twister の理解
ググった。素晴らしい記事があった。
Google検索のキーワード：Mersenne twister 過去 推定
[Mersenne Twister (MT19937) で未来と過去の乱数列を予測してみる【Python】](https://zenn.dev/hk_ilohas/articles/mersenne-twister-previous-state)

ざっくりいうと、Mersenne Twisterの疑似乱数生成器は以下のように振る舞う。
1. 内部状態として32bitがN=624個並んでいる。
2. 乱数リクエストがあると、１個32bitをtemperingして出力する。
3. 次のリクエストでは、次の32bitをtemperingして出力する。
4. 624個使い切ったら、内部状態を更新する。そのときに624個がandやorやxorやbitshiftでいい感じに混ぜる。

私が説明しても言葉足らずになるので、上記ページを見てほしい。

### 2. 解く
上記の
https://zenn.dev/hk_ilohas/articles/mersenne-twister-previous-state
には、まさに過去に出力された乱数の推定法（計算法）も書いてあった。

 1. 乱数列を集める。
 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から消しておく。

2. 過去の出力を推定する
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]になる。）

コードを書いた。
~~~awk: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が表示された！