Cryptographic hash function
$ H: \{0, 1\}^* \to \{0, 1\}^n
可変長のビット列を固定長の短いビット列に変換する関数。
入力のビット列長が大きくてもハッシュ値を高速に求められることが必要
古典的な安全性
原像困難性
yが与えられた時、y=H(x)となるようなxを見つけることが難しい。
第二原像困難性
xが与えられた時、H(x) = H(x')となるようなx’を見つけることが難しい。
衝突困難性
H(x) = H(x') となるようなx, x'を見つけることが難しい。
衝突攻撃の計算量はbirthday attackにより$ 2^{2/n}
SHA3のコンテストにはこれ以外の攻撃に対する耐性（length-extension攻撃、Randomized Hashging）も条件に加わっており、これらがハッシュ関数の安全性として本質的なものなのか説。
indifferentiabilityの性質により安全性を評価するフレームワーク。
Merkle-damgard構造（PGV変換を含む)やsponge構造などの広範な構造に対する安全性評価
ハッシュ関数の機能
*クロード・シャノン提唱
「混ぜる」-> 攪拌処理
ブロック暗号由来
Diffusion （入力値同士の影響）：拡散
permutation：転置
線形性（平文と暗号文の相関）
linear 処理
XOR, ADD, Rotation
平文の統計的な情報の偏りを複雑にする
同じワードの暗号文への関連性など
平文と暗号文との間の統計的な関連性を複雑にする。
Confusion：撹乱
substitution：非線形置換
non-linear 処理
S-box, modular addition, bitwise AND
暗号文と暗号化鍵の関連性をできるだけ隔離する
P-box
https://gyazo.com/22b07bbf6e6a0ff2bb50588d88731160
S-box
m bits入力、n bits出力に変換する関数で、$ 2^mのルックアップテーブルによって実装。
例えば、input: 011011 の時、MSBLSBは01で中間ビットは1101、outputは1001になる。
https://gyazo.com/13233846341044fe651f8cea6b83e14d
「つぶす」
一方向性圧縮関数とか
圧縮
-> 大きな定義域を小さな像にマップする。
不可逆性・一方向性
ブロック暗号
共通鍵暗号の一種で固定長のデータを単位として処理する暗号手法
公開鍵暗号に比べて高速であることが特徴で、ハイブリッド暗号、一方向性関数、MAC、擬似乱数列の生成などに用いられる。鍵の全数探索に対して計算量的安全。
DES: Feistel 構造
22Hで鍵が破られる
56 bits鍵長
トリプルDES
AES(Rijndeal): SPN構造
'00にAESとして選定
128 ~ 256 bitsの鍵長
SubBytes
ShiftRows
MixColumns
AddRoundkey
DES
https://gyazo.com/c2a19fc48ac6d866508daa1906b5351f
Feistel関数
https://gyazo.com/0c78b5ce811dbccfdcfe086f7bb92995
32ビット動作
Expansion
32bits -> 48bits
Key mixing
subkey(master key(64bits)から鍵スケジュールで48 bitsの16個のround keyが生成）
鍵の見た目は64bitsだけどそのうちの8bitsはパリティチェックのため実際は56bits
Substition
8個のs-boxでinput 6bits -> output 4bits
非線形な変換
Permutation
並び替え
ハッシュ関数の難しさ
安全性の根拠を鍵の秘密性や乱数性に置くことができない。
ブロック暗号が入力値と秘密鍵を混ぜるのに対し、暗号学的ハッシュ関数は入力値のみを混ぜなければならない。
一方向性の高速化の難しさ
例えば、離散対数（集合のpermutationかつ一方向）
攪拌と圧縮の適切な組み合わせ
PGV(Prenssel-Govaerts-Vandewalle)変換
Merkle-Damg˚ard構造
sponge構造
Merkle-Damgård構造
https://gyazo.com/14ecf4e15a79f676d196d5293092370a
$ h: \{0,1\}^{512+160} \to \{0,1\}^{160}
入力長672bits（512: message blocks, 160: output)の小さな圧縮関数を繰り返し適用していく。
sha256では64bytesずつmessagrブロックに分割。
大きなハッシュ関数の安全性が小さな圧縮関数fに関する安全性に帰着。（1980年代に衝突困難性に関する帰着の数学的証明がされていた）
あくまでも、圧縮処理のためのインターフェースであり、攪拌処理は圧縮関数内部で行う必要がある
MD5, sha1 -> 内部ブロック暗号はARX型
Addition, Rotation, XORの組み合わせでnon-linearを作る。
TIGER, Whirlpool -> S-box型
look-up tableによるsubstitutionでnon-linearを作る。
2004年Wang教授によるMD5に対する衝突攻撃
sha2もsha1などと類似の構造を取っており、脆弱性が危惧されていたのでsha3では構造が異なるkeccakが選定されたが、逆に最近ではsha2はふつーに強いことが分かってきてる。
ビットコインで使われているSHA-256の仕様と実装について
PGV 変換
攪拌処理はブロック暗号に任せ、圧縮処理の要素を加える。マークル・ダンガード構造内でよく用いられる。
DM(Davies-Meyer)変換、MMO (Matyas-Meyer-Oseas)変換、Miyaguchi-Preneel
基本的には、ブロック暗号の平文を暗号文に差し込んで（例えばXOR）して、それを圧縮関数の出力にするアイデア。（XOR結線をフィードフォワードと言う）
入力長：平文＋鍵の長さ
出力長：暗号文
例えば、sha2はARX型のブロック暗号がDM変換によって圧縮関数に変換され、Merkle-Damgård構造によって繰り返されている。
libstarkの例では、Rijndeal-160が攪拌処理のためのブロック暗号に用いられ、Davies-Meyer変換を適用することでハッシュ関数化している。
Davies-Meyer
https://gyazo.com/fa9c94e2a5b7622bd6ce939e836dfa6c
messageをkeyとして、前のハッシュ値を次の平文に。
MMO
https://gyazo.com/e9e8c7f35693bd5b4154ba23b619c236
前のハッシュ値がkeyとしてg()関数でkey sizeになるようにpaddingし、messageがinputに相当する。
Miyaguchi - Preneel
https://gyazo.com/008798af08c852375dff6533d75f4e45
Sponge構造
https://gyazo.com/916f25fc39ac11e21cc65c3766dae830
keccakが代表的。
小さな圧縮関数を繰り返すのではなく、小さな置換処理を繰り返す。
つまり、圧縮と攪拌を同時に行う安全な圧縮関数を作るのではなく、攪拌だけを行う置換処理を作ればOK。圧縮処理はSponge構造に託す。(例えば、chopによる手法が簡単）
absorbing phaseでメッセージをr bitsごとにブロックに分割して入力（必要に応じてpadding）し、内部状態のrビットとmのXORを求め関数fへの入力とする。つまり、関数fはb = r + c bitsの内部状態を操作するように働き、c bits分は入力ブロックから直接影響を受けることはない。（r: ビットレート、 c: キャパシティ）
全ての入力ブロックが内部状態に吸収されたら、squeezing phaseで同じ関数fでビットレート単位で内部状態が搾取されていく。
keccackは、S-box型のpermutationベースで置換処理を繰り返している。
https://gyazo.com/b558b42c1bbfc3d045a96613b0dbd6d4
https://gyazo.com/b9be9a3449d00d713db8b6571a6a7f43
Blake2
最近イケてるハッシュ関数
blake2b: 64bits最適化
1~64 bytesのdigests
blake2s: 8 or 32 bits最適化
1~32 bytesのdigests
https://gyazo.com/b425df17df0c329b18f01d74dec6cbde
blake2 paper
blake2 new family -> 任意の長さのハッシュ値
よいスライド
よい記事
official implementation
Proposal of precompiled contract for blake2
ChaCha20 core
新しいTLSの暗号方式ChaCha20-Poly1305
証明システムにおけるハッシュ関数
証明システムの文脈では、単に高速なハッシュ関数ではなく、circuit complecityが小さくなるようなハッシュ関数が好まれるようになった。
circuit width, depth, multiplicationなどのどのパラメタが重要になるかはそれぞれの証明システムや暗号プロトコルによるが、SNARKの文脈では、field上の乗算を減らしたいというモチベーション。
（他の暗号プロトコルに関してはPHE - frindley -> low circuit depth
MPC - friendly -> low circuit depth and low number of multiplications)
例えば、sha256はbinary-friendlyでないmodular additionやcyclic sfhitsが大量に使われる。
https://gyazo.com/f72d172bf8836ecc4726bfcb29204b78
MiMC
pedersen commitment
楕円曲線暗号ベース
本来ならば非効率だがSNARKs内計算コストは良い
-> zcash sapling
Friday
えりべん先生考案のbinary-friendlyなハッシュ関数。（primeも開発中）
ハッシュ関数に対する攻撃
interpolation attack
GCD attack
Differential attack
平文の一部の変更により暗号文の変化の偏りを調べ、解読の手がかりを得る手法
Linear attack
平文と暗号文のビットをXORして0になる確率（十分にランダムであれば1/2)が1/2からのズレが大きいビットの箇所を調べて、鍵の情報を得る手法
DESの場合、2^56個試すBrute-force attackよりも少ない計算量である2^47で可能
Higher-order differential attack
Invariant subfield attack
raund constantsを弱く選んだら。
Rebound attack
s-boxで非線形性を導入している構造に有効
Rotational cryptanalysis
ARX型に対する汎用的な攻撃手法で、算術加算、巡回シフト、XORの組み合わせを効率的に線形演算に近似する手法。