Cryptographic hash function

提供: tezos-wiki
移動先: 案内検索

このプロパティを使用すると、ハッシュ関数に基づいた素朴な認証スキームを破ることができます。 HMACの構築は、これらの問題を回避します。

実際には、衝突耐性は多くの実用には不十分である。 衝突抵抗に加えて、敵対者が実質的に同様のダイジェストを持つ2つのメッセージを見つけることは不可能であるべきである。またはそのダイジェストのみが与えられているデータに関する有用な情報を推論することができます。特に、決定論的かつ効率的に計算可能である一方で、ランダム関数(しばしばセキュリティの証明において[[ランダムなオラクル]と呼ばれる]のようにできるだけ振る舞うべきです。理想格子上の特定の問題が計算上困難であるが、線形関数としてこれらの追加の特性を満たさないと仮定すると、衝突耐性であることが厳密に証明できるSWIFFT関数のような関数は除外される。

CRC32やその他の[巡回冗長検査]などのチェックサムアルゴリズムは、はるかに弱い要件を満たすように設計されており、一般的に暗号ハッシュ関数としては不適切です。たとえば、 WEP暗号化規格ではメッセージの完全性にCRCが使用されましたが、チェックサムの直線性を利用した攻撃が容易に発見されました。

難易度[編集]

暗号の実践において、「難しい」とは、一般に、「システムのセキュリティが重要であるとみなされる限り、システムを破壊しないようにしなければならない敵の手の届く範囲をほぼ確実に超えている」ことを意味します。したがって、用語の意味はアプリケーションに多少依存します。なぜなら、悪意のあるエージェントがその作業に取り入れる努力は通常、彼の予想される利益に比例するからです。しかし、必要な努力はダイジェストの長さによって非常に迅速に増加するので、後者に数十ビットを加えることによって処理能力の1000倍の利点を中和することもできる。

パスワードやその他の短いメッセージなど、限られたメッセージセットから選択されたメッセージの場合、セット内のすべての可能なメッセージを試してハッシュを反転することが可能です。暗号ハッシュ関数は通常、迅速に計算されるように設計されているため、このようなブルー​​トフォース攻撃をより困難にする、より大きなコンピューティングリソースを必要とする特殊なキー導出関数が開発されています。

いくつかの理論的分析では、「困難」は「漸近多項式時間で解けない」などの特定の数学的意味を持つ。そのような難易度の解釈は、証明可能に安全な暗号ハッシュ関数の研究において重要であるが、通常、実際のセキュリティと強く結びついてはいない。例えば、指数関数アルゴリズムは、実行可能な攻撃を行うのに十分速い場合もあります。逆に、多項式時間アルゴリズム(例えば、n桁のキーに対してn <20>ステップを必要とするアルゴリズム)は、実際的な使用のためには遅すぎる可能性がある。

イラストレーション[編集]

暗号ハッシュの潜在的な使用例を以下に示します。 Alice Bobに厳しい数学的問題を提起し、解決したと主張します。 ボブはそれを自分自身で試してみたいと思っていますが、アリスが虚偽ではないことを確かめたいと思っています。 したがって、アリスは自分の解決策を書き留め、そのハッシュを計算し、(解決策を秘密にしながら)ハッシュ値をボブに伝える。 その後、Bobが数日後に解決策を提示すると、アリスはそれを明らかにしてボブにそれをハッシュし、前に与えられたハッシュ値と一致することを確認することで解決策を早期に見つけたことを証明することができます。 (これは単純な[コミットメントスキーム]の例です;実際には、アリスとボブはコンピュータプログラムであることが多く、秘密はパズルソリューションよりも簡単に偽装されていません)。

アプリケーション[編集]

ファイルやメッセージの完全性を確認する[編集]

安全なハッシュの重要なアプリケーションは、メッセージの整合性の検証です。たとえば、メッセージ(または[コンピュータファイル|ファイル])に変更が加えられたかどうかを判断するには、送信(または他のイベント)の前後で計算されたメッセージダイジェストを比較します。

このため、ほとんどの電子署名アルゴリズムは、メッセージのハッシュされたダイジェストの真正性を「署名」することのみを確認します。メッセージのハッシュダイジェストの真正性を確認することは、メッセージ自体が本物であるという証拠とみなされます。

MD5SHA1、またはSHA2ハッシュは、完全性の検証を可能にするために、Webサイトまたはフォーラムのファイルとともにポストされることがあります。このプラクティスは、HTTPSによって認証されたサイトにハッシュが投稿されている限り、Chain of trustを確立します。

パスワードの確認[編集]

関連するアプリケーションはパスワード検証(最初に[[Roger Needham]によって発明された)]です。すべてのユーザーパスワードをcleartextとして保存すると、パスワードファイルが侵害された場合に大規模なセキュリティ違反が発生する可能性があります。この危険性を減らす1つの方法は、各パスワードのハッシュダイジェストのみを保存することです。ユーザーを認証するために、ユーザーが提示したパスワードがハッシュされ、保管されたハッシュと比較されます。パスワードは、多くの場合、ランダムで秘密ではない]と連結されていることがあります(この方法では、元のパスワードが忘れたり紛失した場合に取り戻されることはありません。ハッシュ関数が適用される前の値。 saltはパスワードハッシュで保存されます。ユーザーは通常、異なる塩を持つので、塩が使用されている場合は、共通パスワードの事前計算済みハッシュ値の表を保存することは現実的ではありません。一方、標準的な暗号ハッシュ関数は、迅速に計算されるように設計されているため、高い確率で推測されたパスワードを試すことが可能です。一般的な[グラフィックス処理ユニット]は、毎秒何十億もの可能なパスワードを試すことができます。 PBKDF2bcryptscryptのようなKey stretching関数は、通常、暗号化ハッシュの繰り返し呼び出しを使用して、格納されたパスワードダイジェストに対してブルートフォース攻撃を実行する。

2013年に、[パスワードハッシング競争]が発表され、パスワードハッシングのための新しい標準アルゴリズムが選択されました。 2015年7月に選ばれた優勝者は、新たなキーストレッチアルゴリズム[Argon2]でした。 2017年6月、NISTはデジタル認証ガイドラインNIST SP 800-63B-3の新しい改訂版を発行しました。「検証者は、暗記された秘密[すなわちパスワード]をオフライン攻撃に耐えられる形で格納しなければなりません。適切な一方向[キー導出関数]を使用してハッシュします。

実績[編集]

仕事の証明システム(またはプロトコルや機能)は、サービス依頼者から何らかの作業を要求することによって、ネットワーク上の迷惑メールなどのサービス拒否攻撃を阻止するための経済的対策です。通常、コンピュータによる処理時間を意味します。これらのスキームの主な特徴は、アシンメトリーです。要求者側では作業は適度に難しい(ただし実行可能である)必要がありますが、サービスプロバイダを確認するのは簡単です。 BitcoinマイニングHashcashで使われている一般的なシステムの1つは、部分的なハッシュ逆変換を使って、作業が完了したことを証明し、Bitcoinのマイニング報酬を解除し、ハッシュカードで送信者は、ハッシュ値が0ビットの数で始まるメッセージを見つける必要があります。有効なメッセージを見つけるために送信者が実行する必要のある平均作業は、ハッシュ値に必要なゼロビット数で指数関数的ですが、受信者は単一のハッシュ関数を実行してメッセージの有効性を検証できます。例えば、Hashcashでは、送信者は160ビットのSHA-1ハッシュ値が最初の20ビットが0であるヘッダーを生成するように要求されます。送信者は平均して有効なヘッダーを見つける時間を試す必要があります。

ファイルまたはデータ識別子[編集]

メッセージダイジェストは、ファイルを確実に識別する手段としても機能します。 Git、[Mercurial(software)| Mercurial]や[[Monotone(software)| Monotone]など、いくつかのソースコード管理システムは、それらを一意に識別するための様々なタイプのコンテンツ(ファイルコンテンツ、ディレクトリツリー、祖先情報など)のsha1sumハッシュは、peer-to-peer filesharingネットワーク上のファイルを識別するために使用されます。例えば、ed2kリンクでは、MD4 - 変形ハッシュがファイルサイズと組み合わされ、ファイルソースの場所を特定し、ファイルをダウンロードし、その内容を検証するのに十分な情報を提供します。 Magnet linksは別の例です。このようなファイルハッシュは、多くの場合、ハッシュリストまたはハッシュツリーの先頭のハッシュです。

ハッシュ関数の主な用途の1つは、ハッシュテーブル内のデータの高速ルックアップを可能にすることです。特定の種類のハッシュ関数であるため、暗号化ハッシュ関数もこのアプリケーションに適しています。

しかし、標準的なハッシュ関数と比較して、暗号ハッシュ関数は計算上非常に高価になる傾向があります。このため、ユーザーは、潜在的な悪意のある参加者によって、偽造(予想されるデータと同じダイジェストを持つデータの作成)の可能性からユーザーを保護する必要がある場合に使用される傾向があります。

擬似乱数の生成と鍵の導出[編集]

ハッシュ関数は、擬似乱数ビットの生成、または単一の安全な鍵またはパスワードからの新しい鍵またはパスワードの派生にも使用できます。

ブロック暗号に基づく関数をハッシュする[編集]

ブロック暗号を使って暗号ハッシュ関数、具体的には片方向圧縮関数を構築する方法はいくつかあります。

このメソッドは、通常は暗号化に使用される操作のブロック暗号モードに似ています。 MD4MD5SHA-1SHA-2などのよく知られている多くのハッシュ関数は、この目的のために設計されたブロック暗号のようなコンポーネントで構築されています。結果の関数が可逆でないことを保証するフィードバック。最終選考者には、ブロック暗号のようなコンポーネント(例えば[Skeinハッシュ関数| Skein]、[[BLAKE(ハッシュ関数)| BLAKE]など)を持つ関数が含まれていました。最終的にKeccakが選択され、代わりに暗号スポンジ上に構築されました。

これらのカスタムブロック暗号の代わりに、 AESなどの標準ブロック暗号を使用することができます。 組み込みシステムが最小限のコードサイズまたはハードウェア領域で暗号化とハッシングの両方を実装する必要がある場合に役立つ可能性があります。しかし、そのアプローチは効率とセキュリティにコストをかける可能性があります。ハッシュ関数の暗号はハッシュ用に作られています。大きな鍵とブロックを使用し、ブロックごとに効率的に鍵を変更し、[[関連する鍵の攻撃]に抵抗するように設計され検証されています。汎用暗号は異なる設計目標を持つ傾向があります。特に、AESには、長いハッシュ値を生成するために使用することが重要でないように、鍵サイズとブロックサイズがあります。キーが各ブロックを変更すると、AES暗号化の効率が低下します。および関連キー攻撃は、ハッシュ関数での使用が暗号化よりも安全性が低くなる可能性があります。

ハッシュ関数の設計[編集]

メルクル - ダムガード事件[編集]

ファイル:Merkle-Damgard hash big.svg
The Merkle–Damgård hash construction.

このセクションは、一方向圧縮機能に大部分が重複しています。両方ともMerkle-Damgårdconstructionに移動する必要があります。 ハッシュ関数は、任意の長さのメッセージを固定長の出力に処理できなければなりません。これは、入力を一連の等しいサイズのブロックに分割し、一方向圧縮機能を使用して順番に操作することで実現できます。圧縮機能は、ハッシュ用に特別に設計されたものでも、ブロック暗号から構築されたものでもよい。 Merkle-Damgård構造で構築されたハッシュ関数は、圧縮関数と同じくらい衝突に耐性があります。完全なハッシュ関数に対する任意の衝突は、圧縮関数における衝突に引き戻すことができる。

処理された最後のブロックも明白に長さが埋められる;これはこの建設の安全にとって非常に重要です。この構造はMerkle-Damgårdconstructionと呼ばれています。 SHA-1MD5を含む最も一般的な古典的なハッシュ関数は、この形式をとっています。

ワイドパイプ対ナローパイプ[編集]

ハッシュ出力のサイズが(各圧縮ステップの間の)内部状態サイズと等しいMerkle-Damgård構造の簡単なアプリケーションは、「狭パイプ」ハッシュ設計になります。 この設計は、長さ拡張、マルチ衝突、長いメッセージ攻撃、生成と貼り付けの攻撃を含む多くの固有の欠陥を引き起こし、また並列化できません。 その結果、現代のハッシュ関数は、より大きな内部状態サイズを持つ「ワイドパイプ」構造上に構築されます。これは、Merkle-Damgård構造の調整からです。NISTハッシュ関数競技 古典的なMerkle-Damgård構造を使用します。

一方、SHA-512/256で使用されているような長いハッシュの出力を切り捨てると、これらの攻撃の多くが無効になります。

他の暗号プリミティブの構築に使用[編集]

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

メッセージ認証コード(MACs)(キー付きハッシュ関数とも呼ばれる)は、多くの場合、ハッシュ関数から構築されます。 HMACはそのようなMACです。

ハッシュ関数を構築するためにblock cipherを使うことができるように、ハッシュ関数を使ってブロック暗号を構築することができます。ハッシュ関数を使用するLuby-Rackoff構造は、基礎をなすハッシュ関数が安全であるならば、確かに安全です。また、SHA-1SHA-2を含む多くのハッシュ関数は、 Davies-Meyerまたはその他の工事である。その暗号は、同じセキュリティ保証なしに、従来の動作モードでも使用できます。 SHACAL BEAR LIONを参照してください。

擬似乱数生成器 s(PRNGs)は、ハッシュ関数を使って構築できます。これは、(シークレット)ランダムシードとカウンタを組み合わせてハッシュすることによって行われます。

ハッシュ関数([Skein(ハッシュ関数)| Skein]、Keccak、[[RadioGatún]など)は、任意の長いストリームを出力し、ストリーム暗号として使用でき、ストリーム暗号は固定長のダイジェストハッシュ関数から構築することもできます。しばしば、[[暗号的に安全な擬似乱数生成器]を構築してから、ランダムなストリームのストリームをkeystreamとして使用してこれを行います。 SEALSHA-1を使用して内部テーブルを生成し、ハッシュアルゴリズムとは多少関係のないキーストリームジェネレータで使用されるストリーム暗号です。 SEALはSHA-1と同じくらい強い(または弱い)ことは保証されていません。同様に、 HC-128およびHC-256ストリーム暗号のキー拡張は、 SHA-256ハッシュ関数を大量に使用します。

連結[編集]

複数のハッシュ関数からの連結出力は、連結結果に含まれるアルゴリズムのうち最も強いものと同じくらい良好な衝突耐性を提供します。たとえば、[[Transport Layer Security | TLS(Transport Layer Security)とSSL(Secure Sockets Layer)]の古いバージョンでは、連結MD5SHA-1の合計が使用されます。 これにより、ハッシュ関数の1つの衝突を検出するメソッドが、両方のハッシュ関数によって保護されたデータを無効にすることはありません。

Merkle-Damgårdconstructionハッシュ関数の場合、連結された関数は最も強いコンポーネントとして衝突耐性を持ちますが、それ以上の衝突耐性はありません。 [Antoine Joux]は、2つの衝突がn個の衝突を引き起こすことを観察しました。攻撃者が同じMD5ハッシュを持つ2つのメッセージを見つけることが可能な場合、攻撃者は同じMD5ハッシュで攻撃者が望む数のメッセージを見つけることができます大きな困難はありません。同じMD5ハッシュを持つn個のメッセージのうち、SHA-1には衝突が発生する可能性があります。 SHA-1の衝突(指数関数的な誕生日の探索を超える)を見つけるために必要な追加の作業は、多項式時間だけで済みます。

暗号ハッシュアルゴリズム[編集]

暗号化ハッシュ関数は長いリストがありますが、多くのものが脆弱であることが判明しており、使用すべきではありません。ハッシュ関数が壊れていない場合でも、成功した攻撃が弱体化したものに対して、専門家の信頼が損なわれ、その放棄につながる可能性があります。例えば、2004年8月に、SHA-0、RIPEMD、MD5を含む人気のあるいくつかのハッシュ関数に弱点が発見されました。これらの弱点は、SHA-1(強化版SHA-0)、RIPEMD-128、およびRIPEMD-160(いずれもRIPEMDの強化バージョン)の弱いハッシュ関数から導かれた、より強力なアルゴリズムのセキュリティに疑問を投げかけました。 SHA-0もRIPEMDも、強化バージョンに置き換えられているため、広く使用されていません。

2009年現在、2つの最も一般的に使用される暗号ハッシュ関数はMD5SHA-1でした。しかし、MD5に対する攻撃が成功したことで、2008年にTransport Layer Securityが破られました。

米国[国家安全保障局(NSA)]はSHA-0SHA-1を開発した。

2004年8月12日、Joux、Carribault、Lemuet、およびJalbyは、完全なSHA-0アルゴリズムの衝突を発表しました。 JouxらChabaud攻撃とJoux攻撃の一般化を使ってこれを達成しました。彼らは、衝突が複雑さ2 1 51を有することを発見した。スーパーコンピュータのフルタイム使用の13日間に相当する、Itanium 2プロセッサを搭載したスーパーコンピュータで約80,000 CPU時間を費やしました。

2005年2月には、SHA-1に対する攻撃が報告され、約2 69 / 2&apos; 80&apos;&apos;&apos; 160ビットのハッシュ関数が必要です。 2005年8月に、SHA-1に対するもう1つの攻撃が報告されたが、これは2&apos; 63&apos;オペレーション。 SHA-1の理論的な弱点が存在し、2017年2月、GoogleはSHA-1で衝突を発表しました。セキュリティ研究者は、SHA-2などのSHAファミリの後のメンバーを使用するか、または衝突抵抗を必要としないランダム化されたハッシュなどの技術を使用して、新しいアプリケーションがこれらの問題を回避できることを推奨します。

しかし、ハッシュ関数を使用するアプリケーションの長期的な堅牢性を保証するために、SHA-2の代替品を設計するための[NISTハッシュ関数競争|競争]がありました。 2012年10月2日、Keccakは NISTハッシュ関数競争の優勝者に選ばれました。このアルゴリズムのバージョンは、[[SHA-3]という名前で2015年8月5日に[Federal Information Processing Standards | FIPS]標準になりました。

NISTのハッシュ関数コンテストのもう一つのファイナリスト BLAKEは、SHA-3、SHAより高速であることが注目される[[BLAKE(ハッシュ関数)#BLAKE2 | BLAKE2] -2、SHA-1、またはMD5であり、多くのアプリケーションおよびライブラリで使用されています。

関連項目[編集]

ソース[編集]

http://wikipedia.org/