はじめに
をmd5やsha1などのハッシュ関数としたとき，
から
を求める攻撃をLength Extension Attackと呼びます．
この記事では先日の研究室内で開いたCTFで出題した問題を例に，Length Extension Attackの原理と使い方を説明するとともに，Pythonによる実装を公開しようと思います．
Length Extension Attackの原理
ハッシュ関数は入力メッセージをいくつかのブロックに分けて，4ブロックごとに処理します．メッセージのブロック数が4の倍数でないときは，メッセージの最後に適当なパディングが付け足され，4ブロックごとに処理できるようにされます．ハッシュ関数の大まかな処理を下図に載せました．
最初のブロックでは図のように初期ベクトルIVを与え，各ブロックを順番に内部処理していきます．そして，最終的にはA,B,C,Dを並べた値を出力とします．メッセージが4ブロックよりも多い場合は，前の処理で得た出力をIVとして，同様に処理します．今，あるメッセージのハッシュ値を
とします．では，この
をIVとして
のハッシュ値を取るとどうなるでしょうか．単純に考えれば
が計算できそうです．ただし，
のブロック数が4倍でない場合はパディングが追加されてしまうので，実際には
を計算させます．したがって，必ずしも
が得られる訳ではありませんが，ゴミデータが間に入っているハッシュ値でも攻撃に利用できる場合があるのです．
問題（自作問題）
攻撃原理を説明したところで，具体的な問題を解いてみましょう．次の問題は研究室内のCTFで出題したCrypto問題です．Hack You CTF 2014のhashmeという問題をベースに作りました． 問題ファイルとして，次のserver.pyと，これが動いているサーバーのアドレスとポート番号が渡されます．（文字列変数FLAG, SLATが入ったsecret.pyを別途用意する必要あり）
学生としての証明書をいくらでも発行できるサービスなのですが，教師としての証明書を作ることはできません．権限が教師の証明書を使えばフラグを見ることができます．証明書の発行でユーザー名を入力するとdata = 'priv:student|user:' + usernameが作られhash = md5(SALT + data)が計算されます．証明書はbase64(data + hash)として出力されます．construct関数でdataを辞書に展開するのですが，後ろにあるデータが優先されるので，usernameとして'hoge|priv:teacher'を与えれば教師権限を取ることができます．しかし，usernameとして使える文字は限られているので直接これを入力することはできません．
ということで，md5(SALT + m1)が得られるので，ここからhash = md5(SALT + m1 + padding + '|priv:teacher')を計算し，証明書としてbase64(m1 + padding + '|priv:teacher' + hash)を与えれば教師権限を取ることができます．ただし，SALTの文字数が分からないのでパディングがどれだけ必要かは分かりません．これはどうしようもないので，SALTの文字数を1から順に変えていって試すしかないです．
Length Extension Attackの実装
攻撃自体は難しくないのですが，md5の初期ベクトルを変える必要があります．せっかくなので，今回はMD5の実装もしました．（HashPumpというツールもあるので試してみてください．）コードは下記のようになり，案の定MD5の実装に手間と行数を取られました．また，追加データのハッシュを取るだけでなく，そこまでのデータ長を足したものをハッシュに使う必要があることになかなか気付けませんでした．
攻撃と問題の説明はここまでです．興味のある方は，問題を解くコードも作ってみてください． SALTを"hoge"としてみると，こんな感じになります．
$ python lenxpand.py known_md5 = e63f73a0551c84d96fd4d1311410d0ef new_md5 = 77704b5b44435e866c45f001da0f69df new_md5* = 77704b5b44435e866c45f001da0f69df data = 'user\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00@\x00\x00\x00\x00\x00\x00\x00|priv:teacher'
もちろんHashPumpの出力と同じになります．
$ hashpump -s e63f73a0551c84d96fd4d1311410d0ef -d user -k 4 -a "|priv:teacher" 77704b5b44435e866c45f001da0f69df user\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00@\x00\x00\x00\x00\x00\x00\x00|priv:teacher
参考文献
Length Extension Attackに関する詳しい説明： katagaitai CTF勉強会 #5 Crypto
