OMHSO プロトコル

いなければ，AFS I の勝ちとする．AFS I のアドバンテージを以下のように定義する．

Adv_{AFS I} =Pr



 Accepted∈T_sid∗∧ sp←S etup(κ)

Revealed<T_sid∗∧ (sk,ID)← KeyGen(sp) T^sid∗ <S-List sid^∗ ← A^S,T_{FS I}(sp,ID)



.

あらゆる確率的多項式時間Turing機械Aに対して，AdvFSI_Aが無視できるほど小さいとき，

その相互認証プロトコルは，Forward-secureサーバー成りすまし不可能性を満たすという．

Forward-secureサーバー成りすまし不可能性は，いかなる攻撃者であっても，共有鍵を持っ

ていなければ，タグと認証プロトコルを実行し，受理されることは無いことを意味している．

つまり，いかなる攻撃者でも，共有鍵がなければ正しいサーバーのように振る舞うことが出来 ないことを意味している．よって，Forward-secureサーバー成りすまし不可能性は，サーバー の共有鍵を知らなければ，サーバーに成りすますことや，サーバーを偽造することは不可能で あることを保証している．

定義9 (非同期耐性)挑戦者は，SetupアルゴリズムとKeyGenアルゴリズムを実行し，生成 したシステムパラメタと共有鍵とIDをS^とT に与える．次に，攻撃者ADS は，S^とT ^に任 意の順序で問い合わせを行う．それ以前のセッションがいかなる結果であったとしても，ある セッションでS^とT が正しく通信できたとき，圧倒的確率で相互認証に成功するならば，そ の相互認証プロトコルは非同期耐性を満たすという．

この安全性要件は，攻撃者がそれ以前のセッションでいかなる攻撃を行ったとしても，最新 のセッションで通信が正しく行われたならば，そのプロトコルの最新のセッションは正しく実 行されることを保証している．つまり，この安全性要件は，Juelsらが指摘した攻撃[61, 62]

への耐性を意味している．

Server RFID-tag (sk⁺_ID,sk⁻_ID,^ID) (sk_ID,^ID)

S1.X← {^R 0,1}^t.

S2. SendX. ^X - T1.α^′← {^R 0,1}^t.

T2. Compute

β^′←H0(skID,^ID,X, α^′).

RFID tag authentication part T3. SetY^′←α^′||β^′. S3. ParseY^′asα^′||β^′. ^Y′ T4. SendY^′. S4. Compute

β⁺←H0(sk⁺_ID,^ID,X, α^′), β⁻←H₀(sk⁻_ID,^ID,X, α^′).

S5. Ifβ^′=β⁺then acceptand

computeZ←H₁(sk⁺_ID,^ID,X, α^′) S6. else ifβ^′=β⁻then

acceptand

computeZ←H1(sk⁻_ID,^ID,X, α^′) S7. else

rejectand setZ←^R h₁. Server authentication part

S8. SendZ. ^Z - T5. Compute

Z^′←H1(skID,^ID,X, α^′).

Key update part T6. IfZ^′=Zthen

S9. Ifβ^′=β⁺then compute accept

s←H₂(sk⁺_ID,^ID) T7. else

S10. and setsk⁻_ID←sk⁺_ID reject.

S11. and setsk⁺_ID←s, Key update part

S12. else keep the status. T8. IfZ=Z^′then

computes←H2(skID,^ID) T9. and setskID←s T10. else keep the status.

図4.1 OMHSO protocol

• skID：識別子がIDなるRFIDタグが保持している共有鍵．

• sk⁺_ID：サーバーが保持ている識別子がIDなるRFIDタグの最新の共有鍵．

• sk⁻_ID：サーバーが保持ている識別子がIDなるRFIDタグの1つ過去の共有鍵．

• H₀ :{0,1}^∗→ h₀． 安全性証明中では，ランダムオラクルとして扱う．

• H1 :{0,1}^∗→ h1． 安全性証明中では，ランダムオラクルとして扱う．

• H2 :{0,1}^∗→ key． 安全性証明中では，ランダムオラクルとして扱う．

■セットアップ RFID タグは，共有鍵 skID とIDを持っている．サーバーは，最新の共有 鍵 sk⁺_ID，1つ前の共有鍵 sk⁻_ID，RFIDの識別子IDを持っている．初期状態では，skID = sk⁺_ID， sk⁻_ID =⊥^とする．

■相互認証部 相互認証の処理手順を示す．(S1)サーバーは，ランダムにXを選択し，(S2)X をタグに送る．

(T1)タグは，X を受け取ったら，α^{′ をランダムに選択し，}(T2)β^′ ← H0(skID,ID,X, α^′)を計 算して，(T3)Y^′ ← α^′||β^{′ として，}(T4)Y^′をサーバーに返す．

(S3) サーバーは，Y^′ を受け取ったら α^{′ と}β^{′ に分割し，}(S4) β⁺ ← H0(sk⁺_ID,ID,X, α^′) と β⁻ ← H0(sk⁻_ID,ID,X, α^′)を計算し，(S5)β^′ =β⁺が成立するか検査し，成立するならばRFIDタ グの識別子がIDであることを受理し，Z ←H₁(sk_ID⁺,ID,X, α^′)を計算し，(S6)成立しないなら ば， β^′ = β⁻ が成立するか検査し，成立するならばRFIDタグの識別子がIDであることを受 理し，Z ← H1(sk⁻_ID,ID,X, α^′)を計算し，(S7)成立しないならば，RFIDタグの識別子がIDで あることを拒絶し，Z ←^R h1をランダムに選択して，(S8)Zをタグに送る．

(T5)タグは，Zを受け取ったら，Z^′ ←H₁(sk_ID,ID,X, α^′)を計算し，(T6)Z^′ =Z が成立する か検査し，成立するならば正しいサーバーであることを受理し，(T7)成立しないならば，正し いサーバーであることを拒絶する．

■鍵更新部 次に鍵更新の手順を示す．(S9) サーバーは，β^′ = β⁺ が成立するか検査し，成 立するならばタグと共有鍵の同期が取れていると判断し，s ← H₂(sk_ID⁺,ID)を計算し，(S10) sk⁻_ID ← sk⁺_ID として，(S11) sk⁺_ID ← s とすることで共有鍵を更新して，プロトコルを終了し，

(S12)成立しない場合は，更新処理を行わずにプロトコルを終了する．

(T8)タグは，Z^′ =X が成立するか検査し，成立するならばs←H2(sk⁺_ID,ID)を計算し，(T9) skID ← sとして，共有鍵を更新して，プロトコルを終了し，(T10)成立しない場合は，更新処 理を行わずにプロトコルを終了する．

4.4.1 仕組み

RFIDタグとサーバーの双方で共有鍵を更新する相互認証プロトコルでは，もし，一方だけ が共有鍵を更新すると，双方の共有鍵が異なってしまうため，以降のセッションでの認証が正 しく機能しなくなる．つまり，双方で共有鍵を更新する相互認証プロトコルを機能させるため には，鍵更新の非同期を克服しなければならない．

OMHSOプロトコルでは，サーバーはタグとの同期が取れていることを確認し，同期してい

るときにのみ共有鍵を更新することで，同期のずれが広がることを防いでいる．さらに，ハッ シュ関数を利用した2種類のチャレンジ-レスポンスプロトコルを構成して，同期が1つだけ ずれたとしても正しく認証できるよう工夫が施されている．これらの工夫を組み合わせること で，通信のエラーや攻撃によりプロトコルが途中終了したとしても，高々１つしか同期にずれ は生じず，以降のセッションでも正常にプロトコルを実行できる．OMHSOプロトコルの基本 的な安全性要件は，OSKプロトコルの構造を利用して達成している．そして，サーバー側が 最新と直前の2つの共有鍵を持つことで，タグ側の計算効率を維持したままで，非同期耐性を 達成している．