\( \def\vector#1{\boldsymbol{#1}} \)

ハッシュ関数

Takami Torao
  • このエントリーをはてなブックマークに追加

概要

ハッシュ関数 (hash function) は任意長のビット列をある固定の長さのビット列に変換する関数。\(k\) ビット値への変換を行うハッシュ関数 \(h\) は数学記号で \(h: \{0,1\}^* \to \{0,1\}^k\) と記述することができる。ここで出力ビット長 \(k\) は 256 や 512 といった比較的小さな値である。

Table of Contents

  1. 概要
  2. 暗号論的ハッシュ関数
    1. 攻撃耐性
  3. パフォーマンス評価
  4. 参照

暗号論的ハッシュ関数

セキュリティの文脈で以下の特性を満たすハッシュ関数は暗号論的ハッシュ関数 (cryptographically-secure hash function) と呼ばれる。

  • 原像耐性 (preimage resistance) - ハッシュ関数 \(h\) のある出力 \(y\) が与えられたとき、\(y=h(x)\) となるような値 \(x \in \{0,1\}^*\) を見つけることが計算上不可能であること。
  • 第二原像耐性 (2nd preimage resistance) - ハッシュ関数へのある入力 \(x\) が与えられたとき、\(h(x)=h(x')\) となるような値 \(x' \in \{0,1\}^*\) を見つけることが計算上不可能であること。
  • 衝突耐性 (collision resistance) - \(h(x)=h(x')\) となるような 2 つの値 \(x\), \(x'\) を見つけることが計算上不可能であること。

原像耐性 (第一、第二) と衝突耐性 (弱衝突、強衝突) は似ているが、原像耐性が「与えられたある値 \(x\) に対して」であるのに対して衝突耐性は「任意の値 \(x\) に対して」であるという違いがある。

\(k\) ビットの理想的な暗号論的ハッシュ関数に対して原像攻撃を成功させるには \(O(2^k)\) 回の試行を行う必要がある。しかし、同等の確率で \(h(x)=h(x')\) となるような衝突攻撃を成功させるためには、バースデーパラドックス (birthday paradox) と同じ理由により、より少ない \(O(2^{k/2})\) 回程度の試行で済む。言い換えると、出力値が \(k\) ビットの理想的な暗号論的ハッシュ関数は \(k/2\) ビットセキュリティを持つ

攻撃耐性

コンピュータの性能向上や新しいアルゴリズムの報告などによって、かつて暗号論的ハッシュ関数として扱われていたアルゴリズムのいくつかはすでに安全ではないと認識されている。MD2 は早い時期に原像攻撃と衝突攻撃の両方が見つかっている。MD5 も同様に現在では短時間で衝突を発見することができており、また SHA-1 は \(2^{63}\) 程度の操作で衝突が報告されている。

\(y=h(x)\) となるようなハッシュ値 \(y\) が与えられたとき、ある入力 \(x'\) に対して \(y'=h(x \ || \ x')\) となるような \(y'\) が計算可能であることを利用した攻撃を伸長攻撃 (length extension attach) と呼ぶ。MD5, SHA-1, RIPEMD-160, Whirlpool, SHA-2 (SHA-224~512) など多くの暗号論的ハッシュ関数は Merkle–Damgård 構成法に基づいているが、Merkle–Damgård 構成法の完全な出力を使用すると伸長攻撃に対して脆弱となる。SHA-3 や BLAKE2, BLAKE3、または SHA-2 でも出力の切り捨てを伴うタイプは伸長攻撃に対して安全である。

パフォーマンス評価

Table 1 は、すべてのバイト値が 0 に初期化されている 1MB のバイト配列を入力 \(x\) とし、それぞれのアルゴリズムを適用してハッシュ値 \(y=h(x)\) の算出にかかった時間を表している。ここでは暗号論的ハッシュ関数だけではなく、単純なチェックサムの CRC や非暗号論的ハッシュ関数の MurmurHash、AES 拡張命令を使用する aHash を比較の目的で挙げている。

アルゴリズム 算出時間 [μsec/1MB] (±95%信頼区間) 出力サイズ \(k\) 🔒
CRC32 1,876.894 (±1.9%) 32-bit (4B)
MurmurHash64A 185.309 (±2.1%) 64-bit (8B)
MurmurHash3-128 (x64) 229.250 (±4.5%) 128-bit (16B)
aHash 87.792 (±1.6%) 64-bit (8B)
MD2 84,781.845 (±1.2%) 128-bit (16B)
MD5 1,444.497 (±2.3%) 128-bit (16B)
MD6 6,479.074 (±1.7%) 512-bit (64B) 🌞
SHA-1 438.087 (±2.1%) 160-bit (20B)
RIPEMD-160 2,840.412 (±1.7%) 160-bit (20B)
RIPEMD-320 2,570.902 (±1.9%) 320-bit (40B)
Whirlpool 6,020.282 (±1.4%) 512-bit (64B)
SHA-224 467.485 (±2.5%) 224-bit (28B)
SHA-256 468.305 (±1.9%) 256-bit (32B)
SHA-386 2,038.623 (±3.1%) 384-bit (48B)
SHA-512 2,076.962 (±4.4%) 512-bit (64B)
SHA-512/224 2,032.270 (±2.2%) 224-bit (28B) 🌞
SHA-512/256 2,026.481 (±2.1%) 256-bit (32B) 🌞
SHA3-224 2,356.973 (±2.8%) 224-bit (28B) 🌞
SHA3-256 2,511.481 (±3.8%) 256-bit (32B) 🌞
SHA3-384 3,240.217 (±2.2%) 384-bit (48B) 🌞
SHA3-512 4,688.776 (±2.0%) 512-bit (64B) 🌞
Keccak-256 2,489.182 (±2.2%) 256-bit (32B) 🌞
Keccak-512 4,654.524 (±1.6%) 512-bit (64B) 🌞
BLAKE2b 921.216 (±1.6%) 512-bit (64B) 🌞
BLAKE2s 2,501.755 (±1.4%) 256-bit (32B) 🌞
BLAKE3 211.464 (±2.2%) 256-bit (32B) 🌞
SipHash 363.023 (±1.8%) 64-bit (8B) 🌞
SipHash128 364.992 (±2.0%) 128-bit (16B) 🌞
HighwayHash64 59.312 (±1.5%) 64-bit (8B) 🌞
HighwayHash128 59.413 (±1.2%) 128-bit (16B) 🌞
HighwayHash256 59.500 (±1.3%) 256-bit (32B) 🌞
Table 1. アルゴリズムの公開されているハッシュ関数のパフォーマンス。
# AMD Ryzen 9 3900XT 12C/24T 3.8GHz + Windows 10 Pro
> rustc --version
rustc 1.50.0 (cb75ad5db 2021-02-10)

計測結果では AVX/SSE 拡張命令を使用する HighwayHash や AES 拡張命令を使用する aHash の高いパフォーマンスが目を引く。また Ryzen 3900XT と Core i7-8569U での SHA-1, SHA-224, SHA-256 の速度差は CPU が Intel SHAX 拡張命令をサポートしているかの違いによるものと思われる。

このような結果から分かるように、近年のハッシュ関数ではハードウェアアクセラレーション

参照