暗号学的ハッシュ関数

このレッスンでは、迅速な検証と認証に広く使われている暗号学的ハッシュ関数について学びます。

レッスンの終わりまでに、以下の内容を習得します。

暗号学的ハッシュ関数とは何か
ハッシュ関数の使い方を示す Python コードの例
暗号学的ハッシングの応用例
暗号学的ハッシングのセキュリティ
古典コンピュータと量子コンピュータの両方からこれらのアルゴリズムへの脅威

暗号学的ハッシングの概要

ハッシュ関数は、機密性を保ちながら検証を可能にする点で、暗号学において価値ある構成要素です。そのため、ハッシュ関数はハッシュベースメッセージ認証コード（HMAC）やデジタル署名など、データ認証・完全性のメカニズムの重要な構成要素となっています。本記事では、暗号学的ハッシュ関数の基本的な考え方とセキュリティ上の考慮事項を解説し、量子コンピューティングの到来による潜在的な脆弱性についても概説します。

ハッシュ関数の基本的な原理と設計

認証と完全性検証を低コストかつプライベートな情報を検証側に開示せずに行う必要がある場面は数多くあります。

たとえば、リモートサーバーからソフトウェアをダウンロードする際、ダウンロードしたソフトウェアが元の作者によって作成されてから改ざんされていないことを効率的に確認する仕組みが必要です。同様に、ウェブアプリケーションのユーザーを認証する場合、実際のパスワードを物理的に保存・送信しない仕組みが望ましく、これによりパスワードの機密性が守られます。

暗号学的ハッシュ関数（CHF）は、こうしたニーズに効率的かつ安全に応えます。

基本的に、暗号学的ハッシュ関数は任意の長さの入力（またはメッセージ）を受け取り、固定長の n ビット文字列を出力として返します。CHF の出力はダイジェストとも呼ばれます。有用な CHF はいくつかの重要な特性を満たす必要があります。

一様性： CHF が生成するダイジェストは一様に分布し、ランダムに見えるものである必要があります。目的は、出力が入力に関する情報を一切漏らさないようにすることです。
決定性： 与えられた入力に対して、CHF は常に同じダイジェストを生成しなければなりません。つまり、決定的でなければなりません。
非可逆性： CHF は一方向関数であり、ダイジェストが与えられても、ハッシングを逆算して入力を得ることは実質的に不可能でなければなりません。
近似的単射性： CHF は多対一関数ですが、一対一関数のように見えるべきです。これは巨大な出力空間と、入力のわずかな変化でも大きく異なるダイジェストを生じさせるアバランシェ効果を組み合わせることで実現されます。この特性は近似的単射性と呼ばれます。

これにより、データのダイジェストと元のダイジェストを比較することで、データが元のインスタンスと一致するかを検証することができます。

2 つのダイジェストが一致した場合、データが元のものと同一である可能性が高いと確信できます。
ダイジェストが異なる場合、データが改ざんされているか、それ以外の理由で正当でないと断言できます。

CHF のダイジェスト自体はデータや元の内容を明かさないため、プライバシーを保ちながら検証が可能になります。

Mathematical description

ハッシュ関数 $H$ は次のように定義できます。

$H : Σ^* \rightarrow \{0,1\}^n$

ここで $Σ^*$ は、任意の長さのバイナリ文字列と見なせるすべての可能な文字列の集合です。

$H$ の入力域 $Σ^*$ のサイズが非有界であるのに対して、値域 $\{0,1\}^n$ のサイズは有界であるという事実は、 $H$ が必然的に無限に多くの入力を任意の n ビット文字列に対応させる多対一写像であることを意味します。

一様性と決定性という特性は、暗号学的ハッシングのランダムオラクルモデルにおいて適切に捉えられています。

Python での SHA-256 を使った暗号学的ハッシングの例

この簡単な例では、cryptography Python ライブラリが提供する一般的な SHA-256 アルゴリズムを使って暗号学的ハッシングを実演します。まず、平文のわずかな違いがハッシュダイジェストに非常に大きな差をもたらすことを示します。

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

# Begin by importing some necessary modules
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes

# Helper function that returns the number of characters different in two strings
def char_diff(str1, str2):
    return sum(str1[i] != str2[i] for i in range(len(str1)))

# Messages to be hashed
message_1 = b"Buy 10000 shares of WXYZ stock now!"
message_2 = b"Buy 10000 shares of VXYZ stock now!"

print(f"The two messages differ by { char_diff(message_1, message_2)} characters")

The two messages differ by 1 characters

2 つのメッセージはちょうど 1 文字だけ異なります。

次に、hash オブジェクトをインスタンス化してハッシング処理を有効にします。処理には update と finalize という 2 つのメソッドの呼び出しが含まれます。

SHA-256 CHF のアバランシェ効果により、入力メッセージの 1 文字の違いが 2 つの大きく異なるダイジェストを生み出すことがわかります。

# Create new SHA-256 hash objects, one for each message
chf_1 = hashes.Hash(hashes.SHA256(), backend=default_backend())
chf_2 = hashes.Hash(hashes.SHA256(), backend=default_backend())

# Update each hash object with the bytes of the corresponding message
chf_1.update(message_1)
chf_2.update(message_2)

# Finalize the hash process and obtain the digests
digest_1 = chf_1.finalize()
digest_2 = chf_2.finalize()

# Convert the resulting hash to hexadecimal strings for convenient printing
digest_1_str = digest_1.hex()
digest_2_str = digest_2.hex()

# Print out the digests as strings
print(f"digest-1: {digest_1_str}")
print(f"digest-2: {digest_2_str}")

print(f"The two digests differ by { char_diff(digest_1_str, digest_2_str)} characters")

digest-1: 6e0e6261b7131bd80ffdb2a4d42f9d042636350e45e184b92fcbcc9646eaf1e7
digest-2: 6b0abb368c3a1730f935b68105e3f3ae7fd43d7e786d3ed3503dbb45c74ada46
The two digests differ by 57 characters

暗号学的ハッシングの応用

CHF の独自の特性により、幅広い用途に適しています。

データ完全性チェック： ハッシュ関数はデータセットのチェックサムの生成に使用できます。意図的かどうかにかかわらず、データへのいかなる変更もチェックサムの変化をもたらし、システムやユーザーに変更を知らせます。チェックサムは元のデータよりもはるかにコンパクトであることが多く、チェックサムの比較を非常に高速に行えます。

Fig 1: Secure hashing for data integrity checks

図 1. データ完全性のためのセキュアハッシング

デジタル署名： 暗号学的ハッシュはデジタル署名の機能に不可欠です。暗号学的にハッシュされたメッセージを比較することで、プライバシーを保ちながら真正性と完全性を確立します。

Fig 2: Digital signatures

図 2. デジタル署名

ブロックチェーンと暗号通貨： Bitcoin のような暗号通貨は、特にトランザクションの完全性の確保やプルーフ・オブ・ワークのようなコンセンサスメカニズムの実現において、CHF に大きく依存しています。

暗号学的ハッシングのセキュリティ

CHF のセキュリティは通常、原像と衝突という 2 種類の攻撃に対する耐性に基づいて評価されます。

原像耐性

原像耐性とは、ダイジェストが与えられても、その入力を見つけることが実質的に不可能であることを意味します。

これは CHF の一方向性に関係しています。

優れた CHF は、原像攻撃を試みる攻撃者がブルートフォースアプローチ（時間計算量 $2^n$ ）以外に選択肢がないように設計されています。

Mathematical details

CHF $H$ とダイジェスト $g$ が与えられたとき、 $H(m) = g$ を満たす入力 $m$ を $g$ の原像から見つけることは、計算上実質的に不可能である必要があります。

衝突耐性

衝突耐性とは、同じダイジェストにハッシュされる 2 つの異なる入力を見つけることが困難であることを意味します。

暗号ハッシュ衝突は、2 つの入力が同じダイジェストにハッシュされるときに発生します。CHF の多対一の性質から衝突は必然的に存在しますが、優れた CHF は自在に衝突を見つけることを実質的に不可能にします。

衝突耐性は、デジタル署名や証明書などの用途において非常に重要です。悪意ある当事者が同じ値にハッシュされる偽造物を作成できてしまうと、壊滅的な結果をもたらす可能性があります。

Mathematical details of hash collisions

$H(m_1) = H(m_2)$ を満たす $m_1, m_2$ を見つけることができます。

ハッシュ長

衝突耐性は原像耐性よりも厳しい要件であり、原像耐性に必要な出力長の 2 倍の長さが必要です。これは、ハッシュ衝突の特定に使用できるブルートフォース攻撃として知られる誕生日攻撃の時間計算量が $2^{n/2}$ であるためです。

暗号解析上の弱点がない場合、ハッシュ関数のセキュリティはハッシュ長に主に左右されます。ハッシュが長いほど、ブルートフォース攻撃が困難になるため、より安全です。

よく使われる暗号学的ハッシュ関数

以下の表は、よく使われる暗号学的ハッシュ関数と、そのハッシュ長および主な応用分野を示しています。

ハッシュ関数	出力長（ビット）	主な応用
MD5	128	ファイル完全性チェック、旧来のシステム、非暗号用途
SHA-1	160	レガシーシステム、バージョン管理の Git
SHA-256	256	暗号通貨（Bitcoin）、デジタル署名、証明書
SHA-3	可変（最大 512）	各種暗号応用、SHA-2 の後継
Blake2	可変（最大 512）	暗号、一部のシステムで MD5/SHA-1 の代替
Blake3	可変（最大 256）	暗号、ファイルハッシング、データ完全性

MD5 と SHA-1 は、セキュリティ要件の低いアプリケーションでは今でも見られますが、衝突耐性の観点では非推奨とされており、新しいシステムには推奨されません。 SHA-2 ファミリーの一部である SHA-256 は広く使われており、現在ほとんどのアプリケーションで安全です。
SHA-3 は新しい標準であり、2015 年に NIST のハッシュ関数コンペティションの勝者として NIST が選定しました。SHA-2 のドロップイン代替として設計されていますが、内部構造が異なり、SHA-2 に有効な可能性のある特定の攻撃への耐性も備えています。
Blake2 と Blake3 は、MD5、SHA-1、SHA-2、SHA-3 よりも高速でありながら、最新標準の SHA-3 と同等以上のセキュリティを持つ暗号学的ハッシュ関数です。特に速度が重要な新しいシステムで採用が進んでいます。

従来の暗号学的ハッシングへの量子リスク

暗号学的ハッシングに対する主な量子的脅威はブルートフォース攻撃です。

攻撃者は特定のダイジェストに対し、同じダイジェストを生成する入力を見つけるまでランダムな入力を試み続けます。

入力が $n$ ビットの場合、 $2^n$ 通りの可能な値があります。したがって、攻撃者が 50% 超の成功確率を得るには、約 $2^{n-1}$ 個の入力を試す必要があります。

Grover のアルゴリズム

このような非構造的な探索の文脈では、Grover のアルゴリズムが量子振幅増幅と呼ばれる技術を使って二次的な高速化を提供し、原像攻撃の時間計算量を $2^{n/2}$ に削減できます。

実際的な意味では、現在古典コンピュータによる原像攻撃に対して安全とされている 256 ビット CHF は、Grover のアルゴリズムを利用する量子攻撃者に対しては 128 ビット CHF と同等のセキュリティレベルになることを意味します。

Grover のアルゴリズム単体では、古典コンピュータで実行できる誕生日攻撃で設定された限界を超える衝突攻撃に対する追加の量子高速化をもたらすことは知られていません。古典的な誕生日攻撃はすでに、CHF が原像耐性に必要な 2 倍のハッシュ長を使用することを要求しているため、Grover 探索が原像攻撃に関してハッシュ長を実質的に半減させるとしても、実際的な脅威にはなりません。

たとえば SHA-256 の場合、Grover を利用した原像攻撃を実行するために $2^{128}$ オーダーの演算を行うことは、近い将来においても実現不可能です。

BHT アルゴリズム

誕生日攻撃と Grover 探索を組み合わせた量子アルゴリズムが 1997 年に Brassard、Høyer、Tapp（BHT）によって提案され、ハッシュ衝突を見つけるための理論的なスケーリングとして $O(2^{n/3})$ を達成します。ただし、この改善されたスケーリングは、現在存在しない量子ランダムアクセスメモリ QRAM 技術の存在を前提としています。

QRAM がない場合、実現可能なスケーリングは $\tilde{O}(2^{2n/5})$ であり、現在使用されているハッシュ長では、誕生日攻撃に対する衝突発見能力のわずかな改善は重大な脅威とはなりません。

まとめ

暗号学的ハッシュ関数は、デジタル情報システムにおけるデータの完全性とプライバシーを確保するための不可欠な要素であり、多くの文脈で広く活用されています。

CHF のセキュリティ要件は主に、原像攻撃と衝突攻撃への耐性という観点から理解されます。適切に設計された CHF においては、ハッシュ長がセキュリティレベルの良い指標となります。

量子コンピュータが Grover および BHT アルゴリズムを実行することは理論上、従来の CHF の原像耐性と衝突耐性に影響を与えますが、今日すでに使用されている長いハッシュ長を考えると、SHA-3 などの現代的な暗号学的ハッシングアルゴリズムは、未知の暗号解析攻撃が発見されない限り、安全であり続ける可能性が高いです。

CHF の重要性は、量子耐性暗号スキームの基本的な構成要素としての役割にあり、量子コンピューティングアルゴリズムと技術の将来的な進歩に直面しても、デジタル情報の安全性を確保します。

暗号学的ハッシングの概要​

ハッシュ関数の基本的な原理と設計​

Python での SHA-256 を使った暗号学的ハッシングの例​

暗号学的ハッシングの応用​

暗号学的ハッシングのセキュリティ​

原像耐性​

衝突耐性​

ハッシュ長​

よく使われる暗号学的ハッシュ関数​

従来の暗号学的ハッシングへの量子リスク​

Grover のアルゴリズム​

BHT アルゴリズム​

まとめ​