開発者ツール · SHA ハッシュ計算ツール
Merkle–Damgård の説明: SHA-1 および SHA-2 の背後にある構造
· 背景
しゃ-256 暗号化 ブラウザ API
固定サイズ圧縮関数は、それ自体で任意の入力をハッシュすることはできません。 Merkle-Damgård はブロックごとにチェーンします。この投稿では、その構造、その証明のアイデア、およびそれが抱える弱点について説明します。
任意の入力、固定出力 - すべてのハッシュ関数が最初に解決しなければならない問題
ハッシュ関数は、任意の入力を固定出力にマップする必要があります。 3 バイトのメッセージと 3 メガバイトのメッセージは両方とも、SHA-256 に対して正確に 256 ビットの出力を生成する必要があります。ハッシュは決定論的である必要があるため、同じ入力から常に同じ出力が生成されます。出力はランダムに見える必要があります。入力の 1 ビットを変更すると、出力ビットのおよそ半分が変更されるはずです。
これらは一見すると矛盾する要件です。単一の高速アルゴリズムでは任意の長さのメッセージを処理できず、均一な固定幅の出力を生成できないためです。 Merkle-Damgård 構造では、固定サイズの圧縮関数を繰り返し使用し、各アプリケーションの出力を次のアプリケーションの入力に送り込むことで、この問題を解決します。この構造は、SHA-1 とすべての SHA-2 (SHA-256、SHA-384、および SHA-512) で使用されます。
圧縮関数 — 状態とブロックを受け取り、新しい状態を返す固定サイズのミキサー
圧縮関数は、マークル-ダムガード ハッシュを強化するコア暗号プリミティブです。通常、固定サイズの状態 (SHA-256 の場合は 256 ビット、SHA-512 の場合は 512 ビット)、および固定サイズの入力ブロック (通常、SHA-256 の場合は 512 ビット、SHA-512 の場合は 1024 ビット) を受け取ります。圧縮関数は、ビット単位の演算、回転、テーブル検索を使用してこれらを混合し、同じサイズの新しい状態を生成します。この関数は衝突耐性がなければなりません。同じ出力を生成する 2 つの異なる (状態、ブロック) ペアを見つけるのは困難でなければなりません。
圧縮関数自体は完全なハッシュ関数ではありません。任意の入力長を処理せず、以前の状態を持たない最初の入力さえも処理しません。代わりに、それはより大きな構造物を構築するための基礎となるブロックです。圧縮関数は、繰り返し実行される唯一の暗号操作です。他のすべては、この関数を完全なハッシュに結び付ける簿記です。
チェーンと初期化ベクトル - ブロックが固定開始状態からどのように相互に供給されるか
初期化ベクトルは固定開始状態であり、対称性や弱点を避けるために慎重に選択されます。 SHA-256 の場合、IV は、最初の 8 つの素数の平方根の小数部から導出される 8 つの 32 ビット ワードです。これらの値は任意ですが決定的であるため、どの実装でも同じ結果が生成されます。最初のメッセージ ブロックは、圧縮関数を使用して IV と混合され、新しい状態が生成されます。 2 番目のメッセージ ブロックはその状態と混合され、別の新しい状態が生成され、メッセージのブロックごとに同様に繰り返されます。
この連鎖は重要な部分です。1 つのブロックの出力は前のすべてのブロックに依存するため、前のブロックの任意のビットを変更すると、後続のすべてのブロックが変更されます。最後のブロックが処理されるまでに、状態には入力のすべてのビットに関する情報が含まれます。パディングは、この構造を効果的にするためのトリックです。メッセージは必ずしも均等にブロックに分割されるわけではありません。 Merkle-Damgård 構造では MD 強化が使用されます。メッセージに 1 ビットを追加し、ほぼ完全なブロックが残るまでゼロを追加し、その後、元のメッセージの長さを追加します。
メッセージの長さによるパディング — MD 強化が構築を健全にする理由
Merkle-Damgård のセキュリティ引数は、圧縮関数が衝突耐性がある場合、ハッシュ全体も衝突耐性があると述べています。その証拠は還元です。ハッシュ内で衝突を見つけることができれば、圧縮関数内で衝突を抽出できます。これは、圧縮関数が衝突しにくいという仮定に矛盾します。直感的には、状態が完全に引き継がれるため、ハッシュ内の衝突は最終的に圧縮関数呼び出しの 1 つで衝突を引き起こすはずです。
基本構造は健全であっても、時間の経過とともにメルクル・ダムガルドの弱点が発見されました。長さの拡張は 1 つです。メッセージのダイジェストを見た攻撃者は、入力について何も知らなくてもメッセージを拡張し、より長いメッセージの有効なダイジェストを計算できます。 2 番目のプリイメージ攻撃は別のものです。メッセージが与えられた場合、同じハッシュを持つ別のメッセージを見つけることは、ある種のメッセージの場合よりも簡単です。これらの弱点を考慮して、スポンジ構造と呼ばれる別のアプローチを使用する SHA-3 の設計が行われました。
長さエンコーディングのパディングにより、パディングされたメッセージが分離されます。完全なセキュリティ証明はリポジトリの証拠の外にある
SHA-256 の圧縮関数は、256 ビット状態 (8 つの 32 ビット ワード) と 512 ビット ブロックを取ります。この操作では 64 ラウンドを使用し、各ラウンドで状態と定数およびブロックのワードを混合します。混合にはビット単位の演算 (XOR、AND、NOT) が使用されます。設定されているビットを変更せずにビットを移動する回転とシフトを使用します。 XOR だけでは実現できない非線形混合を実現するテーブル ルックアップを使用します。
SHA-512 は SHA-256 と同じ構造を使用しますが、32 ビット操作ではなく 64 ビット操作を使用します。状態は 512 ビット (8 つの 64 ビット ワード)、ブロック サイズは 1024 ビットです。圧縮関数には 64 ではなく 80 ラウンドがあり、定数とテーブル ルックアップが異なります。 SHA-384 の場合、状態と圧縮関数は SHA-512 と同じですが、最終状態の最初の 384 ビットのみが出力されます。最後の 128 ビットは破棄されます。この切り詰めが、SHA-384 が長さの延長に耐えられる理由です。
長さの延長は検証された建設境界です。マルチコリジョンと SHA-3 動機付けクレームは省略されています
マークル-ダムガード ハッシュのセキュリティは、保持するいくつかのプロパティに依存します。圧縮関数は衝突耐性がなければならないため、直接攻撃することは不可能です。パディング スキームでは、メッセージごとに異なるパディング形式が生成されるようにする必要があるため、ハッシュ内のすべての衝突には圧縮関数の衝突が含まれる必要があります。ブロック サイズと状態サイズは、ブルート フォースが実行できないほど十分に大きくなければなりません。州が広いほど一般的な検索スペースが拡大しますが、この記事では、インライン導出とレビューされたソースがなければ、操作数や実現可能性の日付は添付されていません。
攻撃者が圧縮関数の弱点を発見した場合、または量子コンピューターが実用化されて非構造化空間を 2^n 時間ではなく sqrt(2^n) 時間で検索できるようになった場合、セキュリティ マージンは侵食されます。 SHA-3 の原因となった弱点は、圧縮機能の破損ではなく、長さの拡張の問題とその他の構造的な脆弱性でした。スポンジ構造は、完全な内部状態を決して公開しないことで、これらを回避します。
これでカバーされないもの — SHA-256 の特定のラウンド関数については、別の投稿で説明します
Merkle-Damgård 構造があらゆる入力サイズをどのように処理するかは、その設計の実際的な結果です。メッセージを 512 ビット ブロックに分割し、最後のブロックをパディングし、圧縮関数を通じて各ブロックを順番に処理して、最終状態を出力します。 1 バイト入力の場合、パディングにより 512 ビット ブロック (1 バイトのメッセージ、1 ビットのパディング、447 ビットのゼロ、および 64 ビットの長さ) が生成されます。圧縮の数は 512 ビット ブロックの数であり、メッセージの長さに比例します。
ToolAcre SHA ハッシュ計算ツールが生成するすべてのダイジェストは、この構造に基づいています。 64 文字の SHA-256 ダイジェストは、16 進数で出力された最終的な 256 ビットの状態です。 128 文字の SHA-512 ダイジェストは、16 進数で出力された最終的な 512 ビットの状態です。 96 文字の SHA-384 ダイジェストは、最終的な 512 ビット状態の最初の 384 ビットです。バックグラウンドでのパディングにより、考えられるすべてのメッセージが正確に正しいブロック数と正しいダイジェスト幅を生成することが保証されます。これは、ブラウザで実行される標準のマークル-ダムガード構造です。
要点: 4 つのアルゴリズムの背後にある同じスケルトン — ToolAcre SHA ハッシュ計算ツールが生成するすべてのダイジェストはこの構造から来ています
この構造を理解することは、ダイジェストが常に同じ幅である理由、および入力の 1 ビットを変更するとダイジェスト全体が変更される理由を知るのに役立ちます。連鎖特性は、入力のすべてのビットが、一連のミキシング操作を通じて出力のすべてのビットに影響を与えることを意味します。メッセージの初期の 1 ビットの変更は、その後のすべての圧縮に反映されるため、最終的なダイジェストは完全に異なります。この特性は雪崩効果と呼ばれ、サウンド ハッシュ関数の特徴です。
Merkle-Damgård 構造は数十年にわたって使用されており、最も広く導入されているハッシュ関数の基礎を形成しています。 SHA-1 および SHA-2 はこの構造に基づいて構築されており、導入された多くのシステムはその出力に依存しています。この構造は実験的なものではなく確立されたものですが、その歴史がすべての使用を安全にするわけではありません。長さの延長は、文書化された 1 つの境界です。この構造を理解することは、開発者が特定のセキュリティ特性が保持される理由、および特定の攻撃ベクトルが存在する理由を理解するのに役立ちます。