第 4 章 RFID システムの提案と安全性検証
4.6 人手による証明
4.6.4 Forward-secure サーバー成りすまし不可能性
Testクエリに対する振る舞い以外は，第4.6.2節のオラクルと同様の構成であるため，Aは，
S,F,Cのいずれかが生じない限り，各オラクルがシミュレートされたものだと識別できず，式 (4.15)，(4.16)，(4.17)，(4.18)が同様に成り立つ．以上をまとめ，第4.6.2節と同様に評価する ことで，次の式が得られる．
Pr[Bwins]≥ Pr[Awins∧G∧ ¬S∧ ¬F∧ ¬C]
= 1 n ·
(
1− qH +1
|key| )2
· (
1− 2t! 2nt(2t−n)!
)
·AdvAFT I.
攻撃者Bの成功確率が無視できるとすると，攻撃者Aの成功確率も無視できることが示 せた．
対して
S K2 = H2,A(S K1,ID) :=H2,B(S K1,ID), ...
S Ki−1 = H2,A(S Ki−2,ID) := H2,B(S Ki−2,ID)
と設定する．また，H2,Bに問い合わせを行い，H2,Aに対して S Ki+2 = H2,A(S Ki+1,ID) := H2,B(S Ki+1,ID),
...
S Kn = H2,A(S Kn−1,ID) := H2,B(S Kn−1,ID) と設定する．
そして，Bは，IDをAに与え，Aを動作させる．
■ラ ン ダ ム オ ラ ク ル の シ ミ ュ レ ー ト 第 4.6.2 節 と 同 様 に ，特 に 断 り が な い 限 り ， OH0,A,OH1,A,OH2,A へ の 問 い 合 わ せ は ，そ の ま ま OH0,B,OH1,B,OH2,B に 転 送 さ れ ， OH0,B,OH1,B,OH2,Bからの出力をそのまま返す．
■SAのシミュレート 第4.6.2節と同様の手順で，シミュレートを行う．
• j,i,i+1の場合：
– ()を受け取ったら，Xsid
← {R 0,1}t を選択して，Xsid を出力する．
– αsid, βsidを受け取ったら，
∗ βsid = H0,A(S Kj,ID,Xsid, αsid) が成立すれば，Zsid ← H1,A(S Kj,ID,Xsid, αsid) を計算し，Zsidを返す．
∗ βsid = H0,A(S Kj−1,ID,Xsid, αsid)が成立すれば，Zsid ←H1,A(S Kj−1,ID,Xsid, αsid) を計算し，Zsidを返す．
∗ 成立しなければ，Zsid
←R h1 を返す．
• j=iの場合：
– ()を受け取ったら，()をSBに送って，Xsid を受け取り，Xsidを出力する．
– αsid, βsidを受け取ったら，
∗ βsid = H0,A(S Ki−1,ID,Xsid, αsid)が成立すれば，Zsid ←H1,A(S Ki−1,ID,Xsid, αsid) を計算し，Zsidを返す．
∗ 成立しなければ，αsid, βsidをSBに送って，Zsid を受け取り，Zsidを返す．
• j=i+1の場合：
– ()を受け取ったら，()をSBに送って，Xsid を受け取り，Xsidを出力する．
– αsid, βsidを受け取ったら，
∗ βsid = H0,A(S Ki+1,ID,Xsid, αsid)が成立すれば，Zsid ←H1,A(S Ki+1,ID,Xsid, αsid) を計算し，Zsidを返す．
∗ 成立しなければ，αsid, βsidをSBに送って，Zsid を受け取り，Zsidを返す．
■TA のシミュレート 第4.6.2節とほぼ同様にシミュレートを行うが，Testクエリに対する 振る舞いのみが異なる．
• j,iの場合：
– X′sid を受け取ったら，αsid
← {R 0,1}t を選択し，βsid ← H0,A(S Kj,ID,Xsid, αsid)を計 算し，(αsid, βsid)を出力する．
– Z′sidを受け取ったら()を出力する．
– Reveal(sid)クエリ を受け取ったら，
∗ j<iの場合，動作を停止する．
∗ j>iの場合，S Kj を返す．
– Testクエリ を受け取ったら，動作を停止する．
• j=iの場合：
– X′sidを受け取ったら，X′sidをTBに送り，(αsid, βsid)を受け取り，(αsid, βsid)を返す．
– Z′sidを受け取ったら，Zsid′ をTBに送り，()を受け取り，()を返す．
– Reveal(sid)クエリを受け取ったら，動作を停止する．
– Test(X∗)クエリを受け取ったら，X∗ をChallengeオラクルに送り，(α∗, β∗)を受け 取り，(α∗, β∗)を返す．Test(Z∗)を受け取ったら，それをChallengeオラクルに送 り，動作を停止する．
Aが攻撃の対象とするセッション鍵のインデックスiの推測に成功し，Aが攻撃に成功する とき，Bも攻撃に成功することを示す．G,S,F,Cは，第4.6.2節と同じイベントとする．
セッション鍵のインデックスiの推測に成功した場合，すなわちG が生じたとき，Bは，
sid = i||ssid でTAsid にTest クエリを受ける．その時，B は，問い合わされるTest(X∗) を，
Challengeオラクルに転送し，β∗ = H0,B(SK1,ID,X∗, α∗)なる(α∗, β∗)を得る．そして，(α∗, β∗) をAに返し，AよりTest(Z∗)を得て，ChallengeオラクルにZ∗を返す．Aが攻撃に成功する 場合，Z∗ =H1,B(S Ki,ID,X∗, α∗)= H1,B(SK1,ID,X∗, α∗)を満たす．つまり，Challengeオラク ルは，Z∗をacceptする．よって，Bは，AのTestクエリを出力することで，攻撃に成功する ことが示せた．
上記のように，Challengeオラクルを用いると，SK1 に対応するTestクエリを構成できる ため，Aは，Testクエリに対する返り値がシミュレートされたものだと識別できない．また，
Testクエリに対する振る舞い以外は，第4.6.2節のオラクルと同様の構成であるため，Aは，
S,F,Cのいずれかが生じない限り，各オラクルがシミュレートされたものだと識別できず，式 (4.15)，(4.16)，(4.17)，(4.18)が同様に成り立つ．以上をまとめ，第4.6.2節と同様に評価する ことで，次の式が得られる．
Pr[Bwins]≥ Pr[Awins∧G∧ ¬S∧ ¬F∧ ¬C]
≤ 1 n ·
(
1− qH +1
|key| )2
· (
1− 2t! 2nt(2t−n)!
)
·AdvAFS I.
攻撃者Bの成功確率が無視できるとすると，攻撃者Aの成功確率も無視できることが示 せた．