2015年03月15日

P2PでTCGを対戦するソフトでイカサマを対策するには(実装編)

※この記事は、前記事「理論編」の続きです。

誰得記事の続きです。長くなったので2つに分けました。
今回は、アリスとボブに実際の実装内容を、実演してもらいます。
 
 
5:ぼくのかんがえたさいきょうのイカサマ防止システム
とまではいきませんが、暗号技術を使ってこのパズルを解いてみた結果を書いてみたいと思います。

TCG_P2P_02.png

アリスとボブがP2Pで対戦をする、という前提で話を進めます。
まず、アリスは自分のデッキ情報を平文(暗号化されていない状態)で持っています。

5-1:カードデータに細工をする
このソフトは、カード情報を8桁の英数字で保持しているものとします。
TCGのカードには「コレクター番号」という物が付いていると思いますが、これを利用します。
(例えばMTGであれば、「飛鶴の技」というカードに「KTK-176」という番号が割り当てられていますし、WIXOSSであれば「WX01-084」という番号は「THREE OUT」というカードのものです。)

で、ここからが本題で、この8桁のカード識別情報の後ろに、「8桁のランダムな文字列」を2つくっつけます。
先ほどの例で言うと、
・KTK-176_akdQJD4QkDf+eFa
・WX01-084tHg8s/q+E-#dGEr
などという風にしてしまうのです。
なお、このランダムな文字列は、必ず他のカードとカブらないようにします。
こうする事の意味は、後で説明します。

5-2:デッキ情報をボブに渡す
さて、カードデータに細工をしたら、いよいよ暗号化の出番です。

(1)まず、アリスは平文のデッキAをシャッフルします。
(2)アリスはシャッフル後のデッキAをBLOWFISHなどのアルゴリズムを使ってハッシュ化します。(カード1枚1枚を全部同じキーでハッシュ化します。例えば、もしデッキにカードが60枚入っていた場合、60個のハッシュ値を持つ配列変数が出来上がります。)
このときアリスは、AとBの値の対応表を作ります。
(3)アリスは、ハッシュ化の鍵Pと、ハッシュ化したデッキBをボブに渡します。(対応表は渡しません。)

デッキはハッシュ化されているので、仮にボブが渡された配列の中身を覗いたとしても、どれが何のカードなのか分かりません。
そして、それとは別に、もう1つ、ハッシュ化したデッキをボブに渡します。

(4)アリスはシャッフル後のデッキAをBLOWFISHなどのアルゴリズムを使ってハッシュ化します。ただし、今度はカードデータの「頭16桁」のみをハッシュ化します。
(5)アリスは、ハッシュ化の鍵Pと、ハッシュ化したデッキZをボブに渡します。

実際にゲームに使うのは、(3)で渡したBのデッキです。(5)のデッキZは、後でとあるイカサマを調べるために使います。

5-3:ボブがアリスのデッキをシャッフルする
(6)ボブは、アリスから貰ったデッキBを入念にシャッフルします。ボブはハッシュ元のカードが何か分からないので、ここで「自分に都合良くカードを並べ替える」というイカサマは不可能です。
(7)ボブは、シャッフル後のデッキBを、1枚ずつ別々の鍵で暗号化します。(可逆の暗号化なので、鍵があれば元に戻すことができます。)
(8)シャッフルと暗号化が完了したデッキCをアリスに返します。鍵Qは渡しません。

その後、ボブのデッキに対しても同様の処理を行います。
これで、「同じ並び順」のデッキを、ボブとアリスそれぞれが持っている状態になりました。

●なぜ、デッキCが必要なのか?
アリスはBとAの対応表を持っています。そのため、ボブがシャッフル後のデッキBをそのままアリスに渡してしまうと、アリスは対応表を使って、自分のデッキの並び順を知ることができてしまいます。
そのため、ボブが改めて暗号化を行う必要があるのです。

5-4:ゲームを開始する。
アリスが先攻とします。
さて、早速ですが、ゲームが始まったらカードを引く必要があります。
しかし、アリスは「暗号化されたデッキC」しか持っていませんので、自力でカードを引くことができません。
そこで‥‥‥

(1)アリスは、ボブに「カードを引きたい」とリクエストします。
(2)ボブは鍵Qの「一番上の鍵」をアリスに渡します。
(3)アリスはボブに貰った鍵を使って、自分のデッキCの一番上にあるカードの暗号を解きます。(復号)
(4)Cを復号すると、ハッシュ値Bが得られます。アリスはデッキAとデッキBの対応表を持っていますので、ハッシュ値Bから平文Aを得ることができます。

こうして、アリスはカードを引くことができました。
一方、ボブも、アリスがどのハッシュ値のカードを引いたのかが分かりますが、ボブは対応表を持っていないので、それが何のカードなのか知ることができません。

5-5:手札からカードを出す
ゲームが進み、アリスは手札にあるカードを使う事にしました。

(1)アリスは、使うカードを平文で提示します。このとき、後ろのランダムな文字列も含めた24文字全てを伝えます。
(2)ボブは提示された平文Aを、手順5-2(3)で貰った鍵Pを使ってハッシュ化し、ハッシュ値Bを取得します。
(3)「アリスがそのハッシュ値(B)のカードを引いた」という履歴があれば、OKです。もし、アリスがそのハッシュ値のカードを引いたという履歴がなければ、アリスがイカサマをしているという事が分かります。(その時点でノーゲームになるでしょう。)

こうする事によって、「引いてもいないカードを場に出す」という事ができなくなっています。
また、どちらのカードも暗号化されているので、「自分が引いたカード」以外は「表」を見ることができません。

●「自分の手札は自分しか見ることができない」のは分かるけど、手札以外の領域はどうなるの?
場に出たカードは、平文Aが公開されていますので、アリスもボブもそのカードが何かを知る事ができます。
墓地(TCGによって、「トラッシュ」「控え室」など様々な呼び方がありますが、ここでは墓地と総称します)のカードも基本的に公開情報ですので、平文で公開されます。
もし、カードの効果で「デッキの一番上のカード2枚を墓地に置く」という指示があった場合は、
(a)ボブが鍵Qを、上から2枚アリスに渡す。
(b)アリスはその鍵で自分のデッキの一番上のカードを復号し、さらに対応表を使って平文Aを得る。
(c)この時、ボブはアリスのデッキの上2枚のハッシュ値Bが何かを知っています。
(d)アリスは墓地に置かれるカード2枚の平文Aを公開する。
(e)ボブはそのカード2枚を鍵Pでハッシュ化し、(c)の値と比較する。一致すればOK。
という手順を踏む事になります。

●非公開領域(裏向きでカードを置く領域)の情報はどうなるの? 例えばWIXOSSのライフクロスとか、アンジュ・ヴィエルジュのエナジーゾーンとか、MTGの《伏魔殿のピュクシス》の効果とか。
・ボブはそこにあるカードのハッシュ値Bしか知らないので、表が何か知ることができません。
・アリスはボブから鍵Qを貰っていないので、表が何か知ることができません。
・そのカードが表向きになる時が来たら、ボブが鍵Qを公開します。これによって初めて、アリスは平文Aを知る事ができます。アリスが平文Aを公開するので、ボブも表を知ることができます。

●ボブが「対戦相手のデッキの一番上のカードを見る」という効果のカードを使いました。この場合はどうなる?
・ボブがアリスに鍵Qを渡します。
・アリスは鍵Qを使って一番上のカードを復号化してハッシュBを取得し、さらに対応表を使って平文Aを得ます。
・アリスは「平文Aを見ないように目をつぶりながら」ボブに平文Aを伝えます。
‥‥はい、このパターンだけは「セキュリティホール」です。アリスがズルをして薄目を開けていたら、アリスは自分のデッキの一番上のカードを知ることができてしまいます。
ただし、こういう効果のカードは数が非常に少ないですので、もしこのセキュリティホールを突いた改造クライアントを作っても、メリットはほとんど得られないでしょう。(つまり、開発コストに見合う見返りが少なすぎるので、そもそも作る意欲が湧かないと思います。)

5-6:墓地のカードをシャッフルして切り直し、デッキにする。
ゲームが進み、アリスのデッキのカードが空っぽになってしまいました。
TCGによっては、こういう時に、「墓地のカードを切り直して再びデッキにする」という操作を行う事があります。また、カードの効果によって「場にあるカード1枚をデッキの中に入れてシャッフルし直す」という操作を指示される事もあります。

さて、ここでそのままこの操作を行うと問題があります。
すでに場に出たカードについては、ボブも「平文AとハッシュBの両方を知っている」状態なので、そのままシャッフルしてしまうと、どのカードがデッキの何番目にあるのかが分かってしまいます。また、シャッフル時に、ボブの有利になるようなシャッフルをする事ができてしまいます。
※鍵Qはシャッフルのたびに変わるので、アリスがデッキの中身を知ることはできません。

ここで、手順5-1で、わざわざランダムな8桁の文字列を「2つも」くっつけた意味が明らかになります。

(1)まず、アリスはシャッフルし直すカードをまとめます。
(2)そして、対象のカードの「後ろ8桁」のランダムな文字列を、全て振り直します。
(3)それからハッシュ化を行って、デッキBを作ります。(2)でランダムな文字列を振り直しているので、手順5-2(2)の時と同じハッシュ値にはなりません。
(4)アリスが持っている対応表を(3)をもとに作り直します。
(5)以後は手順5-3と同じです。

このとき、振り直すのは「後ろの8桁」だけなので、手順5-2(5)で渡したデッキZには影響を与えません。
そのため、シャッフル時に「デッキに入れてないカードを紛れ込ませる」というイカサマはできません。(ボブが、出されたカードの頭16桁をハッシュ化してデッキZと突き合わせればすぐにバレてしまうため。)

5-7:ゲーム終了
ゲームが終わると、全ての非公開領域のカードの平文が公開されます。
ボブは、アリスが公開したカードを全部鍵Pでハッシュ化し、自分の持っている情報と一致するかを調べます。一致していれば、このゲームでアリスがイカサマをしていなかった事が証明されます。
また、公開されたカードをデッキZと照合し、変なカードが紛れ込んでいないかどうかの検査も行われます。

●2本先取のマッチ制の場合、ゲームが終わっても同じデッキで試合が続くんだけど、それでも公開しなきゃいけないの?
その場合、ルールで「ゲーム終了後に公開する」と決められている非公開領域だけ公開し、あとは隠したまま回収します。そして、全カードの「後ろ8桁」だけをリニューアルして、次のゲームで使います。

●サイドボードの扱いはどうなるの?
サイドボードについては、あらかじめ頭16桁だけをハッシュ化した「サイドボードZ」をボブに渡しておきます。
こうする事で、「サイドボードにすら入れていないカード」をサイドボード時に紛れ込ませる事ができなくなります。
(もしそんな事をしたら、場に出した時点でデッキZと比較されてバレるでしょう。)

●そうすると、「サイドボードからカードを何枚加えたのか」が分かってしまうんじゃね?
‥‥はい、分かってしまいます。対処方法としては
・それを公開情報にしてしまう。(ルールをねじ曲げて「サイドボード時にカードを何枚入れ替えたか」を公開する、というローカルルールを定める。)
・諦める
ぐらいしかありません。
この辺は改良の余地がありますね。

●ランダムな文字列は「8桁+8桁」って書いてあるけど、8桁だと不安だ。
キリが良いから8桁にしているだけなので、別に9桁でも10桁でも64桁でも問題ありません。

6:P2Pで先攻・後攻を決める方法
さて、ここまでゲームプレイ中のイカサマ防止について考えてきましたが、懸念はもう1つあります。
「先攻・後攻を決めるときにどうするか?」という事です。

まず、よく使われている「サイコロを振って目が大きいほうが先攻」という方式はアウトです。
改造クライアントを使えば、常に「6」を出すことなど造作もない事です。

そこで、「じゃんけん」を使います。
方法は簡単で、まず、アリスとボブが、あらかじめジャンケンの手を128個ほど考え、秘密鍵で暗号化(可逆)してから、相手に送ります。
お互いが暗号化された手を受信できたのを確認できたら、今度は鍵を送り合います。そして、それぞれのクライアントで「じゃんけん」を再現し、勝った方が先攻の(もしくは先攻・後攻を決められる)権利を得るのです。

128個も手があれば、あいこになる事はまず無いでしょうし、仮にあいこになったらもう一度同じ手順を繰り返せば良いだけです。
また、多人数戦の時は、そのまま普通のじゃんけんをしても良いですし、「少数決」方式で、「一番少ない手を出した人が勝ち」というルールにするという手もあります。

7:あとがき
というわけで、暗号化技術を適当にこねくり回して、イカサマ防止の1つの案を考えてみました。
とはいえ、冒頭に書いた通り、別にこの理屈を使って何かを作ろうとしているわけではありません。
(考えた事はありましたが、頓挫しました。)

そんなわけで、この理屈を使う予定はありません。
でもそれだと勿体ないので、せめてブログにでも残しておこうと考えた次第です。

改善点もまだありますし、そもそも机上論ですので、実際にうまく動くかは分かりませんし、穴があるかもしれません。
でもまあ、これである程度基本的なイカサマは防げるんじゃないかなぁなんて思っています。

ではでは。
posted by TCT at 13:12| Comment(0) | 日記
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント: