[暗号技術入門] ハッシュ関数

on Crypto
目次の表示
  1. ハッシュ化
  2. 暗号学的ハッシュ関数
    1. 暗号学的ハッシュ関数の例
    2. 暗号学的ハッシュ関数の性質
  3. 安全なハッシュ関数
    1. SHA-2、SHA-256、SHA-512
    2. SHA-3、SHA3-256、SHA3-512、Kecck-256
    3. BLAKE2、BLAKE2s、BLAKE2b
    4. RIPEMD-160
  4. ハッシュ関数の利用例
    1. データの完全性
    2. パスワードの保存
    3. IDの生成
    4. 擬似乱数の生成
  5. Proof-of-Work アルゴリズム
    1. ETHash
    2. Equihash

プログラミングにおけるハッシュ関数はテキスト (またはその他のデータ) を整数にマッピングします。 通常、異なる入力は異なる出力にマッピングされますが、場合によっては衝突が発生することがあります。 このように、異なる入力が同じ出力となることを「衝突」といいます。

暗号化ハッシュ関数は、テキストまたはバイナリデータを固定長のハッシュ値に変換します。 このときの変換は、衝突耐性があり、元に戻せない（不可逆な）ことが知られています。 例えば、暗号化ハッシュ関数の SHA3-256 に、文字列 "hello" を渡すと以下のような結果になります。

SHA3-256("hello") = "3338be694f50c5f338814986cdf0686453a888b84f424d792af4b9202398f392"

上記の SHA3-256 ハッシュ計算は、Python で以下のように書くことができます：

import hashlib
import binascii
sha3_256hash = hashlib.sha3_256(b'hello').digest()
print(f"SHA3-256('hello') = {binascii.hexlify(sha3_256hash)}")

暗号化ハッシュ関数は、暗号化、プログラミング、ブロックチェーンなどで広く使用されています。

ハッシュ化

特定のハッシュ関数の値を計算する処理を「ハッシュ化」といいます。 ハッシュ関数は設計上、不可逆的です。 つまり、ハッシュ値から入力メッセージを復元するアルゴリズムはありません。

HASH("John Smith") = 02
HASH("Lisa Smith") = 01
HASH("Sam Doe")    = 04
HASH("Sandra Dee") = 02

上の例では、テキスト "John Smith" はハッシュ値 02 にハッシュ化され、"Lisa Smith" はハッシュ値 01 にハッシュ化されます。 また、"John Smith" と "Sandra Dee" は両方とも同じ値の 02 にハッシュ化されており、これは「衝突」と呼ばれます。

プログラミングでは、ハッシュ関数は、特定の入力タイプの値を別のタイプの値にマップするデータ構造「ハッシュテーブル」（連想配列）の実装で使用されます。 単純なハッシュ関数は、入力データ/テキストのバイトを合計するだけです。 そのような実装の場合、複数の入力をハッシュ化したときに多くの衝突を引き起こす可能性があります。

より優れたハッシュ関数では、最初のバイトを状態として受け取り、素数で乗算するなどで状態を変換させ、次のバイトを状態に追加してから、再度状態を変換する、Merkle–Damgård構築と呼ばれる仕組みを利用する場合があります。 この構造を使うことで、ハッシュ関数の出力の値がより分散されることで、衝突率が大幅に減少し、改善することができます。

暗号学的ハッシュ関数

暗号化では、ハッシュ関数は任意のサイズの入力データ (テキストメッセージなど) を固定サイズ (256ビットなど) の結果に変換します。 このハッシュ関数による出力は、ハッシュ値 (またはハッシュコード、メッセージダイジェスト、または単にハッシュ) と呼ばれます。 コンピュータの暗号化で使用されるハッシュ関数（ハッシュアルゴリズム）は「暗号ハッシュ関数」と呼ばれます。 このような関数の例としては、任意の入力を 256 ビット出力に変換する SHA-256 および SHA3-256 があります。

暗号学的ハッシュ関数の例

例として、暗号化ハッシュ関数 SHA-256 を使用して、テキストメッセージ "hello" のハッシュ値を計算できます。

SHA-256("hello") = "2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824"

上記の SHA-256 ハッシュ計算は、Python で以下のように書くことができます：

import hashlib
import binascii
sha256hash = hashlib.sha256(b'hello').digest()
print(f"SHA-256('hello') = {binascii.hexlify(sha256hash)}")

ハッシュ値から元の入力メッセージ (上の例では "hello") を見つける効率的なアルゴリズムはありません。 暗号ハッシュ関数は一方向性の不可逆で、元に戻すことができないことはよく知られているため、入力を公開せずにエンコードするために広く使用されています (例: 秘密キーを公開せずにブロックチェーンアドレスに変換してから公開するなど)。

別の例として、暗号ハッシュ関数 SHA3-512 を使用して、同じテキストメッセージ "hello" のハッシュ値を計算できます。

SHA3-512("hello") = "75d527c368f2efe848ecf6b073a36767800805e9eef2b1857d5f984f036eb6df891d75f72d9b154518c1cd58835286d1da9a38deba3de98b5a53e5ed78a84976"

CyberChef ではハッシュ関数 SHA-2 の動作をオンラインでテストすることができます。 次の「CyberChef」では暗号学的ハッシュ関数をオンラインで試すことができるので、適当な入力を入れて遊んでみてください。

暗号学的ハッシュ関数の性質

暗号化ハッシュ関数において衝突が見つかる可能性は非常に低いため、暗号化ハッシュは対応する入力をほぼ一意に識別できるとみなすことができます。 さらに、指定された値にハッシュされる入力メッセージを見つけることは非常に困難です。

暗号化ハッシュ関数は一方向ハッシュ関数であり、逆にすることは不可能です。 強力な暗号化ハッシュ関数 (SHA-256 など) の衝突がブルートフォース攻撃によって見つかる可能性は非常にわずかです。 理想的な暗号化ハッシュ関数には、次の特性が必要となります。

  • 決定的 (Deterministic) : 同じ入力メッセージは常に同じハッシュ値になること
  • 不可逆的 : ハッシュ値から有効な入力メッセージを生成することは不可能であること。これは、ブルートフォース (考えられるすべての入力メッセージを試す) 攻撃よりも大幅に優れた方法はないことを意味します。
  • 衝突なし : 同じハッシュを持つ2つの異なるメッセージを見つけるのは非常に困難 (または事実上不可能) であること
  • 処理速度が高速 : 特定のメッセージのハッシュ値を高速に計算できること
  • 解析が困難 : 入力メッセージを少し変更すると、出力ハッシュ値が完全に変化する性質を持つこと

最新の暗号化ハッシュ関数 (SHA2 や SHA3 など) では上記の性質を持っており、暗号化において広く使用されています。


安全なハッシュ関数

最新の暗号化ハッシュ アルゴリズム (SHA-3 や BLAKE2 など) は、ほとんどのアプリケーションにとって十分に安全であると考えられています。

設計上、ハッシュ出力のビット数が多いほど、より強力なセキュリティとより高い衝突耐性が実現されます。 一般的には、128 ビットのハッシュ関数は 256 ビットのハッシュ関数よりも弱く、256 ビットのハッシュ関数は 512 ビットのハッシュ関数よりも弱くなります。 よって、SHA-512 は SHA-256 よりも強力であるため、SHA-512 の場合は SHA-256 よりも実際に衝突が見つかる可能性が低いことが期待できます。

SHA-2、SHA-256、SHA-512

SHA-2 は、強力な暗号化ハッシュ関数の集まりです。 具体的には SHA-256 (256ビットハッシュ)、SHA-384 (384ビットハッシュ)、SHA-512 (512ビットハッシュ) などがあります。 SHA-2 は、Merkle-Damgård構造に基づいて構成されており、安全性が高いと考えられています。 また、SHA-2は米国で公式の暗号標準として公開されていて、開発者や暗号化分野で広く使用されており、最新の商用アプリケーションには十分な暗号強度があると考えられています。 SHA-256 はビットコインブロックチェーンでも広く使用されています。トランザクションハッシュの識別と、マイナーによって実行されるProof-of-Workマイニングに使用されます。

SHA2 ハッシュの例:

SHA-256('hello') = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
SHA-384('hello') = 59e1748777448c69de6b800d7a33bbfb9ff1b463e44354c3553bcdb9c666fa90125a3c79f90397bdf5f6a13de828684f
SHA-512('hello') = 9b71d224bd62f3785d96d46ad3ea3d73319bfbc2890caadae2dff72519673ca72323c3d99ba5c11d7c7acc6e14b8c5da0c4663475c2e5c3adef46f73bcdec043

SHA-3、SHA3-256、SHA3-512、Kecck-256

SHA-3 (SHA3-224、SHA3-256、SHA3-384、SHA3-512) は、SHA-2 (SHA-224、SHA-256、SHA-384、SHA-512) よりも安全であると考えられています。 同じハッシュ長でも、例えば、SHA3-256 は、SHA-256 よりも高い暗号強度を提供します。 SHA-3 ハッシュ関数は、「スポンジ構築」というアルゴリズムの構造に基づいた「Keccak」ハッシュ関数の代表です。 Keccak は、SHA-3 NIST コンペティションを勝ち抜いたハッシュ関数アルゴリズムです。 SHA-2 とは異なり、SHA-3 ハッシュ関数の暗号化ハッシュ関数は「伸長攻撃 (Length-Extension Attack)」に対して脆弱ではありません。 SHA-3 は安全性が高いと考えられており、米国で公式に推奨される暗号標準として公開されています。 イーサリアムブロックチェーンで使用されるハッシュ関数 Keccak-256 は、SHA3-256 のコード内のいくつかの定数が変更したハッシュ関数です。

ハッシュ関数 SHAKE128(msg, length) および SHAKE256(msg, length) は、SHA3-256 および SHA3-512 アルゴリズムを修正したハッシュ関数であり、入力の length によって出力されるメッセージダイジェストの長さが異なる場合があります。

SHA3 ハッシュの例：

SHA3-256('hello') = 3338be694f50c5f338814986cdf0686453a888b84f424d792af4b9202398f392
Keccak-256('hello') = 1c8aff950685c2ed4bc3174f3472287b56d9517b9c948127319a09a7a36deac8
SHA3-512('hello') = 75d527c368f2efe848ecf6b073a36767800805e9eef2b1857d5f984f036eb6df891d75f72d9b154518c1cd58835286d1da9a38deba3de98b5a53e5ed78a84976
SHAKE-128('hello', 256) = 4a361de3a0e980a55388df742e9b314bd69d918260d9247768d0221df5262380
SHAKE-256('hello', 160) = 1234075ae4a1e77316cf2d8000974581a343b9eb

BLAKE2、BLAKE2s、BLAKE2b

BLAKE、BLAKE2、BLAKE2s、BLAKE2b は、高速で安全性の高い暗号化ハッシュ関数であり、ダイジェストが 160 ビット、224 ビット、256 ビット、384 ビット、および 512 ビットのサイズの計算を提供します。 BLAKE は、SHA-3 NIST コンペティションの最終選考に進んだアルゴリズムの1つです。 BLAKE2は、BLAKEを改良したハッシュ関数です。 BLAKE2s (通常 256 ビット) は、32 ビットマイクロプロセッサ向けにパフォーマンスが最適化された BLAKE2 の改良版です。 BLAKE2b (通常 512 ビット) は、64 ビットマイクロプロセッサ向けにパフォーマンスが最適化された BLAKE2 の改良版です。 BLAKE2 ハッシュ関数は、SHA-3 と同様のセキュリティ強度を持っていますが、SHA-2 や SHA-3 ほど開発者に利用されていないのが現状です。

BLAKE ハッシュの例：

BLAKE2s('hello') = 19213bacc58dee6dbde3ceb9a47cbb330b3d86f8cca8997eb00be456f140ca25
BLAKE2b('hello') = e4cfa39a3d37be31c59609e807970799caa68a19bfaa15135f165085e01d41a65ba1e1b146aeb6bd0092b49eac214c103ccfa3a365954bbbe52f74a2b3620 c94

RIPEMD-160

RIPEMD-160 は安全なハッシュ関数であり、暗号化で広く使用されています。 例えば、PGPとビットコインで使用されています。 RIPEMD の 160 ビット出力版は広く使用されていますが、RIPEMD-128、RIPEMD-256、RIPEMD-320 などの他の種類は一般的ではなく、セキュリティ強度に議論の余地があります。 推奨事項として、RIPEMD の代わりに SHA-2 および SHA-3 を使用することをお勧めします。 これは、ビット長が長く、衝突の可能性が低いため、SHA-2 および SHA-3 は RIPEMD よりも強力であるためです。

RIPEMD ハッシュの例：

RIPEMD-160('hello') = 108f07b8382412612c048d07d13f814118445acd
RIPEMD-320('hello') = eb0cf45114c56a8421fbcb33430fa22e0cd607560a88bbe14ce70bdf59bf55b11a3906987c487992

上記の一般的なハッシュ関数 (SHA-2、SHA-3、BLAKE2、RIPEMD) はすべて商用特許による制限を受けておらず、無料で公的に使用できます。


ハッシュ関数の利用例

暗号化ハッシュ関数 (SHA-256 や SHA3-256 など) は、多くのシナリオで使用されます。 ここでは、最も一般的なアプリケーションを紹介していきます。

データの完全性

ファイル/ドキュメント/メッセージの整合性を検証します。 SHA256 チェックサムは、特定のファイルがチェックサムの計算後に変更されていないことを保証するために利用されます。 例えば、公式 Web サイトからダウンロードしたファイルが、ローカルのファイルと整合性がとれていることを確認するために使います。

パスワードの保存

パスワードの保存とパスワードの検証。 開発者は通常、データベースにプレーンテキストのパスワードを保存する代わりに、パスワード ハッシュ、またはパスワードから派生したより複雑な値 (Scrypt から派生した値など) を保存します。 例えば、Linuxシステムの /etc/shadow ファイルの内容には、パスワードをハッシュ化した値が保存されています。 このパスワードは、ソルトを含む複数ラウンドの SHA-512 ハッシュとして保存されます。

IDの生成

特定のドキュメント/メッセージの（ほぼ）一意の ID を生成します。 暗号化ハッシュ関数は、内容に基づいてドキュメントをほぼ一意に識別します。 理論的には、どの暗号化ハッシュ関数でも衝突が発生する可能性はありますが、発生する可能性は非常に低いため、ほとんどのシステム (Git など) は、使用するハッシュ関数には衝突がないと想定しています。

通常、ドキュメントはハッシュ化され、ドキュメントID (ハッシュ値) は後でドキュメントの存在を証明するときや、ストレージシステムからドキュメントを取得するときのために使用されます。 ハッシュベースの一意の ID の例は、コミットの内容 (例: 3c3be25bc1757ca99aba55d4157596a8ea217698) やビットコインアドレス (例: 1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2) などがあります。

擬似乱数の生成

ハッシュ値は乱数として使うことができます。 そのため、擬似乱数の生成と鍵の導出にも利用することができます。 乱数列を生成する簡単な方法は次のとおりです。

  1. ランダムシード (キーボードのクリックやマウスの移動などのランダムイベントから収集されたエントロピー) から開始します。
  2. 「1」を追加してハッシュを計算して最初の乱数を取得します。
  3. 次に「2」を追加してハッシュを計算して、2番目の乱数を取得します。
  4. 以下繰り返し…

Proof-of-Work アルゴリズム

ほとんどのプルーフ・オブ・ワーク (Proof-of-Work) アルゴリズムは、マイニング難易度と呼ばれる特定の値よりも大きいハッシュ値を計算します。 ハッシュ値は予測できないため、マイナーはこのハッシュ値を見つけるために何十億もの異なるハッシュを計算し、その中で最大のものを取得します。 例えば、Proof-of-Workの例として、$\mathrm{hash}(x + p)$ が先頭に10個のゼロビットを保持するような数値 $p$ を見つける問題などがあります。

ブロックチェーンの Proof-of-Work マイニングアルゴリズムは、計算量とメモリを大量に消費する特別なクラスのハッシュ関数を使用します。 これらのハッシュ関数は、大量の計算リソースと大量のメモリを消費するように設計されており、ハードウェアデバイス (FPGA 集積回路や ASIC マイナーなど) に実装するのは非常に困難です。 このようなハッシュ関数は、ASIC耐性 (ASIC-resistant) として知られています。

多くのハッシュ関数は、Proof-of-Work マイニングアルゴリズム用に設計されています。 ETHash、Equihash、CryptoNight、Cookoo Cycleなどのハッシュ関数は計算に時間がかかり、通常は GPU ハードウェア (NVIDIA GTX 1080 などのグラフィックスカード) または強力な CPU ハードウェア (Intel Core i7-8700K など) と大量の高速 RAM メモリ (DDR4 チップなど) を使用します。 これらのマイニング用のハッシュ関数アルゴリズムが目指すゴールは、小規模マイナーを刺激してマイニングの集中化を最小限に抑え、マイニング業界の大手企業の力を制限することです。 多数の小規模マイナーがいることは、少数の大手マイナーよりも分散化が優れていることを意味します。

ETHash

ETHash は、イーサリアムブロックチェーンのProof-of-Workのハッシュ関数です。 これはメモリを大量に消費するハッシュ関数 (高速に計算するには大量の RAM が必要) であるため、ASIC 耐性があると考えられています。 ハッシュ関数 ETHash は次の性質を持ちます。

  • 「シード」はブロックごとに計算されます (現在のブロックまでのチェーン全体に基づいて)。
  • シードから、16MBの擬似ランダムキャッシュが計算されます。
  • キャッシュから 1GBのデータセットが抽出され、マイニングに使用されます。
  • マイニングには、データセットのランダムなスライスを一緒にハッシュすることが含まれます。

Equihash

Equihash は、Zcash および Bitcoin Gold ブロックチェーンのProof-of-Workハッシュ関数です。 こちらも同様に、メモリを大量に消費するハッシュ関数 (高速計算には大量の RAM を必要とする) であるため、ASIC 耐性があると考えられています。 ハッシュ関数 Equihash は次の性質を持ちます。

  • BLAKE2b を使用して、ブロックチェーン内の以前のブロックから50MBのハッシュデータセットを計算します。
  • 生成されたハッシュデータセットに対する「一般化された誕生日問題」を解きます (2097152 から 512 個の異なる文字列を選択し、それらのバイナリ XOR が 0 になるようにします)。最もよく知られている解法 (ワグナーのアルゴリズム) は指数関数的な時間で実行されるため、多くのメモリとコンピューティングを集中的に使用する計算が必要になります。
View Comments...