ハッシュの詳細

投稿日: 2022-10-19 2022-10-19
タグ: Programming

1. 序章

ハッシュは、アルゴリズム、データ構造、および暗号化で広く使用されています。

このチュートリアルでは、ハッシュとそのアプリケーション領域について詳しく説明します。

最初に、ハッシュのコアコンセプトと原則について説明します。

次に、暗号化ハッシュ関数を分析します。

次に、いくつかのハッシュアルゴリズムと、それらに対する攻撃の可能性を定義します。

最後に、一般的なハッシュベースのデータ構造について説明します。

2. ハッシュ

2.1. ハッシュ関数

ハッシュ関数は可変長の入力データを受け取り、固定長の出力値を生成します。通常、これをハッシュコード、ダイジェスト、ハッシュ値、または単にハッシュと呼びます。ハッシュ関数を特徴付けるいくつかの重要なプロパティがあります。

ハッシュは一方向のプロセスです。したがって、ハッシュから元のデータを取得することはできません。
ハッシュ関数は決定論的です。したがって、同じ入力をハッシュ関数に渡すと、常に同じ出力ハッシュコードが生成されます。 SHA-1ハッシュの長さは160ビットです。
均一性–ハッシュは可能な値全体に均等に分散する必要があります。
特定のハッシュ関数は常に固定サイズの出力を生成します。
衝突のリスクを最小限に抑えるために十分に複雑である必要があります。

例として、JavaのStringクラスで使用されるハッシュ関数を分析してみましょう。

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

Effective Java で、Joshua Blochは、値31は奇数の素数であるため、意図的に選択されたと説明しています。 2による乗算はシフトに類似しているため、偶数を使用すると情報が失われる可能性があります。簡単に言うと、複数の除数を持つ値を使用すると、衝突が増える可能性があります。したがって、除数の少ない数値を使用する方が安全です。

hashcode（）メソッドの動作を見てみましょう。

public static void main(String[] args) {
    String anotherTest = "java";
    String test = "test";
    String oneMoreTest = "dev";
    System.out.println(test.hashCode()); // output: 3556498
    System.out.println(test.hashCode()); // output: 3556498
    System.out.println(anotherTest.hashCode()); // output: 3254818
    System.out.println(oneMoreTest.hashCode()); // output: 99349
}

結果を分析すると、前述のハッシュ関数のプロパティのいくつかを確認できます。

まず、 hashcode（）の呼び出しは一方向のプロセスです。生成されたハッシュ（ int ）から元の文字列を取得する方法はありません。

第二に、この方法は決定論的です。 test 変数で2回呼び出し、同じハッシュを取得しました。

最後に、Javaの int タイプは、 Java VMドキュメントで読むことができるように固定サイズであるため、常に固定長のハッシュコードを生成します。

2.2. 暗号化ハッシュ関数

暗号化ハッシュ関数は、ハッシュ関数の特殊なグループです。これらは、セキュリティのレベルを向上させます。したがって、これらは、パスワード検証、データ整合性検証、ブロックチェーン（暗号通貨）などの暗号化の目的で使用されます。

標準のハッシュ関数のプロパティに加えて、目的に応じて、次の基準を満たすこともできます。

衝突耐性：暗号化ハッシュ関数は完全に衝突耐性がなければなりません。標準のハッシュ関数が衝突のリスクを最小限に抑える必要があることはすでにわかっています。ただし、最小化することは、それらが発生しないことを意味するわけではありません。以前、 hashcode（）関数を分析しました。 int 値を返すため、ハッシュのバリエーションはint範囲-2147483648〜2147483647によって制限されます。その結果、すべての可能な値がなくなると、衝突が発生します（場合によっては、それより前でも衝突が発生する可能性があります）。したがって、暗号化ハッシュ関数では、衝突が発生する可能性はありません。
原像耐性：ダイジェストを持つ暗号化ハッシュ関数の場合、メッセージをすばやく見つける方法はありません。
2番目の原像耐性：特定の関数が衝突耐性である場合、常に2番目の原像耐性がありますが、原像耐性はありません。原像耐性がないハッシュ関数は、暗号化の目的では安全でないと見なされます。
「ランダムオラクルとの区別がつかない」：2つのわずかに異なるハッシュを持つメッセージ（入力値）を見つけることは不可能です。
メッセージのハッシュの計算は迅速に行う必要があります。
メッセージが少しでも変更された場合、新しいハッシュは古いハッシュとは大幅に異なるはずです。言い換えれば、古いハッシュコードと新しいハッシュコードの間に相関関係を見つけることができないはずです。
疑似ランダム性。

簡単に言うと、暗号化ハッシュ関数は、安全で、効果的で、信頼できるものでなければなりません。

2.3. ハッシュアルゴリズム

いくつかの一般的なハッシュアルゴリズムについて説明しましょう。

メッセージダイジェストアルゴリズム5（MD5）は、1991年にRonRivesによって導入されました。 MD5は、任意の長さの入力に対して128ビット長のダイジェストを生成します。残念ながら、MD5での衝突は数秒以内に見つかります。したがって、暗号化の目的で使用することはできなくなります。これは通常、データの整合性を検証するためのチェックサムとして使用されます。

Secure Hash Algorithm 2（SHA-2）は、いくつかのハッシュ関数、つまりSHA-224、SHA-256、SHA-384、SHA-512で構成されています。 National Security Agency（NSA）がSHA-2を設計しましたその後、米国国立標準技術研究所（NIST）は、2001年に連邦情報処理標準（FIPS）として公開しました。最近のセキュリティアプリケーションとプロトコルの中には、TLS、SSL、SSH、ビットコインなどのSHA-2を使用しているものがあります。

BLAKE3 は、2020年1月9日に公開されたリストの最新のものです。このアルゴリズムは、任意に拡張可能な256ビット長のダイジェストを生成します。

BLAKE3は単一のアルゴリズムであり、マークルツリーを使用して内部的に構築されます。また、汎用、高速、並列です。これらのプロパティは、ファイルの整合性のチェック、暗号化署名の入力、メッセージ認証に最適です。ただし、GitHubの公式ドキュメントには、パスワードのハッシュには推奨されていないと記載されています。

3. 暗号攻撃

このセクションでは、ハッシュ関数に影響を与える可能性のあるいくつかの暗号化攻撃を確認します。

3.1. 強引な

すでに知っているように、ハッシュ関数は一方向であるため、ダイジェストから元のメッセージを取得する方法はありません。それらも均一であるため、特定のアルゴリズムは常に特定のメッセージに対して同じハッシュを生成します（例：パスワード）。一方、均一性により、特定のハッシュのメッセージを推測することができます。

このプロパティは、すべての可能なメッセージをチェックして、指定されたハッシュに適合するメッセージを見つけるブルートフォース攻撃によって悪用される可能性があります。理論的には、すべてのハッシュ関数はこのタイプの攻撃に対して脆弱です。実際には、ブルートフォース攻撃の計算の複雑さは非常に高くなります。したがって、十分に長いハッシュを使用すると、特定のハッシュに適合するメッセージを見つけることがほとんど不可能になります。

3.2. 誕生日攻撃

別の方法である誕生日攻撃は、誕生日のパラドックスと呼ばれる統計上の問題に依存しています。簡単に説明しましょう。最初の質問は、特定の日に生まれた人を見つける確率を少なくとも50％取得するために、1つの部屋に何人集まるべきかということです。 1月1日？答えは253です。

問題の核心である2番目の質問は、特定の日に少なくとも2人の人が生まれる確率を少なくとも50％取得するには、1つの部屋に何人集まらなければならないかということです。 1月1日？答えは驚くべきものです：23。 23人のグループは253人の異なるペアを作ります

したがって、128ビット長のハッシュの場合、2 ^ 128メッセージをチェックして、特定のハッシュに適合するメッセージを見つける必要があります。ただし、衝突を見つけるのに2^64回のチェックしか必要ありません。説明のために、特定のハッシュのメッセージを見つけるのに60万年かかるマシンがあると仮定しましょう。同じマシンで、衝突（同じハッシュを持つ2番目のメッセージ）を見つけるのに1時間しかかかりません！

なぜ衝突はとても危険なのですか？例として、一部のアルゴリズムは、入力されたパスワードをデータベースに保存されている hash と比較することによってユーザーを認証します（つまり、登録中）。衝突を見つけるための簡単で迅速な方法があれば、衝突したフレーズを元のフレーズの代わりにパスワードとして使用できます。

3.3. サービス拒否

サービス拒否は、サーバーの過負荷に使用される一般的な暗号化攻撃です。ハッシュ関数はデータ構造でも使用できます。

簡単に言えば、それらの多くは衝突が発生するまで効率的に機能します。衝突したデータ（同じハッシュを持つ入力）を多数追加すると、そのようなデータ構造での操作の時間計算量にわずかに影響を与える可能性があります。したがって、サーバーが目的の機能を実行できなくなる可能性があります。

これは、ファイアウォールやSSHなどのセキュリティ機能を担当するサーバーでは特に危険です。

4. ハッシュ表

ハッシュを使用する最も一般的なデータ構造の1つは、ハッシュテーブルです。これは、データをキーと値のペアとして格納し、データへの高速アクセスが必要な場合に特に役立ちます。

ハッシュテーブルに格納されている要素にアクセスする時間計算量は一定であるため、テーブルのサイズや要素の場所に依存しません。特定のプログラミング言語でのハッシュテーブルの実装の良い例は、JavaのHashMap。です。

このセクションでは、ハッシュテーブルについて詳しく説明します。

4.1. エントリのハッシュ

すでに述べたように、ハッシュテーブルのエントリはキーと値のペアです。 内部的に、ハッシュテーブルはデータをバケットの配列に格納します。キーはハッシュテーブル内で一意である必要があります。既存のキーを使用して新しい値を追加しようとするとどうなりますか？実装によって異なりますが、ほとんどの場合、値は上書きされます。

ハッシュテーブルへのエントリの追加がどのように機能するかを説明しましょう。エントリが与えられると、ハッシュテーブルに実装されたハッシュ関数がキーからダイジェストを計算します。適用されるハッシュアルゴリズムは任意です。前のセクションでは、効果的なハッシュ関数が持つべきプロパティを定義しました。生成されたハッシュコードは、バケットの配列内のエントリの値の位置を示すインデックスです。

対応するキーを使用して値にアクセスできます。 ルックアップ中に、渡されたキーのハッシュが計算され、対応する値の場所が検出されます（ダイジェストは値のインデックスであるため）。値の格納に使用されなかったキーを渡すと、何も起こりません（ほとんどのプログラミング言語では、 null ）。

不変のデータ型をキーとして使用することが重要です。例として、可変オブジェクトをキーとして使用したと仮定します。たとえば、nameとsurnameの2つのプロパティで構成されるオブジェクトを使用しました。ハッシュテーブルに値を追加した後、ハッシュテーブルの外部でキーの状態を変更しました。たとえば、名前をPeterからJohnに変更しました。

状態を変更して保存された値にアクセスした後、このキーを使用するとどうなりますか？新しい状態のキーのダイジェストは、元のキーとは異なります。したがって、インデックスとしてその異なるハッシュを持つ可能性のある、何もまたは異なる値を取得することはできません（たとえば、以前に追加しました）。

4.2. 衝突

2つの異なるメッセージに対して、ハッシュ関数が同じハッシュ値を計算できることはすでにわかっており、これを衝突と呼びます。このような状況は、ハッシュテーブルでも発生する可能性があります。ハッシュテーブルでの衝突を処理するには、さまざまな方法があります。一般的なものをいくつか紹介しましょう。

最初のものは個別連鎖と呼ばれます。この手法では、衝突した要素は同じバケット内の個別のデータ構造内に格納されます。ほとんどの場合、個別のデータ構造はリストです。このような状況では、ハッシュテーブル操作の合計時間計算量は、バケットルックアップに必要な時間（一定）+個別のデータ構造操作の時間です。

たとえば、リンクリスト内の要素にアクセスするための時間計算量はです。したがって、衝突の場合、要素にアクセスするハッシュテーブルの定数時間をに減らすことができます。したがって、バケットでデータ構造が効率的に使用されるほど、効果的です。リストの代わりに、さまざまな種類のツリーが使用されることがあります。

2番目のアプローチはオープンアドレッシングです。この戦略では、ハッシュテーブルは、通常のバケットと同様に、衝突した要素を別々のバケットに格納します。違いは、ダイジェストの計算にあります。ハッシュ関数がハッシュの計算中に衝突を検出すると、増分関数の結果値がハッシュ関数の結果に追加されます。ここで、はプローブ番号です。

衝突の場合のルックアップ中に、正しいキーが見つかるまで、渡されたキーが比較されます。したがって、最悪の場合の時間計算量はです。使用される増分関数に応じて、オープンアドレス法にはさまざまなバリエーションがあります。

線形プロービング、
二次プロービング、
のダブルハッシュ。ここで、はキーの追加の増分関数です。

5. 結論

この記事では、ハッシュのトピックについて深く掘り下げました。

まず、ハッシュ関数と暗号化ハッシュ関数について説明しました。次に、それらの例をいくつかリストしました。次に、暗号化攻撃の例をいくつか紹介しました。次に、ハッシュテーブルのデータ構造を紹介しました。

最後に、ハッシュテーブルが衝突を処理する方法を分析しました。

getdocs

13036