SHA1 padding attack
勇士QさんのKernel/VM Advent Calendar 18日目: CTF 暗号問題 - 勇士Qの日記の問題の解答を書かせて頂きます。まだ、解いていなくて、挑戦したいと言う方は以下、ネタバレを含むのでご注意下さい。なお、勘違い部分もあると思うので間違いがあれば指摘して頂けるとありがたいです。
この問題はCODEGATE2010 CTFの問題が元みたいです。CODEGATEの問題は色んな所で解説が上げられているみたいです。CodeGate 2010 Challenge 15 – SHA1 padding attack
問題の内容はKernel/VM Advent Calendar 18日目: CTF 暗号問題 - 勇士Qの日記を見てください。
目的はadmin権限で認証を突破することです。サーバの認証部分はX'masのやつのヒント的なもの - 勇士Qの日記のようになっています。
つまり、secretkeyが分からない状態で、sha1(secretkey + "admin|...(0以外の何か)")を求めることが目的です。
解き方
adminと入力してLoginすると、レスポンスヘッダの中に
Set-Cookie: webauth=YWRtaW58MA==|481d4710a86d68930145eb471293c4240fc99632; Path=/crypto/
として返ってくるので
sha1(secretkey + "admin|0")
はCookieの中より既知です。（481d4710a86d68930145eb471293c4240fc99632）これを用いて、
sha1(secretkey + "admin|0....(padding)")
を求めることが可能です。これを求めるにはパディングするサイズが必要なため、secretkeyの長さ（バイト数）が必要ですが、そこは余り長くないので最終的にブルートフォースでOKです。
SHA1 extension (or padding) attack
説明しやすいように先に答えを書いてしまうと、secretkeyの長さは23バイトです。情報を整理すると、
分かっていること sha1(secretkey + "admin|0") -> 481d4710a86d68930145eb471293c4240fc99632 len (secretkey) -> 23 知りたいこと sha1(secretkey + "admin|0...(padding)")
secretkeyをxxとして表し、 admin|0 の後ろに以下のように、SHA1のアルゴリズムと同じようにパディングを行う。（RFC3174）
00000000 xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx |................| 00000010 xx xx xx xx xx xx xx 61 64 6d 69 6e 7c 30 80 00 |.......admin|0..| 00000020 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00000030 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 f0 |................|
上述のデータをSHA1で計算したものは以下の手順で求められる。以下では、 PyPy lib_pypyに入っている sha.py を用いている。
% python ...(略)... >>> import sha, struct >>> m = sha.new() >>> (m.H0, m.H1, m.H2, m.H3, m.H4) = struct.unpack(">IIIII", '481d4710a86d68930145eb471293c4240fc99632'.decode("hex")) >>> m.count = [0, 512] # 512 = 64 * 8 >>> m.hexdigest() '10d025a4904fe30af81d4ae390db63f11d481b7e'
secretkey以降のデータをbase64でエンコードしてCookieを作ります。
% echo -n '61 64 6d 69 6e 7c 30 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 f0' | xxd -r -p | base64 YWRtaW58MIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAPA=
くっつけて、
YWRtaW58MIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAPA=|10d025a4904fe30af81d4ae390db63f11d481b7e
これをCookieとして送れば以下のレスポンスが得られる。
% echo "GET /crypto/ HTTP/1.1\nHost: ucq-ctf.appspot.com\nUser-Agent: nc\nCookie: webauth=YWRtaW58MIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAPA=|10d025a4904fe30af81d4ae390db63f11d481b7e\n" | nc ucq-ctf.appspot.com 80 HTTP/1.1 200 OK Cache-Control: no-cache Content-Type: text/plain; charset=UTF-8 Expires: Fri, 01 Jan 1990 00:00:00 GMT Date: Wed, 02 Mar 2011 10:08:59 GMT Server: Google Frontend Transfer-Encoding: chunked 23 Congratulation!! h4ppy m3rry (7f :) 0
Congratulation!! h4ppy m3rry (7f :)
