SHA-3 アルゴリズム

SHA-3 とは

米国の国立標準技術研究所(NIST)は，2012年10月2日に次世代の暗号学的ハッシュ関数の標準を決める Secure Hash Algorithm (SHA-3) として Keccak を選定した (Keccak は “ketchak” のように発音する)．その後，2015年8月5日に正式版 FIPS PUB 202 として公開された．
SHA-3 は，MD5 や SHA-1 に対する攻撃の研究の進展に対応するため SHA-2(SHA-224, SHA-256, SHA-384, SHA-512) の次の世代のハッシュ関数アルゴリズムとして公募していたものである．

Keccak の概要

Keccak は，スポンジ構造に基づくハッシュ関数のファミリーである（すなわち，スポンジ関数のファミリー）． Keccak の基本となる撹拌関数は，7つの Keccak-f [b] ( b ∈ {25, 50, 100, 200, 400, 800, 1600}) で表わされる Keccak-f 関数の集合から選ばれた撹拌関数である．b は撹拌幅であり(ビット数)，スポンジ関数が保持する状態の大きさに対応する．

スポンジ関数の状態は， 5×5 レーンの配列として構成される．配列要素の各々の長さ w は，w ∈ {1, 2, 4, 8, 16, 32, 64} (b = 25w) である． 64ビットプロセッサで実装されたとき，Keccak-f [1600] の各レーンは 64ビットの CPUレジスタ (1語) に格納することができる．

Keccak-f [r+c] 関数に対応するスポンジ構造を適用し，入力メッセージに対する特定のパディングを適用するとき，Keccak [r, c] スポンジ関数をパラメータ c (capacity) と r (bitrate) の関数として定義する．ここで，c はセキュリティパラメータである．

擬似コード

Keccak-f 関数を擬似コードで示す (http://keccak.noekeon.org/specs_summary.html)．
ラウンド数 nr は撹拌幅に依存し，nr = 12 + 2l で与えられる．ここで，2l = w である． Keccak-f [1600] に対しては，24 ラウンドになる．

Keccak-f[b](A) {
  forall i in 0…nr-1
    A = Round[b](A, RC[i])
  return A
}

Round[b](A,RC) {
  θ step
  C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4],
                                              forall x in 0…4
  D[x] = C[x-1] xor rot(C[x+1],1),            forall x in 0…4
  A[x,y] = A[x,y] xor D[x],                   forall (x,y) in (0…4,0…4)

  ρ and π steps
  B[y,2*x+3*y] = rot(A[x,y], r[x,y]),         forall (x,y) in (0…4,0…4)

  χ step
  A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]),
                                              forall (x,y) in (0…4,0…4)

  ι step
  A[0,0] = A[0,0] xor RC

  return A
}

上記の擬似コードにおいて，インデックスを持つ全ての演算は mod 5 で行われる．A は撹拌状態を表わす配列であり，A[x, y] はその状態における特定のレーンを示す． B[x, y], C[x], D[x] は中間的な変数である． r [x, y] はローテーションのオフセット値である（表2 参照）． RC[i] はラウンド定数 (round constants) である（表1 参照）．rot (W, r) はビット毎の巡回右シフト演算であり，位置 i のビットを位置 i + r に移動する（レーンサイズの法で）．

パラメータ c (capacity) と r (bitrate) を持つ Keccak [r, c] スポンジ関数の擬似コードを以下に示す．ここでは，メッセージのビット数は 8 の倍数としている．また，簡単のため r はレーンサイズ w の倍数としている．

Keccak[r,c](M) {
  Initialization and padding
  S[x,y] = 0,                         forall (x,y) in (0…4,0…4)
  P = M || 0x01 || 0x00 || … || 0x00
  P = P xor (0x00 || … || 0x00 || 0x80)

  Absorbing phase
  forall block Pi in P
    S[x,y] = S[x,y] xor Pi[x+5*y],    forall (x,y) such that x+5*y < r/w
    S = Keccak-f[r+c](S)

  Squeezing phase
  Z = empty string
  while output is requested
    Z = Z || S[x,y],                  forall (x,y) such that x+5*y < r/w
    S = Keccak-f[r+c](S)

  return Z
}

上記の擬似コードにおいて，S はレーンの配列として状態を表わす．パディングされたメッセージ P はブロック Pi の配列を構成する．また，Pi はレーンの配列として構成されている．演算子 || は．バイト列の結合を表わす．

定数

Keccak の特徴

Keccak は，従来のハッシュ関数の構造とは異なるスポンジ関数という考え方で構築されている．また，Keccak は論理積とローテーションだけを非線形演算として使用しており，保持すべき内部状態は大きくなるもののハードウェアでの実装の面で有利と言える． 現在では，高速なキャッシュメモリなどが十分安価になっており，内部状態を小さくするよりも高速かつ単純な撹拌関数を利用する利点を優先したものと言える．

スポンジ関数に対して標準的な用語を用いれば， bitrate の r はメッセージブロックサイズであり，撹拌幅とメッセージブロックサイズの差が capacity の c である． 撹拌処理は，5 ビット幅の S-Box を持った換字 (substitution) と転置 (permutation) のネットワーク，あるいは線形演算と非常に単純な非線形演算の組み合わせとみなすことができる．

スポンジ関数方式では，大きな内部状態（スポンジ）を用いて複雑な圧縮関数を不要にしている．入力は単に内部状態の一部（例えば，1600ビット中の 1024ビット）に XOR するような方法で行われる．最後の出力圧縮は，単純な切り出しである． また，将来同じ撹拌関数を用いて入出力するブロックサイズを任意に変更できる．

Keccak のアルゴリズムのうち SHA-3 として使うのは keccak-f [1600] である． ブロック全体のビット数 (撹拌幅)が 1600 であり，

撹拌幅 b = ブロックサイズ r + Capacity c

で計算される．SHA-3では通常

c = 2 * ダイジェスト長 n

となるので，ダイジェスト長が短ければ短いほど一度に処理するデータビット数を大きくできるため処理時間が短くなる． すなわち，ブロックサイズ r は，Keccack-512 に対して 576 ビット，Keccack-384 に対して 832 ビット，Keccack-256 に対して 1088 ビット，Keccack-224 に対して 1152 ビットとなる．

参照文献

[1] G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, "The Keccak reference"

[2] G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, "The Keccak SHA-3 submission"

[3] NIST, "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions", FIPS-PUB 202

inserted by FC2 system