暗号学的ハッシュ関数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
暗号におけるハッシュ関数(特にSHA-1)の動作の様子。入力の微妙な変化で出力が大きく変化する点に注意(雪崩効果

暗号学的ハッシュ関数: cryptographic hash function)は、任意長のデータブロックを入力とし、固定長ビット列である(暗号学的)ハッシュ値を返す決定的手順である。偶然または意図的なデータの改竄によって、そのハッシュ値も変化する。符号化されたデータは「メッセージ (message)」と呼ばれることが多いので、ハッシュ値をメッセージダイジェスト (message digest) と呼ぶ。これを、単にダイジェスト (digest) と呼ぶこともある。

理想的な暗号学的ハッシュ関数は次の4つの特性をもつ。

  • 与えられたメッセージに対してハッシュ値が容易に計算できる。
  • ハッシュ値から元のメッセージを得ることが事実上不可能であること。
  • ハッシュ値を変えずにメッセージを改竄することが事実上不可能であること。
  • 同じハッシュ値をもつ2つのメッセージを求めることが事実上不可能であること。

暗号学的ハッシュ関数は情報セキュリティ分野で様々に利用されており、特にデジタル署名メッセージ認証符号 (MAC)、その他の認証技術で使われている。通常のハッシュ関数としても利用でき、ハッシュテーブルのインデックス、フィンガープリント、重複データの検出、ファイルの一意な識別、データの誤りを検出するチェックサムなどの用途がある。情報セキュリティの文脈では、ハッシュ値のことをフィンガープリントチェックサムなどとも呼ぶが、実際にはこれらの特性や目的はそれぞれ異なる。

特性[編集]

暗号学的ハッシュ関数の多くは、可変長の文字列を入力とし、固定長のハッシュ値を生成する。

暗号学的ハッシュ関数は既知の全暗号攻撃法に耐性がなければならない。少なくとも、次のような特性が必須である。

原像計算困難性 (preimage resistance)
ハッシュ値 h が与えられたとき、そこから h = hash(m) となるような任意のメッセージ m を探すことが困難でなければならない。これは一方向性関数の原像計算困難性に関連している。この特性がない関数は原像攻撃に対して脆弱である。
第2原像計算困難性 (second preimage resistance)
入力 m1 が与えられたとき、hash(m1) = hash(m2) となるようなもう1つの入力 m2m1とは異なる入力)を見つけることが困難でなければならない。これを「弱衝突困難性 (weak collision resistance)」ともいう。この特性がない関数は第2原像攻撃に対して脆弱である。
衝突困難性 (collision resistance)
hash(m1) = hash(m2) となるような2つの異なるメッセージ m1m2 を探すことが困難でなければならない。このような組を衝突と呼び、この特性を「強衝突困難性 (strong collision resistance)」ともいう。原像計算困難性を持つハッシュ値よりも少なくとも2倍の長さのハッシュ値を必要とし、さもなくば誕生日攻撃によって衝突を探し当てられる可能性がある。

これらの特性は、悪意ある攻撃者でもダイジェストを変化させずに入力データを改竄できないことを示すものである。したがって、2つの文字列のダイジェストが同じ場合、それらが同一のメッセージである可能性は非常に高い。

これらの基準に適合した関数でも、好ましくない特性を持つものがありうる。現在よく使われている暗号学的ハッシュ関数は length-extension 攻撃に対して脆弱である。すなわち、ハッシュ値 h(m) とメッセージ長 len(m) が分かっていて m そのものは不明の場合、適当な m を選んで h (m || m') を計算できる。ここで、|| はメッセージの連結を意味する。この特性を利用して、ハッシュ関数に基づく単純な認証方式を破ることが可能である。HMACはこの問題への対策として考案された。

理想的には、さらに強い条件を課すこともできる。例えば、悪意ある者が非常に良く似たダイジェストを生成する2つのメッセージを見つけることができないのが望ましい。また、ダイジェストのみから元のデータについて何らかの有用な情報を推測できないのが望ましい。したがって暗号学的ハッシュ関数は可能な限りランダム関数のように振舞うが、決定性と計算効率は維持しなければならない。

CRC32などの巡回冗長検査に代表されるチェックサムアルゴリズムは、要求される条件が上記よりも弱く、そのまま暗号学的ハッシュ関数として使うのは一般に推奨されない。例えば、CRCはWEPでのメッセージ完全性保証に使われていたが、チェックサムの線形性を利用して簡単に攻撃が可能となった。

「困難」の意味[編集]

暗号について「困難 (hard)」と言った場合、一般に「攻撃者がどんな手段を使ってシステムを破ろうとしてもほぼ確実に防げる」ことを意味する。したがって、用途によって具体的な意味に若干の差がある。なぜなら、得られるものが大きいほど攻撃者は攻撃に手間をかけると予想されるからである。しかし、ダイジェストの長さが大きくなるとそれを破るのに必要な手間は急激に増大していくので、数ビット長くしただけでも数千倍の攻撃努力に対抗できるようになる。

計算複雑性理論では「困難 (hard)」という用語は特定の意味を持つ。しかしここでいう「困難」は、それとはほとんど関係がない。

用途[編集]

暗号学的ハッシュ関数の典型的な利用例を以下に示す。アリスは難しい数学問題をボブに提示し、彼女自身はそれを解いたと主張する。ボブも解いてみたいが、その前にアリスがはったりをかましていないことを確認したい。そこでアリスは自分の解答にランダムな文字列 (nonce) を付け、そのハッシュ値を計算し、ボブにハッシュ値を知らせる(この時点では解答そのものとnonceは秘密にしておく)。何日かしてボブがその問題を解くと、アリスはnonceと自分の解答をボブに示すことで、既にその問題を解いていたことを証明できる。これはコミットメントスキームの簡単な例である。実際にはアリスとボブはコンピュータプログラムであることが多く、秘密にされることは数学問題の解法などといったものではなく、もっと簡単に改竄できるものである。

安全なハッシュのもう1つの重要な用途として、データ完全性の検証がある。メッセージ(あるいはファイル)に改変が加えられているかの判定であり、例えばメッセージを転送する前と後でメッセージダイジェストを計算し、比較することで検証する(転送以外の事象の前後でもよい)。

メッセージダイジェストは確実にファイルを識別する手段としてバージョン管理システムで使われている(例えば、GitMercurialMonotone)。また、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 で構築されたハッシュ関数は、その圧縮関数と同程度の衝突困難性がある。ハッシュ関数全体で発生する衝突は、圧縮関数での衝突に起因する。

最後のブロックには明らかにパディングが必要で、この部分はセキュリティ上重要である。このような構築法を Merkle-Damgård construction と呼ぶ。SHA-1MD5などのよく使われているハッシュ関数はこの形式である。

この構築法の本質的欠点として、length-extension 攻撃や generate-and-paste 攻撃に弱く、並列処理できないという点が挙げられる。結果として現在公募され評価中のSHA-3の候補の多くは全く異なる構築法を採用しており、一部は全く新しい方式を採用している。

他の暗号プリミティブ構築における利用[編集]

ハッシュ関数は他の暗号プリミティブの構築に使える。それらプリミティブが暗号学的に安全であるためには、正しく構築するよう注意が必要となる。

メッセージ認証符号 (MAC) はハッシュ関数から構築することが多い。例えばHMACがある。

ブロック暗号を使ってハッシュ関数を構築できると同時に、ハッシュ関数を使ってブロック暗号を構築できる。Feistel構造で構築されたブロック暗号は、使用したハッシュ関数が安全である限り、その暗号自体も安全であると言える。また多くのハッシュ関数(SHAなど)は専用のブロック暗号を使い Davis-Mayer などの構成法で構築されている。その暗号はブロック暗号として従来のモードでも使えるが、同程度のセキュリティは保証できない。

擬似乱数生成器 (PRNG) はハッシュ関数を使って構築できる。この場合(秘密の)乱数種とカウンタをハッシュに利用する。

ストリーム暗号はハッシュ関数を使って構築できる。多くの場合、暗号論的擬似乱数生成器をまず構築し、それが生成するランダムなバイト列を鍵ストリームとして使用する。SEALというストリーム暗号はSHA-1を使って内部の表を生成し、その表は鍵ストリーム生成に使われる。

ハッシュ関数の連結[編集]

複数のハッシュ関数の出力を連結すると、連結対象のハッシュ関数のうち最強のものと少なくとも同等以上の衝突困難性を提供できる[1]。例えば、TLS/SSLMD5SHA-1を連結して利用している。これにより、どちらか一方が破られても全体としてはセキュリティを保てるようにしている。

しかし、Merkle-Damgård で構成したハッシュ関数は連結しても個々のハッシュ関数と同等な強度にしかならず、より強くなることはない[2]。Joux[3]によれば、MD5のハッシュ値が同じになる2つのメッセージを見つけることができれば、攻撃者がさらに同じハッシュ値となるメッセージを見つけることは簡単である。MD5で衝突を起こす多数のメッセージの中にはSHA-1でも衝突を起こすものもありうるだろう。そうなれば、SHA-1での衝突を探すのに必要な時間は多項式時間でしかない。この論旨は Hal Finney が要約している[4]

アルゴリズム[編集]

暗号学的ハッシュ関数は多数存在するが、その多くは脆弱性が判明し、使われなくなっている。ハッシュ関数自体が破られたことがなくとも、それを弱めたバリエーションへの攻撃が成功すると専門家が徐々にそのハッシュ関数への信頼を失い、結果として使われなくなることもある。実際、2004年8月、当時よく使われていたハッシュ関数(SHA-0、RIPEMD、MD5など)の弱点が判明した。このことから、これらのハッシュ関数から派生したアルゴリズム、特にSHA-1(SHA-0を強化したもの)とRIPEMD-128とRIPEMD-160(RIPEMDを強化したもの)の長期的なセキュリティに疑問が投げかけられた。SHA-0とRIPEMDは既に強化されたバージョンに置換され、使われなくなっている。

2009年現在、最も広く使われている暗号学的ハッシュ関数はMD5SHA-1である。しかし、MD5は既に破られており、2008年にはSSLへの攻撃にその脆弱性が利用された[5]

SHA-0とSHA-1はNSAの開発したSHAファミリに属する。2005年2月、SHA-1について160ビットのハッシュ関数に期待される 280 回の操作より少ない 269 回のハッシュ生成で衝突を見つける攻撃法が報告された。2005年8月、今度は 263 回で衝突を見つける攻撃法の報告があった。SHA-1には理論上の弱点も指摘されており[6][7]、数年で解読されるという示唆もある。さらに2009年6月、理論的には 252 回でSHA-1での衝突を見つけられる攻撃法が報告された[8]。最近ではSHA-2などのより新しいSHAファミリに移行したり、衝突困難性を必要としない無作為化ハッシュ[9][10]などの技法を使って問題を回避している。

しかし、ハッシュ関数を応用しているものは多く、長期的な頑健性の保証は重要である。そのためSHA-2の後継となるSHA-3の公募が行われ、今後FIPS規格となる予定である[11]

次の表に挙げたアルゴリズムは、安全でないと分かっているものもある。それぞれのアルゴリズムの状態は個々の項目を参照のこと。

アルゴリズム 出力長(ビット) 内部状態長 ブロック長 メッセージ長(を表すビット数) ワード長 衝突攻撃 (complexity) 原像攻撃 (complexity)
HAVAL英語版 256/224/192/160/128 256 1024 64 32 Yes
MD2 128 384 128 No 8 Almost
MD4 128 128 512 64 32 Yes (2^1)[12] With flaws (2^102)[13]
MD5 128 128 512 64 32 Yes (2^5) No
Panama英語版 256 8736 256 No 32 Yes
RadioGatún英語版 Arbitrarily long 58 words 3 words No 1-64 Yes
RIPEMD 128 128 512 64 32 Yes
RIPEMD-128/256 128/256 128/256 512 64 32 No
RIPEMD-160/320 160/320 160/320 512 64 32 No
SHA-0 160 160 512 64 32 Yes (2^39)
SHA-1 160 160 512 64 32 With flaws (2^52)[7] No
SHA-224, SHA-256 256/224 256 512 64 32 No No
SHA-384, SHA-512, SHA-512/224, SHA-512/256 384/512/224/256 512 1024 128 64 No No
SHA3-224 224 1600 1152 - 64 No No
SHA3-256 256 1600 1088 - 64 No No
SHA3-384 384 1600 832 - 64 No No
SHA3-512 512 1600 576 - 64 No No
Tiger(2)-192/160/128英語版 192/160/128 192 512 64 64 No
Whirlpool 512 512 512 256 8 No
MINMAX 256/512 512 512 256 8 No

注: 「内部状態」とは、各データブロックを圧縮した後の「内部ハッシュ和」を意味する。多くのハッシュ関数は追加の変数として、それまでに圧縮したデータ長などの変数を保持しており、例えばデータ長がブロックに満たない場合のパディングに利用する。詳しくは Merkle-Damgård construction を参照。

関連項目[編集]

脚注・出典[編集]

  1. ^ 証明は自明である。連結されたハッシュ関数での衝突を探すアルゴリズムは明らかに個々の関数での衝突も見つけることができる。
  2. ^ さらに一般には、1つのハッシュ関数の「内部状態」での衝突を見つけられれば、全体への攻撃は単に個々の関数への誕生日攻撃と同程度の難しさでしかない。
  3. ^ Antoine Joux. Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. LNCS 3152/2004, pages 306-316 全文.
  4. ^ Hal Finney, More problems with hash functions, 2004年8月20日
  5. ^ 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
  6. ^ Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu, Finding Collisions in the Full SHA-1
  7. ^ a b Bruce Schneier, Cryptanalysis of SHA-1 (summarizes Wang et al. results and their implications)
  8. ^ Cameron McDonald, Philip Hawekes, and Josef Pieprzyk, Differential Path for SHA-1 with complexity O(252)
  9. ^ Shai Halevi, Hugo Krawczyk, Update on Randomized Hashing
  10. ^ Shai Halevi and Hugo Krawczyk, Randomized Hashing and Digital Signatures
  11. ^ CRYPTOGRAPHIC HASH ALGORITHM COMPETITION NIST.gov - Computer Security Division - Computer Security Resource Center
  12. ^ Yu Sasaki, et al. (2007). New message difference for MD4. http://www.iacr.org/archive/fse2007/45930331/45930331.pdf. 
  13. ^ Bart Preneel, Cryptographic Algorithms and Protocols for Network Security

参考文献[編集]