\( \def\vector#1{\boldsymbol{#1}} \)
ハッシュ関数
概要
ハッシュ関数 (hash function) は任意長のビット列をある固定の長さのビット列に変換する関数。\(k\) ビット値への変換を行うハッシュ関数 \(h\) は数学記号で \(h: \{0,1\}^* \to \{0,1\}^k\) と記述することができる。ここで出力ビット長 \(k\) は 256 や 512 といった比較的小さな値である。
Table of Contents
- 概要
- ドメイン分離
- 暗号論的ハッシュ関数
- 攻撃耐性
- SHA-3
- 可変長出力ハッシュ関数
- ドメイン分離ハッシュ関数
- タプル型ハッシュ関数
- パフォーマンス評価
- 参考文献
ドメイン分離
ハッシュ関数は同じアルゴリズムを使っていても目的によって異なる変種を使用すべきである。例えば同じ入力値 "passwd" に対してユーザ ID 用途のハッシュ関数 \(\mbox{hash_u}\) とパスワード用とのハッシュ関数 \(\mbox{hash_p}\) では異なるハッシュ値を返すことが望ましい。このような方法をドメイン分離 (domain separation) と呼ぶ。
単純な例では、すべての入力に対してドメインごとに異なる固定値を付けてドメインを分離した変種のハッシュ関数を生成する方法が考えられる。\[ \begin{eqnarray*} \mbox{hash_u}(x) & = & \mbox{hash}(x\,||\,{\tt "u"}) \\ \mbox{hash_p}(x) & = & \mbox{hash}(x\,||\,{\tt "p"}) \\ \end{eqnarray*} \] Salt を使用したパスワードのハッシュ化は Salt によってユーザごとにドメイン分離を行っているのと同じ意味である。
暗号論的ハッシュ関数
セキュリティの文脈で以下の特性を満たすハッシュ関数は暗号論的ハッシュ関数 (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-2 は秘密をハッシュ化しないケースであれば今でも広く使われている)。SHA-3 や BLAKE2, BLAKE3、または SHA-2 でも出力の切り捨てを伴うタイプは伸長攻撃に対して安全である。
SHA-3
SHA-3 (secure hash algorithm 3) は FIPS 202 [1] で NIST によって標準化された暗号論的ハッシュ関数である。これは Keccakと呼ばれるハッシュ関数に基づいており、SHA-3 策定時に指摘されたいくつかのセキュリティの強化やパフォーマンスの向上の変更が加えられている (したがって選択可能な場合は当初の Keccak-f よりも SHA-3 を使用すべきである)。\[ \left\{ \begin{eqnarray*} \mbox{SHA3-224}(M) & = & \mbox{Keccak}[448](M\,||\,{\tt 01},224) \\ \mbox{SHA3-256}(M) & = & \mbox{Keccak}[512](M\,||\,{\tt 01},256) \\ \mbox{SHA3-384}(M) & = & \mbox{Keccak}[768](M\,||\,{\tt 01},384) \\ \mbox{SHA3-512}(M) & = & \mbox{Keccak}[1024](M\,||\,{\tt 01},512) \end{eqnarray*} \right. \] SHA-3 の基となる Keccak は、入出力が固定長のハッシュ化基礎関数である Keccak-p と、そのような関数の入出力を任意長に拡張するフレームワークのスポンジ構造の 2 つで構成されている。ここで:
\(\mbox{Keccak}[c](N,d) = \mbox{SPONGE}[\mbox{Keccak-}p[1600,24],\mbox{pad10*1},1600-c](N,d)\)
\(\mbox{SPONGE}[f,\mbox{pad},r](N,d)\) は基礎関数 \(f\) とパディング関数 \(\mbox{pad}\)、レート \(r\) に基づいて任意長の入力 \(N\) から長さ \(d\) のビット列を生成するスポンジ構造
\(\mbox{Keccak-}p[b,n_r](S)\) は長さ \(b\) のビット列 \(S\) を転置・置換して同じ長さ \(b\) のビット列を出力する基礎関数 (\(n_r\) は内部的な反復回数)
\(\mbox{pad10*1}(x,m)\) は長さ \(m\) のビット列に対して長さが \(x\) の整数倍となるように付加すべきビット列を生成するパディング関数
である。Keccak のスポンジ構造は任意長の出力を生成することができるが、SHA-3 では出力長を固定値として使用している。
また cSHAKE, KMAC, TupleHash などの SHA-3 (Keccak) 派生関数が NIST によって標準化されている [2]。
可変長出力ハッシュ関数
SHA-3 の可変長出力関数 (XOF; extendable-output function) である派生関数 SHAKE ("secure hash algorithm" with "KECCAK") が FIPS 202 [1] で標準化されている。これは特定の長さの乱数列や鍵を生成するときに余計な考慮を省略でき Keccak の転置関数を利用し高速に生成することのできるため安全で利便性が高い。\[ \left\{ \begin{eqnarray*} \mbox{SHAKE128}(M,d) & = & \mbox{Keccak}[256](M\,||\,{\tt 1111},d) \\ \mbox{SHAKE256}(M,d) & = & \mbox{Keccak}[512](M\,||\,{\tt 1111},d) \end{eqnarray*} \right. \]
ドメイン分離ハッシュ関数
NIST SP 800-185 [2] で仕様化されている cSHAKE は SHAKE をドメイン分離が可能なように拡張したもので、基礎に Keccak プリミティブを使ったハッシュ関数の変種を生成することができる。例えば cSHAKE128 では以下のように適用される。\[ \left\{ \begin{eqnarray*} \mbox{cSHAKE128}(M,d,"","") & = & \mbox{SHAKE128}(M,d) \\ \mbox{cSHAKE128}(M,d,N,S) & = & \mbox{Keccak}[256](\mbox{bytepad}(\mbox{encode_string}(N)\,|| \\ & & \hspace{.4cm} \mbox{encode_string}(S),168))\,||\,M\,||\,{\tt 00},d) \\ \end{eqnarray*} \right. \] ここで \(N\) は長さ 2040 未満のビット列で NIST の定義する関数名を表す (cSHAKE として使用するのであれば長さ 0 のビット列でよい)。\(S\) は長さ 2040 未満のビット列でユーザがカスタマイズ可能なドメインを指定する。\(N_1 \ne N_2\) または \(S_1 \ne S_2\) であれば双方の cSHAKE 出力に関連性はない。
タプル型ハッシュ関数
複数の値から一つのハッシュ値を生成する場合、単純に文字列を連結した値をハッシュ化する方法では衝突を発生させやすく安全ではない。例えば宛先 addr と金額 amt からなるトランザクションをハッシュ化するケースで単純に \(h({\tt addr}\,||\,{\tt amt})\) のようにすると、addr=123 宛ての amt=20 送金と、addr=12 宛ての amt=320 送金で同じハッシュ値 \(h(\mbox{"12320"})\) が生成されることになる。
cSHAKE と共に標準化された TupleHash は、このような複数の値からなるタプルをハッシュ化するための標準である。TupleHash は cSHAKE に基づいて複数の値リストから曖昧さのない方法でハッシュ値を生成することができる。
Table 1 は、すべてのバイト値が 0 に初期化されている 1MB のバイト配列を入力 \(x\) とし、それぞれのアルゴリズムを適用してハッシュ値 \(y=h(x)\) の算出にかかった時間を表している。ここでは暗号論的ハッシュ関数だけではなく、単純なチェックサムの CRC や非暗号論的ハッシュ関数の MurmurHash、AES 拡張命令を使用する aHash を比較の目的で挙げている。
アルゴリズム |
算出時間 [μsec/1MB] (±95%信頼区間) |
出力サイズ \(k\) |
🔒 |
CRC32 |
1,821.801 (±1.7%) |
32-bit (4B) |
|
MurmurHash64A |
171.591 (±2.3%) |
64-bit (8B) |
|
MurmurHash3-128 (x64) |
499.188 (±2.0%) |
128-bit (16B) |
|
aHash |
65.593 (±3.6%) |
64-bit (8B) |
|
MD2 |
74,384.134 (±0.7%) |
128-bit (16B) |
☔ |
MD5 |
1,316.656 (±0.3%) |
128-bit (16B) |
☔ |
MD6 |
5,358.656 (±1.9%) |
512-bit (64B) |
🌞 |
SHA-1 |
428.569 (±0.3%) |
160-bit (20B) |
☔ |
RIPEMD-160 |
2,520.825 (±0.9%) |
160-bit (20B) |
⛅ |
RIPEMD-320 |
2,169.878 (±2.2%) |
320-bit (40B) |
⛅ |
Whirlpool |
5,922.141 (±0.9%) |
512-bit (64B) |
⛅ |
SHA-224 |
456.999 (±0.3%) |
224-bit (28B) |
⛅ |
SHA-256 |
456.920 (±0.5%) |
256-bit (32B) |
⛅ |
SHA-386 |
1,364.148 (±4.5%) |
384-bit (48B) |
⛅ |
SHA-512 |
1,367.632 (±4.5%) |
512-bit (64B) |
⛅ |
SHA-512/224 |
1,364.047 (±2.5%) |
224-bit (28B) |
🌞 |
SHA-512/256 |
1,365.937 (±2.7%) |
256-bit (32B) |
🌞 |
SHA3-224 |
1,964.872 (±4.1%) |
224-bit (28B) |
🌞 |
SHA3-256 |
2,069.398 (±1.7%) |
256-bit (32B) |
🌞 |
SHA3-384 |
2,730.082 (±1.7%) |
384-bit (48B) |
🌞 |
SHA3-512 |
3,949.316 (±3.6%) |
512-bit (64B) |
🌞 |
SHAKE128 |
1,675.281 (±1.0%) |
512-bit (64B) |
🌞 |
SHAKE256 |
2,061.755 (±1.5%) |
512-bit (64B) |
🌞 |
Keccak-256 |
2,079.445 (±5.1%) |
256-bit (32B) |
🌞 |
Keccak-512 |
3,935.405 (±1.3%) |
512-bit (64B) |
🌞 |
BLAKE2b |
731.625 (±3.4%) |
512-bit (64B) |
🌞 |
BLAKE2s |
1,210.488 (±0.6%) |
256-bit (32B) |
🌞 |
BLAKE3 |
177.786 (±0.7%) |
256-bit (32B) |
🌞 |
SipHash |
304.354 (±1.9%) |
64-bit (8B) |
🌞 |
SipHash128 |
318.930 (±13.4%) |
128-bit (16B) |
🌞 |
HighwayHash64 |
55.596 (±0.7%) |
64-bit (8B) |
🌞 |
HighwayHash128 |
55.643 (±0.8%) |
128-bit (16B) |
🌞 |
HighwayHash256 |
56.187 (±2.4%) |
256-bit (32B) |
🌞 |
Table 1. アルゴリズムの公開されているハッシュ関数のパフォーマンス。
# AMD Ryzen 7 5700X 8C/16T 3.4GHz + Windows 11 Pro
> rustc +nightly --version
rustc 1.74.0-nightly (58e967a9c 2023-09-03)
アルゴリズム |
算出時間 [μsec/1MB] (±95%信頼区間) |
出力サイズ \(k\) |
🔒 |
CRC32 |
3,336.378 (±3.0%) |
32-bit (4B) |
|
MurmurHash64A |
196.916 (±2.8%) |
64-bit (8B) |
|
MurmurHash3-128 (x64) |
286.406 (±2.6%) |
128-bit (16B) |
|
aHash |
32.361 (±8.2%) |
64-bit (8B) |
|
MD2 |
108,267.728 (±2.5%) |
128-bit (16B) |
☔ |
MD5 |
1,513.948 (±0.8%) |
128-bit (16B) |
☔ |
MD6 |
4,984.893 (±2.3%) |
512-bit (64B) |
🌞 |
SHA-1 |
1,072.668 (±3.6%) |
160-bit (20B) |
☔ |
RIPEMD-160 |
3,381.397 (±0.3%) |
160-bit (20B) |
⛅ |
RIPEMD-320 |
2,492.434 (±1.4%) |
320-bit (40B) |
⛅ |
Whirlpool |
3,029.967 (±0.3%) |
512-bit (64B) |
⛅ |
SHA-224 |
3,086.530 (±4.1%) |
224-bit (28B) |
⛅ |
SHA-256 |
3,042.411 (±0.7%) |
256-bit (32B) |
⛅ |
SHA-386 |
1,848.614 (±0.2%) |
384-bit (48B) |
⛅ |
SHA-512 |
1,851.782 (±0.9%) |
512-bit (64B) |
⛅ |
SHA-512/224 |
1,873.750 (±3.6%) |
224-bit (28B) |
🌞 |
SHA-512/256 |
1,850.387 (±0.6%) |
256-bit (32B) |
🌞 |
SHA3-224 |
1,689.597 (±0.2%) |
224-bit (28B) |
🌞 |
SHA3-256 |
1,789.130 (±0.4%) |
256-bit (32B) |
🌞 |
SHA3-384 |
2,346.811 (±1.0%) |
384-bit (48B) |
🌞 |
SHA3-512 |
3,378.917 (±2.1%) |
512-bit (64B) |
🌞 |
SHAKE128 |
1,452.391 (±1.0%) |
512-bit (64B) |
🌞 |
SHAKE256 |
1,793.653 (±1.5%) |
512-bit (64B) |
🌞 |
Keccak-256 |
1,789.531 (±0.5%) |
256-bit (32B) |
🌞 |
Keccak-512 |
3,418.558 (±3.5%) |
512-bit (64B) |
🌞 |
BLAKE2b |
988.888 (±4.1%) |
512-bit (64B) |
🌞 |
BLAKE2s |
1,625.104 (±2.3%) |
256-bit (32B) |
🌞 |
BLAKE3 |
569.527 (±0.3%) |
256-bit (32B) |
🌞 |
SipHash |
579.611 (±3.4%) |
64-bit (8B) |
🌞 |
SipHash128 |
569.084 (±0.4%) |
128-bit (16B) |
🌞 |
HighwayHash64 |
134.010 (±0.7%) |
64-bit (8B) |
🌞 |
HighwayHash128 |
134.094 (±0.9%) |
128-bit (16B) |
🌞 |
HighwayHash256 |
134.226 (±1.2%) |
256-bit (32B) |
🌞 |
Table 2. アルゴリズムの公開されているハッシュ関数のパフォーマンス。
# Apple M1 Pro 10C/10T + macOS 13.4.1
% rustc +nightly --version
rustc 1.74.0-nightly (58e967a9c 2023-09-03)
アルゴリズム |
算出時間 [μsec/1MB] (±95%信頼区間) |
出力サイズ \(k\) |
🔒 |
CRC32 |
2,039.248 (±5.0%) |
32-bit (4B) |
|
MurmurHash64A |
284.636 (±6.0%) |
64-bit (8B) |
|
MurmurHash3-128 (x64) |
311.602 (±3.7%) |
128-bit (16B) |
|
aHash |
102.361 (±4.9%) |
64-bit (8B) |
|
MD2 |
85,453.103 (±2.4%) |
128-bit (16B) |
☔ |
MD5 |
1,827.365 (±4.1%) |
128-bit (16B) |
☔ |
MD6 |
7,848.815 (±6.5%) |
512-bit (64B) |
🌞 |
SHA-1 |
1,726.049 (±5.1%) |
160-bit (20B) |
☔ |
RIPEMD-160 |
3,528.334 (±4.3%) |
160-bit (20B) |
⛅ |
RIPEMD-320 |
3,220.246 (±11.6%) |
320-bit (40B) |
⛅ |
Whirlpool |
7,337.722 (±6.3%) |
512-bit (64B) |
⛅ |
SHA-224 |
4,555.092 (±6.8%) |
224-bit (28B) |
⛅ |
SHA-256 |
4,504.360 (±4.5%) |
256-bit (32B) |
⛅ |
SHA-386 |
2,378.131 (±4.0%) |
384-bit (48B) |
⛅ |
SHA-512 |
2,357.841 (±4.0%) |
512-bit (64B) |
⛅ |
SHA-512/224 |
2,397.882 (±7.8%) |
224-bit (28B) |
🌞 |
SHA-512/256 |
2,369.942 (±4.3%) |
256-bit (32B) |
🌞 |
SHA3-224 |
3,036.547 (±6.1%) |
224-bit (28B) |
🌞 |
SHA3-256 |
3,243.020 (±7.4%) |
256-bit (32B) |
🌞 |
SHA3-384 |
4,253.709 (±9.3%) |
384-bit (48B) |
🌞 |
SHA3-512 |
6,020.349 (±5.9%) |
512-bit (64B) |
🌞 |
Keccak-256 |
3,175.690 (±5.2%) |
256-bit (32B) |
🌞 |
Keccak-512 |
5,980.489 (±4.7%) |
512-bit (64B) |
🌞 |
BLAKE2b |
1,185.160 (±5.9%) |
512-bit (64B) |
🌞 |
BLAKE2s |
2,858.685 (±8.4%) |
256-bit (32B) |
🌞 |
BLAKE3 |
237.569 (±3.9%) |
256-bit (32B) |
🌞 |
SipHash |
413.324 (±6.1%) |
64-bit (8B) |
🌞 |
SipHash128 |
412.154 (±9.8%) |
128-bit (16B) |
🌞 |
HighwayHash64 |
67.815 (±4.3%) |
64-bit (8B) |
🌞 |
HighwayHash128 |
68.272 (±9.3%) |
128-bit (16B) |
🌞 |
HighwayHash256 |
69.092 (±7.9%) |
256-bit (32B) |
🌞 |
Table 3. アルゴリズムの公開されているハッシュ関数のパフォーマンス。
# Intel(R) Core(TM) i7-8569U CPU 4C/8T 2.80GHz + MacOS 10.15.7 Catalina
% rustc -version
rustc 1.50.0 (cb75ad5db 2021-02-10)
計測結果では AVX/SSE 拡張命令を使用する HighwayHash や AES 拡張命令を使用する aHash の高いパフォーマンスが目を引く。特に Ryzen 5700X と Core i7-8569U での SHA-1, SHA-224, SHA-256 の速度差は CPU が Intel SHAX 拡張命令をサポートしているかの違いによるものと思われる。また AVX 命令を持たない M1 (ARM64) では Ryzen や Core ほど HighwayHash の速度が伸びていない。
このような結果から分かるように、近年のハッシュ関数の性能はハードウェアアクセラレーションのサポートが大きな影響を及ぼしている。
参考文献
- DWORKIN, Morris J. SHA-3 standard: Permutation-based hash and extendable-output functions. 2015.
- KELSEY, John; CHANG, Shu-jen; PERLNER, Ray. SHA-3 derived functions: cSHAKE, KMAC, TupleHash, and ParallelHash. NIST special publication, 2016, 800: 185.