Hatena::ブログ(Diary)

人素(とーしろー)の物思い このページをアンテナに追加 RSSフィード

2012-11-03

【CODEGATE2011 - Quals】 Crypto400

人素 お勉強中... (-"-)

問題文:

The attacker got a secret!

問題ファイル:

Crypto400 (2404656D5DA22F5DBA41CDD7AA1C1F7B) 243K

ファイルを調べる。
root@bt:~# file 2404656D5DA22F5DBA41CDD7AA1C1F7B
2404656D5DA22F5DBA41CDD7AA1C1F7B: ASCII text ← テキストファイルのようだ。


#~ ファイルを見てみる。 ~#
root@bt:~# head 2404656D5DA22F5DBA41CDD7AA1C1F7B 
1.2.3.4 - [Sat Mar  5 01:37:37 2011] "GET /8LU7LaBB_KSe8LmDkGCzRaIeorRgX4RBdRsmYdZzjx0 HTTP/1.0" 200
1.2.3.4 - [Sat Mar  5 01:37:37 2011] "GET /bgY_9ZIe9pz8P-r9kz67QKIeorRgX4RBdRsmYdZzjx0 HTTP/1.0" 500
1.2.3.4 - [Sat Mar  5 01:37:37 2011] "GET /bgY_9ZIe9pz8P-r9kz67QaIeorRgX4RBdRsmYdZzjx0 HTTP/1.0" 500
1.2.3.4 - [Sat Mar  5 01:37:37 2011] "GET /bgY_9ZIe9pz8P-r9kz67QqIeorRgX4RBdRsmYdZzjx0 HTTP/1.0" 500
1.2.3.4 - [Sat Mar  5 01:37:37 2011] "GET /bgY_9ZIe9pz8P-r9kz67Q6IeorRgX4RBdRsmYdZzjx0 HTTP/1.0" 500
1.2.3.4 - [Sat Mar  5 01:37:37 2011] "GET /bgY_9ZIe9pz8P-r9kz67RKIeorRgX4RBdRsmYdZzjx0 HTTP/1.0" 500
1.2.3.4 - [Sat Mar  5 01:37:37 2011] "GET /bgY_9ZIe9pz8P-r9kz67RaIeorRgX4RBdRsmYdZzjx0 HTTP/1.0" 500
1.2.3.4 - [Sat Mar  5 01:37:37 2011] "GET /bgY_9ZIe9pz8P-r9kz67R6IeorRgX4RBdRsmYdZzjx0 HTTP/1.0" 403
1.2.3.4 - [Sat Mar  5 01:37:37 2011] "GET /bgY_9ZIe9pz8P-r9kz4ARKIeorRgX4RBdRsmYdZzjx0 HTTP/1.0" 500
1.2.3.4 - [Sat Mar  5 01:37:37 2011] "GET /bgY_9ZIe9pz8P-r9kz4BRKIeorRgX4RBdRsmYdZzjx0 HTTP/1.0" 500

HTTPのアクセスログでしょうか。。

HTTPリクエストと、行末にはステータスコードがありますねぇ。


このログを見た瞬間、「Padding Oracle Attacks(パディングオラクル攻撃)」ではないかと気づく。。。のだそうですが、

当然、人素にはわかりませんでした。(__)/~

はい、以下、各有識者様サイト参考のもと、お勉強記録です。。


ということで、パディングオラクル攻撃ですが、

ブロック暗号の解読エラーを利用するもので、適当な文字列を暗号文として送りつけ、パディングが不正な場合に起きる特殊なエラーもしくは処理されないという事実を利用して、その文字列が暗号文として適切かどうかを調べる。それを繰り返すことで、暗号化データを鍵無しで解読できるようになるという脆弱性で、ASP.NET、Ruby on Rails、JSFなどにあるそうです。(パッチ適用済み)


ここで、パディングって何?ってことですが、

データをブロック暗号にする際、1ブロックのデータサイズが足りない時に詰め物(padding)をするということですね。

 例:)1ブロック8バイトとした場合、「data(4文字)+パディング(4文字[16進数])」

   f:id:tooshiroo:20121111162223p:image

   1文字パディングなら

   01

   2文字パディングなら

   0202

   以下同じく

   030303

   04040404

   0505050505

   ・・・

ちなみに、パディングの16進数文字ですが、

パディング文字数と同じ数字を、その数だけ入れるのは、PKCS#7(PKCS#5)padding方式だそうです。

(※ #5はブロック長が8固定)


また、ブロック暗号化には暗号化利用モードがありますが、処理速度と強度からCBCモード(Cipher Block Chaining)がよく利用されるようですので、今回もこれを想定して見ていこうと思います。

f:id:tooshiroo:20121111161512p:image


※ 図は、以下を参考にさせてもらいました。(暗号化本の定番と言えばこの本ですよね。)

新版暗号技術入門 秘密の国のアリス

新版暗号技術入門 秘密の国のアリス


あと、"oracle"は、暗号分野で言う所の「暗号理論における一種の神託機械(理論的ブラックボックス)」の意で、

RDBMSの方じゃないというのは。。。ですよね。orz


パディングオラクル攻撃をした際のHTTPステータスコードですが、

それぞれ以下のような意味になります。

番号メッセージ意味
500Internal Errorパディングが不正。
403Forbiddenパディングは一致しているが、Keyが不正。
200OKパディングもKeyもどちらも一致している。

それでは、上記を踏まえログファイルを見ていきます。

ファイルを整形し、内容を確認する。
#~ 操作し易いようにファイル名を変更 ~#
root@bt:~# mv 2404656D5DA22F5DBA41CDD7AA1C1F7B log.txt


#~ pythonスクリプトを作成し、不要な文字列を除き、文字列部分を16進数に変換する。 ~#
root@bt:~# vi shaping.py

【shaping.py】

#!/usr/bin/env phthon
import re
import sys
from base64 import urlsafe_b64decode

logfile = open('log.txt').read()

# Base64文字列とステータスコードを抽出する。
relist = re.findall("GET /(.*0) HTTP/1.0\" (\d+)", logfile)

# Base64文字列をデコードし、16進数に変換する。
for block, rescode in relist:
  block += '=' * (4 - (len(block) % 4))    # Base64デコードのパディングを調整する。
  block = urlsafe_b64decode(block)        # デコード時に"-","+"を"_","/"へ変換する。
  hexenc = block.encode('hex')              # 16進数へ変換する。

    # 16進数値を半分区切りで出力、ステータスコード出力
  print hexenc[:len(hexenc)//2], hexenc[len(hexenc)//2:], int(rescode)

#~ スクリプトを実行し、文字列抽出 ~#
root@bt:~# python shaping.py > shap.txt

#~ 内容確認 ~#
root@bt:~# head shap.txt
f0b53b2da041fca49ef0b9839060b345 a21ea2b4605f8441751b2661d6738f1d 200
6e063ff5921ef69cfc3feafd933ebb40 a21ea2b4605f8441751b2661d6738f1d 500
6e063ff5921ef69cfc3feafd933ebb41 a21ea2b4605f8441751b2661d6738f1d 500
6e063ff5921ef69cfc3feafd933ebb42 a21ea2b4605f8441751b2661d6738f1d 500
6e063ff5921ef69cfc3feafd933ebb43 a21ea2b4605f8441751b2661d6738f1d 500
6e063ff5921ef69cfc3feafd933ebb44 a21ea2b4605f8441751b2661d6738f1d 500
6e063ff5921ef69cfc3feafd933ebb45 a21ea2b4605f8441751b2661d6738f1d 500
6e063ff5921ef69cfc3feafd933ebb47 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69cfc3feafd933e0044 a21ea2b4605f8441751b2661d6738f1d 500
6e063ff5921ef69cfc3feafd933e0144 a21ea2b4605f8441751b2661d6738f1d 500

● 1行目が、ステータスコード"200"で成功しています。

● 8行目に、ステータスコード"403"でパディングが一致しています。


また、2行目以降を見ると、前半のブロック(16バイト)において、

最終1バイトの値が1づつ増えていっているのが分かります。そして、ステータスコード"403"でパディングが一致すると、次のステップに移り、9行目以降は最終2バイト目が1づつ増えていっているのが分かります。


これは、以下のような攻撃シーケンスが行われていることになります。


パディングオラクル攻撃シーケンス

例えば、以下のようにブロック暗号(CBCモード)にて、"testdes\x01" が暗号化及び、復号化されるとします。


暗号化は、

 1. 初期化ベクタとプレーンテキスト"testdes\x01"の16進数値を"XOR"します。

 2. その値(ここでは中間値とする)を、暗号処理します。(例:3DES)

 3. 暗号化テキスト"R\xed\x83\xe7.7\xe3\xb4"が生成されます。

f:id:tooshiroo:20121111232506p:image


復号化は、暗号化の逆順序ですので、

 1. 暗号化テキスト"R\xed\x83\xe7.7\xe3\xb4"を復号処理します。(例:3DES)

 2. その値(ここでは中間値とする)と、前ブロックの暗号化テキスト(ここでは初期ベクタ)を"XOR"します。

 3. プレーンテキスト"testdes\x01"が生成されます。

f:id:tooshiroo:20121111232505p:image




ここで、ランダムな文字列で暗号文をサーバへ送信し、ステータスコード"200"が返ってくる場合というのは、

1つ前の暗号文ブロック文字列のみです。この例では初期ベクタ(以降、IV)となります。

f:id:tooshiroo:20121112013152p:image


ただ、復号処理部分(例では3DES)の鍵が分からない以上、プレーンテキストは分かりません。

しかし、パディングオラクルの脆弱性があるサーバでは、パディングの一致・不一致がステータスコードによって分かってしまいます。




そこでまず、IVを"0"として送信したとします。

パディング不正により、ステータスコード"500"が返ってきます。

※ 実際は、中間値は分かりませんので、ただ"0"を送信したら、ステータスコード"500"が返ってきたというだけです。

f:id:tooshiroo:20121112013153p:image


IVが"1"の場合では、

f:id:tooshiroo:20121112013154p:image


これを1づつ増やして続けていきます。

そして、IVが"5A"の時、ステータスコード"403"が返ってきます。

f:id:tooshiroo:20121112013155p:image




これは、パディングとしてなら一致しているということです。

つまり、"0x5A"の時のプレーンテキストがパディング"0x01"ということで、

  中間値 xor "0x5A" = "0x01"

        ↓

  中間値 = "0x01" xor "0x5A"

となり、最終バイトの中間値が"0x5B"と判明してしまうのです\(◎o◎)/!


f:id:tooshiroo:20121112013156p:image




続いて、パディングが2バイトの場合を試します。

最終1バイトの中間値は、"0x5B"と確定していますので、"0x02"とのXORで、IVは"0x59"。

最終2バイト目のバイトを、0から順に1づつ増やして試していきます。

f:id:tooshiroo:20121112013157p:image


IVを"0x7159"とした時、ステータスコード"403"が返ってきて、これが"0x0202"のはずなので、

最終2バイトの中間値が"0x735B"と判明。

f:id:tooshiroo:20121112013158p:image


以降、同じようにして全バイトパディングの時まで実施することで、中間値が全て判明します。

f:id:tooshiroo:20121112013159p:image




中間値というのは、復号処理(3DES)を終えた後の値ですので、これが判明してしまえば、

先に正当な初期ベクタが判明していますので、2つをXORするとプレーンテキストが解読できるというわけです。コワ(;_;

f:id:tooshiroo:20121112031304p:image


ということで、問題に戻ります。

ステータスコード"200","403"を抽出する
#~ ステータスコード"500"を除く。 ~#
root@bt:~# cat shap.txt | grep -Ev '500$' > except500.txt

#~ 内容確認 ~#
root@bt:~# cat except500.txt 
f0b53b2da041fca49ef0b9839060b345 a21ea2b4605f8441751b2661d6738f1d 200
6e063ff5921ef69cfc3feafd933ebb47 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69cfc3feafd933eb244 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69cfc3feafd9360b345 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69cfc3feafdf167b442 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69cfc3feae3f066b543 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69cfc3fd6e0f365b640 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69cfc9cd7e1f264b741 a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69ca693d8eefd6bb84e a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ef69da792d9effc6ab94f a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5921ec69ea491daecff69ba4c a21ea2b4605f8441751b2661d6738f1d 403
6e063ff59209c79fa590dbedfe68bb4d a21ea2b4605f8441751b2661d6738f1d 403
6e063ff5f50ec098a297dceaf96fbc4a a21ea2b4605f8441751b2661d6738f1d 403
6e063f6df40fc199a396ddebf86ebd4b a21ea2b4605f8441751b2661d6738f1d 403
6e06416ef70cc29aa095dee8fb6dbe48 a21ea2b4605f8441751b2661d6738f1d 403
6edb406ff60dc39ba194dfe9fa6cbf49 a21ea2b4605f8441751b2661d6738f1d 403
a5c45f70e912dc84be8bc0f6e573a056 a21ea2b4605f8441751b2661d6738f1d 403

以下のように、前半の16バイトの最終バイトから徐々にパディング値を検出している。

f0b53b2da041fca49ef0b9839060b345  ←正当暗号ブロック

6e063ff5921ef69cfc3feafd933ebb47
6e063ff5921ef69cfc3feafd933eb244
6e063ff5921ef69cfc3feafd9360b345
6e063ff5921ef69cfc3feafdf167b442
6e063ff5921ef69cfc3feae3f066b543
6e063ff5921ef69cfc3fd6e0f365b640
6e063ff5921ef69cfc9cd7e1f264b741
6e063ff5921ef69ca693d8eefd6bb84e
6e063ff5921ef69da792d9effc6ab94f
6e063ff5921ec69ea491daecff69ba4c
6e063ff59209c79fa590dbedfe68bb4d
6e063ff5f50ec098a297dceaf96fbc4a
6e063f6df40fc199a396ddebf86ebd4b
6e06416ef70cc29aa095dee8fb6dbe48
6edb406ff60dc39ba194dfe9fa6cbf49
a5c45f70e912dc84be8bc0f6e573a056

ブロック長が16バイトなので、全バイトがパディングの場合は、

16(16進数では"0x10")が16回で、"0x10101010101010101010101010101010"。


この時の暗号ブロック文字列が"0xa5c45f70e912dc84be8bc0f6e573a056"ということで、

  中間値 = "0xa5c45f70e912dc84be8bc0f6e573a056" xor "0x10101010101010101010101010101010"

  中間値 = "0xb5d44f60f902cc94ae9bd0e6f563b046"


中間値が判明したので、正当な暗号ブロック文字列とのXORでプレーンテキストを求める。
root@bt:~# python
Python 2.6.5 (r265:79063, Apr 16 2010, 13:57:41) 
[GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
   #~ 正当な暗号ブロック文字列と中間値のXOR ~#
>>> key = 0xf0b53b2da041fca49ef0b9839060b345 ^ 0xb5d44f60f902cc94ae9bd0e6f563b046

   #~ 文字列へデコードする。 ~#
>>> format(key, 'x').decode('hex')
'EatMYC000kiee\x03\x03\x03'


'EatMYC000kiee\x03\x03\x03'

見事にプレーンテキストが現れた\(^o^)/

パディングもバッチリ含まれている。


EatMYC000kiee

これが答えのようだ。


(p_-) ===【 感 想 戦 】=== (p_-)

それにしても、この脆弱性をよく見つけたよなぁー (^_^;

そして、まだパッチを当てていないサーバは、早急な対応が必要なことがよく分かる。

攻撃ツールも公開されているので、速攻で解読されてしまう。


なんか今日はよく勉強した気がする。。zzz

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/tooshiroo/20121103/p1
リンク元