説明

情報処理装置及び暗号アルゴリズム評価方法及びプログラム

【課題】MD構造を持つハッシュ関数を用いた暗号アルゴリズムが安全であることを証明する。
【解決手段】ランダムオラクル圧縮関数(hRO)とMD構造で構成したハッシュ関数HMD(hRO)とIndifferentiableである追跡ランダムオラクル(ROT)部107を用いて、ハッシュ関数HMD(hRO)を用いる暗号アルゴリズムPの安全性を評価する。攻撃アルゴリズムA2実行部106が、暗号アルゴリズムPを実施する暗号アルゴリズムP実行部111と追跡ランダムオラクル(ROT)部107と通信を行い、条件C2における暗号アルゴリズムPの安全性S2を破る攻撃をシミュレートし、攻撃アルゴリズムA1実行部105が、暗号アルゴリズムPが利用する暗号アルゴリズムXの安全性S1を条件C1のもとで破る攻撃をシミュレートして、暗号アルゴリズムPの安全性を評価する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、暗号アルゴリズムの評価技術に関し、特に、ランダムオラクル関数を用いて暗号アルゴリズムを評価する技術に関する。
【背景技術】
【0002】
例えば、素因数分解の困難性に基づく暗号アルゴリズムの安全性の評価に関して、特許文献1に記載の技術がある。
【0003】
また、ハッシュ関数を用いた暗号アルゴリズムの安全性の評価に関して、非特許文献1〜非特許文献5に記載の技術がある。
【0004】
ハッシュ関数は暗号アルゴリズムでよく用いられるが、その安全性を直接評価することはできない。
通常、ハッシュ関数が用いられている暗号アルゴリズムの安全性の評価方法は、ハッシュ関数を理想化ハッシュ関数であるランダムオラクル(RO)に置き換え、ランダムオラクル(RO)を用いた暗号アルゴリズムを評価する。しかし、通常の暗号アルゴリズムの実装では、圧縮関数から構成したハッシュ関数Hが用いられる。
ランダムオラクル(RO)で安全性証明がつけられた暗号アルゴリズムがハッシュ関数Hを用いていても安全であることを示すためには、ハッシュ関数Hがランダムオラクル(RO)とIndifferentiableであることを示さなければならない。
Indifferentiableの定義については後述するが、概念的には、Indifferentiableとは、2つの対象(ハッシュ関数Hとランダムオラクル(RO))の区別が困難で、2つの対象が等価であるとみなせることである。
【0005】
ランダムオラクル(RO)とは、図13に示すように、ランダムオラクル(RO)への入力値とそれに対する出力値を記録するハッシュリストLを持ち、ハッシュリストLに無い初めての入力値に対しては決まった長さのランダムな値を決めそれを出力し、入力値と出力値をハッシュリストLに格納し、以前入力された値がハッシュリストLの中にあった場合、それに対応するハッシュリストLに記録された出力値を出力する関数である。
ランダムオラクル(RO)の入力は任意長で、出力は固定長である。
また、ランダムオラクル圧縮関数(hRO)はランダムオラクル(RO)の入力長が固定の関数である。
【0006】
ハッシュ関数とは、入力長が任意で出力長が固定の関数である。
通常、ハッシュ関数の構成には入力長出力長ともに固定の圧縮関数が用いられ、ハッシュ関数の構成法(圧縮関数の組み合わせ方)にはMerkle−Damgaard(MD)構造が用いられる。
【0007】
非特許文献2及び非特許文献3で提案されたMD構造を用いたハッシュ関数HMDは、圧縮関数をh(入力長をa、出力長をbとおく)とおくと、以下の通りになる。
HMD(M):
・M’=M||1||0…0||<M>,(パディングする0の数が最小となりかつM’の長さがa−bの倍数となるようにする。ただし、<M>はMのビット長の64ビット符号語)
・M’=(m[1],…,m[n]),(|m[i]|=a−b)
・for i=1,…,n,c[i+1]=h(c[i],m[i])
・c[n+1]を出力 つまり、ハッシュ関数への入力値Mにパディングを行ったM’を、a−bビット長ごとに分割してm[1],…,m[n]とし、初期値IV(bビット)とm[1]をMD構造の最初の圧縮関数hに入力し、この最初の圧縮関数hの出力(bビット)とm[2]を2番目の圧縮関数hに入力し、2番目の圧縮関数hの出力とm[3]を3番目の圧縮関数hに入力し、以降同様の手順を繰り返し、n番目の圧縮関数hからの出力(bビット)がハッシュ値となる。
【0008】
また、非特許文献3では、関数Xが関数YとIndifferentiableでかつ関数Yを用いた暗号アルゴリズムP(Y)が安全ならば、関数YをXに置き換えた暗号アルゴリズムP(X)も安全であることが示されている。
関数Xが関数YとIndifferentiableであるとの定義は、任意の識別者Dに対して|Pr[D(X)⇒1]−Pr[D(Y)⇒1]|<e(eは無視できるくらい小さい値)が成り立つことである。
【0009】
以上の説明をもとに、ランダムオラクル圧縮関数(hRO)とMD構造を用いたハッシュ関数HMD(hRO)について説明する。
図14は、ランダムオラクル圧縮関数(hRO)とMD構造を用いたハッシュ関数HMD(hRO)を説明する図である。
図14では、MD構造の各圧縮関数が、ランダムオラクル圧縮関数(hRO)で構成されている。ランダムオラクル圧縮関数(hRO)とは、前述したように、入力長が固定長のランダムオラクル(RO)である。
この場合にも、ハッシュ関数への入力値Mにパディングを行ったM’を、a−bビット長ごとに分割してm[1],…,m[n]とし、初期値IV(bビット)とm[1]をMD構造の最初のランダムオラクル圧縮関数(hRO)に入力し、この最初のランダムオラクル圧縮関数(hRO)の出力(bビット)とm[2]を2番目のランダムオラクル圧縮関数(hRO)に入力し、2番目のランダムオラクル圧縮関数(hRO)の出力とm[3]を3番目の圧縮関数に入力し、以降同様の手順を繰り返し、n番目のランダムオラクル圧縮関数(hRO)からの出力(bビット)がハッシュ値となる。
【0010】
非特許文献2では、MD構造とランダムオラクル圧縮関数(hRO)を用いて構成したハッシュ関数HMD(hRO)は、ランダムオラクル(RO)とIndifferentiableではないことが示されている。
このため、ランダムオラクル圧縮関数(hRO)とMD構造で構成したハッシュ関数HMD(hRO)を用いた暗号アルゴリズムP(HMD(hRO))を、ランダムオラクル(RO)を用いた暗号アルゴリズムP(RO)に置き換え、暗号アルゴリズムP(RO)について安全性が証明されても、ハッシュ関数HMD(hRO)は、ランダムオラクル(RO)とIndifferentiableでないため、暗号アルゴリズムP(HMD(hRO))は安全であるとはいえない。
【特許文献1】特開2006−072336号公報
【非特許文献1】Mihir Bellare, Phillip Rogaway: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. ACM Conference on Computer and Communications Security 1993: pp.62−73
【非特許文献2】Jean−Sebastien Coron, Yevgeniy Dodis, Cecile Malinaud, Prashant Puniya: Merkle−Damgard Revisited: How to Construct a Hash Function. CRYPTO 2005: pp.430−448
【非特許文献3】Ueli M. Maurer, Renato Renner, Clemens Holenstein: Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology. TCC 2004: pp.21−39
【非特許文献4】Ralph C. Merkle: One Way Hash Functions and DES. CRYPTO 1989: pp.428−446
【非特許文献5】A Design Principle for Hash Functions. CRYPTO 1989: pp.416−427
【発明の開示】
【発明が解決しようとする課題】
【0011】
MD構造はSHA−1(Secure Hash Algorithm−1)やSHA−256など世界標準のハッシュ関数に採用されており、MD構造を採用したハッシュ関数を用いた暗号アルゴリズムの評価は重要である。
前述したように、非特許文献2において、MD構造とランダムオラクル圧縮関数(hRO)で構成したハッシュ関数HMD(hRO)はランダムオラクル(RO)とIndifferentiableにならないことが示されている。
すなわち、ランダムオラクル(RO)で安全性証明がついた暗号アルゴリズムに対して、ランダムオラクル(RO)をランダムオラクル圧縮関数(hRO)とMD構造で構成したハッシュ関数HMD(hRO)に置き換えたときの暗号アルゴリズムの安全性を示すことはできないという課題がある。
【0012】
本発明は、このような課題を解決することを主な目的の一つとしており、ランダムオラクル圧縮関数(hRO)とMD構造で構成したハッシュ関数HMD(hRO)を用いた暗号アルゴリズムの安全性を証明可能な機構を実現することを主な目的とする。
【課題を解決するための手段】
【0013】
本発明に係る情報処理装置は、
第1の値と乱数値である第2の値の組が一つ以上示される組情報を記憶する組情報記憶部と、
任意の値を第2の値とする問い合わせを受けた際に前記組情報記憶部に記憶されている前記組情報を検索し、当該第2の値と組となる第1の値が前記組情報から抽出できた場合に抽出した第1の値を応答し、当該第2の値と組となる第1の値が前記組情報から抽出できない場合に抽出できないことを示す値を応答する追跡オラクル部を含み、MD(Merkle−Damgaard)構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数とIndifferentiableである追跡ランダムオラクル部と、
MD構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数を用いる、評価対象の暗号アルゴリズムが示される暗号アルゴリズム情報を入力する情報入力部と、
前記追跡ランダムオラクル部を用いて、前記暗号アルゴリズム情報に示されている評価対象暗号アルゴリズムの評価を行うアルゴリズム評価部とを有することを特徴とする。
【発明の効果】
【0014】
本発明によれば、MD構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数とIndifferentiableである追跡ランダムオラクル部を用いることで、当該ハッシュ関数を用いた暗号アルゴリズムの安全性を証明することができる。
【発明を実施するための最良の形態】
【0015】
実施の形態1.
本実施の形態では、ランダムオラクル圧縮関数(hRO)とMD構造で構成したハッシュ関数HMD(hRO)とIndifferentiableなアルゴリズムである追跡ランダムオラクル(ROT)を導入する。
追跡ランダムオラクル(ROT)を用いて安全性が証明された場合は、ランダムオラクル圧縮関数(hRO)とMD構造で構成したハッシュ関数HMD(hRO)を用いた暗号アルゴリズムは安全である。
追跡ランダムオラクル(ROT)はランダムオラクル(RO)に新たな機能である追跡オラクル(TO)を追加したアルゴリズムである。
【0016】
追跡オラクル(TO)を次のように定義する。
追跡オラクル(TO)は、あるアルゴリズムの入力値と出力値のペアが格納されているリストの中身を知ることができ、追跡オラクル(TO)への質問yに対して、追跡オラクル(TO)はリストの中のペアの中で出力値に対応する部分にyが存在するかどうか調べ、存在する場合はそれに対応する入力値を返し、存在しない場合は、存在しないことを示す値を返信する。
【0017】
追跡ランダムオラクル(ROT)は、例えば、図2〜図4のいずれかの方式で実現される。
【0018】
図2に示す例では、追跡ランダムオラクル(ROT)は、出力長が固定長(ここではbビットとする)のランダムオラクル(RO)と追跡オラクル(TO)から構成される。
ランダムオラクル(RO)の動作自体は、図13を参照して説明した通りである。
追跡ランダムオラクル(ROT)は初期状態として空のハッシュリストLを所有する。
ランダムオラクル(RO)は質問Xが来た場合、∃(X,Y)∈LならばYを返信する。もしそのようなYが存在しないならば、bビットの乱数Zを返信し、ハッシュリストLに(X,Z)を追加する。
追跡オラクル(TO)は質問Yに対して、もし∃(X,Y)∈Lならば、Xを返信する。
もしそのようなXが存在しないならば、存在しないことが分かる値を返信する。
【0019】
また、図3に示す例では、ランダムオラクル(RO)は初期状態として空のハッシュリストLを所有する。
ランダムオラクル(RO)は質問Xが来た場合、∃(X,Y)∈LならばYを返信する。もしそのようなYが存在しないならば、bビットの乱数Zを返信し、ハッシュリストLに(X,Z)を追加する。
追跡オラクル(TO)からランダムオラクル(RO)にハッシュリストLを見せるように要請された場合は、追跡オラクル(TO)にハッシュリストLの中の値を全て追跡オラクル(TO)に返信する。
追跡オラクル(TO)は質問Yに対してランダムオラクル(RO)にハッシュリストLを見せるように要請し、ハッシュリストLの中身を受け取る。
追跡オラクル(TO)は、もし∃(X,Y)∈Lならば、Xを返信する。もしそのようなXが存在しないならば、存在しないことが分かる値を返信する。
【0020】
図4に示す例では、ランダムオラクル(RO)は初期状態として空のハッシュリストLを所有する。
ランダムオラクル(RO)は質問Xが来た場合、∃(X,Y)∈LならばYを返信する。もしそのようなYが存在しないならば、bビットの乱数Zを返信し、ハッシュリストLに(X,Z)を追加する。
追跡オラクル(TO)は、ランダムオラクル(RO)のハッシュリストLを自由に閲覧することができ、追跡オラクル(TO)への質問Yに対して、ランダムオラクル(RO)のハッシュリストLを閲覧し、もし∃(X,Y)∈Lならば、Xを返信する。もしそのようなXが存在しないならば、存在しないことが分かる値を返信する。
【0021】
MD構造の圧縮関数にランダムオラクル圧縮関数(hRO)を用いたハッシュ関数HMD(hRO)は、追跡ランダムオラクル(ROT)とIndifferentiableである。
この証明は、後述する。
【0022】
本実施の形態では、追跡ランダムオラクル(ROT)を用いて暗号アルゴリズムを評価する。
この評価で安全であれば、MD構造とランダムオラクル圧縮関数(hRO)を用いたハッシュ関数HMD(hRO)を用いた暗号アルゴリズムは安全であるといえる。
【0023】
次に、本実施の形態に係る暗号アルゴリズムの評価方法を図5を用いて説明する。
【0024】
MD構造と複数のランダムオラクル圧縮関数(hRO)で構成したハッシュ関数HMD(hRO)を用いた暗号アルゴリズムを評価対象暗号アルゴリズムP(HMD(hRO))とする。
また、暗号アルゴリズムP(HMD(hRO))が利用する暗号アルゴリズムを暗号アルゴリズムXとする。
また、暗号アルゴリズムXの評価条件を条件C1とし、暗号アルゴリズムXが満たすべき安全性を安全性S1とする。また、暗号アルゴリズムP(HMD(hRO))の評価条件を条件C2とし、暗号アルゴリズムP(HMD(hRO))が満たすべき安全性を安全性S2とする。
そして、暗号アルゴリズムXが条件C1のとき安全性S1を満たす場合に、HMD(hRO)を追跡ランダムオラクル(ROT)に置き換えた暗号アルゴリズムP(ROT)が、条件C2のもとで安全性S2を満たすことを評価する。
前述のように、ハッシュ関数HMD(hRO)は追跡ランダムオラクル(ROT)とIndifferentiableであるため、このような置き換えが可能である。
なお、HMD(hRO)の追跡ランダムオラクル(ROT)への置き換えとは、具体的には、後述するように、暗号アルゴリズムP(HMD(hRO))の安全性S2を破る攻撃をシミュレートする際に追跡ランダムオラクル(ROT)を利用することである。
【0025】
具体的には、図5のように、条件C2のもとで暗号アルゴリズムP(ROT)の安全性S2を破る攻撃者(アルゴリズム)を用いて、条件C1のもとで暗号アルゴリズムXを破る攻撃者(アルゴリズム)が構成できるかどうか判定する。これが構成できた場合、暗号アルゴリズムP(HMD(hRO))が安全であると判定する。
なお、暗号アルゴリズムP(HMD(hRO))との表記には、複数のハッシュ関数HMD1(hRO1),…,HMDn(hROn)が用いられる暗号アルゴリズムP(HMD1(hRO1),…,HMDn(hROn))が含まれる。
また、同様に、暗号アルゴリズムP(ROT)との表記には、暗号アルゴリズムP(HMD1(hRO1),…,HMDn(hROn))に対応する暗号アルゴリズムP(ROT1,…,ROTn)が含まれる。
また、以下では、暗号アルゴリズムP(HMD(hRO))と暗号アルゴリズムP(ROT)の区別が必要でないときは、両者を一括して暗号アルゴリズムPと表記する。
【0026】
上記の判定の原理は、「暗号アルゴリズムXが条件C1のもとで安全性S1を満たせば、暗号アルゴリズムP(HMD(hRO))は条件C2のもとで安全性S2を満たす」という命題に対する対偶である「条件C2のもとで暗号アルゴリズムP(HMD(hRO))の安全性S2が破られれば、条件C1のもとで暗号アルゴリズムXの安全性S1が破られる」ことを暗号アルゴリズムP(ROT)を通じて証明することで、上記の命題を証明し、「暗号アルゴリズムXが条件C1のもとで安全性S1を満す」ことは既知であるため、「暗号アルゴリズムP(HMD(hRO))は条件C2のもとで安全性S2を満たす」と評価するものである。
なお、暗号アルゴリズムPは評価対象暗号アルゴリズムの例であり、暗号アルゴリズムXは関連暗号アルゴリズムの例である。
また、条件C1は第1の評価条件の例であり、条件C2は第2の評価条件の例であり、安全性S1は第1の安全性の例であり、安全性S2は第2の安全性の例である。
【0027】
上記の暗号アルゴリズムの評価方法の具体例を説明する。
RSA(Rivest Shamir Adleman)関数(RSAは登録商標)が選択平文攻撃のもとで一方向性を満たすとき、RSA−OAEP(RSA optimal asymmetric encryption padding)暗号(RSAは登録商標)が適応的選択暗号文攻撃のもとで識別不可能安全であることを示すためには、RSA−OAEP暗号に対して、適応的選択暗号文攻撃を行い、RSA−OAEP暗号の識別不可能安全を破る攻撃者を用いて、選択平文攻撃を行い、RSA関数のRSA仮定を破る攻撃者を構成する必要がある。
この場合は、暗号アルゴリズムXをRSA関数とし、暗号アルゴリズムPをRSA−OAEP暗号アルゴリズムとし、条件1を選択平文攻撃、安全性S1を一方向性、条件2を適応的選択暗号文攻撃、安全性S2を識別不可能性とし、追跡ランダムオラクルの個数を2として評価を行う。
【0028】
上記の暗号アルゴリズムの評価方法の具体例を説明する。
落とし戸付き一方向性関数が選択平文攻撃のもとで一方向性を満たすとき、FDH(Full Domain Hash)が適応的選択文書攻撃のもとで存在的偽造不可能であることを示すためには、FDHに対して、適応的選択文書攻撃を行い、FDHの存在的偽造不可能を破る攻撃者を用いて、直接攻撃を行い、落とし度付き一方向性関数の一方向性を破る攻撃者を構成する必要がある。
この場合は、暗号アルゴリズムXを落とし戸付き一方向性関数とし、暗号アルゴリズムPをFDHアルゴリズムとし、条件1を直接攻撃、安全性S1を一方向性、条件2を適応的選択文書攻撃、安全性S2を存在的偽造不可能とし、追跡ランダムオラクルの個数を1として評価を行う。
【0029】
以上の説明を前提に、図1を参照して、本実施の形態に係る暗号アルゴリズム評価装置の構成例を説明する。
図1に示す暗号アルゴリズム評価装置100は、情報処理装置の例である。
【0030】
図1において、情報入力部101は、各種情報を入力する。情報入力部101は、例えば、評価対象の暗号アルゴリズムP(HMD(hRO))、暗号アルゴリズムP(HMD(hRO))が利用する暗号アルゴリズムXが示される暗号アルゴリズム情報を入力する。
また、情報入力部101は、暗号アルゴリズムXの条件C1及び安全性S1、暗号アルゴリズムP(HMD(hRO))の条件C2及び安全性S2が示される条件情報を入力する。
【0031】
情報出力部102は、後述するアルゴリズム評価部104による暗号アルゴリズムの評価結果等を出力(表示、音声出力等)する。
制御部103は、暗号アルゴリズム評価装置100の全体的な制御を行う。
【0032】
アルゴリズム評価部104は、評価対象暗号アルゴリズムP(ROT)及び暗号アルゴリズムXの評価を行う。
アルゴリズム評価部104は、攻撃アルゴリズムA1実行部105と攻撃アルゴリズムA2実行部106を備える。
攻撃アルゴリズムA1実行部105は、暗号アルゴリズムXを攻撃する攻撃アルゴリズムA1を実行する。
攻撃アルゴリズムA2実行部106は、暗号アルゴリズムP(ROT)を攻撃する攻撃アルゴリズムA2を実行する。
換言すると、攻撃アルゴリズムA2実行部106は、条件情報に示される条件C2のもとで安全性S2を破る攻撃を評価対象暗号アルゴリズムP(ROT)に対してシミュレートする。
また、攻撃アルゴリズムA1実行部105は、攻撃アルゴリズムA2実行部106による攻撃内容に基づき、条件情報に示される条件C1のもとで安全性S1を破る攻撃を暗号アルゴリズムXに対してシミュレートする。
攻撃アルゴリズムA1実行部105は、第1の攻撃部の例であり、攻撃アルゴリズムA2実行部106は、第2の攻撃部の例である。
そして、アルゴリズム評価部104は、前述したように、攻撃アルゴリズムA2実行部106が暗号アルゴリズムP(ROT)に対する攻撃のシミュレーションにおいて条件C2のもとでS2を破り、攻撃アルゴリズムA1実行部105が暗号アルゴリズムXに対する攻撃のシミュレーションにおいて条件C1のもとで安全性S1を破った場合に、「暗号アルゴリズムXが条件C1のもとで安全性S1を満たせば、暗号アルゴリズムP(HMD(hRO))は条件C2のもとで安全性S2を満たす」という命題に対する対偶である「条件C2のもとで暗号アルゴリズムP(HMD(hRO))の安全性S2が破られれば、条件C1のもとで暗号アルゴリズムXの安全性S1が破られる」が証明され、対偶の証明により上記の命題が証明され、「暗号アルゴリズムXが条件C1のもとで安全性S1を満す」ことは既知であるため、「暗号アルゴリズムP(HMD(hRO))は条件C2のもとで安全性S2を満たす」と評価する。
【0033】
追跡ランダムオラクル(ROT)部107は、前述した追跡ランダムオラクル(ROT)を実現する。
つまり、追跡ランダムオラクル(ROT)部107は、ランダムオラクル(RO)部108と追跡オラクル(TO)部109を備え、MD構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数とIndifferentiableである。
ランダムオラクル(RO)部108は、ランダムオラクル(RO)を実現する。つまり、ランダムオラクル(RO)部108は、任意の値x(第1の値)についての問い合わせを受けた際に後述するハッシュリスト記憶部110に記憶されているハッシュリストLを検索し、値xと組となる値y(第2の値)がハッシュリストLから抽出できた場合に抽出した値yを応答し、当該値xと組となる値がハッシュリストLから抽出できない場合に乱数値を生成し、生成した乱数値を当該値xと組となる値yとして応答し、当該第値xと当該値yの組をハッシュリストLに追加してハッシュリスト記憶部110に記憶させる。
追跡オラクル(TO)部109は、追跡オラクル(TO)を実現する。
つまり、追跡オラクル(TO)部109は、任意の値y(第2の値)についての問い合わせを受けた際にハッシュリスト記憶部110に記憶されているハッシュリストLを検索し、当該値yと組となる値x(第1の値)がハッシュリストLから抽出できた場合に抽出した値xを応答し、当該値yと組となる値がハッシュリストLから抽出できない場合に抽出できないことを示す値を応答する。
【0034】
ハッシュリスト記憶部110は、ハッシュリストLを記憶する。
ハッシュリストLは、組情報の例であり、また、ハッシュリスト記憶部110は組情報記憶部の例である。
【0035】
暗号アルゴリズムP実行部111は、暗号アルゴリズムP(HMD(hRO))を実行する。
暗号アルゴリズムP実行部111は、評価対象暗号アルゴリズム実行部の例である。
また、暗号アルゴリズムX実行部112は、関連暗号アルゴリズムである暗号アルゴリズムXを実行する。
暗号アルゴリズムX実行部112は、関連暗号アルゴリズム実行部の例である。
【0036】
なお、以下では、攻撃アルゴリズムA1実行部105をA1実行部、攻撃アルゴリズムA2実行部106をA2実行部、追跡ランダムオラクル(ROT)部107をROT部、ランダムオラクル(RO)部108をRO部、追跡オラクル(TO)部109をTO部、暗号アルゴリズムP実行部111をP実行部、暗号アルゴリズムX実行部112をX実行部とも表記する。
【0037】
次に、図6を用いて、本実施の形態に係る暗号アルゴリズム評価装置100の動作の概要を説明する。
【0038】
攻撃アルゴリズムA1(攻撃アルゴリズムA1実行部105)が、攻撃アルゴリズムA2(攻撃アルゴリズムA2実行部106)に安全性S2に沿ったデータを与える。攻撃アルゴリズムA2は、このデータについて、暗号アルゴリズムPの安全性S2を破る攻撃を行う。
また、攻撃アルゴリズムA2は、暗号アルゴリズムP(暗号アルゴリズムP実行部111)、ランダムオラクル(RO)(ランダムオラクル(RO)部108)、追跡オラクル(TO)(追跡オラクル(TO)部109)の各々に対して質問を行い、質問に対する応答を得て、質問内容と応答内容とを解析して、攻撃アルゴリズムA1から与えられたデータについて、暗号アルゴリズムPの安全性S2を破る攻撃を行う。
攻撃アルゴリズムA2は、条件C2のもとで自由に暗号アルゴリズムP、ランダムオラクル(RO)、追跡オラクル(TO)を用いることができる。
【0039】
ランダムオラクル(RO)は、攻撃アルゴリズムA2からの質問ciに対してハッシュリストLを参照して、出力値diを応答する。
追跡オラクル(TO)は、攻撃アルゴリズムA2からの質問eiに対してハッシュリストLを参照して、出力値fiを応答する。
暗号アルゴリズムPは、攻撃アルゴリズムA2からの質問aiに対して、質問aiに基づいてランダムオラクル(RO)への質問giと暗号アルゴリズムX(暗号アルゴリズムX実行部112)への質問miを生成し、それぞれランダムオラクル(RO)及び暗号アルゴリズムXに出力し、ランダムオラクル(RO)から出力値hiを取得し、暗号アルゴリズムXから出力値niを取得し、取得した値hiと値niから攻撃アルゴリズムA2への応答値biを生成し、出力する。
そして、攻撃アルゴリズムA2は、質問内容と応答内容とを解析して、攻撃アルゴリズムA1から与えられたデータについて、暗号アルゴリズムPの安全性S2を破る攻撃結果を攻撃アルゴリズムA1に回答する。
【0040】
攻撃アルゴリズムA1は、すべての通信記録と、暗号アルゴリズムPと追跡ランダムオラクル(ROT)の内部記録データを解析して、暗号アルゴリズムXの安全性S1を破る攻撃を行う。
すべての通信記録とは、攻撃アルゴリズムA2の攻撃に用いられたすべての質問内容、応答内容であり、具体的には、攻撃アルゴリズムA2と暗号アルゴリズムXとの間で通信された値aiと値bi、攻撃アルゴリズムA2とランダムオラクル(RO)との間で通信された値ciと値di、攻撃アルゴリズムA2と追跡オラクル(TO)との間で通信された値eiと値fi、暗号アルゴリズムPとランダムオラクル(RO)との間で通信された値giと値hi、暗号アルゴリズムPと暗号アルゴリズムXとの間で通信された値miと値niである。
【0041】
そして、攻撃アルゴリズムA2が高い確率で暗号アルゴリズムPの安全性S2を破り、攻撃アルゴリズムA1が高い確率で暗号アルゴリズムXの安全性S1を破る場合に、前述の「条件C2のもとで暗号アルゴリズムPの安全性S2が破られれば、条件C1のもとで暗号アルゴリズムXの安全性S1が破られる」という対偶が証明され、暗号アルゴリズムP(HMD(hRO))は安全である(安全性S2を満たす)と評価される。
【0042】
例えば、暗号アルゴリズムXをRSA関数とし、暗号アルゴリズムPをRSA−OAEP暗号アルゴリズムとし(RSAは登録商標)、条件C1を選択平文攻撃、安全性S1を一方向性、条件C2を適応的選択暗号文攻撃、安全性S2を識別不可能性とし、追跡ランダムオラクルの個数を2とした場合は、攻撃アルゴリズムA1は、2つの平文を生成するとともに、暗号アルゴリズムPにより各々の平文の暗号文を生成し、生成した2つの平文と、生成した2つの暗号文のうちのいずれか1つの暗号文を攻撃アルゴリズムA2に出力する。
攻撃アルゴリズムA2は、ランダムオラクル(RO)、追跡オラクル(TO)、暗号アルゴリズムPへ問い合わせを行い、問い合わせに対する応答を取得し、問い合わせ内容と応答内容を解析して、攻撃アルゴリズムA1から入力した暗号文に対応する平文がいずれであるかを識別する。
【0043】
例えば、暗号アルゴリズムXを落とし戸付き一方向性関数とし、暗号アルゴリズムPをFDHアルゴリズムとし、条件C1を直接攻撃、安全性S1を一方向性、条件C2を適応的選択文書攻撃、安全性S2を存在的偽造不可能とする。
攻撃アルゴリズムA2は、ランダムオラクル(RO)、追跡オラクル(TO)、暗号アルゴリズムPへ問い合わせを行い、問い合わせに対する応答を取得し、問い合わせ内容と応答内容を解析して、暗号アルゴリズムPの偽造署名を出力する。
【0044】
次に、本実施の形態に係る暗号アルゴリズム評価装置100の動作例を図7及び図8のフローチャートを用いて説明する。
【0045】
まず、情報入力部101が、暗号アルゴリズム情報を入力して、暗号アルゴリズムP(HMD(hRO))及び暗号アルゴリズムXの指定を受け付ける(S701)(情報入力ステップ)。
次に、情報入力部101が、条件情報を入力して、攻撃アルゴリズムA1の動作条件、攻撃アルゴリズムA2の動作条件を受け付ける(S702)(情報入力ステップ)。
この動作条件には、条件C1、条件C2、安全性S1、安全性S2のほか、攻撃アルゴリズムA1及び攻撃アルゴリズムA2を実行するために必要な条件が含まれる。例えば、攻撃アルゴリズムA1実行部105が、ランダムオラクル(RO)部108、追跡オラクル(TO)部109、暗号アルゴリズムP実行部111への質問を終了するための終了条件(質問回数、時間等)が含まれる。
【0046】
次に、制御部103が、攻撃アルゴリズムA1実行部105及び攻撃アルゴリズムA2実行部106を起動し(S703)、攻撃アルゴリズムA1実行部105が追跡ランダムオラクル(ROT)部107、暗号アルゴリズムP実行部111、暗号アルゴリズムX実行部112を起動する(S704)。
【0047】
次に、攻撃アルゴリズムA1実行部105が条件C2に沿ったデータを生成し、攻撃アルゴリズムA2実行部106に渡す(S705)(アルゴリズム評価ステップ)。
例えば、暗号アルゴリズムP(HMD(hRO))が、RSA(登録商標)−OAEP等の公開鍵暗号アルゴリズムであれば、攻撃アルゴリズムA1実行部105は、2つの平文を生成するとともに、暗号アルゴリズムP(HMD(hRO))により各々の平文の暗号文を生成し、生成した2つの平文と、生成した2つの暗号文のうちのいずれか1つの暗号文を攻撃アルゴリズムA2実行部106に出力する。
【0048】
次に、攻撃アルゴリズムA2実行部106は、攻撃アルゴリズムA1実行部105から入力したデータについて、暗号アルゴリズムP(HMD(hRO))の安全性S2を破る攻撃をシミュレートする。
具体的には、S706〜S709の処理を終了条件に合致するまで繰り返すことにより攻撃をシミュレートする。
【0049】
攻撃アルゴリズムA2実行部106は、まず、質問対象(ランダムオラクル(RO)部108、追跡オラクル(TO)部109、暗号アルゴリズムP実行部111)とその質問対象への質問内容を導出する(S706)(アルゴリズム評価ステップ)。
攻撃アルゴリズムA2実行部106は、既にいずれかの質問対象に対して行った質問内容及びその回答内容を解釈して、次の質問対象及び質問内容を導出する。
次に、攻撃アルゴリズムA2実行部106は、質問対象に質問内容を問い合わせる(S707)(アルゴリズム評価ステップ)。
【0050】
攻撃アルゴリズムA2実行部106から質問を受けた質問対象は、当該質問に回答し(S708)、攻撃アルゴリズムA2実行部106は、質問対象から回答を受け取り、攻撃アルゴリズムA1実行部105が参照可能なメモリに質問内容と回答内容を格納する(S709)。
そして、終了条件に合致していない場合(S710でNO)は、S706以降の処理を繰り返し、終了条件に合致している場合(S710でYES)は、攻撃アルゴリズムA2実行部106は攻撃アルゴリズムA1実行部105に解を答える(S711)(アルゴリズム評価ステップ)。
例えば、攻撃アルゴリズムA1実行部105から2つの平文と1つの暗号文を入力している場合は、攻撃アルゴリズムA2実行部106はS706〜S709の処理で得た質問と回答を解析して、2つの平文のうちのどちらの平文が暗号文に対応しているかを識別し、識別結果を解として攻撃アルゴリズムA1実行部105に答える。
例えば、攻撃アルゴリズムA2実行部106はS706〜S709の処理で得た質問と回答を解析して、暗号アルゴリズムPの偽造署名を攻撃アルゴリズムA1実行部105に答える。
【0051】
次に、攻撃アルゴリズムA1実行部105が、安全性S1を破る処理を試行する(S712)(アルゴリズム評価ステップ)。攻撃アルゴリズムA2実行部106からの解は常に正しいため、攻撃アルゴリズムA1実行部105は攻撃アルゴリズムA2実行部106の解が正しいか否かを確認する必要なく、安全性S1を破る処理を施行する。
S712において、攻撃アルゴリズムA1実行部105は、S709及び後述のS908においてメモリに記憶されている内容を解析して、安全性S1を破る処理を実行する。メモリに記憶されている内容は、攻撃アルゴリズムA2実行部106の攻撃に用いられたすべての質問内容、応答内容である。
攻撃アルゴリズムA1実行部105は、例えば、S712において、選択平文攻撃においてRSA関数(RSAは登録商標)の一方向性を破る攻撃を行う。
攻撃アルゴリズムA1実行部105は、例えば、S712において、直接攻撃において落とし度付き一方向性関数の一方向性を破る攻撃を行う。
【0052】
次に、アルゴリズム評価部104が、攻撃アルゴリズムA1実行部105により暗号アルゴリズムXの安全性S1が破られたか否かを判断する(S713)(アルゴリズム評価ステップ)。
暗号アルゴリズムXの安全性S1が破られている場合(S714でYES)は、アルゴリズム評価部104は暗号アルゴリズムP(HMD(hRO))は安全であると評価する(暗号アルゴリズムP(HMD(hRO))は条件C2のもと安全性S2を満たすと評価する)(S714)(アルゴリズム評価ステップ)。
一方、暗号アルゴリズムXの安全性S1が破られていない場合(S714でNO)は、アルゴリズム評価部104は暗号アルゴリズムP(HMD(hRO))が安全か否かの判断ができないと評価する(暗号アルゴリズムP(HMD(hRO))が条件C2のもと安全性S2を満たすとの判断ができないと評価する)(S715)(アルゴリズム評価ステップ)。
最後に、情報出力部102が、アルゴリズム評価部104の評価結果を出力する(S716)。
【0053】
次に、図7のS707及びS708の処理の詳細を、質問対象ごとに説明する。
図9は、攻撃アルゴリズムA2実行部106が暗号アルゴリズムP実行部111に質問を問い合わせ、暗号アルゴリズムP実行部111が回答を行う際の処理の詳細を示す。
図10は、攻撃アルゴリズムA2実行部106がランダムオラクル(RO)部108に質問を問い合わせ、ランダムオラクル(RO)部108が回答を行う際の処理(追跡ランダムオラクル実行ステップ)の詳細を示す。
図11は、攻撃アルゴリズムA2実行部106が追跡オラクル(TO)部109に質問を問い合わせ、追跡オラクル(TO)部109が回答を行う際の処理(追跡ランダムオラクル実行ステップ)の詳細を示す。
【0054】
まず、図9について説明する。
最初に、攻撃アルゴリズムA2実行部106が条件C2を満足する値aiを暗号アルゴリズムP実行部111に問い合わせる(S901)。
具体的には、条件C2が適応的選択暗号文攻撃である場合には、攻撃アルゴリズムA2実行部106は、攻撃アルゴリズムA1実行部105から与えられた暗号文とは異なる任意の暗号文を暗号アルゴリズムP実行部111に問い合わせて、問い合わせた暗号文から復号された平文を暗号アルゴリズムP実行部111から得ることができる。
具体的には、条件C2が適応的選択文書攻撃である場合には、攻撃アルゴリズムA2実行部106は、任意の平文を暗号アルゴリズムP実行部111に問い合わせて、問い合わせた平文に対する署名を暗号アルゴリズムP実行部111から得ることができる。
【0055】
次に、攻撃アルゴリズムA2実行部106から値aiの問い合わせを受けた暗号アルゴリズムP実行部111は、問い合わせのあった値aiに基づいてランダムオラクル(RO)部108への質問値giを生成し、生成した質問値giをランダムオラクル(RO)部108に問い合わせる(S902)。
【0056】
次に、ランダムオラクル(RO)部108が、ハッシュリストLを作りつつ、質問giに対する回答値hiを暗号アルゴリズムP実行部111に回答する(S903)。
つまり、ランダムオラクル(RO)部108は、質問giと組となる値がハッシュリストLにある場合は、組となる値を回答値hiとして暗号アルゴリズムP実行部111に回答し、質問giと組となる値がハッシュリストLにない場合は、乱数値を生成し、当該乱数値を回答値hiとして暗号アルゴリズムP実行部111に回答し、当該乱数値を質問giと組にしてハッシュリストLに追加する。
【0057】
次に、暗号アルゴリズムP実行部111は、ランダムオラクル(RO)部108からの回答を取得する(S904)。
【0058】
次に、暗号アルゴリズムP実行部111は、攻撃アルゴリズムA2実行部106から問い合わせのあった値aiに基づいて暗号アルゴリズムX実行部112への質問値miを生成し、生成した質問値miを暗号アルゴリズムX実行部112に問い合わせる(S905)。
次に、暗号アルゴリズムX実行部112が、暗号アルゴリズムP実行部111から問い合わせのあった値miに対する回答値niを暗号アルゴリズムXに従って導出し、暗号アルゴリズムX実行部112に回答値niを回答する(S906)。
【0059】
次に、暗号アルゴリズムP実行部111が、回答値hi及び回答値niに基づき、攻撃アルゴリズムA2実行部106からの問い合わせ値aiに対する回答値biを生成し、回答値biを攻撃アルゴリズムA2実行部106に回答する(S907)。
例えば、攻撃アルゴリズムA2実行部106から暗号文の問い合わせを受けている場合は、暗号アルゴリズムP実行部111は暗号アルゴリズムPにより復号される平文を攻撃アルゴリズムA2実行部106に回答する。
例えば、攻撃アルゴリズムA2実行部106から平文の問い合わせを受けている場合は、暗号アルゴリズムP実行部111は暗号アルゴリズムPにより生成される署名を攻撃アルゴリズムA2実行部106に回答する。
最後に、暗号アルゴリズムP実行部111は、攻撃アルゴリズムA1実行部105が参照できるメモリに、S901〜S906において通信された質問と回答を格納する(S908)。ここで格納された質問及び回答は、図8のS712において攻撃アルゴリズムA1実行部105により参照される。
【0060】
なお、図9では、暗号アルゴリズムP実行部111は、ランダムオラクル(RO)部108へ質問した後に暗号アルゴリズムX実行部112に質問する順序になっているが、質問の順序はこれに限らず、暗号アルゴリズムX実行部112へ質問した後にランダムオラクル(RO)部108に質問してもよい。また、ランダムオラクル(RO)部108と暗号アルゴリズムX実行部112に同時に質問してもよい。また、攻撃アルゴリズムA2実行部106からの問い合わせの度に、ランダムオラクル(RO)部108への質問と暗号アルゴリズムX実行部112への質問の質問順序を変えてもよい。
【0061】
次に、図10について説明する。
攻撃アルゴリズムA2実行部106は、安全性S2を破るための質問ciをランダムオラクル(RO)部108に問い合わせ(S1001)、ランダムオラクル(RO)部108はハッシュリストLを作りつつ、質問ciに対する回答値diを攻撃アルゴリズムA2実行部106に回答する(S1002)。
つまり、ランダムオラクル(RO)部108は、質問ciと組となる値がハッシュリストLにある場合は、組となる値を回答値diとして攻撃アルゴリズムA2実行部106に回答し、質問ciと組となる値がハッシュリストLにない場合は、乱数値を生成し、当該乱数値を回答値diとして攻撃アルゴリズムA2実行部106に回答し、当該乱数値を質問ciと組にしてハッシュリストLに追加する。
【0062】
次に、図11について説明する。
攻撃アルゴリズムA2実行部106は、安全性S2を破るための質問eiを追跡オラクル(TO)部109に問い合わせ(S1001)、追跡オラクル(TO)部109はハッシュリストLを参照して質問eiに対する回答値fiを攻撃アルゴリズムA2実行部106に回答する(S1002)。
つまり、追跡オラクル(TO)部109は、質問eiと組となる値がハッシュリストLにある場合は、組となる値を回答値fiとして攻撃アルゴリズムA2実行部106に回答し、質問eiと組となる値がハッシュリストLにない場合は、組となる値が存在しないことを示す値を回答値fiとして攻撃アルゴリズムA2実行部106に回答する。
【0063】
以上説明したように、本実施の形態によれば、追跡ランダムオラクル(ROT)を用いることにより、MD構造とランダムオラクル圧縮関数(hRO)で構成したハッシュ関数HMD(hRO)を用いた暗号アルゴリズムP(HMD(hRO))の安全性を評価することができる。
前述したように、暗号アルゴリズムP(HMD(hRO))を、ランダムオラクル(RO)を用いた暗号アルゴリズムP(RO)に置き換えた場合に、暗号アルゴリズムP(RO)について安全性が証明されても、ハッシュ関数HMD(hRO)は、ランダムオラクル(RO)とIndifferentiableでないため、暗号アルゴリズムP(HMD(hRO))は安全であるとはいえない。
この点、本実施の形態によれば、ハッシュ関数HMD(hRO)とIndifferentiableである追跡ランダムオラクル(ROT)を用い、追跡ランダムオラクル(ROT)を用いた暗号アルゴリズムP(ROT)の安全性を証明することで、ハッシュ関数HMD(hRO)を用いた暗号アルゴリズムP(HMD(hRO))の安全性を証明することができる。
【0064】
(Indifferentiableであることの証明)
次に、MD構造の圧縮関数にランダムオラクルを用いたハッシュ関数H1は、追跡ランダムオラクル(ROT)とIndifferentiableであることを以下にて証明する。
【0065】
識別者Dは追跡オラクル(TO)に質問をしないとする。
識別者Dがランダムオラクル(RO)またハッシュ関数H1と対話しているときの質問をM、それに対する返信値をzとおくと、識別者Dの質問回答を(IV,M,z)、識別者DがシミュレータSまたは圧縮関数(hRO)と対話しているときの質問を(x,m)、回答をyとおくと、識別者Dの質問回答を(x,m,y)とする。
r[i]を識別者Dのi番目の質問返信値とし、識別者DのviewをV[i]=(r[1],…,r[i])とする。
このとき、V*[i]を以下のように定義する。
・V[i]⊂V*[i]
・(a,b,c),(c,d,e)∈V*[i]⇒(a,b||d,e)∈V*[i]
・(a,b||d,e),(a,b,c)∈V*[i]⇒(c,d,e)∈V*[i]
【0066】
シミュレータSを以下のように構成する。
シミュレータSへのi番目の質問(x[i],m[i])に対して、シミュレータSは以下のような動きをする。
ここで、SV[i]はシミュレータに対するi番目までの質問返答値の集合とする。
SV*[i]はシミュレータSに対する質問返答値に関してV*[i]と同様の定義である。
・もし∃(IV,M,x[i])∈SV*[i−1]ならばy[i]=RO(M||m[i])とし、y[i]を返信する。
・もしx[i]=IVならばy[i]=RO(m[i])とし、y[i]を返信する。
・それ以外は、A=TO(x[i])とし、以下の操作を実行する。
・もしA≠errorならばy[i]=RO(A||m[i])とし、y[i]を返信する。
・それ以外はランダムな値y[i]を選んで、その値を返信する。
【0067】
次にTrivial Queryを定義する。
i番目の質問回答値が以下の条件を満たすときr[i]をtrivial queryと呼ぶことにする。
・r[i]=(IV,M,y[i])かつM=m[1]||…||m[s],かつ
(IV,m[1],y[1]),(y[1],m[2],y[2]),…,(y[s−1],m[s],y[s])∈V*[i−1]、
・r[i]=(y[s−1],m[s],y[s])かつM=m[1]||…||m[s],かつ
(IV,m[1],y[1]),(y[1],m[2],y[2]),…,(y[s−2],m[s−1],y[s−1]),(IV,M,y)∈V*[i−1]
・r[i]∈V[i−1]
上記の質問返信値r[i]は質問しても識別者Dはなにも情報を得ることができないので、識別者Dはtrivial queryをしないとする。
【0068】
Badイベント
Supp(j)={a|∀(a,b,c)∈V[i]}∪{c|∀(a,b,c)∈V[i]}と定義する。このときBadイベントを次のように定義する。識別者Dの全ての質問r[1],...,r[q]に対して、次の性質を満たすj∈{1,...,q}が存在するときBadを真とする。r[j]=(a,b,c)かつc∈{a}∪Supp(i−1)。
E1を識別者Dがハッシュ関数H1とランダムオラクル圧縮関数(RO)と対話しているときにBadが真となるイベントとし、同様にE2を識別者Dが追跡ランダムオラクル(ROT)とシミュレータSと対話しているときにBadが真となるイベントとする。
このときPr[D(ROT,S)⇒1|¬E1]=Pr[D(H1,hRO)⇒1|¬E2]ならば次の不等式が成り立つ。
Adv(D)<2×max{Pr[E1],Pr[E2]}。
この不等式は、
「Indifferentiable Security Analysis of Popular Hash Function with prefix−free padding Donghoon Chang, Sangjin Lee, Mridul Nandi, Moti Yung」
の論文で示されている。
Adv(D)の値が非常に小さければハッシュ関数H1と追跡ランダムオラクル(ROT)はindifferentiableであるといえる。
そのため、Pr[D(ROT,S)⇒1|¬E1]=Pr[D(H1,hRO)⇒1|¬E2]を示し、Pr[E1],Pr[E2]を求める。
【0069】
以下、ランダムオラクル(RO),ランダムオラクル圧縮関数(RO),ハッシュ関数H1,シミュレータSの出力ビット長をnとおく。
【0070】
Pr[D(ROT,S)⇒1|¬E1]=Pr[D(H1,hRO)⇒1|¬E2]の証明:
識別者Dが追跡ランダムオラクル(ROT)、シミュレータSと対話しているとき、E1が真ではないので、識別者Dに帰ってくる返信値は全て異なる。
識別者Dは追跡ランダムオラクル(ROT)の中のランダムオラクル(RO)とシミュレータSと対話する。返信値は全て初での場合はランダムに選ばれる。また、同じ値が存在しないので、返信値は全て独立にランダムに選ばれている。よって、E1が真ではないとき、i番目の返信値は{0,1}^n−{i−1番目までの全ての返信値}からランダムに選ばれる。
識別者Dがハッシュ関数H1,ランダムオラクル圧縮関数(RO)と対話しているとき、E2が真ではないので、識別者Dに帰ってくる返信値は全て異なる。返信値は全てランダムに選ばれ、かつ同じ値が存在しないので、返信値は全て独立にランダムに選ばれる。よって、E1が真ではないとき、i番目の返信値は{0,1}^n−{i−1番目までの全ての返信値}からランダムに選ばれる。
よって、Pr[D(ROT,S)⇒1|¬E1]=Pr[D(H1,hRO)⇒1|¬E2]がなりたつ。
【0071】
Pr[E1]の導出:
先ず初めに、Pr[E1]の値を求める。
E1が真のとき、i番目のランダムオラクル圧縮関数(hRO)の呼び出しで、i−1番目までの入力の和集合と出力の和集合とi番目の入力の和集合の和集合をA[i]、i番目のランダムオラクル圧縮関数(RO)の呼び出し時の出力をb[i]とおくと、b[i]∈A[i]となるような、iが存在する。
よって、q’を圧縮関数の総呼び出し回数、qを識別者Dが質問できる最大回数、lを識別者Dが質問できる最大ブロック長とすると、q’=lqのときq’が最大となる。
よって、Pr[E1]=1−(2^n−1)(2^n−3)...(2^n−2q’+1)/2^{nq’}=O(l^2q^2)/2^n。
次に、Pr[E2]の値を求める。
E2が真のとき、識別者Dはtrivial queryをしないので、識別者Dが受け取る値は全てランダムに選ばれる。
よって、Pr[E2]=1−2^n(2^n−1)...(2^n−q+1)/2^{nq}≦1−(1−q/2^n)^q≦O(q^2/2^n)。
よって、Adv(D)=O(l^2q^2/2^n)となり、この値は非常に小さい値なので、ハッシュ関数H1は追跡ランダムオラクル(ROT)とIndifferentiableである(証明終了)。
【0072】
次に、本実施の形態で説明した内容の概要を以下にて再度述べる。
【0073】
本実施の形態では、質問yに対して、リストの中を見て、yに対応する値がリストの中に存在する場合は、対応する値を返信し、存在しない場合は、存在しないことが分かる値を返信する追跡オラクルを説明した。
【0074】
また、本実施の形態では、追跡オラクルとランダムオラクルから構成される追跡ランダムオラクルを説明した。
ランダムオラクルは、初期状態として空のハッシュリストを持ち、質問xに対して、xがハッシュリストの質問値格納欄にない場合は、それに対応する返信値格納欄の値yを返信し、xがハッシュリストの質問値格納欄に無い場合、固定長の値yをランダムに決め、yを返信し、xを質問値格納欄へ、yを返信値格納欄にそれぞれ記録する。
ここでの追跡オラクルの動作は、追跡オラクルへの質問値yに対して、yがハッシュリストの返信値格納欄にある場合、yに対応する質問値格納欄の値xを返信し、無い場合、無いことが分かる値を返信する。
【0075】
また、本実施の形態では、上記の追跡ランダムオラクルを有する暗号アルゴリズム評価装置を説明した。
【0076】
また、本実施の形態では、
暗号アルゴリズムXと、
追跡ランダムオラクルを用いた暗号アルゴリズムPの安全性S2を条件C2の制約のもとで破る攻撃アルゴリズムA2を用いて攻撃アルゴリズムA1を構成し、アルゴリズムA2の出力結果から、追跡ランダムオラクルを用いた暗号アルゴリズムPが条件C2のもとで安全性S2を満たし、暗号アルゴリズムXが条件C1のもとで安全性S1を満たするかどうかを評価する暗号アルゴリズム評価装置を説明した。
【0077】
また、本実施の形態では、暗号アルゴリズムPをRSA−OAEP暗号、暗号アルゴリズムXをRSA関数(RSAは登録商標)、C1を選択平文攻撃、C2を適応的選択暗号文攻撃、S1をpartial−domain onewayness、S2を識別不可能性とする暗号アルゴリズム評価装置を説明した。
【0078】
最後に、本実施の形態に示した暗号アルゴリズム評価装置100のハードウェア構成例について説明する。
図12は、本実施の形態に示す暗号アルゴリズム評価装置100のハードウェア資源の一例を示す図である。
なお、図12の構成は、あくまでも暗号アルゴリズム評価装置100のハードウェア構成の一例を示すものであり、暗号アルゴリズム評価装置100のハードウェア構成は図12に記載の構成に限らず、他の構成であってもよい。
【0079】
図12において、暗号アルゴリズム評価装置100は、プログラムを実行するCPU911(Central Processing Unit、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう)を備えている。
CPU911は、バス912を介して、例えば、ROM(Read Only Memory)913、RAM(Random Access Memory)914、通信ボード915、表示装置901、キーボード902、マウス903、磁気ディスク装置920と接続され、これらのハードウェアデバイスを制御する。
更に、CPU911は、FDD904(Flexible Disk Drive)、コンパクトディスク装置905(CDD)、プリンタ装置906、スキャナ装置907と接続していてもよい。また、磁気ディスク装置920の代わりに、光ディスク装置、メモリカード(登録商標)読み書き装置などの記憶装置でもよい。
RAM914は、揮発性メモリの一例である。ROM913、FDD904、CDD905、磁気ディスク装置920の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置の一例である。
通信ボード915、キーボード902、マウス903、スキャナ装置907、FDD904などは、入力装置の一例である。
また、通信ボード915、表示装置901、プリンタ装置906などは、出力装置の一例である。
【0080】
通信ボード915は、ネットワークに接続されている。例えば、通信ボード915は、LAN(ローカルエリアネットワーク)、インターネット、WAN(ワイドエリアネットワーク)などに接続されていている。
【0081】
磁気ディスク装置920には、オペレーティングシステム921(OS)、ウィンドウシステム922、プログラム群923、ファイル群924が記憶されている。
プログラム群923のプログラムは、CPU911がオペレーティングシステム921、ウィンドウシステム922を利用しながら実行する。
【0082】
また、RAM914には、CPU911に実行させるオペレーティングシステム921のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。
また、RAM914には、CPU911による処理に必要な各種データが格納される。
【0083】
また、ROM913には、BIOS(Basic Input Output System)プログラムが格納され、磁気ディスク装置920にはブートプログラムが格納されている。
暗号アルゴリズム評価装置100の起動時には、ROM913のBIOSプログラム及び磁気ディスク装置920のブートプログラムが実行され、BIOSプログラム及びブートプログラムによりオペレーティングシステム921が起動される。
【0084】
上記プログラム群923には、本実施の形態の説明において「〜部」として説明している機能を実行するプログラムが記憶されている。プログラムは、CPU911により読み出され実行される。
【0085】
ファイル群924には、本実施の形態の説明において、「〜の判断」、「〜の計算」、「〜の比較」、「〜の評価」、「〜の更新」、「〜の設定」、「〜の登録」、「〜の選択」、「〜の参照」等として説明している処理の結果を示す情報やデータや信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」の各項目として記憶されている。
「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してCPU911によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示などのCPUの動作に用いられる。
抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示のCPUの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリ、レジスタ、キャッシュメモリ、バッファメモリ等に一時的に記憶される。
また、本実施の形態で説明しているフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、RAM914のメモリ、FDD904のフレキシブルディスク、CDD905のコンパクトディスク、磁気ディスク装置920の磁気ディスク、その他光ディスク、ミニディスク、DVD等の記録媒体に記録される。また、データや信号は、バス912や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【0086】
また、本実施の形態の説明において「〜部」として説明しているものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明しているものは、ROM913に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、DVD等の記録媒体に記憶される。プログラムはCPU911により読み出され、CPU911により実行される。すなわち、プログラムは、本実施の形態の「〜部」としてコンピュータを機能させるものである。あるいは、本実施の形態の「〜部」の手順や方法をコンピュータに実行させるものである。
【0087】
このように、本実施の形態に示す暗号アルゴリズム評価装置100は、処理装置たるCPU、記憶装置たるメモリ、磁気ディスク等、入力装置たるキーボード、マウス、通信ボード等、出力装置たる表示装置、通信ボード等を備えるコンピュータであり、上記したように「〜部」として示された機能をこれら処理装置、記憶装置、入力装置、出力装置を用いて実現するものである。
【図面の簡単な説明】
【0088】
【図1】実施の形態1に係る暗号アルゴリズム評価装置の構成例を示す図。
【図2】実施の形態1に係る追跡ランダムオラクルの例を示す図。
【図3】実施の形態1に係る追跡ランダムオラクルの例を示す図。
【図4】実施の形態1に係る追跡ランダムオラクルの例を示す図。
【図5】実施の形態1に係る暗号アルゴリズムの評価原理を示す図。
【図6】実施の形態1に暗号アルゴリズムの評価手順の概要を示す図。
【図7】実施の形態1に係る暗号アルゴリズム評価装置の動作例を示すフローチャート図。
【図8】実施の形態1に係る暗号アルゴリズム評価装置の動作例を示すフローチャート図。
【図9】実施の形態1に係る暗号アルゴリズム評価装置の動作例を示すフローチャート図。
【図10】実施の形態1に係る暗号アルゴリズム評価装置の動作例を示すフローチャート図。
【図11】実施の形態1に係る暗号アルゴリズム評価装置の動作例を示すフローチャート図。
【図12】実施の形態1に係る暗号アルゴリズム評価装置のハードウェア構成例を示す図。
【図13】ランダムオラクルを説明する図。
【図14】ランダムオラクル圧縮関数とMD構造を用いたハッシュ関数を説明する図。
【符号の説明】
【0089】
100 暗号アルゴリズム評価装置、101 情報入力部、102 情報出力部、103 制御部、104 アルゴリズム評価部、105 攻撃アルゴリズムA1実行部、106 攻撃アルゴリズムA2実行部、107 追跡ランダムオラクル(ROT)部、108 ランダムオラクル(RO)部、109 追跡オラクル(TO)部、110 ハッシュリスト記憶部、111 暗号アルゴリズムP実行部、112 暗号アルゴリズムX実行部。

【特許請求の範囲】
【請求項1】
第1の値と乱数値である第2の値の組が一つ以上示される組情報を記憶する組情報記憶部と、
任意の値を第2の値とする問い合わせを受けた際に前記組情報記憶部に記憶されている前記組情報を検索し、当該第2の値と組となる第1の値が前記組情報から抽出できた場合に抽出した第1の値を応答し、当該第2の値と組となる第1の値が前記組情報から抽出できない場合に抽出できないことを示す値を応答する追跡オラクル部を含み、MD(Merkle−Damgaard)構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数とIndifferentiableである追跡ランダムオラクル部と、
MD構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数を用いる、評価対象の暗号アルゴリズムが示される暗号アルゴリズム情報を入力する情報入力部と、
前記追跡ランダムオラクル部を用いて、前記暗号アルゴリズム情報に示されている評価対象暗号アルゴリズムの評価を行うアルゴリズム評価部とを有することを特徴とする情報処理装置。
【請求項2】
前記追跡ランダムオラクル部は、更に、
任意の値を第1の値とする問い合わせを受けた際に前記組情報記憶部に記憶されている前記組情報を検索し、当該第1の値と組となる第2の値が前記組情報から抽出できた場合に抽出した第2の値を応答し、当該第1の値と組となる第2の値が前記組情報から抽出できない場合に乱数値を生成し、生成した乱数値を当該第1の値と組となる第2の値として応答し、当該第1の値と当該第2の値の組を前記組情報に追加して前記組情報記憶部に記憶させるランダムオラクル部を有することを特徴とする請求項1に記載の情報処理装置。
【請求項3】
前記情報入力部は、
前記アルゴリズム評価部における前記評価対象暗号アルゴリズムの評価条件と前記評価対象暗号アルゴリズムに要求される安全性が示される条件情報を入力し、
前記アルゴリズム評価部は、
前記条件情報に示される評価条件のもとで前記条件情報に示される安全性を破る攻撃を前記評価対象暗号アルゴリズムに対してシミュレートして、前記評価対象暗号アルゴリズムを評価することを特徴とする請求項1又は2に記載の情報処理装置。
【請求項4】
前記情報入力部は、
前記評価対象暗号アルゴリズムとともに、前記評価対象暗号アルゴリズムが利用する暗号アルゴリズムが関連暗号アルゴリズムとして示される暗号アルゴリズム情報を入力し、
前記アルゴリズム評価部における前記評価対象暗号アルゴリズムの評価条件と前記評価対象暗号アルゴリズムに要求される安全性と、前記アルゴリズム評価部における前記関連暗号アルゴリズムの評価条件と前記関連暗号アルゴリズムに要求される安全性とが示される条件情報を入力し、
前記アルゴリズム評価部は、
前記条件情報に示される評価条件のもとで前記条件情報に示される安全性を破る攻撃を前記評価対象暗号アルゴリズムに対してシミュレートする第2の攻撃部と、
前記第2の攻撃部による攻撃内容に基づき、前記条件情報に示される評価条件のもとで前記条件情報に示される安全性を破る攻撃を前記関連暗号アルゴリズムに対してシミュレートする第1の攻撃部とを有することを特徴とする請求項1〜3のいずれかに記載の情報処理装置。
【請求項5】
前記第2の攻撃部は、
前記追跡オラクル部に第2の値として任意の値を問い合わせて前記追跡オラクル部から応答値を取得し、前記ランダムオラクル部に第2の値として任意の値を問い合わせて前記ランダムオラクル部から応答値を取得し、問い合わせ内容と応答内容を解析して、前記評価対象暗号アルゴリズムに対する攻撃をシミュレートすることを特徴とする請求項4に記載の情報処理装置。
【請求項6】
前記情報処理装置は、更に、
前記評価対象暗号アルゴリズムを実行する評価対象暗号アルゴリズム実行部を有し、
前記第2の攻撃部は、
所定の問い合わせ値を生成し、生成した問い合わせ値を前記評価対象暗号アルゴリズム実行部に問い合わせて前記評価対象暗号アルゴリズム実行部から対応する応答値を取得して、生成した問い合わせ値と取得した応答値を解析して、前記評価対象暗号アルゴリズムに対する攻撃をシミュレートすることを特徴とする請求項4に記載の情報処理装置。
【請求項7】
前記第1の攻撃部は、
前記条件情報に示されている前記評価対象暗号アルゴリズムの安全性に沿ったデータを生成し、生成したデータを前記第2の攻撃部に出力し、
前記第2の攻撃部は、
前記第1の攻撃部からデータを入力し、
前記追跡オラクル部、前記ランダムオラクル部及び前記評価対象暗号アルゴリズム実行部へ問い合わせを行い、問い合わせに対する応答を取得し、問い合わせ内容と応答内容を解析して、前記第1の攻撃部から入力したデータについて、前記条件情報に示されている前記評価対象暗号アルゴリズムの安全性を破ることを特徴とする請求項6に記載の情報処理装置。
【請求項8】
前記第1の攻撃部は、
前記条件情報に示されている前記評価対象暗号アルゴリズムの安全性に沿ったデータとして、2つ以上の平文を生成するとともに、前記評価対象暗号アルゴリズムにより各々の平文の暗号文を生成し、生成した2つ以上の平文と、生成した2つ以上の暗号文のうちのいずれか1つの暗号文を前記第2の攻撃部に出力し、
前記第2の攻撃部は、
前記第1の攻撃部から2つ以上の平文と、1つの暗号文を入力し、
前記追跡オラクル部、前記ランダムオラクル部及び前記評価対象暗号アルゴリズム実行部へ問い合わせを行い、問い合わせに対する応答を取得し、問い合わせ内容と応答内容を解析して、前記第1の攻撃部から入力した暗号文に対応する平文がいずれであるかを識別することを特徴とする請求項7に記載の情報処理装置。
【請求項9】
前記第1の攻撃部は、
前記条件情報に示されている前記評価対象暗号アルゴリズムの安全性に沿ったデータとして、文書データを生成し、生成した文書データを前記第2の攻撃部に出力し、
前記第2の攻撃部は、
前記第1の攻撃部から文書データを入力し、
前記追跡オラクル部、前記ランダムオラクル部及び前記評価対象暗号アルゴリズム実行部へ問い合わせを行い、問い合わせに対する応答を取得し、問い合わせ内容と応答内容を解析して、前記評価対象暗号アルゴリズムに対応させて前記文書データの電子署名を生成することを特徴とする請求項7に記載の情報処理装置。
【請求項10】
前記情報処理装置は、更に、
前記関連暗号アルゴリズムを実行する関連暗号アルゴリズム実行部を有し、
前記評価対象暗号アルゴリズム実行部は、
前記第2の攻撃部から問い合わせ値の問い合わせを受けた場合に、問い合わせを受けた問い合わせ値に基づき所定の値を前記ランダムオラクル部に第2の値として問い合わせて前記ランダムオラクル部から応答値を取得するとともに、問い合わせを受けた問い合わせ値に基づき所定の値を前記関連暗号アルゴリズム実行部に問い合わせて前記関連暗号アルゴリズム実行部から応答値を取得し、前記ランダムオラクル部からの応答値及び前記関連暗号アルゴリズム実行部からの応答値を解析して、前記第2の攻撃部から問い合わせのあった問い合わせに対する応答値を生成することを特徴とする請求項6〜9のいずれかに記載の情報処理装置。
【請求項11】
前記第1の攻撃部は、
前記第2の攻撃部から前記追跡オラクル部、前記ランダムオラクル部及び前記評価対象暗号アルゴリズム実行部への問い合せ内容、問い合わせに対する前記追跡オラクル部、前記ランダムオラクル部及び前記評価対象暗号アルゴリズム実行部から前記第2の攻撃部への応答内容、前記評価対象暗号アルゴリズム実行部から前記ランダムオラクル部及び前記関連暗号アルゴリズム実行部への問い合わせ内容、及び前記ランダムオラクル部及び前記関連暗号アルゴリズム実行部から前記評価対象暗号アルゴリズム実行部への応答内容のうちの少なくともいずれかを解析して、前記関連暗号アルゴリズムに対する攻撃をシミュレートすることを特徴とする請求項10に記載の情報処理装置。
【請求項12】
前記アルゴリズム評価部は、
前記第2の攻撃部が前記評価対象暗号アルゴリズムに対する攻撃のシミュレーションにおいて前記条件情報に示される評価条件のもとで前記条件情報に示される安全性を破り、前記第1の攻撃部が前記関連暗号アルゴリズムに対する攻撃のシミュレーションにおいて前記条件情報に示される評価条件のもとで前記条件情報に示される安全性を破った場合に、
前記評価対象暗号アルゴリズムが、前記条件情報に示される評価条件のもとで前記条件情報に示される安全性を満たすと評価することを特徴とする請求項4〜11のいずれかに記載の情報処理装置。
【請求項13】
前記関連暗号アルゴリズムは、第1の評価条件のもとで第1の安全性を満たすものであり、
前記情報入力部は、
前記関連暗号アルゴリズムの評価条件として前記第1の評価条件が示され、前記関連暗号アルゴリズムの安全性として前記第1の安全性が示され、前記評価対象暗号アルゴリズムの評価条件として第2の評価条件が示され、前記評価対象暗号アルゴリズムの安全性として第2の安全性が示される条件情報を入力し、
前記第2の攻撃部は、
前記第2の評価条件のもとで前記第2の安全性を破る攻撃を前記評価対象暗号アルゴリズムに対してシミュレートし、
前記第1の攻撃部は、
前記第2の攻撃部による攻撃内容に基づき、前記第1の評価条件のもとで前記第1の安全性を破る攻撃を前記関連暗号アルゴリズムに対してシミュレートし、
前記アルゴリズム評価部は、
前記第2の攻撃部が前記評価対象暗号アルゴリズムに対する攻撃のシミュレーションにおいて前記第2の評価条件のもとで前記第2の安全性を破り、前記第1の攻撃部が前記関連暗号アルゴリズムに対する攻撃のシミュレーションにおいて前記第1の評価条件のもとで前記第1の安全性を破った場合に、
前記関連暗号アルゴリズムが前記第1の評価条件のもとで前記第1の安全性を満たせば前記評価対象暗号アルゴリズムが前記第2の評価条件のもとで前記第2の安全性を満たすという命題に対する対偶である前記第2の評価条件のもとで前記評価対象暗号アルゴリズムの前記第2の安全性が破られれば前記第1の評価条件のもとで前記関連暗号アルゴリズムの前記第1の安全性が破られることが証明され、対偶の証明により前記命題が証明され、前記関連暗号アルゴリズムは前記第1の評価条件のもとで前記第1の安全性を満たすものであることから、前記評価対象暗号アルゴリズムが、前記第2の評価条件のもとで前記第2の安全性を満たすと評価することを特徴とする請求項12に記載の情報処理装置。
【請求項14】
第1の値と乱数値である第2の値の組が一つ以上示される組情報を記憶するコンピュータが行う暗号アルゴリズム評価方法であって、
前記コンピュータが、MD(Merkle−Damgaard)構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数を用いる、評価対象の暗号アルゴリズムが示される暗号アルゴリズム情報を入力する情報入力ステップと、
任意の値を第2の値とする問い合わせを受けた際に、前記組情報を検索し、当該第2の値と組となる第1の値が前記組情報から抽出できた場合に抽出した第1の値を応答し、当該第2の値と組となる第1の値が前記組情報から抽出できない場合に抽出できないことを示す値を応答する追跡オラクルが含まれ、MD構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数とIndifferentiableである追跡ランダムオラクルを前記コンピュータが実行する追跡ランダムオラクル実行ステップと、
前記コンピュータが、前記追跡ランダムオラクル実行ステップでの実行結果を用いて、前記暗号アルゴリズム情報に示されている評価対象暗号アルゴリズムの評価を行うアルゴリズム評価ステップとを有することを特徴とする暗号アルゴリズム評価方法。
【請求項15】
前記追跡ランダムオラクル実行ステップは、
任意の値を第1の値とする問い合わせを受けた際に前記組情報を検索し、当該第1の値と組となる第2の値が前記組情報から抽出できた場合に抽出した第2の値を応答し、当該第1の値と組となる第2の値が前記組情報から抽出できない場合に乱数値を生成し、生成した乱数値を当該第1の値と組となる第2の値として応答し、当該第1の値と当該第2の値の組を前記組情報に追加して記憶させるランダムオラクルが含まれる追跡ランダムオラクルを前記コンピュータが実行することを特徴とする請求項14に記載の暗号アルゴリズム評価方法。
【請求項16】
前記情報入力ステップは、
前記コンピュータが、前記評価対象暗号アルゴリズムの評価条件と前記評価対象暗号アルゴリズムに要求される安全性が示される条件情報を入力し、
前記アルゴリズム評価ステップは、
前記コンピュータが、前記条件情報に示される評価条件のもとで前記条件情報に示される安全性を破る攻撃を前記評価対象暗号アルゴリズムに対してシミュレートして、前記評価対象暗号アルゴリズムを評価することを特徴とする請求項14又は15に記載の暗号アルゴリズム評価方法。
【請求項17】
第1の値と乱数値である第2の値の組が一つ以上示される組情報を記憶するコンピュータに、
MD(Merkle−Damgaard)構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数を用いる、評価対象の暗号アルゴリズムが示される暗号アルゴリズム情報を入力する情報入力処理と、
任意の値を第2の値とする問い合わせを受けた際に、前記組情報を検索し、当該第2の値と組となる第1の値が前記組情報から抽出できた場合に抽出した第1の値を応答し、当該第2の値と組となる第1の値が前記組情報から抽出できない場合に抽出できないことを示す値を応答する追跡オラクルが含まれ、MD構造の複数の圧縮関数の各々をランダムオラクルとするハッシュ関数とIndifferentiableである追跡ランダムオラクルを実行する追跡ランダムオラクル実行処理と、
前記追跡ランダムオラクル実行処理での実行結果を用いて、前記暗号アルゴリズム情報に示されている評価対象暗号アルゴリズムの評価を行うアルゴリズム評価処理とを実行させることを特徴とするプログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate