high-low2 (cryptography 400)

実はhigh-lowにサーバの鍵が含まれていたのは出題ミスだったらしい。そういうわけで急遽湧いてきたらしい本来のhigh-lowである2問目。

proof/verify部分はほとんど対称な処理をしているように見えたので挙動の検討がついたのだが，shuffle部分については把握できなかった。処理が長くて面倒だったのもあるがサーバ側の挙動が隠れているのも一因である。 実際のところはshuffleこそまったく対称な処理であり，後にプロトコルの解説を見ながら読んでみれば確かに対称な処理になっていることがわかった。コードの複雑さとメソッド名に惑わされた。

脆弱性はproof/verifyの方だろうと当たりをつけて(数式の上で)何か悪さができないか考えていたが，時間内には解けなかった。

終了後に次の文献を参考にしながら読んだ。

• MentalPoker - A TTP-free mental poker protocol achieving player confidentiality - Qiita

  • via わふぅ。 • tkbctf4 参加記

• 元論文: http://www.tdx.cat/bitstream/handle/10803/5804/jcr1de1.pdf

一点気になるところがあるものの，ほぼ論文のプロトコルに忠実に実装されているように見える。

• init2で$C_0$を受け取り
• shffle1と，shuffle2の送信までが自分のProtocol 48
• shuffle2の受信とshuffle3が相手のProtocol 48
• prove1と，prove2の送信までがProtocol 49
• prove2の受信とverifyがProtocol 50

つまり，二人でシャッフルし合い，以下を繰り返す

1. サーバ側がカードをドロー (ただしまだ中身を見ない)
2. クライアント側はhigh/lowを宣言
3. サーバ側のカードドローの続き (サーバが中身を見る)
4. サーバ側がカードを公開

$C_i$の送信タイミングがProtocol 47に書いてあるよりも早いが，$C_i$を知っていたとしても$u$(プログラム上のm)の選択に影響を与えるとは思えない。

ふと思いついて，非正規の順序でリクエストを発行したところ，フライングでverifyリクエストを送ってもエラーを返さないことに気づいた。 つまり，サーバ側のstate管理に問題があり，verifyリクエストがchoiceの前に実行できるようになってしまっている。 よって選ぶ前にverify2の返信，m_cardを入手できてしまう。これにより，次のカードを決定できる。ただしverifyリクエストによってサーバ側の持つカードの集合からドローしたカードが取り除かれるため，二回呼ぶとエラーになることに注意する。

main.jsのplay関数を差し替える(Fiddler利用)。cp_proofによってverifyリクエストが発行されるので，それを除去する。

   1 function play (me, room) {
   2     return room.drawn.length < numbers.cards ?
   3             next(me, room).then(choose)
   4                           .then(function (c_card, me, room) {
   5                             return cp_verify(me.m1_card, me.m2_card, me, room);
   6                           })
   7                           .then(check)
   8                           .then(change_ui, miss)
   9                           .then(play) : undefined;
  10 }

Firefoxのコンソール上で

   1 var solver = setInterval(function(){ 
   2     if (flag) { clearInterval(solver); return }
   3     cp_prove(me.c_card, me, room).done(function (c_card, m_card, me, room) {
   4         me.m1_card = c_card;
   5         me.m2_card = m_card;
   6         (room.drawn[room.drawn.length-1] < get_card(m_card, room.x, room.p) ? $("[value=high]"): $("[value=low]")).click()
   7     });
   8 }, 1000);

Congratulations! FLAG{R1ceSp1n5Th3W0rld!}