第 4 章 RFID システムの提案と安全性検証
4.6 人手による証明
4.6.3 Forward-secure タグ成りすまし不可能性
OMHSOプロコトルのForward-secureタグ成りすまし不可能性を破る攻撃者Aが存在した
ら，第4.5.1節で示した単純化 OMHSOプロコトルのタグ成りすまし不可能性を破る攻撃者
Bが存在することを示す．ここでは，Aを利用すると，Bが構成できることを示すことで，
OMHSOプロコトルの安全性証明を行う．第4.6.2節と同様に，Aは，ServerオラクルSAに
高々 n回まで問い合わせを行い，Tag オラクルTA に高々n回まで問い合わせを行うとする．
さらに，ランダムオラクルOH0,A,OH1,A,OH2,Aに対して，合計qH 回の問い合わせを行うと する．そして，Aは，任意のタイミングでSAにTest()クエリを送り，X∗ を受け取って，SA
に受理されるような(α∗, β∗)—つまり，β∗ = H0S Ki,ID,X∗, α∗またはβ∗ = H0S Ki−1,ID,X∗, α∗ なる(α∗, β∗)．—を出力することで，タグに成りすまそうとする．
Bは，Serverオラクル SB に高々n 回まで問い合わせを行い，Tag オラクル TB に高々 n
回まで問い合わせを行うとする．さらに，ランダムオラクル OH0,B,OH1,B,OH2,B に対して，
合計qH 回の問い合わせを行うとする．そして，() をChallengeオラクルに送り，X∗ を受け 取ったら，受理される(α∗, β∗)を出力しようとする．まず，Bの構成を示す．Bは，SA，TA， OH0,A,OH1,A,OH2,AをシミュレートしてAを動作させ，Challengeオラクルからのチャレン ジにこたえようとする．Bは次のように各オラクルをシミュレートし，シミュレートが成功し たときにAが出力するX∗,Z∗を得て，Bはそれを出力する．
■初期設定 第4.6.2節と同様の手順で，シミュレートを行う．まず，Bは，ターゲットとな るRFIDのIDと，攻撃のターゲットするセッションの次のセッション鍵SK2を受け取る．B は，Aがターゲットとするセッション鍵のインデックス i←R [1,n]を予測し，S Ki+1 ← SK2
と設定する．そして，ランダムにS K1 を選択して，H2,Bに対して問い合わせを行い，H2,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のシミュレート
• 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 を返す．
– Testクエリ()を受け取ったら動作を停止する．
• 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を返す．
– Testクエリ ()を受け取ったら()をChallengeに転送し，X∗ を受け取り，X∗ を返 す．そして，(α∗, β∗)を受け取り，それをChallengeに転送して動作を停止する．
• 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を返す．
– Testクエリ()を受け取ったらi+1がRevealedならば停止する．Revealed でなけ れば，()をChallengeに転送し，X∗を受け取り，X∗を返す．そして，(α∗, β∗)を受 け取り，それをChallengeに転送して動作を停止する．
■TAのシミュレート
• j,iの場合：
– X′sid を受け取ったら，αsid
← {R 0,1}t を選択し，βsid ← H0,A(S Kj,ID, j,Xsid, αsid)を 計算し，(αsid, βsid)を出力する．
– Z′sidを受け取ったら()を出力する．
– Reveal(sid)クエリ を受け取ったら，
∗ j<iの場合，動作を停止する．
∗ j>iの場合，S Kj を返す．
• j=iの場合：
– X′sidを受け取ったら，X′sidをTBに送り，(αsid, βsid)を受け取り，(αsid, βsid)を返す．
– Z′sidを受け取ったら，Zsid′ をTBに送り，()を受け取り，()を返す．
– Reveal(sid)クエリを受け取ったら，動作を停止する．
Aが攻撃の対象とするセッション鍵のインデックスiの推測に成功し，Aが攻撃に成功する とき，Bも攻撃に成功することを示す．G,S,F,Cは，第4.6.2節と同じイベントとする．
セッション鍵のインデックス i の推測に成功した場合，つまり G が生じたとき，B は，
sid =i||ssidまたはsid= i+1||ssidで，SAsidにTestクエリを受ける．
sid=i||sidでTestクエリを受けた場合，Bは，問い合わされるTest()を，Challengeオラク ルに転送し，X∗を受け取る．そして，Bは，X∗をAに返し，AよりTest(α∗, β∗)を受け取っ たら，Challengeオラクルに(α∗, β∗)を転送する．Aが攻撃に成功する場合，
β∗ = H0,B(S Ki,ID,X∗, α∗)= H0,B(SK1,ID,X∗, α∗) (4.19)
β∗ = H0,B(S Ki−1,ID,X∗, α∗) (4.20)
のいずれか満たす(α∗, β∗)を返す．ここで，Aが攻撃対象とするセッション鍵のインデックス iの推測に成功していることに注意すると，Aが出力する(α∗, β∗)は，式(4.19)であることが わかる．よって，Challengeオラクルは，(α∗, β∗)をacceptするため，Bは，AのTestクエリ を出力することで，攻撃に成功することが示せた．
また，sid =i+1||sidでTestクエリを受けた場合，S Ki+1 がRevealedでなければ，Bは，問 い合わされるTest()を，Challengeオラクルに転送し，X∗ を受け取る．そして，Bは，X∗ を Aに返し，AよりTest(α∗, β∗)を受け取ったら，Challengeオラクルに(α∗, β∗)を転送する．A が攻撃に成功する場合，
β∗ = H0,B(S Ki+1,ID,X∗, α∗)=H0,B(SK2,ID,X∗, α∗) (4.21) β∗ = H0,B(S Ki,ID,X∗, α∗)= H0,B(SK1,ID,X∗, α∗) (4.22) のいずれか満たす(α∗, β∗)を返す．ここで，Aが攻撃対象とするセッション鍵のインデックス iの推測に成功していることに注意すると，Aが出力する(α∗, β∗)は，式(4.22)であることが わかる．よって，Challengeオラクルは，(α∗, β∗)を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)!
)
·AdvAFT I.
攻撃者Bの成功確率が無視できるとすると，攻撃者Aの成功確率も無視できることが示 せた．