Keccak

ケチャック

SHA-2までの構造とは違う形。

内部状態が最大1600bitあるので3倍くらいになっている。

ブロックサイズは別にあり、内部状態より小さくなる。

αβσとアルゴリズム別に名がついていて組み合わせて作られている

Keccak-f

KECCAK-p パラメータ

b 幅 25,50,100,200,400,800,1600 SHA系は1600固定

nr 反復数

最大? 5x5x64bit (1600bit)ぐらいの内部状態を持ち、部分的に更新していく。

計算用には2つぐらい1600bitの列があれば足りそう。

暗号強度になるキャパシティ c を決める SHAの場合は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］

暗号強度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