P2Pでセキュアにじゃんけん
はじめに
じゃんけんを1対１のP2Pネットワークでセキュアに行なう方法を考えます。
基本的に車輪の再発明なので、頭の体操みたいなものと思ってください。つっこみも歓迎します。
リアルワールドでのじゃんけん
まず、リアルでのじゃんけんは 「じゃんけん、ほい！」 っと掛け声を言ってタイミングを合わせてお互いの手を突き出し、瞬時にグー、チョキ、パーのいずれかの形状に手のひらを固定します。
勝者を決めるルールはグーがチョキに勝ち、チョキがパーに勝ち、パーがグーに勝つ、と定められています。
じゃんけんにたいする攻撃として考えられるものとしては、相手の出す手を知ってからこちらの手を決める「後出し」というものがあります。それを防ぐために、意外と重要になるのがこの掛け声です。
時間と空間を共有していることを利用して、お互いに手を出すタイミングを掛け声で同期し、お互いの目視による監視で同時に手を出していることを保証して後出し攻撃を防いでいます。
じゃんけんで出す手を決定する過程を互いに監視できる条件下であればある程度セキュアな仕組みといえます。
しかしネットワーク上でお互いのピアとネットワークを監視することは難しいため、この方法をとることは非現実的です。
封じ手によるじゃんけん
タイミングを同期させる以外にも後出しを防ぐ方法があります。「封じ手」を使うパターンです。
例えばじゃんけんで出す手を予め決めておきカードの裏に書いて場に伏せておきます。お互いがカードを出した後で好きなタイミングでカードを返して皆にみせれば、じゃんけんの勝敗を決めることができます。
この方法であれば、じゃんけんの手を決めるタイミングがずれていても後出し攻撃を防ぐことができます。
クライアントサーバ型で封じ手じゃんけん
P2Pを考える前にクライアントサーバパターンで考えてみます。この場合はサーバをトラストすれば話は簡単です。
２つクライアントがサーバにじゃんけんの手を送信しサーバーが保管します。両方のクライアントの手が出揃ったところで、サーバが勝敗を決定し、クライアントに結果を通知します。
P2P型でじゃんけん（ベーシック）
P2Pネットワークで「封じ手」を実現する方法を考えます。封じ手の封筒の代わりになるものとして考えつくものはフィンガープリントがあります。
お互いの手のフィンガープリントを予め交換しておいて、その後そのフィンガープリントの入力になったじゃんけんの手の情報をあかせば後出し攻撃を防げそうです。
手順を順に説明します。（画像参照）
- 手をフィンガープリントに変換。相手には秘密にしたままお互いの手を決めて、その手のフィガープリントを計算します。
- フィンガープリントをピア同士で交換。
- フィンガープリントが届いたことを確認してからピア同士で手を交換。フィンガープリントを先に送っているのでこの時点で手を変更することはできません。
- 相手の手がフィンガープリントと一致することを検証。お互いに相手の手のフィンガープリントが予め受け取っていたものと一致することを確認します。相手の封じ手がこの時点で判明するため、お互いのピアで勝敗がわかります。
手順
辞書攻撃対策
攻撃方法
前段の手法は辞書攻撃に対して脆弱です。
例えば、じゃんけんの手の情報を交換するには、まず手を共通の方法で符号化する必要があります。
そこで、符号化をぐーをgちょきをc,ぱーをpというテキストとしたとします。
３パターンしかないので攻撃側はあらかじめ、全ての手のフィンガープリントを計算しておくことができます。
すなわち手順の２.でフィンガープリントを交換した時点で相手の手がわかってしまいます。
// フィンガープリントにSHA256を採用した場合
// `g`のフィンガープリント
fg = sha256('g');
// '768c71d785bf6bbbf8c4d6af6582041f2659027140a962cd0c55b11eddfd5e3d'
// `c`のフィンガープリント
fc = sha256('c');
// a3a5e715f0cc574a73c3f9bebb6bc24f32ffd5b67b387244c2c909da779a1478
// `p`のフィンガープリント
fp = sha256('p');
// fd6641673e7f3bf6e80e4bc5401fcb2821a1e117206c8e1c65cef23a58dc37ff
攻撃手順は以下のようになります。
- 手順２で相手が送ってくるまで自分の手のフィンガープリントを送らない
- 相手が送ってきたフィンガープリントをあらかじめ計算しておいた表に照らし合わせて相手の手を突き止める
- 相手の手に勝つ手のフィンガープリントを送る
これでじゃんけんに毎回勝つことができてしまいます。
対策
対策としてはソルトを使う方法があるかと思います。
フィンガープリントを作成する際に、符号の後にソルトを結合してから作成するようにします。ソルトはじゃんけんの度にピアが生成するランダムな値とします。
これでフィンガープリントから手を推測することはできなくなりました。
検証のために手順３で手の他にソルトを相手にあかす必要があるため、ソルトはじゃんけんの度に毎回ピアで新しく作成する必要があります。
衝突対策（おまけ）
単に強衝突耐性が破られていないハッシュ関数を使えば問題ないのですが（SHA256のダブルハッシュとか？）、今後強衝突耐性が破られた場合も考えてみました。
フィンガープリントを計算するハッシュ関数の強衝突耐性が破られた場合以下のような手順で攻撃が可能と考えられます。
- あらかじめ'g','c','p'のどの手の場合でも 同じフィンガープリント になるソルトを３つ計算しておく。
- 手順２で１で計算したフィンガープリントを送る。
- 手順３で、相手の手が送られてくるのを確認してから、それに勝つ自分の手とソルトを相手に送る。
- 相手が検証を行ってもフィンガープリントは一致するため攻撃を検知できない。
強衝突耐性があるのであれば、攻撃手順の１は実行が不可能なはずです（ソルトが短すぎるなどの場合を除く）。おそらく、一番賢明な方法は衝突攻撃が成功したことを確認したらより安全なハッシュ関数に切り替えることなのでしょう。
なのであまり考えても仕方がないといえば仕方がないのですが、誰かが密かに衝突攻撃に成功していた場合に、どんな対策ができるかも考えてみました。
衝突攻撃を行なうには攻撃手順１で３つの衝突をみつける計算を行なう必要があります。SHA１の衝突が発表されたとき衝突には数週間から１年くらいかかる？ と言われていました。
何が言いたいかというと攻撃者に十分な時間を与えなければ、ムーアの法則やアルゴリズムの改善に対して時間稼ぎができるということです。
そのためには例えば、もともとの手順１に対して手順０を追加することができます。
- ランダムなソルト（r0）を作成し対戦相手に渡す。ソルトの作成時点でタイムアウト（例えば１０分）を設定し、全手順がタイムアウトまでに完了しなければじゃんけんを無効とする。
０で相手から渡されたr0を手順１でフィンガープリントを作成する際に、自分で作ったソルト（r1）に加えて使用するルールにします。こうすることで、衝突攻撃を行おうとする相手はタイムアウトまでに３つの衝突を見つける必要があります。おそらくスーパーコンピュータを使ってもしばらくは不可能なはずです。
まとめ
最終的な手順は以下のとおりです。
- ランダムなソルト（ソルト0）を作成し対戦相手に渡す。ソルトの作成時点でタイムアウト（例えば１０分）を設定し、全手順がタイムアウトまでに完了しなければじゃんけんを無効とする。
- 手にソルト0と自分で作成したソルト１を足し、フィンガープリントに変換する。相手には手とソルト１を秘匿する。
- フィンガープリントをピア同士で交換。
- フィンガープリントが届いたことを確認してからピア同士で手と、ソルト１を交換。フィンガープリントを先に送っているのでこの時点で手を変更することはできません。
- 相手の手とソルト０、ソルト１を足した値がフィンガープリントと一致することを検証。お互いに相手の手のフィンガープリントが予め受け取っていたものと一致することを確認します。相手の封じ手が判明するため、お互いのピアで独立に勝敗が判明します。
※ 0で設定したタイムアウトまでに４まで完了しなければ無効。
手順（完全版）
…ここまで考えて、もし負けた相手に「いや俺は負けていない」とごねられたらどうすればいいのかなと言うことを考えてなかったことに気が付きました。勝った方は、手とフィンガープリント、r0,r1,r0',r1'を証拠として提出できますが、相手は「いやそのフィンガープリントではなかった」と主張してくるかもしれません。
リアルじゃんけんでいえば、明らかに負けているのにあとから「俺はグーじゃなくてパーを出したから勝った」と言い出すような話なので、相手との信頼関係はボロボロになりますが、匿名の相手とであれば想定すべきかもしれません。
あんまり深く考えられていないですが、対策としては手順０と２と３の時点で、フィンガープリントとr1,r0の値にお互いの秘密鍵で署名しておくとかでしょうか。こうしておけば後で言い逃れしようとしても、他の人にこの人が署名した値を示せば、勝利を証明できます。負けたほうは勝つパターンの値と署名を偽造できますが、「負けるパターン」の署名を相手が持っていることは取り消すことができないためです。
以上です。「四神包囲（あっちむいてほい）」ゲームとかでも似たような方法で考えられそうです。
なんでこんなことを考えたのかと言うと「P2Pでトランプの山札ってどうやって作れるのかな？ そもそもP2Pで公平な勝負をするのって難しそう…」というのがスタートだったのですが、じゃんけんだけでこんなに長くなってしまいました。
落ち
さてここまで書いて、調べたらマジックプロトコルというのが既にあることをあとから知りました。
これマジックプロトコルで勝敗を決めておいてじゃんけんの表示は適当に辻褄を合わせればいいですね。完全に車輪の再発明でした…。まあ頭の体操ということで（二度目）。
Discussion