ハッシュ値演算装置、方法、プログラム及びその記録媒体
【課題】攻撃を受けているかどうかをより少ない記憶領域で実現する。
【解決手段】入力されたビット列に対応するハッシュ値を演算する演算部２と、攻撃を受けている可能性が高い場合に上記演算部でハッシュ値を演算する過程で生じるビット列が満たす条件を記憶するパターン記憶部４と、上記演算部でハッシュ値を演算する過程で生じたビット列が、上記パターン記憶部から読み込んだ条件を満たすか判断して、条件を満たす場合には攻撃を受けていると判断する判断部１とを含む。
【解決手段】入力されたビット列に対応するハッシュ値を演算する演算部２と、攻撃を受けている可能性が高い場合に上記演算部でハッシュ値を演算する過程で生じるビット列が満たす条件を記憶するパターン記憶部４と、上記演算部でハッシュ値を演算する過程で生じたビット列が、上記パターン記憶部から読み込んだ条件を満たすか判断して、条件を満たす場合には攻撃を受けていると判断する判断部１とを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号学的ハッシュ関数（以下、単にハッシュ関数と呼ぶ。）に対するショートカット攻撃を検出する技術に関する。
【背景技術】
【０００２】
ハッシュ関数Ｈは、任意の長さのビット列を入力して、固定長のビット列を出力する関数である。ハッシュ関数Ｈは、少なくとも次の２つの性質を満たす場合に安全と呼ばれる。
【０００３】
１．衝突困難性 Ｈ（ｘ）＝Ｈ（ｘ’）となるｘ，ｘ’（≠ｘ）を見つけることが演算量的に困難
２．一方向性 与えられたｙに対してｙ＝Ｈ（ｘ）となるｘを見つけることが演算量的に困難
【０００４】
ハッシュ関数Ｈの出力値のビット数をｎとする。このとき、誕生日の逆理により、どのようなハッシュ関数Ｈに対しても、ランダムな入力ｘを２ｎ／２程度生成しそれぞれの入力ｘに対してハッシュ値Ｈ（ｘ）を演算すれば、Ｈ（ｘ）＝Ｈ（ｘ’）となるｘ，ｘ’（≠ｘ）を高い確率で見つけることができ、衝突困難性を破ることができる。また、ランダムな入力ｘを２ｎ程度生成しそれぞれの入力ｘに対してハッシュ値Ｈ（ｘ）を演算すれば、与えられたｙに対してｙ＝Ｈ（ｘ）となるｘを高い確率で見つけることができ、一方向性を破ることができる。
【０００５】
一般に、ｎは十分大きな値であり、ハッシュ関数ＨがＭＤ５の場合にはｎ＝１２８ビットである。したがって、２ｎ／２及び２ｎは一般に膨大な数となる。「演算量的に困難」とは、上記のように、衝突困難性を破るためにはハッシュ値Ｈ（ｘ）を２ｎ／２回程度演算する必要があることを意味し、一方向性を破るためにはハッシュ値Ｈ（ｘ）を２ｎ回程度演算する必要があることを意味する。
【０００６】
これに対して、２ｎ／２回以下のハッシュ値Ｈ（ｘ）の演算よりも少ない演算量で衝突困難性を破る手法や、２ｎ回以下のハッシュ値Ｈ（ｘ）の演算よりも少ない演算量で一方向性を破る手法がある場合、これらの手法をショートカット攻撃と呼ぶ。
【０００７】
ハッシュ関数の具体例として、ＭＤ４、ＭＤ５、ＳＨＡ−１、ＳＨＡ−２等が知られている。ＭＤ４、ＭＤ５、ＳＨＡ−１については、暗号解析技術の進歩によりショートカット攻撃が知られており安全ではなくなっている。しかし、これらのハッシュ関数は現在も多くのシステムで使われている。例えば電子メールをサーバから受信するための認証プロトコルＡＰＯＰではＭＤ５が使われている。
【０００８】
ＭＤ５の衝突困難性を破るショートカット攻撃によりＡＰＯＰで用いられるパスワードを復元する技術が非特許文献１に記載されている。また、この非特許文献１に記載された攻撃を検出する技術が非特許文献２に記載されている。非特許文献２では、攻撃を完全に検出するためにはＭＤ５の過去の演算結果を全て記憶しておき、ＭＤ５の演算を行う度に、そのＭＤ５の演算結果とこれまでに演算したＭＤ５の各演算結果とが一致するかどうかを判定し、一致すれば攻撃を受けていると判断する。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Yu Sasaki, Lei Wang, Kazuo Ohata, Noboru Kunihiro, “Security of MD5 Challenge and Response: APOP Password Recovery Attack”, CT-RSA2008, 2008
【非特許文献２】奥秋清次，坂井祐介，太田和夫、國廣昇，「ＡＰＯＰ攻撃検知法の提案とシミュレーションによる検証：目には目を，歯には歯を」，ＳＣＩＳ２００９，２００９
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、非特許文献２に記載された技術では、攻撃を完全に検出するためにはＭＤ５の過去の演算結果を全て記憶しておくため膨大な記憶領域が必要であるというという課題がある。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、この発明は、攻撃を受けている可能性が高い場合にハッシュ値を演算する過程で生じるビット列が満たす条件をパターン記憶部に記憶しておき、ハッシュ値を演算する過程で生じたビット列が上記パターン記憶部から読み出した条件を満たすか判断して、その条件を満たせば攻撃を受けていると判断する。
【発明の効果】
【００１２】
攻撃を受けている可能性が高い場合にハッシュ値を演算する過程で生じるビット列が満たす条件を記憶しておけば足り、ＭＤ５の過去の演算結果の全てを記憶しておく必要はない。したがって、必要な記憶領域を削減することができる。
【図面の簡単な説明】
【００１３】
【図１】ハッシュ値演算装置の例の機能ブロック図。
【図２】演算部の例の機能ブロック図。
【図３】ハッシュ値演算方法のフローチャートを例示する図。
【図４】攻撃ビット条件を例示する図。
【図５】攻撃ビット条件を例示する図。
【発明を実施するための形態】
【００１４】
以下、この発明の実施の形態について、詳細に説明する。
図１にハッシュ値演算装置の機能ブロック図を例示する。図３にハッシュ値演算方法のフローチャートを例示する。
【００１５】
パターン記憶部４には、攻撃を受けている可能性が高い場合にハッシュ値を演算する過程で生じるビット列が満たす条件（以下、攻撃ビット条件する。）が記憶されている。攻撃ビット条件は、用いるハッシュ関数Ｈや攻撃方法により異なる。攻撃ビット条件の具体例については後述する。
【００１６】
ビット列ｘは、演算部２に入力される。必要に応じて、判断部１にも入力される。
【００１７】
図１に、演算部２の機能ブロック図を例示する。演算部２のハッシュ値演算部２１は、入力されたビット列ｘをハッシュ関数Ｈに入力することによりハッシュ値Ｈ（ｘ）を演算する（ステップＳ１）。一般に、ハッシュ値Ｈ（ｘ）の演算は複数のステップから成り立っており、最終的なハッシュ値を演算するまでの各ステップにおいて中間演算結果であるビット列が生じる。このハッシュ値Ｈ（ｘ）を演算する過程で生じたビット列は、判断部１に送られる。
【００１８】
ハッシュ値Ｈ（ｘ）を演算する過程で生じたビット列は一般に複数存在する。複数存在するビット列の中で、後述する判断部１が攻撃の有無の判断のために用いるビット列が少なくとも判断部１に送られる。この段階ではハッシュ値Ｈ（ｘ）の演算は必ずしも最後まで行われる必要はない。少なくとも判断部１が攻撃の有無の判断のために用いるビット列が得られるステップまでハッシュ値Ｈ（ｘ）の演算を行えば足りる。
【００１９】
判断部１は、ハッシュ値Ｈ（ｘ）を演算する過程で生じたビット列が、パターン記憶部４から読み出した、そのビット列に対応する攻撃ビット条件を満たすか判断する（ステップＳ２）。
【００２０】
攻撃ビット条件を満たさない場合には、攻撃を受けていないと判断して、ハッシュ値演算装置は演算されたハッシュ値Ｈ（ｘ）を、入力されたビット列ｘに対応する出力値ｙとして出力する（ステップＳ３）。ステップＳ１において、ハッシュ値Ｈ（ｘ）を最後まで演算していない場合には、攻撃を受けていないとステップＳ２において判断された後に、ハッシュ値Ｈ（ｘ）を最後まで演算して出力する。
【００２１】
攻撃ビット条件を満たす場合には、攻撃を受けていると判断する。攻撃を受けていると判断された場合、攻撃を受けている旨の判断結果が警告部３に送られて、警告部３は攻撃を受けている旨の警告情報を出力する（ステップＳ４）。
【００２２】
攻撃を受けているかどうかを判断するために考慮すべきビット列が複数ある場合には、判断部１はこれらのビット列の全部又は一部のそれぞれが、パターン記憶部４から読み出した対応する攻撃ビット条件が満たすかどうかを判断する。判断部１は、これらのビット列の全部又は一部のそれぞれが対応する攻撃ビット条件を満たす場合には、攻撃を受けていると判断する。
【００２３】
ハッシュ関数の中にはいわゆるマークル・ダンガード構造で構成されているものがある。これは、入力されたビット列ｘをｘ＝ｘ０‖ｘ１‖…‖ｘＬ−１とＬ個のビット列に分割し、ＩＶ（Ｉｎｉｔｉａｌ Ｖａｌｕｅ）を定数とし、ｙ０＝ＩＶとし、ｉ＝１，…，Ｌ−１として、ｙｉ＋１＝ｈ（ｙｉ，ｘｉ）の演算を順次繰り返すことにより得たｙＬを入力されたビット列ｘに対するハッシュ値とするものである。
【００２４】
ｙ０＝ＩＶ
ｙｉ＋１＝ｈ（ｙｉ，ｘｉ），ｉ＝１，…，Ｌ−１
ハッシュ関数がこのマークル・ダンガード構造で構成されている場合には、入力されたビット列ｘに対応するハッシュ値Ｈ（ｘ）を演算する過程で生じるビット列の内、あるｈ（ｙｉ，ｘｉ）（演算量を削減するためにｉは小さい方が望ましい。）を演算する過程で生じるビット列を、攻撃を受けているかどうかを判断するために考慮すべきビット列としてもよい。また、各ｈ（ｙｉ，ｘｉ）（ｉ＝１，…，Ｌ−１）を演算する過程で生じるビット列を、攻撃を受けているかどうかを判断するために考慮すべきビット列としてもよい。攻撃を受けているかどうかを判断するために考慮すべきビット列が多くなるほど、攻撃を検出することができる確率が上がる。
【００２５】
従来はＭＤ５の演算結果の全てを記憶しておく必要があったが、この発明においては攻撃ビット条件を記憶しておけば足り、必要な記憶領域を削減することができる。
【００２６】
［変形例等］
ステップＳ２において、ハッシュ値Ｈ（ｘ）を演算する過程で生じたビット列が対応する攻撃ビット条件を満たしており、攻撃を受けていると判断することができる場合に、ハッシュ値Ｈ（ｘ）とは異なる値を入力ビット列ｘに対応する出力値ｙとして出力してもよい。
【００２７】
例えば、ハッシュ値Ｈ（ｘ）とは異なる関数の値Ｄ（ｘ）を演算して、入力ビット列ｘに対応する出力値ｙとしてＤ（ｘ）を出力してもよい（ステップＳ５、図３）。また、ハッシュ値Ｈ（ｘ）とは異なる関数の値Ｄ（ｘ）（ｘ≠Ｄ（ｘ）となるＤ（ｘ））を用いて、Ｈ（Ｄ（ｘ））を演算して、入力ビット列ｘに対応する出力値ｙとしてＨ（Ｄ（ｘ））を出力してもよい（ステップＳ６）。もちろん、Ｈ（Ｈ（ｘ））を入力ビット列ｘに対応する出力値ｙとしてもよい。
【００２８】
Ｄ（ｘ）として、安全な乱数を生成する関数を採用できる。この場合、演算部２に乱数生成部２２（図２）を設けて、この乱数生成部２２が安全な乱数を生成する。生成された乱数を出力値ｙとして出力してもよいし（ステップＳ５）、ハッシュ値演算部２１が生成された乱数ｒに対応するハッシュ値Ｈ（ｒ）を演算して出力値ｙとして出力してもよい（ステップＳ６）
また、ハッシュ関数Ｈ（ｘ）がパラメータに応じて出力する値が異なるハッシュ関数である場合には、パラメータを変更した関数をＤ（ｘ）としてもよい。例えば、ハッシュ関数としてＭＤ５を用いる場合には、いわゆるＩＶ（Ｉｎｉｔｉａｌ Ｖａｌｕｅ）を変更した関数をＤ（ｘ）としてもよい。
【００２９】
パラメータＰ１に基づくハッシュ関数をＨ（ｘ）、パラメータＰ２に基づくハッシュ関数をＤ（ｘ）とする。ステップＳ２において攻撃を受けていないと判断された場合には、演算部２のハッシュ値演算部２１はハッシュ値Ｈ（ｘ）を演算する（ステップＳ３）。ステップＳ２において攻撃を受けていると判断された場合には、パラメータ変更部２３はハッシュ値演算部２１が用いるハッシュ関数のパラメータをＰ２に変更する。ハッシュ値演算部２１は、ハッシュ値Ｄ（ｘ）を演算して出力値ｙとして出力する（ステップＳ５）。また、ハッシュ値演算部２４が、演算されたＤ（ｘ）を用いてＨ（Ｄ（ｘ））を演算して出力値ｙとして出力してもよい（ステップＳ６）。
【００３０】
さらに、Ｄ（ｘ）として、ハッシュ関数Ｈ（ｘ）とは異なる安全なハッシュ関数を用いてもよい。安全なハッシュ関数とは現段階では例えばＳＨＡ−２である。この場合、ステップＳ２において攻撃を受けていると判断された場合には、ハッシュ値演算部２１がＤ（ｘ）を演算して出力値ｙとして出力する（ステップＳ５）。また、ハッシュ値演算部２４が、演算されたＤ（ｘ）を用いてＨ（Ｄ（ｘ））を演算して出力値ｙとして出力してもよい。
【００３１】
パターン記憶部４に記憶される、攻撃を受けている可能性が高い場合に演算部２でハッシュ値を演算する過程で生じるビット列が満たす条件を更新するパターン更新部５を設けてもよい。ハッシュ関数に対するショートカット攻撃は日々開発されている。新たに開発されたショートカット攻撃を受けている可能性が高い場合に演算部２でハッシュ値を演算するビット列が満たす条件をパターン記憶部４に追加することにより、その新たに開発されたショートカット攻撃に対応することができる。
【００３２】
上記の例ではハッシュ値を演算する過程で生じたビット列が攻撃ビット条件を満たすかどうかにより攻撃の有無を判断したが、さらに入力されたビット列ｘがパターン記憶部２に記憶された対応する攻撃ビット条件を満たすかどうかにより攻撃の有無を判断してもよい。
【００３３】
［攻撃ビット条件の具体例１］
ハッシュ関数Ｈ（ｘ）としてＭＤ５を用いた場合の攻撃ビット条件の具体例１について説明する。この具体例１は、参考文献１に記載されたＭＤ５の衝突困難性に対するショートカット攻撃に基づくものである。
【００３４】
〔参考文献１〕Xiaoyun Wang, Hongbo Yu, “How to Break MD5 and Other Hash Functions”, Advances in Cryptology, EUROCRYPT 2005, Volume 3494 of Lecture Notes in Computer Science, pp.19-35. Springer-Verlag, Berlin, Heidelberg, New York, 2005.
まず、ＭＤ５について説明する。ＭＤ５の詳細は参考文献２を参照のこと。
【００３５】
〔参考文献２〕R. L. Rivest. Request for Comments 1321: The MD5 Message Digest
Algorithm. The Internet Engineering Task Force, 1992., http://www.ietf.org/rfc/rfc1321.txt
入力されたビット列ｘはパディング処理が施されて５１２ビットの倍数のビット列Ｍとなる。パティングは「ｘ‖１‖０‖０‖…‖０‖ｘのビット長」となるように施される。ｘのビット長は６４ビットで表示され、０はＭが５１２ビットの倍数となるように適切な数だけ追加される。Ｍを以下のように表記する。Ｍｉ（ｉ＝０，１，…，ｔ−１）は５１２ビットのビット列である。
【００３６】
Ｍ＝（Ｍ０，Ｍ１，…，Ｍｔ−１）
ＭＤ５の圧縮関数をｆとして、Ｈｉ（ｉ＝０，１，…，ｔ）を１２８ビットのビット列とし、Ｈ０をＩＶ（Ｉｎｉｔｉａｌ Ｖａｌｕｅ）として、Ｈｉ及びＭｉを圧縮関数ｆに入力してＨｉ＋１を順次求める。最後に求まったＨｔがＭＤ５のハッシュ値となる。ＩＶは例えば0123456789abcdeffedcba9876543210（１６進数表記）である。
【００３７】
Ｈ０＝ＩＶ
Ｈｉ＋１＝ｆ（Ｈｉ，Ｍｉ） ０≦ｉ≦ｔ−１
圧縮関数ｆ（Ｈｉ，Ｍｉ）について説明する。５１２ビットの入力Ｍｉは１６個の３２ビットのワードに分割される。
【００３８】
Ｍｉ＝（ｍ０，ｍ１，…，ｍ１５）
また、１２８ビットの入力Ｈｉも４個の３２ビットのワードに分割される。
【００３９】
Ｈｉ＝（ａｉ，ｂｉ，ｃｉ，ｄｉ）
３２ビットのワードに解釈される場合には常にリトルエンディアン（little endian）で解釈される。つまり、例えばａ０＝67452301（１６進数表記）となる。
【００４０】
まず、以下の４つの式の演算がｉ＝０，４，…，６０に対して順に施される。これにより、（ａ１，ｂ１，ｃ１，ｄ１），（ａ２，ｂ２，ｃ２，ｄ２），…，（ａ１６，ｂ１６，ｃ１６，ｄ１６）が順次演算される。
【００４１】
a1+i/4 = bi/4 + ((ai/4 + Φi(bi/4,ci/4,di/4) + wi + ti) <<< si)
d1+i/4 = ai/4 + ((di/4 + Φi(ai/4,bi/4,ci/4) + wi+1 + ti+1) <<< si+1)
c1+i/4 = di/4 + ((ci/4 + Φi(di/4,ai/4,bi/4) + wi+2 + ti+2) <<< si+2)
b1+i/4 = ci/4 + ((bi/4 + Φi(ci/4,di/4,ai/4) + wi+3 + ti+3) <<< si+3)
ここで「+」はｍｏｄ２３２の加算であり、Ｘ<<<ＹはＸを左Ｙビット巡回シフトすることを示す。また、ｗｉ＝ｍπ（ｉ）であり、π（ｉ）は次の通りである。
【００４２】
【数１】
【００４３】
また、ｔｉ（ｉ＝０，１，…，６３）を次のように定める。一番左上がｔ０であり、ｔｉの右がｔｉ＋１であり、ｔｉの下がｔｉ＋８であり、ｔｉを１６進数で表記している。
【００４４】
【数２】
【００４５】
また、ｓｉを次のように定める
【数３】
さらに、Φｉを次のように定める。ここで、∧、∨、○の中に＋の記号はそれぞれ論理積、論理和、排他的論理和を表し、上付きバーはビットごとの反転を表す。
【００４６】
【数４】
最後に、Ｈｉ＝（ａ０，ｂ０，ｃ０，ｄ０）に（ａ１６，ｂ１６，ｃ１６，ｄ１６）を足したものをＨｉ＋１とし、これが圧縮関数ｆ（Ｈｉ，Ｍｉ）の出力となる。
【００４７】
Hi+1 = (a0 + a16, b0 + b16, c0 + c16, d0 + d16)
このとき、攻撃ビット条件は図４及び図５に例示される。ｉ＝０，１，…，ｔ−１、例えばｉ＝０として、図４はＨｉ＋１＝ｆ（Ｈｉ，Ｍｉ）を演算するときに生じるビット列ａｊ，ｂｊ，ｃｊ，ｄｊについての攻撃ビット条件を例示し、図５はＨｉ＋２＝ｆ（Ｈｉ＋１，Ｍｉ＋１）を演算するときに生じるビット列ａｊ，ｂｊ，ｃｊ，ｄｊについての攻撃ビット条件を例示している。ａｉ，ｊはビット列ａｉの右からｊ番目のビットを意味する。ｂｉ，ｊ，ｃｉ，ｊ，ｄｉ，ｊについても同様である。
【００４８】
この例ではこのように判断部１が攻撃の有無の判断のために用いるビット列が複数ある。ハッシュ値を演算する過程で生じたビット列が図４及び図５に示す攻撃ビット条件のすべてを満たす場合には、攻撃が行われていると判断することができる。しかし、攻撃の有無の判断処理を軽減するために、これらの攻撃ビット条件の一部を満たす場合には、攻撃が行われている可能性が高いため、攻撃が行われていると判断してもよい。
【００４９】
なお、参考文献１では、入力されたビット列ｘに対応するハッシュ値と、入力されたビット列ｘを予め定められた量Δｘだけ変化させたビット列ｘ＋Δｘに対応するハッシュ値とを同じ値にしようとしている。したがって、入力されたビット列ｘに対応するハッシュ値を演算する過程で生じるビット列が攻撃ビット条件を満たすかどうかを判断する代わりに、ビット列ｘ＋Δｘに対応するハッシュ値を演算する過程で生じるビット列が上記と同じ攻撃ビット条件を満たすかどうかを判断することにより、攻撃の有無を判断することができる。
【００５０】
ｘ＋Δｘをパディングして５１２ビットの倍数のビット列Ｍ’を取得して、これを５１２ビットごとに分割する。Ｍｉ’（ｉ＝０，１，…，ｔ−１）は５１２ビットのビット列である。
【００５１】
Ｍ’＝（Ｍ０’，Ｍ１’，…，Ｍｔ−１’）
ΔＭ０＝Ｍ０’−Ｍ０、ΔＭ１＝Ｍ１’−Ｍ１として、ΔＭ０及びΔＭ１は以下の条件を満たす。ΔＭ０及びΔＭ１が以下の条件を満たすようにΔｘが決められる。
【００５２】
ΔＭ０＝（0,0,0,0,231,0,0,0,0,0,0,215,0,0,231,0）
ΔＭ１＝（0,0,0,0,231,0,0,0,0,0,0,-215,0,0,231,0）
このとき、Ｈ１＝ｆ（Ｈ０，Ｍ０’）を演算するときに生じるビット列ａｊ，ｂｊ，ｃｊ，ｄｊが図４に例示した攻撃ビット条件の全部又は一部を満たし、Ｈ２＝ｆ（Ｈ１，Ｍ１’）を演算するときに生じるビット列ａｊ，ｂｊ，ｃｊ，ｄｊが図５に例示した攻撃ビット条件の全部又は一部を満たす場合に、攻撃が行われていると判断してもよい。
【００５３】
［攻撃ビット条件の具体例２］
ハッシュ関数Ｈ（ｘ）として４−ｐａｓｓ ＨＡＶＡＬの２５６ビットハッシュ値を用いた場合の攻撃ビット条件の具体例２について説明する。この具体例２は、参考文献３に記載された４−ｐａｓｓ ＨＡＶＡＬに対するショートカット攻撃に基づくものである。
【００５４】
〔参考文献３〕Y. Sasaki and K. Aoki, “Preimage Attacks on 3, 4, and 5-pass HAVAL”, In J. Pieprzyk, editor, Advances in Cryptology-ASIACRYPT 2008, Volume 5350 of Lecture Notes in Computer Science, pp.253-271. Springer-Verlag, Berlin, Heidelberg, New York, 2008.
まず、４−ｐａｓｓ ＨＡＶＡＬについて説明する。
【００５５】
入力されたビット列ｘはパディング処理が施されて１０２４ビットの倍数のビット列Ｍとなる。Ｍを以下のように表記する。Ｍｉ（ｉ＝０，１，…，ｔ−１）は１０２４ビットのビット列である。
【００５６】
Ｍ＝（Ｍ０，Ｍ１，…，Ｍｔ−１）
ＨＡＶＡＬの圧縮関数として、Ｈｉ（ｉ＝０，１，…，ｔ）を２５６ビットのビット列とし、Ｈ０をＩＶ（Ｉｎｉｔｉａｌ Ｖａｌｕｅ）として、Ｈｉ及びＭｉを圧縮関数ｆに入力してＨｉ＋１を順次求める。最後に求まったＨｔがＨＡＶＡＬのハッシュ値となる。ＩＶは予め定められた定数である。
【００５７】
Ｈ０＝ＩＶ
Ｈｉ＋１＝ｆ（Ｈｉ，Ｍｉ） ０≦ｉ≦ｔ−１
圧縮関数ｆ（Ｈｉ，Ｍｉ）について説明する。１０２４ビットの入力Ｍｉは３２個の３２ビットのワードに分割される。
【００５８】
Ｍｉ＝（ｍ０，ｍ１，…，ｍ１５）
ｐ０＝Ｈｉとして、ｊ＝０，１，…，ｋ（ｋ＝１２７）に対して順次ｐｊ＋１＝Ｒｊ（ｐｊ，ｍπ（ｊ））が計算されて、最終的にｐｋが計算される。計算されたｐｋにＨｉを加算したものをｆ（Ｈｉ，Ｍ）の出力値であるＨｉ＋１とする。
【００５９】
関数π（ｊ）は、次の通りである。左上がπ（０）であり、あるπ（ｊ）の右がπ（ｊ＋１）であり、あるπ（ｊ）の下がπ（ｊ＋３２）である。
【００６０】
【数５】
次に、関数Ｒｊ（ｐｊ，ｍπ（ｊ））について説明する。Ｑｊは３２ビットのビット列であり、次の関係を満たすとする。
【００６１】
ｐｊ＝（Ｑｊ−７‖Ｑｊ−６‖Ｑｊ−５‖Ｑｊ−４‖Ｑｊ−３‖Ｑｊ−２‖Ｑｊ−１‖Ｑｊ）
このとき関数Ｒｊ（ｐｊ，ｍπ（ｊ））は次のように定義される。
【００６２】
Ｔ＝ｆｊ・φ４，└ｊ／３２┘＋１（Ｑｊ−６，Ｑｊ−５，Ｑｊ−４，Ｑｊ−３，Ｑｊ−２，Ｑｊ−１，Ｑｊ）
Ｒｊ（ｐｊ，ｍπ（ｊ））＝（Ｑｊ−７>>>１１）＋（Ｔ>>>７）＋ｍπ（ｊ）＋Ｋ４，ｊ
ｆｊは、次のように定義される。
【００６３】
【数６】
φ４，└ｊ／３２┘＋１は、次のように定義される。なお、└・┘は、・以下の最大の整数を意味する。
【００６４】
【数７】
「+」はｍｏｄ２３２の加算であり、Ｘ>>>ＹはＸを右Ｙビット巡回シフトすることを示す。Ｋ４，ｊは予め定められた定数である。
【００６５】
このとき攻撃ビット条件はＱ２２＝１かつＱ２３＝Ｑ２４＝Ｑ２６＝Ｑ２７＝Ｑ２８＝０となる。
【００６６】
ハッシュ値演算装置は、コンピュータによって実現することができる。この場合、これらの装置がそれぞれ有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これらの装置における各処理機能が、コンピュータ上で実現される。
【００６７】
この処理内容を記述したハッシュ値演算プログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００６８】
この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【００６９】
１ 判断部
２ 演算部
２２ 乱数生成部
３ 警告部
４ パターン記憶部
５ パターン更新部
【技術分野】
【０００１】
この発明は、暗号学的ハッシュ関数（以下、単にハッシュ関数と呼ぶ。）に対するショートカット攻撃を検出する技術に関する。
【背景技術】
【０００２】
ハッシュ関数Ｈは、任意の長さのビット列を入力して、固定長のビット列を出力する関数である。ハッシュ関数Ｈは、少なくとも次の２つの性質を満たす場合に安全と呼ばれる。
【０００３】
１．衝突困難性 Ｈ（ｘ）＝Ｈ（ｘ’）となるｘ，ｘ’（≠ｘ）を見つけることが演算量的に困難
２．一方向性 与えられたｙに対してｙ＝Ｈ（ｘ）となるｘを見つけることが演算量的に困難
【０００４】
ハッシュ関数Ｈの出力値のビット数をｎとする。このとき、誕生日の逆理により、どのようなハッシュ関数Ｈに対しても、ランダムな入力ｘを２ｎ／２程度生成しそれぞれの入力ｘに対してハッシュ値Ｈ（ｘ）を演算すれば、Ｈ（ｘ）＝Ｈ（ｘ’）となるｘ，ｘ’（≠ｘ）を高い確率で見つけることができ、衝突困難性を破ることができる。また、ランダムな入力ｘを２ｎ程度生成しそれぞれの入力ｘに対してハッシュ値Ｈ（ｘ）を演算すれば、与えられたｙに対してｙ＝Ｈ（ｘ）となるｘを高い確率で見つけることができ、一方向性を破ることができる。
【０００５】
一般に、ｎは十分大きな値であり、ハッシュ関数ＨがＭＤ５の場合にはｎ＝１２８ビットである。したがって、２ｎ／２及び２ｎは一般に膨大な数となる。「演算量的に困難」とは、上記のように、衝突困難性を破るためにはハッシュ値Ｈ（ｘ）を２ｎ／２回程度演算する必要があることを意味し、一方向性を破るためにはハッシュ値Ｈ（ｘ）を２ｎ回程度演算する必要があることを意味する。
【０００６】
これに対して、２ｎ／２回以下のハッシュ値Ｈ（ｘ）の演算よりも少ない演算量で衝突困難性を破る手法や、２ｎ回以下のハッシュ値Ｈ（ｘ）の演算よりも少ない演算量で一方向性を破る手法がある場合、これらの手法をショートカット攻撃と呼ぶ。
【０００７】
ハッシュ関数の具体例として、ＭＤ４、ＭＤ５、ＳＨＡ−１、ＳＨＡ−２等が知られている。ＭＤ４、ＭＤ５、ＳＨＡ−１については、暗号解析技術の進歩によりショートカット攻撃が知られており安全ではなくなっている。しかし、これらのハッシュ関数は現在も多くのシステムで使われている。例えば電子メールをサーバから受信するための認証プロトコルＡＰＯＰではＭＤ５が使われている。
【０００８】
ＭＤ５の衝突困難性を破るショートカット攻撃によりＡＰＯＰで用いられるパスワードを復元する技術が非特許文献１に記載されている。また、この非特許文献１に記載された攻撃を検出する技術が非特許文献２に記載されている。非特許文献２では、攻撃を完全に検出するためにはＭＤ５の過去の演算結果を全て記憶しておき、ＭＤ５の演算を行う度に、そのＭＤ５の演算結果とこれまでに演算したＭＤ５の各演算結果とが一致するかどうかを判定し、一致すれば攻撃を受けていると判断する。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Yu Sasaki, Lei Wang, Kazuo Ohata, Noboru Kunihiro, “Security of MD5 Challenge and Response: APOP Password Recovery Attack”, CT-RSA2008, 2008
【非特許文献２】奥秋清次，坂井祐介，太田和夫、國廣昇，「ＡＰＯＰ攻撃検知法の提案とシミュレーションによる検証：目には目を，歯には歯を」，ＳＣＩＳ２００９，２００９
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、非特許文献２に記載された技術では、攻撃を完全に検出するためにはＭＤ５の過去の演算結果を全て記憶しておくため膨大な記憶領域が必要であるというという課題がある。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、この発明は、攻撃を受けている可能性が高い場合にハッシュ値を演算する過程で生じるビット列が満たす条件をパターン記憶部に記憶しておき、ハッシュ値を演算する過程で生じたビット列が上記パターン記憶部から読み出した条件を満たすか判断して、その条件を満たせば攻撃を受けていると判断する。
【発明の効果】
【００１２】
攻撃を受けている可能性が高い場合にハッシュ値を演算する過程で生じるビット列が満たす条件を記憶しておけば足り、ＭＤ５の過去の演算結果の全てを記憶しておく必要はない。したがって、必要な記憶領域を削減することができる。
【図面の簡単な説明】
【００１３】
【図１】ハッシュ値演算装置の例の機能ブロック図。
【図２】演算部の例の機能ブロック図。
【図３】ハッシュ値演算方法のフローチャートを例示する図。
【図４】攻撃ビット条件を例示する図。
【図５】攻撃ビット条件を例示する図。
【発明を実施するための形態】
【００１４】
以下、この発明の実施の形態について、詳細に説明する。
図１にハッシュ値演算装置の機能ブロック図を例示する。図３にハッシュ値演算方法のフローチャートを例示する。
【００１５】
パターン記憶部４には、攻撃を受けている可能性が高い場合にハッシュ値を演算する過程で生じるビット列が満たす条件（以下、攻撃ビット条件する。）が記憶されている。攻撃ビット条件は、用いるハッシュ関数Ｈや攻撃方法により異なる。攻撃ビット条件の具体例については後述する。
【００１６】
ビット列ｘは、演算部２に入力される。必要に応じて、判断部１にも入力される。
【００１７】
図１に、演算部２の機能ブロック図を例示する。演算部２のハッシュ値演算部２１は、入力されたビット列ｘをハッシュ関数Ｈに入力することによりハッシュ値Ｈ（ｘ）を演算する（ステップＳ１）。一般に、ハッシュ値Ｈ（ｘ）の演算は複数のステップから成り立っており、最終的なハッシュ値を演算するまでの各ステップにおいて中間演算結果であるビット列が生じる。このハッシュ値Ｈ（ｘ）を演算する過程で生じたビット列は、判断部１に送られる。
【００１８】
ハッシュ値Ｈ（ｘ）を演算する過程で生じたビット列は一般に複数存在する。複数存在するビット列の中で、後述する判断部１が攻撃の有無の判断のために用いるビット列が少なくとも判断部１に送られる。この段階ではハッシュ値Ｈ（ｘ）の演算は必ずしも最後まで行われる必要はない。少なくとも判断部１が攻撃の有無の判断のために用いるビット列が得られるステップまでハッシュ値Ｈ（ｘ）の演算を行えば足りる。
【００１９】
判断部１は、ハッシュ値Ｈ（ｘ）を演算する過程で生じたビット列が、パターン記憶部４から読み出した、そのビット列に対応する攻撃ビット条件を満たすか判断する（ステップＳ２）。
【００２０】
攻撃ビット条件を満たさない場合には、攻撃を受けていないと判断して、ハッシュ値演算装置は演算されたハッシュ値Ｈ（ｘ）を、入力されたビット列ｘに対応する出力値ｙとして出力する（ステップＳ３）。ステップＳ１において、ハッシュ値Ｈ（ｘ）を最後まで演算していない場合には、攻撃を受けていないとステップＳ２において判断された後に、ハッシュ値Ｈ（ｘ）を最後まで演算して出力する。
【００２１】
攻撃ビット条件を満たす場合には、攻撃を受けていると判断する。攻撃を受けていると判断された場合、攻撃を受けている旨の判断結果が警告部３に送られて、警告部３は攻撃を受けている旨の警告情報を出力する（ステップＳ４）。
【００２２】
攻撃を受けているかどうかを判断するために考慮すべきビット列が複数ある場合には、判断部１はこれらのビット列の全部又は一部のそれぞれが、パターン記憶部４から読み出した対応する攻撃ビット条件が満たすかどうかを判断する。判断部１は、これらのビット列の全部又は一部のそれぞれが対応する攻撃ビット条件を満たす場合には、攻撃を受けていると判断する。
【００２３】
ハッシュ関数の中にはいわゆるマークル・ダンガード構造で構成されているものがある。これは、入力されたビット列ｘをｘ＝ｘ０‖ｘ１‖…‖ｘＬ−１とＬ個のビット列に分割し、ＩＶ（Ｉｎｉｔｉａｌ Ｖａｌｕｅ）を定数とし、ｙ０＝ＩＶとし、ｉ＝１，…，Ｌ−１として、ｙｉ＋１＝ｈ（ｙｉ，ｘｉ）の演算を順次繰り返すことにより得たｙＬを入力されたビット列ｘに対するハッシュ値とするものである。
【００２４】
ｙ０＝ＩＶ
ｙｉ＋１＝ｈ（ｙｉ，ｘｉ），ｉ＝１，…，Ｌ−１
ハッシュ関数がこのマークル・ダンガード構造で構成されている場合には、入力されたビット列ｘに対応するハッシュ値Ｈ（ｘ）を演算する過程で生じるビット列の内、あるｈ（ｙｉ，ｘｉ）（演算量を削減するためにｉは小さい方が望ましい。）を演算する過程で生じるビット列を、攻撃を受けているかどうかを判断するために考慮すべきビット列としてもよい。また、各ｈ（ｙｉ，ｘｉ）（ｉ＝１，…，Ｌ−１）を演算する過程で生じるビット列を、攻撃を受けているかどうかを判断するために考慮すべきビット列としてもよい。攻撃を受けているかどうかを判断するために考慮すべきビット列が多くなるほど、攻撃を検出することができる確率が上がる。
【００２５】
従来はＭＤ５の演算結果の全てを記憶しておく必要があったが、この発明においては攻撃ビット条件を記憶しておけば足り、必要な記憶領域を削減することができる。
【００２６】
［変形例等］
ステップＳ２において、ハッシュ値Ｈ（ｘ）を演算する過程で生じたビット列が対応する攻撃ビット条件を満たしており、攻撃を受けていると判断することができる場合に、ハッシュ値Ｈ（ｘ）とは異なる値を入力ビット列ｘに対応する出力値ｙとして出力してもよい。
【００２７】
例えば、ハッシュ値Ｈ（ｘ）とは異なる関数の値Ｄ（ｘ）を演算して、入力ビット列ｘに対応する出力値ｙとしてＤ（ｘ）を出力してもよい（ステップＳ５、図３）。また、ハッシュ値Ｈ（ｘ）とは異なる関数の値Ｄ（ｘ）（ｘ≠Ｄ（ｘ）となるＤ（ｘ））を用いて、Ｈ（Ｄ（ｘ））を演算して、入力ビット列ｘに対応する出力値ｙとしてＨ（Ｄ（ｘ））を出力してもよい（ステップＳ６）。もちろん、Ｈ（Ｈ（ｘ））を入力ビット列ｘに対応する出力値ｙとしてもよい。
【００２８】
Ｄ（ｘ）として、安全な乱数を生成する関数を採用できる。この場合、演算部２に乱数生成部２２（図２）を設けて、この乱数生成部２２が安全な乱数を生成する。生成された乱数を出力値ｙとして出力してもよいし（ステップＳ５）、ハッシュ値演算部２１が生成された乱数ｒに対応するハッシュ値Ｈ（ｒ）を演算して出力値ｙとして出力してもよい（ステップＳ６）
また、ハッシュ関数Ｈ（ｘ）がパラメータに応じて出力する値が異なるハッシュ関数である場合には、パラメータを変更した関数をＤ（ｘ）としてもよい。例えば、ハッシュ関数としてＭＤ５を用いる場合には、いわゆるＩＶ（Ｉｎｉｔｉａｌ Ｖａｌｕｅ）を変更した関数をＤ（ｘ）としてもよい。
【００２９】
パラメータＰ１に基づくハッシュ関数をＨ（ｘ）、パラメータＰ２に基づくハッシュ関数をＤ（ｘ）とする。ステップＳ２において攻撃を受けていないと判断された場合には、演算部２のハッシュ値演算部２１はハッシュ値Ｈ（ｘ）を演算する（ステップＳ３）。ステップＳ２において攻撃を受けていると判断された場合には、パラメータ変更部２３はハッシュ値演算部２１が用いるハッシュ関数のパラメータをＰ２に変更する。ハッシュ値演算部２１は、ハッシュ値Ｄ（ｘ）を演算して出力値ｙとして出力する（ステップＳ５）。また、ハッシュ値演算部２４が、演算されたＤ（ｘ）を用いてＨ（Ｄ（ｘ））を演算して出力値ｙとして出力してもよい（ステップＳ６）。
【００３０】
さらに、Ｄ（ｘ）として、ハッシュ関数Ｈ（ｘ）とは異なる安全なハッシュ関数を用いてもよい。安全なハッシュ関数とは現段階では例えばＳＨＡ−２である。この場合、ステップＳ２において攻撃を受けていると判断された場合には、ハッシュ値演算部２１がＤ（ｘ）を演算して出力値ｙとして出力する（ステップＳ５）。また、ハッシュ値演算部２４が、演算されたＤ（ｘ）を用いてＨ（Ｄ（ｘ））を演算して出力値ｙとして出力してもよい。
【００３１】
パターン記憶部４に記憶される、攻撃を受けている可能性が高い場合に演算部２でハッシュ値を演算する過程で生じるビット列が満たす条件を更新するパターン更新部５を設けてもよい。ハッシュ関数に対するショートカット攻撃は日々開発されている。新たに開発されたショートカット攻撃を受けている可能性が高い場合に演算部２でハッシュ値を演算するビット列が満たす条件をパターン記憶部４に追加することにより、その新たに開発されたショートカット攻撃に対応することができる。
【００３２】
上記の例ではハッシュ値を演算する過程で生じたビット列が攻撃ビット条件を満たすかどうかにより攻撃の有無を判断したが、さらに入力されたビット列ｘがパターン記憶部２に記憶された対応する攻撃ビット条件を満たすかどうかにより攻撃の有無を判断してもよい。
【００３３】
［攻撃ビット条件の具体例１］
ハッシュ関数Ｈ（ｘ）としてＭＤ５を用いた場合の攻撃ビット条件の具体例１について説明する。この具体例１は、参考文献１に記載されたＭＤ５の衝突困難性に対するショートカット攻撃に基づくものである。
【００３４】
〔参考文献１〕Xiaoyun Wang, Hongbo Yu, “How to Break MD5 and Other Hash Functions”, Advances in Cryptology, EUROCRYPT 2005, Volume 3494 of Lecture Notes in Computer Science, pp.19-35. Springer-Verlag, Berlin, Heidelberg, New York, 2005.
まず、ＭＤ５について説明する。ＭＤ５の詳細は参考文献２を参照のこと。
【００３５】
〔参考文献２〕R. L. Rivest. Request for Comments 1321: The MD5 Message Digest
Algorithm. The Internet Engineering Task Force, 1992., http://www.ietf.org/rfc/rfc1321.txt
入力されたビット列ｘはパディング処理が施されて５１２ビットの倍数のビット列Ｍとなる。パティングは「ｘ‖１‖０‖０‖…‖０‖ｘのビット長」となるように施される。ｘのビット長は６４ビットで表示され、０はＭが５１２ビットの倍数となるように適切な数だけ追加される。Ｍを以下のように表記する。Ｍｉ（ｉ＝０，１，…，ｔ−１）は５１２ビットのビット列である。
【００３６】
Ｍ＝（Ｍ０，Ｍ１，…，Ｍｔ−１）
ＭＤ５の圧縮関数をｆとして、Ｈｉ（ｉ＝０，１，…，ｔ）を１２８ビットのビット列とし、Ｈ０をＩＶ（Ｉｎｉｔｉａｌ Ｖａｌｕｅ）として、Ｈｉ及びＭｉを圧縮関数ｆに入力してＨｉ＋１を順次求める。最後に求まったＨｔがＭＤ５のハッシュ値となる。ＩＶは例えば0123456789abcdeffedcba9876543210（１６進数表記）である。
【００３７】
Ｈ０＝ＩＶ
Ｈｉ＋１＝ｆ（Ｈｉ，Ｍｉ） ０≦ｉ≦ｔ−１
圧縮関数ｆ（Ｈｉ，Ｍｉ）について説明する。５１２ビットの入力Ｍｉは１６個の３２ビットのワードに分割される。
【００３８】
Ｍｉ＝（ｍ０，ｍ１，…，ｍ１５）
また、１２８ビットの入力Ｈｉも４個の３２ビットのワードに分割される。
【００３９】
Ｈｉ＝（ａｉ，ｂｉ，ｃｉ，ｄｉ）
３２ビットのワードに解釈される場合には常にリトルエンディアン（little endian）で解釈される。つまり、例えばａ０＝67452301（１６進数表記）となる。
【００４０】
まず、以下の４つの式の演算がｉ＝０，４，…，６０に対して順に施される。これにより、（ａ１，ｂ１，ｃ１，ｄ１），（ａ２，ｂ２，ｃ２，ｄ２），…，（ａ１６，ｂ１６，ｃ１６，ｄ１６）が順次演算される。
【００４１】
a1+i/4 = bi/4 + ((ai/4 + Φi(bi/4,ci/4,di/4) + wi + ti) <<< si)
d1+i/4 = ai/4 + ((di/4 + Φi(ai/4,bi/4,ci/4) + wi+1 + ti+1) <<< si+1)
c1+i/4 = di/4 + ((ci/4 + Φi(di/4,ai/4,bi/4) + wi+2 + ti+2) <<< si+2)
b1+i/4 = ci/4 + ((bi/4 + Φi(ci/4,di/4,ai/4) + wi+3 + ti+3) <<< si+3)
ここで「+」はｍｏｄ２３２の加算であり、Ｘ<<<ＹはＸを左Ｙビット巡回シフトすることを示す。また、ｗｉ＝ｍπ（ｉ）であり、π（ｉ）は次の通りである。
【００４２】
【数１】
【００４３】
また、ｔｉ（ｉ＝０，１，…，６３）を次のように定める。一番左上がｔ０であり、ｔｉの右がｔｉ＋１であり、ｔｉの下がｔｉ＋８であり、ｔｉを１６進数で表記している。
【００４４】
【数２】
【００４５】
また、ｓｉを次のように定める
【数３】
さらに、Φｉを次のように定める。ここで、∧、∨、○の中に＋の記号はそれぞれ論理積、論理和、排他的論理和を表し、上付きバーはビットごとの反転を表す。
【００４６】
【数４】
最後に、Ｈｉ＝（ａ０，ｂ０，ｃ０，ｄ０）に（ａ１６，ｂ１６，ｃ１６，ｄ１６）を足したものをＨｉ＋１とし、これが圧縮関数ｆ（Ｈｉ，Ｍｉ）の出力となる。
【００４７】
Hi+1 = (a0 + a16, b0 + b16, c0 + c16, d0 + d16)
このとき、攻撃ビット条件は図４及び図５に例示される。ｉ＝０，１，…，ｔ−１、例えばｉ＝０として、図４はＨｉ＋１＝ｆ（Ｈｉ，Ｍｉ）を演算するときに生じるビット列ａｊ，ｂｊ，ｃｊ，ｄｊについての攻撃ビット条件を例示し、図５はＨｉ＋２＝ｆ（Ｈｉ＋１，Ｍｉ＋１）を演算するときに生じるビット列ａｊ，ｂｊ，ｃｊ，ｄｊについての攻撃ビット条件を例示している。ａｉ，ｊはビット列ａｉの右からｊ番目のビットを意味する。ｂｉ，ｊ，ｃｉ，ｊ，ｄｉ，ｊについても同様である。
【００４８】
この例ではこのように判断部１が攻撃の有無の判断のために用いるビット列が複数ある。ハッシュ値を演算する過程で生じたビット列が図４及び図５に示す攻撃ビット条件のすべてを満たす場合には、攻撃が行われていると判断することができる。しかし、攻撃の有無の判断処理を軽減するために、これらの攻撃ビット条件の一部を満たす場合には、攻撃が行われている可能性が高いため、攻撃が行われていると判断してもよい。
【００４９】
なお、参考文献１では、入力されたビット列ｘに対応するハッシュ値と、入力されたビット列ｘを予め定められた量Δｘだけ変化させたビット列ｘ＋Δｘに対応するハッシュ値とを同じ値にしようとしている。したがって、入力されたビット列ｘに対応するハッシュ値を演算する過程で生じるビット列が攻撃ビット条件を満たすかどうかを判断する代わりに、ビット列ｘ＋Δｘに対応するハッシュ値を演算する過程で生じるビット列が上記と同じ攻撃ビット条件を満たすかどうかを判断することにより、攻撃の有無を判断することができる。
【００５０】
ｘ＋Δｘをパディングして５１２ビットの倍数のビット列Ｍ’を取得して、これを５１２ビットごとに分割する。Ｍｉ’（ｉ＝０，１，…，ｔ−１）は５１２ビットのビット列である。
【００５１】
Ｍ’＝（Ｍ０’，Ｍ１’，…，Ｍｔ−１’）
ΔＭ０＝Ｍ０’−Ｍ０、ΔＭ１＝Ｍ１’−Ｍ１として、ΔＭ０及びΔＭ１は以下の条件を満たす。ΔＭ０及びΔＭ１が以下の条件を満たすようにΔｘが決められる。
【００５２】
ΔＭ０＝（0,0,0,0,231,0,0,0,0,0,0,215,0,0,231,0）
ΔＭ１＝（0,0,0,0,231,0,0,0,0,0,0,-215,0,0,231,0）
このとき、Ｈ１＝ｆ（Ｈ０，Ｍ０’）を演算するときに生じるビット列ａｊ，ｂｊ，ｃｊ，ｄｊが図４に例示した攻撃ビット条件の全部又は一部を満たし、Ｈ２＝ｆ（Ｈ１，Ｍ１’）を演算するときに生じるビット列ａｊ，ｂｊ，ｃｊ，ｄｊが図５に例示した攻撃ビット条件の全部又は一部を満たす場合に、攻撃が行われていると判断してもよい。
【００５３】
［攻撃ビット条件の具体例２］
ハッシュ関数Ｈ（ｘ）として４−ｐａｓｓ ＨＡＶＡＬの２５６ビットハッシュ値を用いた場合の攻撃ビット条件の具体例２について説明する。この具体例２は、参考文献３に記載された４−ｐａｓｓ ＨＡＶＡＬに対するショートカット攻撃に基づくものである。
【００５４】
〔参考文献３〕Y. Sasaki and K. Aoki, “Preimage Attacks on 3, 4, and 5-pass HAVAL”, In J. Pieprzyk, editor, Advances in Cryptology-ASIACRYPT 2008, Volume 5350 of Lecture Notes in Computer Science, pp.253-271. Springer-Verlag, Berlin, Heidelberg, New York, 2008.
まず、４−ｐａｓｓ ＨＡＶＡＬについて説明する。
【００５５】
入力されたビット列ｘはパディング処理が施されて１０２４ビットの倍数のビット列Ｍとなる。Ｍを以下のように表記する。Ｍｉ（ｉ＝０，１，…，ｔ−１）は１０２４ビットのビット列である。
【００５６】
Ｍ＝（Ｍ０，Ｍ１，…，Ｍｔ−１）
ＨＡＶＡＬの圧縮関数として、Ｈｉ（ｉ＝０，１，…，ｔ）を２５６ビットのビット列とし、Ｈ０をＩＶ（Ｉｎｉｔｉａｌ Ｖａｌｕｅ）として、Ｈｉ及びＭｉを圧縮関数ｆに入力してＨｉ＋１を順次求める。最後に求まったＨｔがＨＡＶＡＬのハッシュ値となる。ＩＶは予め定められた定数である。
【００５７】
Ｈ０＝ＩＶ
Ｈｉ＋１＝ｆ（Ｈｉ，Ｍｉ） ０≦ｉ≦ｔ−１
圧縮関数ｆ（Ｈｉ，Ｍｉ）について説明する。１０２４ビットの入力Ｍｉは３２個の３２ビットのワードに分割される。
【００５８】
Ｍｉ＝（ｍ０，ｍ１，…，ｍ１５）
ｐ０＝Ｈｉとして、ｊ＝０，１，…，ｋ（ｋ＝１２７）に対して順次ｐｊ＋１＝Ｒｊ（ｐｊ，ｍπ（ｊ））が計算されて、最終的にｐｋが計算される。計算されたｐｋにＨｉを加算したものをｆ（Ｈｉ，Ｍ）の出力値であるＨｉ＋１とする。
【００５９】
関数π（ｊ）は、次の通りである。左上がπ（０）であり、あるπ（ｊ）の右がπ（ｊ＋１）であり、あるπ（ｊ）の下がπ（ｊ＋３２）である。
【００６０】
【数５】
次に、関数Ｒｊ（ｐｊ，ｍπ（ｊ））について説明する。Ｑｊは３２ビットのビット列であり、次の関係を満たすとする。
【００６１】
ｐｊ＝（Ｑｊ−７‖Ｑｊ−６‖Ｑｊ−５‖Ｑｊ−４‖Ｑｊ−３‖Ｑｊ−２‖Ｑｊ−１‖Ｑｊ）
このとき関数Ｒｊ（ｐｊ，ｍπ（ｊ））は次のように定義される。
【００６２】
Ｔ＝ｆｊ・φ４，└ｊ／３２┘＋１（Ｑｊ−６，Ｑｊ−５，Ｑｊ−４，Ｑｊ−３，Ｑｊ−２，Ｑｊ−１，Ｑｊ）
Ｒｊ（ｐｊ，ｍπ（ｊ））＝（Ｑｊ−７>>>１１）＋（Ｔ>>>７）＋ｍπ（ｊ）＋Ｋ４，ｊ
ｆｊは、次のように定義される。
【００６３】
【数６】
φ４，└ｊ／３２┘＋１は、次のように定義される。なお、└・┘は、・以下の最大の整数を意味する。
【００６４】
【数７】
「+」はｍｏｄ２３２の加算であり、Ｘ>>>ＹはＸを右Ｙビット巡回シフトすることを示す。Ｋ４，ｊは予め定められた定数である。
【００６５】
このとき攻撃ビット条件はＱ２２＝１かつＱ２３＝Ｑ２４＝Ｑ２６＝Ｑ２７＝Ｑ２８＝０となる。
【００６６】
ハッシュ値演算装置は、コンピュータによって実現することができる。この場合、これらの装置がそれぞれ有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これらの装置における各処理機能が、コンピュータ上で実現される。
【００６７】
この処理内容を記述したハッシュ値演算プログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００６８】
この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【００６９】
１ 判断部
２ 演算部
２２ 乱数生成部
３ 警告部
４ パターン記憶部
５ パターン更新部
【特許請求の範囲】
【請求項１】
入力されたビット列に対応するハッシュ値を演算する演算部と、
攻撃を受けている可能性が高い場合に上記演算部でハッシュ値を演算する過程で生じるビット列が満たす条件を記憶するパターン記憶部と、
上記演算部でハッシュ値を演算する過程で生じたビット列が、上記パターン記憶部から読み込んだ条件を満たすか判断して、条件を満たす場合には攻撃を受けていると判断する判断部と、
を含むハッシュ値演算装置。
【請求項２】
請求項１に記載されたハッシュ値演算装置において、
上記演算部は、上記判断部において攻撃を受けていると判断された場合には、上記入力されたビット列に対応するハッシュ値とは異なる値を出力する、
ことを特徴とするハッシュ値演算装置。
【請求項３】
請求項１又は２に記載されたハッシュ値演算装置において、
上記パターン記憶部に記憶されたビット列を更新するパターン更新部を更に含む、
ことを特徴とするハッシュ値演算装置。
【請求項４】
請求項１から３の何れかに記載されたハッシュ値演算装置において、
上記判断部において攻撃を受けていると判断された場合には、攻撃を受けている旨の警告情報を出力する警告部を更に含む、
ことを特徴とするハッシュ値演算装置。
【請求項５】
請求項１から４の何れかに記載されたハッシュ値演算装置において、
上記演算部は、入力されたビット列を予め定められた値だけ変化させたビット列に対応するハッシュ値を演算する、
ことを特徴とするハッシュ値演算装置。
【請求項６】
請求項２から５の何れかに記載されたハッシュ値演算装置において、
上記演算部は、乱数を生成する乱数生成部を更に含み、
上記演算部は、上記判断部において攻撃を受けていると判断された場合には、上記乱数を上記異なる値として出力する、
ことを特徴とするハッシュ値演算装置。
【請求項７】
請求項２から５の何れかに記載されたハッシュ値演算装置において、
上記演算部は、乱数を生成する乱数生成部を更に含み、
上記演算部は、上記判断部において攻撃を受けていると判断された場合には、上記生成された乱数に対応するハッシュ値を演算して、そのハッシュ値を上記異なる値として出力する、
ことを特徴とするハッシュ値演算装置。
【請求項８】
請求項２から５の何れかにに記載されたハッシュ値演算装置において、
上記演算部は、パラメータに応じて出力する値が異なるハッシュ関数に入力されたビット列を代入することによりハッシュ値を演算し、
上記演算部は、上記判断部において攻撃を受けていると判断された場合には、上記判断部において攻撃が行われていないと判断された場合のパラメータとは異なるパラメータのハッシュ関数に入力されたビット列を代入することによりハッシュ値を演算して、そのハッシュ値を上記異なる値として出力する、
ことを特徴とするハッシュ値演算装置。
【請求項９】
請求項２から５の何れかに記載されたハッシュ値演算装置において、
上記演算部は、パラメータに応じて出力する値が異なるハッシュ関数に入力されたビット列を代入することによりハッシュ値を演算し、
上記演算部は、上記判断部において攻撃を受けていると判断された場合には、上記判断部において攻撃が行われていないと判断された場合のパラメータとは異なるパラメータのハッシュ関数に入力されたビット列を代入することにより第一ハッシュ値を演算し、その第一ハッシュ値を上記判断部において攻撃が行われていないと判断された場合のパラメータのハッシュ関数に代入することにより第二ハッシュ値を演算して、その第二ハッシュ値を上記異なる値として出力する、
ことを特徴とするハッシュ値演算装置。
【請求項１０】
請求項２から５の何れかに記載されたハッシュ値演算装置において、
上記演算部は、上記判断部において攻撃が行われていないと判断された場合には第一ハッシュ関数に入力されたビット列を代入することによりハッシュ値を演算し、上記判断部において攻撃を受けていると判断された場合には第一ハッシュ関数とは異なる第二ハッシュ関数に入力されたビット列を代入することにより第二ハッシュ値を演算しその第二ハッシュ値を上記異なる値として出力する、
ことを特徴とするハッシュ値演算装置。
【請求項１１】
請求項２から５の何れかに記載されたハッシュ値演算装置において、
上記演算部は、上記判断部において攻撃が行われていないと判断された場合には第一ハッシュ関数に入力されたビット列を代入することによりハッシュ値を演算し、上記判断部において攻撃を受けていると判断された場合には第一ハッシュ関数とは異なる第二ハッシュ関数に入力されたビット列を代入することにより第二ハッシュ値を演算しその第二ハッシュ値を第一ハッシュ関数に代入することにより得たハッシュ値を上記異なる値として出力する、
ことを特徴とするハッシュ値演算装置。
【請求項１２】
入力されたビット列に対応するハッシュ値を演算する演算ステップと、
攻撃を受けている可能性が高い場合に上記演算部でハッシュ値を演算する過程で生じるビット列が満たす条件を記憶するパターン記憶ステップと、
上記演算部でハッシュ値を演算する過程で生じたビット列が、上記パターン記憶部から読み込んだ条件を満たすか判断して、条件を満たす場合には攻撃を受けていると判断する判断ステップと、
を含むハッシュ値演算方法。
【請求項１３】
請求項１から１１の何れかに記載されたハッシュ値演算装置の各部としてコンピュータを機能させるためのハッシュ値演算プログラム。
【請求項１４】
請求項１３に記載されたハッシュ値演算プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１】
入力されたビット列に対応するハッシュ値を演算する演算部と、
攻撃を受けている可能性が高い場合に上記演算部でハッシュ値を演算する過程で生じるビット列が満たす条件を記憶するパターン記憶部と、
上記演算部でハッシュ値を演算する過程で生じたビット列が、上記パターン記憶部から読み込んだ条件を満たすか判断して、条件を満たす場合には攻撃を受けていると判断する判断部と、
を含むハッシュ値演算装置。
【請求項２】
請求項１に記載されたハッシュ値演算装置において、
上記演算部は、上記判断部において攻撃を受けていると判断された場合には、上記入力されたビット列に対応するハッシュ値とは異なる値を出力する、
ことを特徴とするハッシュ値演算装置。
【請求項３】
請求項１又は２に記載されたハッシュ値演算装置において、
上記パターン記憶部に記憶されたビット列を更新するパターン更新部を更に含む、
ことを特徴とするハッシュ値演算装置。
【請求項４】
請求項１から３の何れかに記載されたハッシュ値演算装置において、
上記判断部において攻撃を受けていると判断された場合には、攻撃を受けている旨の警告情報を出力する警告部を更に含む、
ことを特徴とするハッシュ値演算装置。
【請求項５】
請求項１から４の何れかに記載されたハッシュ値演算装置において、
上記演算部は、入力されたビット列を予め定められた値だけ変化させたビット列に対応するハッシュ値を演算する、
ことを特徴とするハッシュ値演算装置。
【請求項６】
請求項２から５の何れかに記載されたハッシュ値演算装置において、
上記演算部は、乱数を生成する乱数生成部を更に含み、
上記演算部は、上記判断部において攻撃を受けていると判断された場合には、上記乱数を上記異なる値として出力する、
ことを特徴とするハッシュ値演算装置。
【請求項７】
請求項２から５の何れかに記載されたハッシュ値演算装置において、
上記演算部は、乱数を生成する乱数生成部を更に含み、
上記演算部は、上記判断部において攻撃を受けていると判断された場合には、上記生成された乱数に対応するハッシュ値を演算して、そのハッシュ値を上記異なる値として出力する、
ことを特徴とするハッシュ値演算装置。
【請求項８】
請求項２から５の何れかにに記載されたハッシュ値演算装置において、
上記演算部は、パラメータに応じて出力する値が異なるハッシュ関数に入力されたビット列を代入することによりハッシュ値を演算し、
上記演算部は、上記判断部において攻撃を受けていると判断された場合には、上記判断部において攻撃が行われていないと判断された場合のパラメータとは異なるパラメータのハッシュ関数に入力されたビット列を代入することによりハッシュ値を演算して、そのハッシュ値を上記異なる値として出力する、
ことを特徴とするハッシュ値演算装置。
【請求項９】
請求項２から５の何れかに記載されたハッシュ値演算装置において、
上記演算部は、パラメータに応じて出力する値が異なるハッシュ関数に入力されたビット列を代入することによりハッシュ値を演算し、
上記演算部は、上記判断部において攻撃を受けていると判断された場合には、上記判断部において攻撃が行われていないと判断された場合のパラメータとは異なるパラメータのハッシュ関数に入力されたビット列を代入することにより第一ハッシュ値を演算し、その第一ハッシュ値を上記判断部において攻撃が行われていないと判断された場合のパラメータのハッシュ関数に代入することにより第二ハッシュ値を演算して、その第二ハッシュ値を上記異なる値として出力する、
ことを特徴とするハッシュ値演算装置。
【請求項１０】
請求項２から５の何れかに記載されたハッシュ値演算装置において、
上記演算部は、上記判断部において攻撃が行われていないと判断された場合には第一ハッシュ関数に入力されたビット列を代入することによりハッシュ値を演算し、上記判断部において攻撃を受けていると判断された場合には第一ハッシュ関数とは異なる第二ハッシュ関数に入力されたビット列を代入することにより第二ハッシュ値を演算しその第二ハッシュ値を上記異なる値として出力する、
ことを特徴とするハッシュ値演算装置。
【請求項１１】
請求項２から５の何れかに記載されたハッシュ値演算装置において、
上記演算部は、上記判断部において攻撃が行われていないと判断された場合には第一ハッシュ関数に入力されたビット列を代入することによりハッシュ値を演算し、上記判断部において攻撃を受けていると判断された場合には第一ハッシュ関数とは異なる第二ハッシュ関数に入力されたビット列を代入することにより第二ハッシュ値を演算しその第二ハッシュ値を第一ハッシュ関数に代入することにより得たハッシュ値を上記異なる値として出力する、
ことを特徴とするハッシュ値演算装置。
【請求項１２】
入力されたビット列に対応するハッシュ値を演算する演算ステップと、
攻撃を受けている可能性が高い場合に上記演算部でハッシュ値を演算する過程で生じるビット列が満たす条件を記憶するパターン記憶ステップと、
上記演算部でハッシュ値を演算する過程で生じたビット列が、上記パターン記憶部から読み込んだ条件を満たすか判断して、条件を満たす場合には攻撃を受けていると判断する判断ステップと、
を含むハッシュ値演算方法。
【請求項１３】
請求項１から１１の何れかに記載されたハッシュ値演算装置の各部としてコンピュータを機能させるためのハッシュ値演算プログラム。
【請求項１４】
請求項１３に記載されたハッシュ値演算プログラムを記録したコンピュータ読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１０−２５６５６５（Ｐ２０１０−２５６５６５Ａ）
【公開日】平成２２年１１月１１日（２０１０．１１．１１）
【国際特許分類】
【出願番号】特願２００９−１０５６００（Ｐ２００９−１０５６００）
【出願日】平成２１年４月２３日（２００９．４．２３）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年１１月１１日（２０１０．１１．１１）
【国際特許分類】
【出願日】平成２１年４月２３日（２００９．４．２３）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]