Forward-secure タグ識別不可能性

もし，OMHSOプロコトルのForward-secure タグ識別不可能性安全性を破る攻撃者A^が

存在したら，第 4.5.1節で示した単純化 OMHSO プロコトルの単純化タグ識別不可能性の 安全性を破る攻撃者 Bを構成できること示す．ここで B ^{が存在しないことが第}4.5.2 節で

CryptoVerifにより証明されているため，そのようなAは存在しないことを示すことができる．

A^は，ServerオラクルSAに高々n回まで問い合わせを行い，TagオラクルTAに高々n回 まで問い合わせを行うとする．さらに，ランダムオラクルOH_0,A,OH_1,A,OH_2,Aに対して，合 計qH 回の問い合わせを行うとする．このとき，タグとサーバー間の相互認証が成功するのは 高々n回であるから，高々n個のセッション鍵が存在しうる．そして，A^{は，任意のタイミン}

グでTag オラクルにTest(X^∗)クエリを送り，(α^∗, β^∗)を受け取って，それが，Tagの出力であ るか，ランダムに選択された値であるかを識別しようとし，その結果b^′ ∈ {0,1}^{を出力する．}

B^は，ServerオラクルSBに高々n回まで問い合わせを行い，TagオラクルTBに高々n回 まで問い合わせを行うとする．さらに，ランダムオラクルOH0,B,OH1,B,OH2,Bに対して，合 計q_H 回の問い合わせを行うとする．そして，(X^∗)をChallengeオラクルに送り，(α^∗, β^∗)が Tagの出力であるか，ランダムに選択された値であるか否かを識別しようとする．

Send, Test

Send, Test, Reveal

Send

Send

Test

図4.2 Forward-Secureタグ識別攻撃者Aを利用したタグ識別攻撃者B^の構成.

B^{は，あるセッション鍵}SK2 =OH_2,B(SK1,ID)を受け取り，RFIDタグIDのセッション鍵 SK1 が用いられるセッションを攻撃の対象とする．ここでは，Aが攻撃対象とする鍵のイン デックスiを予め推測し，そのiに対応する共有鍵S Ki がS Ki = SK1 となるように各オラク ルを構成し，B^{へのチャレンジ問題を}A^{に解かせようとする}B^{を与える．}B^は，S K_i =SK1

を与えられないため，S Ki がかかわる問い合わせには，SB，TB を利用して回答することで，

S Ki =SK1 となるようにSA，TAをシミュレートする．

また，それ以外のセッションは，A^{の視点からは，}SK1,SK2に関わるセッション鍵が使わ れる実際のプロトコル実行と区別が出来ないようにSA，TAをシミュレートする．そして，A

からのTestクエリをB^のChallengeオラクルに転送することで，B^{のチャレンジ問題を}A^の

チャレンジ問題に割り当てる．このようにして，A^の解がBの解にもなるように，各オラク ルを構成する．

簡単のため，sid = j||ssid ，jはセッション鍵の世代とし，あるセッション sidに対応する ServerオラクルをS^sid_A ^，TagオラクルをT_A^{sid と記述する．また，}Bの攻撃対象のプロトコル 実行を実環境，Bがシミュレートして行うプロトコル実行をシミュレート環境と呼ぶ．

まず，B^{の構成を示す．}B^は，SA，TA，OH0,A,OH1,A,OH2,AをシミュレートしてA^を動作

させ，Challengeオラクルからのチャレンジに答えようとする．図.4.2は，A^を用いたB^の構

成である．Bは次のように各オラクルをシミュレートし，シミュレートが成功したときにA が出力するb^′を得て，B^はb^′ を出力する．

■初期設定 まず，B^{は，ターゲットとなる}RFIDのIDと，攻撃のターゲットするセッショ ンの次のセッション鍵SK2 を受け取る．B^は，Aがターゲットとするセッション鍵のイン デックスi ←^R [1,n]を予測し，S K_i+1 ← SK2 と設定する．そして，ランダムにS K₁ を選択し て，H2,Bに対して問い合わせを行い，H2,Aに対して

S K2 = H2,A(S K1,ID) :=H2,B(S K1,ID), ...

S K_i−1 = H_2,A(S K_i−2,ID) := H_2,B(S K_i−2,ID) と設定する．

また，H_2,Bに問い合わせを行い，H_2,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^{を動作させる．}

■ランダムオラクルのシミュレート A^{からランダムオラクル}OH0,A,OH1,A,OH2,Aへの問い 合わせに対して，B^は，OH0,A,OH1,A,OH2,Aへの問い合わせを，そのままOH0,B,OH1,B,OH2,B

に転送し，OH_0,B,OH_1,B,OH_2,Bから受け取った値をOH_0,A,OH_1,A,OH_2,A の出力として返す．

■SA のシミュレート S Ki = SK1 が無ければ正しく回答できない問い合わせに対して，SB

を利用してシミュレートを行い，それ以外の問い合わせに対しては，B^{が設定した共有鍵を用} いてシミュレートを行う．そのために，iの値に応じて次のようにシミュレートする．

• j,i,i+1の場合：

– S^sid_A ^は，Send()を受け取ったら，X_sid ← {^R 0,1}^{t を選択して，}X_sid を出力する．

– S^sid_A ^は，Ysid =αsid||βsid なるSend(Ysid)を受け取ったら，

∗ βsid =OH0,A(S Kj,ID,Xsid, αsid)が成立すれば，Zsid ←OH1,A(S Kj,ID,Xsid, αsid) を計算し，Z_sidを返す．

∗ βsid =OH0,A(S Kj−1,ID,Xsid, αsid)が成立すれば，Zsid← OH1,A(S Kj−1,ID,Xsid, αsid) を計算し，Zsidを返す．

∗ ^{成立しなければ，}Z_sid ←^R h₁ を返す．

• j=iの場合：

– S^sid_A ^は，Send()を受け取ったら，Send()をSBに送って，Xsid を受け取り，Xsidを 出力する．

– S^sid_A ^は，Ysid =αsid||βsid なるSend(αsid, βsid)を受け取ったら，

∗ βsid = H0,A(S Ki−1,ID,Xsid, αsid)が成立すれば，Zsid ←H1,A(S Ki−1,ID,Xsid, αsid) を計算し，Z_sidを返す．

∗ ^{成立しなければ，}αsid, βsidをSBに送って，Z_sid を受け取り，Z_sidを返す．

• j=i+1の場合：

– S^sid_A ^は，Send()を受け取ったら，Send()をSBに送って，Xsid を受け取り，Xsidを 出力する．

– Ysid =αsid||βsidなるSend(αsid, βsid)を受け取ったら，

∗ βsid = H0,A(S Ki+1,ID,Xsid, αsid)が成立すれば，Zsid ←H1,A(S Ki+1,ID,Xsid, αsid) を計算し，Z_sidを返す．

∗ ^{成立しなければ，}αsid, βsidをSBに送って，Zsid を受け取り，Zsidを返す．

■TA のシミュレート S K_i = SK1 が無ければ計算できない問い合わせに対して，TBを利用 してシミュレートを行い，それ以外の問い合わせに対しては，Bが設定した共有鍵を用いてシ ミュレートを行う．Aが攻撃対象とするインデックスiの予測が正しければ，Revealクエリは j>iなる jに対してのみ行われ，Testクエリはiに対してのみ行われる．つまり，前述の場合 以外にRevealクエリ，Testクエリが行われたとき，iの予測に失敗しているため，B^はシミュ レートを停止する．

• j,iの場合：

– T_A^{sid は ，}Send(X^′_sid) を 受 け 取 っ た ら ，αsid

← {R 0,1}^{t を 選 択 し ，}βsid ← H_0,A(S K_j,ID,X^′_sid, αsid)を計算し，(αsid, βsid)を出力する．

– T_A^sidは，Send(Z^′_sid)を受け取ったら，()を出力する．

– Reveal(sid)クエリ を受け取ったら，

∗ j<iの場合，動作を停止する．

∗ j>iの場合，S Kj を返す．

– Testクエリ を受け取ったら，動作を停止する．

• j=iの場合：

– T_A^sidは，Send(X_sid^′ )を受け取ったら，X^′_sidをTBに送り，TBから(αsid, βsid)を受け 取り，A^に(αsid, βsid)を返す．

– T_A^sidは，Send(Z^′_sid)を受け取ったら，Z^′_sidをTBに送り，TBから()を受け取り，A に()を返す．

– Revealクエリを受け取ったら，動作を停止する．

– Test(X^∗)クエリを受け取ったら，X^∗ をChallengeオラクルに送り，(α^∗, β^∗)を受け 取り，(α^∗, β^∗)を返す．

以下，Bが正しくタグ識別不可能性を破る確率Pr[Bwins]を評価する．

まず，Pr[Bwins]を評価するために，Bが各オラクルのシミュレートに成功する確率を評価 する．そのために，以下の補題9を示す．

補題9 RO : D1× D2 → Rは，ランダムオラクルとする．まず，k ← D^R 1 をランダムに選択 する．A^は，高々qH 回まで，任意にd1 ∈ D1,d2 ∈ D2 を選択しRO1 に問い合わせを行い，

RO(d1,d2)を得る．また，A^は，高々qp 回まで，任意にd₂^′ ∈ D2 を選択しRO2に問い合わせ を行い，RO(k,d₂^′)を得る．最終的に，A^は，k^′ ∈ D1を出力する．このとき，

Pr [

k^′ =k|k ← D^R 1,A^RO1,RO2 →k^′

] = qH+1

|D1| である．ただし，κはセキュリティパラメタとする．

証明:

RO^′₁ : D1 × D2 → R^，RO^′₂ : D2 → R^なる 2つのランダムオラクルを考える．そして，A^が (RO₁,RO₂)と対話しているか，(RO^′₁,RO^′₂)と対話しているかを識別する確率を評価する．

(RO1,RO2)は，ROに問い合わせを行い返り値を決定する．ROは，初出の問い合わせに対 して Rよりランダムに選択した値を返し，既出の問い合わせに対しては以前返したのと同じ の値を返す．つまり，RO₁ とRO₂ を介して，同じ問い合わせが行われたときは，同じ値を返 すため，RO₁(k,d₂)= RO₂(d₂)が成立する．上記の問い合わせ以外の場合，RO₁ からROへの

問い合わせとRO₂ からROへの問い合せが一致することは無いため，RO₁ とRO₂ は，独立の ランダムオラクルと同様に振る舞う．

一方，(RO^′₁,RO^′₂)は，それぞれ異なるランダムオラクルであるため，(RO1,RO2)とは異な り，独立に返り値を決定する．つまり，圧倒的確率で，RO1(k,d2),RO2(d2)となる．

よって，Aの視点から，(RO₁,RO₂)と(RO^′₁,RO^′₂)の返り値に違いが生じるのは，(k,d₂)を 問い合せたときのみである．ただし，d2 ∈ D2 で，Aが任意に選択した値とする．

つまり，(k,d2)が問い合わされない限り，(RO1,RO2)と(RO^′₁,RO^′₂)は，それぞれ異なる２つ のランダムオラクルと同様に振る舞うため，それらの出力分布は完全に一致する．(RO^′₁,RO^′₂) は，kを用いずに動作するため，それらの出力値はkに関する情報を一切含まない．よって，

(RO1,RO2)は，(k,d2)が問い合わされない限り，kに関する情報を含まないことが示せた．

言い換えると，A^はkを入手しない限り，(RO₁,RO₂)，(RO^′₁,RO^′₂)からkに関する情報を得 ることができない．kは，D1 よりランダムに選択された値であるため，A^{は，ランダムに推} 測する以上の確率でkを入手できない．また，A^は，(RO1,RO2)か(RO^′₁,RO^′₂)に問い合わせ ることで，高々q_H 回まで，推測したk^′ が正しいかを確認できる．さらに，q_H 回の推測がす べて外れたとしても，最終的な出力として新たに推測したk^′ を選択できる．よって，A^が正 しくkを入手できる確率は，高々(qH +1)/|D1|^である．

まず，次の3つのイベントを定義し，それぞれ生じる確率を評価する．

• S：A^が j < iなる実環境の秘密鍵SKj を入手するイベントとする．提案方式の実環 境での秘密鍵SKj は，B^{の挑戦者が}keyよりランダムに選択したSK0 からランダム オラクル OH_2,B を用いて連鎖的に計算される値である．SKj は，T_A^j||ssid,S_A^{j||ssid のシ} ミュレートには用いられないため，A^は，T_A^j||ssid,S_A^{j||ssid への問い合わせから}SKj を推 測することはできない．つまり，A^は，k ≥ i+1なるSKk より，ランダムオラクル OH_2,Bの出力であるSKj を直接推測することでしか入手できない．よって，補題9で D1 = key，D2 = IDs，R = keyとすると，ランダムオラクルOH2,B への問い合わせは 高々qH 回なので，

Pr[S]≤ qH +1

|key| (4.15)

となる．

• F：A^が j< iなるシミュレート環境の秘密鍵S Kj を入手するイベントとする．シミュ レート環境の秘密鍵S K_jは，B^がkeyより一様ランダムに選択したSK0 から，ランダ ムオラクルOH2,Bを用いて連鎖的に計算される値で，実環境の鍵とは独立に計算され る．そのため，Revealクエリにより入手できるk>iなる実環境の鍵SKkからは，S Kj

を計算できない．

一 方 ，T_A^j||ssid,S_A^j||ssid の シ ミ ュ レ ー ト に S K_j は 用 い ら れ る ．SA は ，一 様 ラ ン ダ ム に選択した X を出力した後，(α, β) を受け取り，Z = OH1,B(S Kj,ID,X, α) か Z = OH1,B(S Kj−1,ID,X, α)かrnd ∈h1 を出力する．よって，T_A^{j||ssid への問い合わせから}F が生じる確率は，補題9でD1 = key，D2 = IDs× {0,1}^t× {0,1}^t，R =h₁とすると，ラ ンダムオラクルOH1,Bへの問い合わせは高々qH 回なので，(qH +1)/|key|^となる．

ま た ，TA は ，X を 受 け 取 っ た 後 ，一 様 ラ ン ダ ム に 選 択 さ れ た 値 α ^と β = OH_0,B(S K_j,ID,X, α) を 出 力 す る ．よ っ て ，S_A^j||ssid へ の 問 い 合 わ せ か ら F が 生 じ る確率は，補題9でD1 =key，D2 = IDs× {0,1}^t× {0,1}^t，R=h0 とすると，ランダム オラクルOH0,Bへの問い合わせは高々qH 回なので，(qH+1)/|key|^となる．

各ランダムオラクルは独立にシミュレートされるため，OH_0,BとOH_1,Bは，互いに依存 せず動作する．さらに，各ランダムオラクルへの問い合わせ回数の合計の上限がqH 回 であるから，

Pr[F]≤ qH +1

|key| (4.16)

となる．

• C：SAの出力Xが衝突を起こすイベントとする．Xは，SAにより{0,1}^{t から一様ラン} ダムに選択される要素であり，SAへの問い合わせは高々n回であるから，

Pr[C]= 2^t!

2^nt(2^t−n)! (4.17)

となる．nはセキュリティパラメタに対して多項式であり，Pr[C]が生じる確率は無視 できるようにtを選択しているとする．

Aが上記のように構成されたオラクルと対話を行ったとき，S, F, Cが生じない限り，A^は 実環境とシミュレート環境を識別できないことを示す．

■j>iなる各オラクルへの問い合わせ： B^は，SK2 を更新して得た実際の共有鍵を用いて SAとTA をシミュレートしている．そのため，実環境とシミュレート環境の出力は完全に一 致するため，Aは実環境との違いに気付くことはない．

■j < iなる各オラクルへの問い合わせ： B^{は，実際の共有鍵}SK2 とは独立に決定したシ ミュレート鍵S K₁, . . . ,S K_i−1 を用いてSA とTAをシミュレートする．SAの出力は，一様ラ ンダムに選択されるXとランダムオラクルOH1,Bの出力Zからなる．また，TAの出力は，一 様ランダムに選択された値α^{とランダムオラクル}OH0,Bの出力βからなる．ランダムオラク