まとめ
ハッシュ関数の中には、SHA256のように伸長攻撃(Length Extension Attack)ができるものがある。
これがよく分からなかったので、伸長攻撃を行うライブラリHashPumpの実装を読むことで、 伸長攻撃がどのようにして行われるかを調査した。
調査の結果、以下のリンクに書いてあることが正しかった。（めっっっっっちゃ遠回りした……）
1. 伸長攻撃とは
伸長攻撃とは、未知のソルトが先頭に結合されたハッシュが与えられたとき、
の2点を利用して、既知のハッシュと文字列の情報を組み合わせて、全く新しいが、システムが正しいと判断するハッシュと文字列の組み合わせ を作成する攻撃である。*1
2. 実装
伸長攻撃ライブラリの実装は、HashPumpが有名だ。
HashPumpでは、MD5/SHA1/SHA256/SHA512の伸長攻撃をサポートしている。
今回はその中でSHA512の伸長攻撃を行うファイル SHA512ex.cpp/SHA512ex::GenerateStretchedData() の実装を読解した。
2.1 参考: SHA512の仕様
SHA512の仕様は、以下が非常に詳しい。
断りのない限り、定数名は上記の記事に倣う。
2.2 HashPumpの実装
HashPump/SHA512ex.cpp at master · bwall/HashPump · GitHub
繰り返しになるが、伸長攻撃では、以下のような文字列とそのハッシュに対して攻撃を行う。
図でいうKeyの部分が、いわゆるソルトと呼ばれている部分であり、伸長攻撃では、このソルトを知ることなしに（ソルト付きの）新しいハッシュを得ることを目標にしている。そのためにはKeyの長さがどうしても必要なのだが、これは分からないので通常あり得そうな値を全探索する（40文字程度探索すれば当たると思う）。
2.2.1 宣言（60行目）
伸長攻撃で必要な情報は、既知のハッシュ(hash)、既知の文字列(originalMessage)、未知の文字列の長さ(keylength)、付加したい文字列(added)の4つだ。 ここでは、それらを引数に取っている。戻り値は、付加したい文字列を付け加えた文字列(ret)と、そのハッシュ(newSig)である。
2.2.2 初期化（61〜64行目）
まずretにoriginalMessageをコピーする。retはハッシュ化する前の文字列だが、未知の文字列が先頭にある。そのため、本来のretの長さはkeylengthだけ長い。なので、本来のretの長さを示す変数tailLengthを用意して、そこに ret.size()+keylength を格納する。tailLengthは、ビット単位の長さが欲しいので、8倍しておく。
2.2.3 パディング（65〜75行目）
ここが伸長攻撃で一番大事な部分。
に書かれている、 SHA512の仕様と全く同じパディング を行う。
すなわち、この時点でのretは以下のようになる。
ここで偽のパディングを行ったことにより、(key|ret)で構成される文字列のハッシュは、引数で与えられたハッシュ(hash)に一致することになる。
SHA512は1024bitごとに決まった処理を行うので、あるブロックで内部状態を一致させさえすれば、どのような情報でも付加できるようになる。
ここで正確にパディングを行うため、Keyが分からなくても、Keyの長さを知っておく必要があった。
2.2.4 内部状態の再現（76〜90行目）
SHA512の出力は、内部変数 \( H_{i} (0 \leq i \leq 7) \) に一致するので、OpenSSLライブラリで使われている、SHA512関数の計算を行うときに使う構造体 SHA512_CTX stretch; に内部状態をコピーする。
コピーしているときに（79〜90行目）、ハッシュが転置しているように見えるが、これはハッシュ関数が出力する際に、8ビット単位で逆さまにして出力しているのを補正するためである。*2
2.2.5 付加したい情報のハッシュ化（92〜100行目）
内部状態と、それに至る入力が手に入ったので、あとはどのような情報を付加しても有効なハッシュとなる（生み出したハッシュと、相手側のシステムが作ったハッシュが一致する）。伸長攻撃で使う付加したい文字列addedを対象に、再現した内部状態を使ってハッシュ化する。
最後にaddedを付加したretを返して終わり。
3. 伸長攻撃の利用先
好きな情報を付加できるので強い攻撃のように見えるが、入力とそのハッシュの両方を好きに操作できるような環境でなければ、効果はないと考えられる（二度目になるが、衝突耐性が破られたわけではないので）。そして大抵のシステムではハッシュを知ることができないので、伸長攻撃を行うことはできないだろう。
4. 余談
SHA2の後継であるSHA3では、たとえブロック長に等しい長さの入力が与えられたとしても、決められたパディングを付加する。この方法ならば、伸長攻撃を防ぐことができる。
*1:全く新しいハッシュではなく、既知のハッシュと同じハッシュを作る攻撃だと勘違いしていたので理解できなかった。これは強衝突耐性の突破を意味するので、ものすごくやばい脆弱性になる。
*2:上記のQiitaには書いていないが、仕様ではそうなっていそう。OpenSSLライブラリの実装ではそうなっていた https://github.com/openssl/openssl/blob/master/crypto/sha/sha512.c
