第 4 章 RFID システムの提案と安全性検証
4.3 安全性モデルと定義
4.3.1 攻撃モデル
RFIDシステムの攻撃者は，サーバーとRFIDタグの通信を盗聴・改ざんしたり，RFIDタ グの物理的解析を行うなどにより，攻撃に有用な情報を入手できる．そのような情報は，攻撃 者がオラクルに問い合わせを行うことで入手するとして，攻撃モデルを定式化する．
相互認証プロトコルへの攻撃者のモデル化には，サーバーオラクル，タグオラクル，ランダ ムオラクルの3種のオラクルを用いる．タグから得られるすべての情報はタグオラクルT の 出力で記述され，サーバーから得られるすべての情報はサーバーオラクル Sの出力で記述さ れる．また，ハッシュ関数の計算結果は，ランダムオラクルRの出力で記述される．つまり，
T,S, R利用して，攻撃者が攻撃により入手可能なすべての情報を表現することで，攻撃モデ ルを定式化する．
まず，我々のすべての攻撃モデルで共通に用いるT,S,Rを与える．
■サーバーオラクル S サーバーオラクルS は，相互認証プロトコルを実行する正直なサー バーの出力を攻撃者に与える．sidはセッションIDとし，Ssid は，セッションsidに対応し た振る舞いをするサーバーオラクルとする．攻撃者は，Ssid にSendクエリを送ることができ
る．Ssid は，SendクエリSend(∗)を受け取ると，正直なサーバーがセッションsidで(∗)を受 け取った場合と同じ処理を行い，その結果である値をサーバーの出力を攻撃者に返す．
また，Ssid は，sidでの Sの状態とし，sid で認証プロトコルを実行した結果，Ssidがタグ の認証に成功したらAccepted∈Ssidと設定されるとする．
Sは，S-Listを保持しており，セッションIDsidとSへの入出力の組(sid,Inputdata,Out putdata) を全て記録する．なお，S-Listは，定義8で，攻撃者のアドバンテージAdvFS IA を定義する ためだけに用いるリストであり，攻撃対象として管理する情報ではない．
■タグオラクルT タグオラクルT は，相互認証プロトコルを実行する正直なタグの出力を 攻撃者に与える．sidはセッションIDとし，Tsid は，セッションsidに対応した振る舞いをす るタグオラクルとする．攻撃者は，Tsid にSendクエリとRevealクエリを送ることができる．
Tsid がSendクエリSend(∗)を受け取ると，正直なタグがセッション sid で(∗)を受け取った 場合と同じ処理を行い，その処理の結果得られるタグの出力を攻撃者に返す．また，Tsid が Revealクエリを受け取ると, Tsid はセッション sid で共有したセッション鍵 skID,sid を返す．
そして，攻撃者に与えた skID,sid を用いる全てのセッションと，それ以降の全てのセッション はRevealed状態に設定されるとする．
Tsidは，sidでのT の状態とする．sidで認証プロトコルを実行した結果，Tsidがサーバーの 認証に成功したらAccepted∈Tsidと設定され，sidでRevealed状態である時，Revealed ∈Tsid
と設定されるとする．つまり，Tsidは，AcceptedとRevealedの2ビットで構成される．
ま た ，T は ，T-List を 保 持 し て お り ，セ ッ シ ョ ン IDsid と T へ の 入 出 力 の 組 (sid,Inputdata,Out putdata) を 全 て 記 録 す る ．T-List は ，定 義 7 で 攻 撃 者 の ア ド バ ン テージを定義するためだけに使用する．
■ランダムオラクルHi ランダムオラクルHiは，理想化されたハッシュ関数を表現したオラ クルである．OMHSOプロトコルでは，3種のハッシュ関数:H0,H1,H2を使っている．
4.3.2 安全性要件の定義
我々は，Forward-secureタグ成りすまし不可能性，Forward-secureサーバー成りすまし不可
能性，Forward-secureタグ識別不可能性，非同期耐性の4つの安全性を定義する. κ:はセキュ
リティパラメタであり，鍵付ハッシュ関数の鍵長をあらわすとする.
定義6 (Forward-secureタグ識別不可能性) :挑戦者は，b∈ {0,1}をランダムに選択し，Setup アルゴリズムとKeyGenアルゴリズムを実行し，生成したシステムパラメタ，共有鍵，IDをS
とT に与え，攻撃者AFI にシステムパラメタとIDを与える．AFI は，SとT に任意の順番 で問い合わせを行い，ランダムオラクルにも任意の順序で問い合わせを行う．そして，AFI は 任意のタイミングで，任意のsid∗に対応するTsid∗ に，Testクエリを送る．もしb= 0ならば，
T は，セッションsid∗に対応する通常の処理を行い，その結果をAFI に返す．b=1ならば，
T は，タグが出力しうる値の集合からランダムに値を選択し，その値をAFI に返す．AFI が Testクエリを送った後も，AFI は，SとT に任意の順序で問い合わせを行う．最終的に，AFI
は，b˜ ∈ {0,1}を出力して停止する．もしb˜ = bかつ，Tsid∗ でRevealedでなければ，AFI の勝 ちとし，AFI のアドバンテージを
AdvAFI = Pr
sp← S etup(κ)
b˜ =b∧ (sk,ID)←KeyGen(sp) Revealed <Tsid∗ b← {R 0,1},
b˜ ← AS,TFI (sp,ID)
. とする．
あらゆる確率的多項式時間Turing機械Aに対して，AdvFIAが無視できるほど小さいとき，
そのRFID認証プロトコルはForward-secureタグ識別不可能性を満たすという．
この安全性要件は，直感的には，いかなる攻撃者でもタグの出力と乱数列を区別できないこ とを意味している．つまり，いかなる攻撃者でも，タグの出力からは全く情報が得られず，対 応する共有鍵を入手しない限りタグを区別することができない．よって，Forward-secureタグ 識別不可能性は，システムの出力を全て盗聴したとしても，特定のタグを追跡できない追跡不 可能性を保証している，
OMHSOプロトコルは，もし，攻撃者がサーバーからタグへの送られる情報を全て遮断する
などして，タグによるサーバーの認証を失敗させると，タグは共有鍵の更新を行わないよう設 計されている．言い換えると，攻撃者は，容易に，タグの共有鍵更新を妨害し，同じ共有鍵を 使用させることができる．もし，タグが解析され，その共有鍵が漏えいしたとすると，共有鍵 を所持していれば，通信履歴からタグを特定することができるため，そのタグは追跡をうける．
第4.1.2節で述べたように，現状では，鍵の更新が妨害された場合に追跡を防ぐ実用的な対
策法が存在しない．このため，鍵の更新が妨害された場合の追跡不可能性は，本論文の議論の 対象外とするが，タグから共有鍵が漏えいする場合には，そのタグが攻撃者の手に渡っている ので，追跡攻撃の状況にはならないと考えられる．
我々は，共有鍵が更新された場合の追跡不可能性を考える．大雑把に言うと，鍵更新前の タグの出力と，鍵更新後のタグの出力を対応付けられないことは，タグの出力が乱数列と区 別できなければ保証されるので，上で定義した識別不可能性を満たせば十分なことがわかる．
OMHSOプロトコルは，鍵更新回数の上限に何ら制約をおかず，検証のコストもほぼ維持した ままで，上記の性質を満たしている．さらに，鍵更新回数の上限がないことで，文献[61]で指 摘されたような DoSに似た攻撃を受けたとしてもタグの破壊を防ぐことができ，システムへ の被害を抑えることができる．
定義7 (Forward-secureタグ成りすまし不可能性) :挑戦者は，SetupアルゴリズムとKeyGen アルゴリズムを実行し，生成したシステムパラメタ，共有鍵，IDをSとT に与え，攻撃者 AFI にシステムパラメタとIDを与える．攻撃者AFT I は，SとT に任意の順番でアクセスす る．ランダムオラクルモデルの場合，AFT I は，ランダムオラクルにも任意の順番でアクセス する．AFT I 任意のタイミングで，任意の sid∗に対応するSsid∗ に，Testクエリを送る．Ssid∗ は，セッションIDsid∗ に対応する通常の処理を行い，AFT I と認証プロトコルを実行する．
もし，Ssid∗ がAcceptedであり,Tsid∗ がRevealedでなく，Ssid∗ がT に問い合わされていな ければ，AFT I の勝ちとする．AFT I のアドバンテージを以下のように定義する．
AdvAF T I = Pr
Accepted∈Ssid∗∧ sp←S etup(κ)
Revealed <Tsid∗∧ (sk,ID)← KeyGen(sp) Ssid∗ <T-List sid∗ ← AS,TFT I(sp,ID)
.
あらゆる確率的多項式時間Turing機械Aに対して，AdvFTIAが無視できるほど小さいとき，
その相互認証プロトコルは，Forward-secureタグ成りすまし不可能性を満たすという．
Forward-secureタグ成りすまし不可能性は，いかなる攻撃者であっても，共有鍵を持ってい
なければ，サーバーと認証プロトコルを実行し，受理されることは無いことを意味している．
つまり，いかなる攻撃者でも，共有鍵がなければ正しいタグのように振る舞うことが出来ない ことを意味している．よって，Forward-secureタグ成りすまし不可能性は，タグの共有鍵を知 らなければ，タグに成りすますことや，タグを偽造することは不可能であることを保証して いる．
定義8 (Forward-secure サーバー成りすまし不可能性 ) : 挑戦者は，Setup アルゴリズムと
KeyGenアルゴリズムを実行し，生成したシステムパラメタ，共有鍵，IDをSとT に与え，
攻撃者AFI にシステムパラメタと IDを与える．攻撃者AFS I は，SとT に任意の順番でア クセスする．ランダムオラクルモデルの場合，AFS I は，ランダムオラクルにも任意の順番で アクセスする．AFS I 任意のタイミングで，任意のsid∗ に対応するTsid∗ に，Testクエリを送 る．T は，セッションID sid∗に対応する通常の処理を行い，AFS I と認証プロトコルを実行 する．もし，Tsid∗ がAccepted であり, Tsid∗ がRevealedでなく，Tsid∗ がSに問い合わされて
いなければ，AFS I の勝ちとする．AFS I のアドバンテージを以下のように定義する．
AdvAFS I =Pr
Accepted∈Tsid∗∧ sp←S etup(κ)
Revealed<Tsid∗∧ (sk,ID)← KeyGen(sp) Tsid∗ <S-List sid∗ ← AS,TFS I(sp,ID)
.
あらゆる確率的多項式時間Turing機械Aに対して，AdvFSIAが無視できるほど小さいとき，
その相互認証プロトコルは，Forward-secureサーバー成りすまし不可能性を満たすという．
Forward-secureサーバー成りすまし不可能性は，いかなる攻撃者であっても，共有鍵を持っ
ていなければ，タグと認証プロトコルを実行し，受理されることは無いことを意味している．
つまり，いかなる攻撃者でも，共有鍵がなければ正しいサーバーのように振る舞うことが出来 ないことを意味している．よって，Forward-secureサーバー成りすまし不可能性は，サーバー の共有鍵を知らなければ，サーバーに成りすますことや，サーバーを偽造することは不可能で あることを保証している．
定義9 (非同期耐性)挑戦者は，SetupアルゴリズムとKeyGenアルゴリズムを実行し，生成 したシステムパラメタと共有鍵とIDをSとT に与える．次に，攻撃者ADS は，SとT に任 意の順序で問い合わせを行う．それ以前のセッションがいかなる結果であったとしても，ある セッションでSとT が正しく通信できたとき，圧倒的確率で相互認証に成功するならば，そ の相互認証プロトコルは非同期耐性を満たすという．
この安全性要件は，攻撃者がそれ以前のセッションでいかなる攻撃を行ったとしても，最新 のセッションで通信が正しく行われたならば，そのプロトコルの最新のセッションは正しく実 行されることを保証している．つまり，この安全性要件は，Juelsらが指摘した攻撃[61, 62]
への耐性を意味している．