SHA-3とは何？ わかりやすく解説 Weblio辞書 (original) (raw)

SHA-3[1] (Keccak)

SHA-3は、元はKeccak (あるいは)[4][5]として知られた暗号学的ハッシュ関数である。SHAシリーズの代替という目的[6]からSHA-3という名があるが、その内部構造はSHA-2までの方式（en:Merkle–Damgård construction）とは全く異なっている。RadioGatúnを基にし、Guido Bertoni、Joan Daemen、Michaël Peeters、Gilles Van Asscheによって設計された。

SHA-3は、2004年のCRYPTOにはじまる、MD5への攻撃成功の確認[7]とSHA-1への攻撃の理論的確立[8] [9]という、急速に進んだ在来の関数の危殆化を動機としたアメリカ国立標準技術研究所(NIST)による、これらに類似した構造を持たないハッシュ関数を求めたコンペティションによるものである。

その後、SHA-2への攻撃法の研究は進んだものの、2017年初頭時点では効率的な（有効な）攻撃法の報告が無いことなどにより、結果としてSHA-2の代替の用意が重要ではなくなると思われていた[10]。その一方で、SHA-1については2017年2月にはクラウドコンピューティングの演算力を利用したGoogleによる衝突攻撃（強衝突耐性の突破）の成功が現実に示され[11]、2017年現在、SHA-2への移行は喫緊の要求となっている。

2012年10月2日、Keccakがコンペティションの勝者として選ばれ[4]、2015年8月5日に正式版が FIPS PUB 202 として公表された[2]。

Keccakはスポンジ構造（英語版）[12][13]を採用しており、メッセージのブロックは状態の初期ビットとのXORを取ったのちに後述のブロック置換が行われる。SHA-3で用いられているバージョンでは、状態は64ビットのワード長の5×5アレイから構成され、総計で1600ビットである。設計者によれば、KeccakはIntel Core 2で12.5 cycles per byteの速度が出ると主張している[3]。また、ハードウェア実装では他のどの最終候補よりも高速であった[14]。

Keccakの設計者は、認証付き暗号や特定のアーキテクチャにおいてより高速のハッシュ計算を実現する「木」構造のハッシュなど、標準化されていない関数の利用法を提唱している[15]。Keccakでは、2の冪で表現できる任意のワード長を使うことができる（最小のワード長は w=20 = 1 であり、そのときの状態は25ビット）。小さい状態長は暗号研究でのテストに有用であり、中間的な状態長（_w_=4のとき100ビット、_w_=32のとき800ビット）は、実用的な軽量の代替実装として利用できる。

ハッシュ関数の構造

ハッシュ関数のスポンジ構造
pi：入力
zi：ハッシュ出力
使われない「キャパシティ」 cは、衝突攻撃や原像攻撃に対して望む耐性の2倍必要である。

Keccakはスポンジ構造を採用しており、入力が一定の比率で内部状態に「吸収」され、ハッシュ出力では同じ比率で「絞り出」される。

データの r ビットを吸収するときには、データと状態の先頭ビットの排他的論理和を取り、ブロック置換を行う。絞り出すときには、状態の先頭 r ビットを出力として生成し、さらなる出力が必要な時にはブロック置換を行う。

この機構の中心はハッシュ関数の「キャパシティ」であり、入力でも出力でも触れられることのない c_=25_w_−_r ビットの状態である。これは求められるセキュリティ強度に応じて調整可能であり、SHA-3では出力ハッシュ長を n ビットとしたとき c_=2_n と保守的な設定がなされている。そのため、1回のブロック置換ごとに吸収されるメッセージの長さ r は出力ハッシュ長に依存することとなり、224、256、384、512ビットの出力ハッシュ長に対して、r はそれぞれ1152、1088、832、576となる。SHA-2シリーズと異なり、SHA-3の関数（固定長を出力する224、256、384、512バージョンおよび可変長出力のSHAKE128およびSHAKE256）は全て同じブロック置換関数を持つ。これらのハッシュ関数を区別するものはパディングとスポンジ関数のパラメータの差のみである。

ハッシュの計算においては、状態を 0 に初期化し、入力をパディングし、それを r ビットごとに分割する。入力を状態に吸収するには、r ビットごとに分割した入力と状態の排他的論理和を取ってからブロック置換を行う。 最終ブロック置換の後の、状態の先頭の n ビットが求めるハッシュ値である。r は常に n より大きいため、絞り出す過程において更なるブロック置換は不要である。

パディング

メッセージを r ビットごとのブロックに分割するためにはパディングが必要である。SHA-3 では、ビットパターン 100....001 が採用されている。つまり、メッセージの後ろに、1つのビット1、その後に幾つかのビット0（0個から r - 1 個まで）、そして最後に1つのビット1を追加する。

パディングの最初と最後のビット1は必須であり、メッセージの長さがすでに r で割り切れる場合であっても追加される。[1]:5.1この場合、_100...001_である長さ r のブロックが追加される。 最後のメッセージブロックが r-1 ビットの場合は、そのブロックに1を追加して r ビットとし、さらに_00...001_である長さ r のブロックが追加される。 このような処理は、ブロック数が増加するため無駄に見えるかもしれないが、安全性のために必要である。

もし最初のパディングビット1がない場合は、パディングが必要なメッセージのハッシュ値と、「パディングされたかのようなメッセージ」のハッシュ値が同じになってしまう（衝突）。

また、最後のビット1は、異なるレート（異なるハッシュ長）のバリアントに対して安全性を保障するために必要である（マルチレートパディング）。もし最後の1がなければ、一つの短いメッセージに対する2つのハッシュ値（例えば r=1152 の場合と r=1088 の場合）が同じになってしまう。

ブロック置換

この置換は、ワード長を w としたとき、5×5×w ビットの状態を別の状態に変換する。2の冪である任意の w=2ℓ に対して定義されているが、SHA-3においてはワード長は w=64 (ℓ= 6) が使われる。

状態は5×5×_w_ビットのアレイで表現される。_A_[_x_][y_][z_] はリトルエンディアンに従うと (5_y + x)×_w + z 番目の入力ビットとなる。インデックス演算は、最初の2つの次元に対しては modulo 5、3つめの次元に対しては modulo w となる。

基本的なブロック置換関数は5つの副ラウンドからなる 12+2ℓ の繰り返しで構成される。それぞれの副ラウンドは単純なものである（代入形式で記述される場合、入力状態を _A_、出力状態を A’ とする）。

θ

5×w_（_w = 64のとき320）ごとの5ビットのカラムのパリティ (この場合、5ビットの排他的論理和) を計算し、さらに隣接する2つのカラムとの排他的論理和を取る。

_A’_[_x_][_y_][_z_] = _A_[_x_][_y_][_z_] ⊕ parity(_A_[_x_-1][0...4][_z_]) ⊕ parity(_A_[x+1][0...4][_z_−1])

ρ

25ワードごとに異なる三角数 0, 1, 3, 6, 10, 15, .... でローテートする。

_A_[0][0]はローテートせず、出力_A’_にコピーする。それ以外すべての 0≤_t_≤23 に対して、_A’_[_x_][_y_][_z_] = _A_[_x_][_y_][_z_−(t+1)(t+2)/2] とする。このとき ( x y ) = ( 0 1 2 3 ) t ( 1 0 ) {\displaystyle {\begin{pmatrix}x\\y\end{pmatrix}}={\begin{pmatrix}0&1\\2&3\end{pmatrix}}^{t}{\begin{pmatrix}1\\0\end{pmatrix}}} カテゴリ：ハッシュ関数・メッセージ認証コード・認証付き暗号

カテゴリ