Keccak
ケチャック
SHA-3, SHAKE128/SHAKE256の元になっているもの SHA-2までの構造とは違う形。
内部状態が最大1600bitあるので3倍くらいになっている。(SHA2-256 512bit, SHA2-512 1024bitか)
ブロックサイズは別にあり、内部状態より小さくなる。
αβσとアルゴリズム別に名がついていて組み合わせて作られている
Keccak
sponge
Keccak-f
Keccak-p
ステップ θ, ρ, π, χ, ι
Keccakはビット単位でpaddingが可能。ビット並びは 87654321 の順、S[0]が 1 S[1] が2 に対応するような
Keccak-p 順列
KECCAK-p $ [b, n_r]
パラメータ
順列化される文字列の固定長 b 順列の幅と呼ぶ 幅 25,50,100,200,400,800,1600
$ n_r 反復数 （ラウンド数) 任意の正の整数
KECCAK-p 順列のラウンドはRnd で示され、ステップマッピングと呼ばれる5つの変換シーケンスで構成される。
順列は、繰り返し更新されるbビットの値の配列で定義され、state(状態)と呼ばれる。stateは順列の入力値で最初に定義される。
SHA3, SHAKEではb = 1600固定
State
KECCAK-p[b, nr]順列の状態はbビットで構成されます。この標準の仕様には、bに関連する他の2つの量、つまりそれぞれwとlで表されるb/25とlog2(b/25)が含まれています。KECCAK-p順列に対して定義されているこれらの変数の7つの可能な値は、以下の表1の列に示されています。
table:表1: KECCAK-p順列幅と関連量
b 25 50 100 200 400 800 1600
w 1 2 4 8 16 32 64 b/25
l 0 1 2 3 4 5 6 log2(b/25)
順列の入力状態と出力状態をbビットの文字列として表し、ステップマッピングの入力状態と出力状態を5×5×wのビット配列として表すと便利です。Sが状態を表す文字列を表す場合、そのビットは0からb-1までインデックス付けされ、
code:S
となります。
A が状態を表す 5 x 5 x w のビット配列を表す場合、そのインデックスは 0 ≤ x < 5、0 ≤ y < 5、0 ≤ z < w となる整数の 3 つ (x、y、z) です。(x、y、z) に対応するビットは A[x、y、z] で表されます。状態配列は、このようにインデックス付けされた 3 次元配列による状態の表現です。
状態配列の構成要素
KECCAK-p 順列の状態配列とその低次元サブ配列は、b = 200 の場合、つまり w = 8 の場合、上の図 1 (省略) に示されています。2 次元サブ配列はシート、プレーン(面, plane)、スライスと呼ばれ、1 次元サブ配列は行(row)、列(column)、レーン(lane)と呼ばれます。これらのサブ配列の代数定義は、用語集のセクション 2.1 に記載されています。
state xyz
plane y を固定した xz面 5w
slice z を固定した zy面 5x5
sheet x を固定した yz面 5w
row yz固定 x方向
column xz固定 y方向
lane xy固定 z方向
bit 1x1x1
A[x, y, z] = S[w(5y+x)+z]
となっていて y x z の順で変換されるので注意。
立体表現上では x と y は 3 4 0 1 2 の順になっているが、表現上のことなのでしばらく気にしなくてもいい。
stete, plane, lane と bit の方向で把握するとよさそう。
バイト列とのマッピングはまだ出てこないが、w から64bitのlong型などの配列で用意するといい。
SHA用には64bit の 5x5配列を用意したい。
ステップ
θ, ρ, π, χ, と ι の5つのステップがある。
入力がAと bまたはw (省略する)。出力がA'。
ι では2つめのパラメータ、ラウンドインデックスirがある。他のステップはラウンドインデックスに依存しない。
SHAなど
SHA-3は互換目的でのみ利用する。RFCなどで規格化される場合はSHAKE128/SHAKE256が使われていてSHA-3は使われない。
暗号強度になるキャパシティ c を決める SHA, SHAKEの場合は2倍 SHA3-256なら512、SHA3-512なら1024
出力 d
暗号強度(SHA) c = d * 2
Keccak ではc = dでもいいがSHAでは2倍している。
b = r + c だったかで r が入出力用ブロックサイズ r = b - c
b = 1600 のとき Keccak［c］っぽく書くことができる -fが付くかも?
table:SHA-3 と強度
SHA b = r + c r ブロックサイズ c キャパシティ 強度 SHA出力 元になるKeccak
SHA-3-256 1600 1088 512 256 Keccak［512］
SHA-3-384 1600 832 768 384 Keccak［768］
SHA-3-512 1600 576 1024 512 Keccak［1024］
SHAKE128 1600 1344 256 256(可変) Keccak［256］
SHAKE256 1600 1088 512 512(可変) Keccak［512］
暗号強度cが増えると1回の入出力に使えるブロックサイズrは減る。
SHA-3では出力サイズがもともと短いので出力側は気にしなくてもいいが、rのさらに先頭を切り出す。SHA-3 512でも1回のサイズに収まっている。
入出力はビット単位で扱う。バイト列と変換する場合は1バイト中の下位ビットが先 76543210 の並び
ビット単位でpaddingができる。padding は 10*1 で 先頭と最後を1にするかたち。
SHA-3 ではpaddingの前にデータの最後に2ビット10を追加してKeccakの値と一致しないようにしている。SHAKEも1111を追加する。
SHA-3はバイト単位で入力 Keccak に2ビット足して渡し、Keeccakで r bit に padding
スポンジ構造
内部状態は b (1600) bit あり、攪拌は1600bit全体に対して行われるのに対して入力、出力は キャパシティ c (暗号強度的なもの) を引いたサイズ r になる。全体を使わないのは nonce や salt 的な役割を持つ部分を残している、長くなると入力数回分からの予測、衝突も難しい、というようなのでわかりやすくなる?
違うデータでハッシュが偶然同じものを見つける、数バイト足したデータは従来のハッシュだと同じ値になってしまう。Keccak では内部状態cまで同じになっていないので同じデータを足してみたところで次のブロックrは別々のものが出てくる。
Keccak、SHAKEでは、出力サイズ d も可変ということで、1回の出力rで足りなければ次の攪拌後の値を追加して出力できる。スポンジ構造を持っているので最初の出力が衝突してもMD5やSHA-2をくり返してみたようなことになったりはしない。
一方向なAESの長い版かStream暗号用としても使えそう?
RawSHAKE
KMACXOF
TupleHashXOF
実装してみるとこんな感じ