暗号学的ハッシュ関数
暗号学的ハッシュ関数（あんごうがくてきハッシュかんすう、英: cryptographic hash function）は、ハッシュ関数のうち、暗号など情報セキュリティの用途に適する暗号数理的性質をもつもの。任意の長さの入力を（通常は）固定長の出力に変換する。
「メッセージダイジェスト」は、暗号学的ハッシュ関数の多数ある応用のひとつであり、メールなどの「メッセージ」のビット列から暗号学的ハッシュ関数によって得たハッシュ値を、そのメッセージの内容を保証する「ダイジェスト」として利用するものである。
要求される性質
編集暗号学的ハッシュ関数には、一般的なハッシュ関数に望まれる性質や、決定的であることの他、次のような暗号学的な性質が要求される。
- ハッシュ値から、そのようなハッシュ値となるメッセージを得ることが（事実上）不可能であること（原像計算困難性、弱衝突耐性）。
- 同じハッシュ値となる、異なる2つのメッセージのペアを求めることが（事実上）不可能であること（強衝突耐性）。
- メッセージをほんの少し変えたとき、ハッシュ値は大幅に変わり、元のメッセージのハッシュ値とは相関がないように見えること。
暗号学的ハッシュ関数は情報セキュリティ分野で様々に利用されている。たとえば、デジタル署名、メッセージ認証符号 (MAC)、その他の認証技術などである。目的によって要求される性質はそれぞれ異なる。
一般に通常のハッシュ関数と比べ、長い（最低でも100ビット程度）ハッシュ値が必要であり必要な計算も多いが、メッセージのチェックなどの目的に使われることからそういった用途では高速に計算できるほうが望ましい。一方、パスワードハッシュなどの用途では、ハッシュ値を求める計算が重い（遅い）ことが必要である。この場合には、ハッシュ値のハッシュ値を何度も求める「ストレッチング」などの技法を用いるか、そういった目的に適するように設計された特別な鍵導出関数、たとえばbcryptを用いる。通常のハッシュ関数として、ハッシュテーブルのインデックス、フィンガープリント、重複データの検出、ファイルの一意な識別、データの誤りを検出するチェックサムなどにも利用できるが、通常のハッシュ関数と比べて計算が重い点で、必ずしも適していない。
なお「（事実上）」とは、探索しなければならない対象が数え上げ可能なために[注 1]総当たり攻撃ができるため、実際には探索の計算に必要な時間が現実的に十分に長いかどうか、という意味だからである。理想的には一方向性関数であれば良いのだが、一方向性であるという保証のある（一方向性であると証明された）ハッシュ関数はまだ得られておらず、そもそも数理的にそれが存在するか否かもわかっていない。現状では、構成法が広く暗号研究者に知られていて攻撃法が研究されており、かつ、効果的・効率的な攻撃法が発見されていないハッシュ関数であれば安全であろう、とみなされて運用されている。もし理想的なハッシュ関数があったとしたなら、暗号学的には、総当たり攻撃（および誕生日攻撃）以外には攻撃法が無いということになる。
特性
編集以上のような要求される性質にもとづき、暗号学的ハッシュ関数の特性について、もう少し詳細に説明する。
暗号学的ハッシュ関数は、任意長のビット列を入力とし、固定長のビット列を出力とする。その出力が「入力に対するハッシュ値」である。2019年現在の時点では、多くのコンピュータシステムがデータ量としてオクテット単位であるため、オクテット列を入力としている実装がもっぱらではある。
暗号学的ハッシュ関数には、少なくとも次のような特性が必須である。
- 原像攻撃の難しさ
-
- 原像計算困難性 (preimage resistance)
- ハッシュ値 h が与えられたとき、そこから h = hash(m) となるような任意のメッセージ m を探すことが困難でなければならない。これは一方向性関数の原像計算困難性に関連している。この特性がない関数は（第1）原像攻撃に対して脆弱である。
- 第2原像計算困難性
- 入力 m1 が与えられたとき、h = hash(m1) = hash(m2) となる（すなわち、衝突する）ような別の入力 m2（m1とは異なる入力）を見つけることが困難でなければならない。これを「弱衝突耐性」ともいう。この特性がない関数は、第2原像攻撃に対して脆弱である。（第1）原像攻撃と異なり、h を単純に固定するのではなく m1 のハッシュ値となるように固定する。
- 誕生日攻撃の難しさ
-
- 強衝突耐性
- h = hash(m1) = hash(m2) となるような2つの異なるメッセージ m1 と m2 を探し出すことが困難でなければならない。第2原像計算困難性と異なる点として、h は任意に選んでよい。一般に誕生日のパラドックス[注 2]によって、強衝突耐性を持つためには、原像計算困難性を持つために必要なハッシュ値の2倍の長さのハッシュ値が必要である。
これらの特性は、悪意ある攻撃者でもダイジェストを変化させずに入力データを改竄できないことを示すものである。したがって、2つの文字列のダイジェストが同じ場合、それらが同一のメッセージである可能性は非常に高い。
これらの基準に適合した関数でも、好ましくない特性をもつものがありうる。現在よく使われている暗号学的ハッシュ関数は伸長攻撃に対して脆弱である。すなわち、ハッシュ値 h(m) とメッセージ長 len(m) が分かっていて m そのものは不明の場合、適当な m' を選んで h (m || m') が計算できる。ここで、|| はメッセージの連結を意味する。この特性を利用して、ハッシュ関数に基づく単純な認証方式を破ることが可能である。HMACはこの問題への対策として考案された。
理想的には、さらに強い条件を課すこともできる。例えば、悪意ある者が非常によく似たダイジェストを生成する2つのメッセージを見つけることができないのが望ましい。また、ダイジェストだけから元のデータについて何らかの有用な情報を推測できないのが望ましい。これはある意味で、暗号学的ハッシュ関数は疑似乱数列を生成する関数（特に、暗号論的擬似乱数生成器）の関数に似ているといえる。しかし、決定性と計算効率は維持しなければならず、疑似乱数列生成系においては通常必要とされる最長周期の保証といった特性は、暗号学的ハッシュ関数にはない。
単純なチェックサムはもとより、巡回冗長検査 (CRC) などの誤り検出符号も、上で説明したような攻撃への耐性はなく、暗号的な目的には不適である。例えば、CRCがWEPでのデータ完全性保証に使われていたので、チェックサムの線形性を利用した攻撃が可能となった。
用途
編集暗号学的ハッシュ関数の典型的な利用例を以下に示す。アリスは難しい数学問題をボブに提示し、彼女自身はそれを解いたと主張する。ボブも解いてみるが、その前にアリスがはったりをかましていないことを確認したい。このときアリスは、自分の解答にランダムな文字列 (nonce) を付けてそのハッシュ値を計算し、ボブにハッシュ値を知らせる（この時点では解答そのものとnonceは秘密にしておく）。何日かしてボブがその問題を解いたら、アリスはnonceと自分の解答をボブに示すことで、既にその問題を解いていたことが証明できる。これはコミットメントスキームの簡単な例である。実際にはアリスとボブはコンピュータプログラムであることが多く、秘密にされることは数学問題の解などといったものではなく、もっと簡単に改竄できるものである。
安全なハッシュのもう1つの重要な用途として、データ完全性の検証がある。メッセージ（あるいはファイル）に改変が加えられているかどうかの判定であり、例えばメッセージを転送する前と後でメッセージダイジェストを計算し、比較することで検証する（転送以外の事象の前後でもよい）。
メッセージダイジェストは、確実にファイルを識別する手段としてバージョン管理システムで使われている（例えば、Git、Mercurial、Monotone）。また、sha1sum を使うと様々な種類のコンテンツ（ファイル、ディレクトリツリーなど）が一意に識別できる。
関連する用途としてパスワードハッシュ（鍵導出関数#パスワードハッシュ）がある。パスワードは秘匿する必要があるので、通常はそのままクリアテキストでは格納されておらず、何らかのダイジェストの形式で格納されている。利用者を認証する際、利用者が入力したパスワードにハッシュ関数を適用し、出力のハッシュ値と格納されているハッシュ値とを比較する。
セキュリティ上の理由と性能上の理由から、デジタル署名アルゴリズムの多くはメッセージのダイジェストについてだけ「署名」し、メッセージそのものには署名しない。ハッシュ関数は擬似乱数ビット列の生成にも使われる。
ハッシュは Peer to Peer のファイル共有ネットワークでのファイルの識別にも使われている。例えばed2kリンクでは、MD4から派生したハッシュとファイルサイズを組み合わせ、ファイルの識別に十分な情報を提供している。他にもMagnetリンクがある。このようなファイルのハッシュは、ハッシュリストやハッシュ木のトップハッシュであることが多く、それによって別の利点も生じる。
ブロック暗号に基づくハッシュ関数
編集ブロック暗号を使って暗号学的ハッシュ関数を構築する手法はいくつかある。
その手法は、暗号化に通常使われるブロック暗号の暗号利用モードに似ている。よく知られているハッシュ関数（MD4、MD5、SHA-1、SHA-2など）はブロック暗号的なコンポーネントを使った設計になっていて、関数が全単射にならないようフィードバックをかけている。
AESのような標準的ブロック暗号を暗号学的ハッシュ関数のブロック暗号部分に利用することも可能だが、一般に性能低下が問題となる。しかし、ハッシュと同時にブロック暗号を使った暗号化のような暗号機能も必要とするシステムで、しかもICカードのような組み込みシステムでは、コードの大きさやハードウェアの規模が制限されているので、共通化が有利となるかもしれない。
Merkle-Damgård construction
編集
暗号学的ハッシュ関数は、任意長のメッセージを固定長の出力に変換しなければならない。したがって、入力を一連の固定長のブロックに分割し、それらに順次一方向性圧縮関数を作用させる。この圧縮関数はハッシュのために特に設計したものでもよいし、ブロック暗号を使って構築したものでもよい。Merkle-Damgård construction で構築されたハッシュ関数は、その圧縮関数と同程度の衝突困難性がある。ハッシュ関数全体で発生する衝突は、圧縮関数での衝突に起因する。最後のブロックには明らかにパディングが必要で、この部分はセキュリティ上重要である。
このような構築法を Merkle-Damgård construction と呼ぶ。SHA-1やMD5などのよく使われているハッシュ関数は、この形式である。
この構築法の本質的欠点として、length-extension 攻撃や generate-and-paste 攻撃に弱く、並列処理できないという点が挙げられる。より新しいハッシュ関数であるSHA-3は全く異なる構築法を採用している。
他の暗号の構築における利用
編集暗号学的ハッシュ関数（以下では「暗号学的」を省略する）は他の暗号の構築に使える。それらが暗号学的に安全であるためには、正しく構築するよう注意が必要である。
メッセージ認証符号 (MAC) はハッシュ関数から構築することが多い。例えばHMACがある。
ブロック暗号を使ってハッシュ関数を構築できると同時に、ハッシュ関数を使ってブロック暗号が構築できる。Feistel構造で構築されたブロック暗号は、使用したハッシュ関数が安全である限り、その暗号自体も安全であるといえる。また多くのハッシュ関数（SHAなど）は専用のブロック暗号を使い Davis-Mayer などの構成法で構築されている。そのような暗号は、ブロック暗号として従来のモードでも使えるが、同程度のセキュリティは保証できない。
擬似乱数列生成器 (PRNG) を、ハッシュ関数を使って構築できるが、そのままでは通常の「一般の擬似乱数列生成器の出力を暗号学的ハッシュ関数を通すようにして安全にしたもの」のような安全性はない（過去の出力結果が十分にあれば、未来の結果が予測可能だから）。安全にするにはさらにハッシュ関数を通さなければならない。また、現代的な擬似乱数列生成器では通常、周期は確定的だが、ハッシュ関数を利用したPRNGの周期は、衝突の確率でしか推定できず、確定的ではない。
ストリーム暗号はハッシュ関数を使って構築できる。多くの場合、暗号論的擬似乱数生成器をまず構築し、それが生成するランダムなバイト列を鍵ストリームとして使用する。SEALというストリーム暗号は、SHA-1を使って内部の表を生成し、その表は鍵ストリーム生成に使われる。
ハッシュ関数の連結
編集複数のハッシュ関数の出力を連結すると、連結対象のハッシュ関数のうち最強のものと少なくとも同等以上の衝突困難性を提供できる[注 3]。例えば、TLS/SSLはMD5とSHA-1を連結して利用している。これによって、どちらか一方が破られても全体としてはセキュリティが保てるようにしている。
しかし、Merkle-Damgård で構成したハッシュ関数は連結しても個々のハッシュ関数と同等な強度にしかならず、より強くなることはない[注 4]。Joux[1]によれば、MD5のハッシュ値が同じになる2つのメッセージを見つけることができれば、攻撃者がさらに同じハッシュ値となるメッセージを見つけることは簡単である。MD5で衝突を起こす多数のメッセージの中にはSHA-1でも衝突を起こすものもありうるだろう。そうなれば、SHA-1での衝突を探すのに必要な時間は多項式時間でしかない。この論旨はハル・フィニーが要約している[2]。
アルゴリズム
編集暗号学的ハッシュ関数は多数存在するが、その多くは脆弱性が判明し、使われなくなっている。ハッシュ関数自体が破られたことがなくとも、それを弱めたバリエーションへの攻撃が成功すると専門家が徐々にそのハッシュ関数への信頼を失い、結果として使われなくなることもある。実際、2004年8月、当時よく使われていたハッシュ関数（SHA-0、RIPEMD、MD5など）の弱点が判明した。このことから、これらのハッシュ関数から派生したアルゴリズム、特にSHA-1（SHA-0を強化したもの）とRIPEMD-128とRIPEMD-160（RIPEMDを強化したもの）の長期的なセキュリティに疑問が投げかけられた。SHA-0とRIPEMDは、既に強化されたバージョンに置換され、使われなくなっている。
2009年現在、最も広く使われている暗号学的ハッシュ関数はMD5とSHA-1である。しかし、MD5は既に破られており、2008年にはSSLへの攻撃にその脆弱性が利用された[3]。
SHA-0とSHA-1はNSAの開発したSHAファミリに属する。2005年2月、SHA-1について160ビットのハッシュ関数に期待される 280 回の操作より少ない 269 回のハッシュ生成で衝突を見つける攻撃法が報告された。2005年8月には 263 回で衝突を見つける攻撃法の報告があった。SHA-1には理論上の弱点も指摘されており[4][5]、数年で解読されるという示唆もある。さらに2009年6月に、理論的には 252 回でSHA-1での衝突を見つけられる攻撃法が報告された[6]。最近ではSHA-2などのより新しいSHAファミリに移行したり、衝突困難性を必要としない無作為化ハッシュ[7][8]などの技法を使って問題を回避している。
しかし、ハッシュ関数を応用しているものは多く、長期的な頑健性の保証は重要である。そのためSHA-2の後継となるSHA-3の公募が行われ[9]、2015年にFIPS規格として発行された。
次の表に挙げたアルゴリズムは、安全でないと分かっているものもある。それぞれのアルゴリズムの状態は、個々の項目を参照のこと。
| アルゴリズム | 出力長
（ビット） |
内部状態長 | ブロック長 | メッセージ長
（を表すビット数） |
ワード長 | 衝突攻撃
(complexity) |
原像攻撃
(complexity) |
|---|---|---|---|---|---|---|---|
| HAVAL | 256,
224, 192, 160, 128, |
256 | 1024 | 64 | 32 | Yes | |
| MD2 | 128 | 384 | 128 | No | 8 | Almost | |
| MD4 | 128 | 512 | 64 | 32 | Yes (2^1)[10] | With flaws (2^102)[11] | |
| MD5 | Yes (2^5) | No | |||||
| Panama | 256 | 8736 | 256 | No | Yes | ||
| RadioGatún | Arbitrarily long | 58 words | 3 words | 1-64 | |||
| RIPEMD | 128 | 512 | 64 | 32 | |||
| RIPEMD-128/256 | 128,
256 |
No | |||||
| RIPEMD-160/320 | 160,
320 | ||||||
| SHA-0 | 160 | Yes (2^39) | |||||
| SHA-1 | With flaws (2^52)[5] | No | |||||
| SHA-224, | 256,
224 |
256 | No | ||||
| SHA-384, | 384,
512, 224, 256 |
512 | 1024 | 128 | 64 | ||
| SHA3-224 | 224 | 1600 | 1152 | - | |||
| SHA3-256 | 256 | 1088 | |||||
| SHA3-384 | 384 | 832 | |||||
| SHA3-512 | 512 | 576 | |||||
| Tiger(2)-192/160/128 | 192,
160, 128 |
192 | 512 | 64 | |||
| Whirlpool | 512 | 512 | 256 | 8 | |||
| MINMAX | 256,
512 | ||||||
注: 「内部状態」とは、各データブロックを圧縮した後の「内部ハッシュ和」を意味する。多くのハッシュ関数は追加の変数として、それまでに圧縮したデータ長などの変数を保持しており、例えばデータ長がブロックに満たない場合のパディングに利用する。詳しくは Merkle-Damgård construction を参照。
脚注
編集注釈
編集- ^
0, 1, 00, 01, 10, 11, ...のようにして、1ビットずつメッセージの長さを伸ばしながら辞書順で探索するなどすればよい。強衝突耐性については探索に必要な時間に上界があることが鳩の巣原理によって言えるが、原像計算困難性については言えない。 - ^ h が誕生日に相当する。誕生日のパラドックスにあっても、重複する誕生日は任意に選んで構わない。
- ^ 証明は自明である。連結されたハッシュ関数での衝突を探すアルゴリズムは、明らかに個々の関数での衝突も見つけることができる。
- ^ さらに一般には、1つのハッシュ関数の「内部状態」での衝突を見つけられれば、全体への攻撃は単に個々の関数への誕生日攻撃と同程度の難しさでしかない。
出典
編集- ^ Antoine Joux. Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. LNCS 3152/2004, pp. 306-316 全文 (PDF)
- ^ Hal Finney, More problems with hash functions] - ウェイバックマシン（2016年4月9日アーカイブ分）2004年8月20日、 2023年9月2日閲覧。
- ^ Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger, MD5 considered harmful today: Creating a rogue CA certificate, accessed March 29, 2009
- ^ Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu, Finding Collisions in the Full SHA-12023年9月2日閲覧。
- ^ a b Bruce Schneier, Cryptanalysis of SHA-1 (summarizes Wang et al. results and their implications) 2023年9月2日閲覧。
- ^ Cameron McDonald, Philip Hawekes, and Josef Pieprzyk, Differential Path for SHA-1 with complexity O(252)
- ^ Shai Halevi, Hugo Krawczyk, Update on Randomized Hashing - ウェイバックマシン（2008年9月17日アーカイブ分）2023年9月2日閲覧。
- ^ Shai Halevi and Hugo Krawczyk, Randomized Hashing and Digital Signatures - ウェイバックマシン（2006年11月14日アーカイブ分）2023年9月2日閲覧。
- ^ CRYPTOGRAPHIC HASH ALGORITHM COMPETITION NIST.gov - Computer Security Division - Computer Security Resource Center] - ウェイバックマシン（2017年9月10日アーカイブ分）2023年9月2日閲覧。
- ^ Yu Sasaki, et al. (2007). New message difference for MD4.
- ^ Bart Preneel, Cryptographic Algorithms and Protocols for Network Security - ウェイバックマシン（2009年3月19日アーカイブ分）2023年9月2日閲覧。
参考文献
編集- Bruce Schneier. Applied Cryptography. John Wiley & Sons, 1996. ISBN 0-471-11709-9.