Google CTF 2016 Writeup - Eucalypt Forest, Wolf Spider

2016/4/29~2016/5/1に開催されたGoogle CTF 2016にチームm1z0r3として参加しました．今回はEucalypt ForestとWolf Spiderという暗号問題のWrite-Upを書こうと思います．
https://capturetheflag.withgoogle.com/

Eucalypt Forest　[Crypto 100pt]

Task

Can you find any weaknesses in the use of the encryption keys?

Head over to eucalypt-forest.ctfcompetition.com

Overview

リンクにアクセスするとブログサイトが表示される．このサイトに攻撃を仕掛け，adminとしてログインするとFlagが得られることが分かる．"Signup"からは任意のユーザー名を入力してログインできるが，ユーザー名にadminに指定した時にのみアクセスが弾かれるようになっている．

ブログの開発記事を読んでみると，Cookie（UID）を用いてセッション管理をしていることが分かる．セッション情報は{ "username": "hoge" }のようなフォーマット（これをobjと呼ぶことにする）になっているが，objはAES-CBCで暗号化され，以下のようにUIDが決定する．

UID = IV + Encrypt(obj + padding)

IVはCBCモードのInitial Vector（16byte）であり，暗号文のバイト数が16（ブロック長）の倍数になるようにpaddingが挿入されている．

暗号化および復号処理のコードは以下のようになっている．

class CookieCutter:
	KEY_SIZE=16

	@staticmethod
	def encode(obj):
		s = json.dumps(obj)

		iv = os.urandom(16)

		# because len(s) may not be a multiple of the key size, we need to pad it
		# https://tools.ietf.org/html/rfc2315#section-10.3 has a way of
		# clearly indicating how padding should be performed, and how it
		# should be removed.

		pad = (16 - (len(s) % 16))
		s += chr(pad) * pad 

		algo = AES.new(Storage.aes_key,
			AES.MODE_CBC,
			IV=iv)
		crypttext = algo.encrypt(s)
		c = (iv + crypttext).encode('hex')
		return c

	@staticmethod
	def decode(string):
		crypttext = string.decode('hex')
		if len(crypttext) < 16:
			return None
		iv, crypttext = crypttext[:16], crypttext[16:]
		algo = AES.new(Storage.aes_key,
			AES.MODE_CBC,
			IV=iv)
		plaintext = str(algo.decrypt(crypttext))
		pad = ord(plaintext[-1])
		if pad > CookieCutter.KEY_SIZE:
			raise ValueError, "pad error - pad is %d" % (pad)

		expected = chr(pad) * pad
		piece = plaintext[-pad:]

		if piece != expected:
			raise ValueError, "padding is corrupted"

		try:
			obj = json.loads(plaintext[:-pad])
		except:
			return None

		return obj

Solution

概要より，"Signup"からログインしなくてもadminのCookieを特定してセットすることでセッションハイジャックが成立し，adminとしてログインできることが推測できる．つまり，objが{ "username":"admin" }と復号されるようなCookieを作成すればよい．ここで，ブロック暗号におけるCBCモードの復号処理は以下のようになっている．

暗号利用モード - Wikipedia

図からわかるように，CBCモードでは1ブロック目の平文にはIVの値が影響を与える．今回，IVの値を任意の値に改ざんして送信することができるため，つまりは1ブロック目の平文を自由に操作することができるとうことになる．このようなCBCモードへの攻撃については，結城浩先生の『暗号技術入門 秘密の国のアリス』でも言及されている．

今，ユーザー名にadminを指定してログイン出来ないため，`dminとしてログインしてみると，以下のUIDの値を得る．

UID=e3c9e5d160562dd4fb7d8944f46b67429b23b5aeb301ff166d780197c1b84b0eabe6c79a622fe09b95533a0b5a3d3684

これをブロックごとに分割すると以下のようになる

e3c9e5d160562dd4fb7d8944f46b6742 <- IV
9b23b5aeb301ff166d780197c1b84b0e <- encrypt('{ "username":"`d')
abe6c79a622fe09b95533a0b5a3d3684 <- enctypt('min" }' + padding)

これを見ると，1つ目の平文ブロックの後ろから2byte目は`となっており，復号の直前にIVの後ろから2byte目の値（0x67）とXORされることがわかる．`はASCIIコードで言えばaのひとつ前の文字であり，1bitの差がある．つまり，IVの後ろから2byte目を1bit反転して0x66にすると，`として復号されるはずのものがaとして復号され，{ "username":"admin" }という形になる．

したがって，adminとしてログインしたい時のUIDの値は次のようになる．

UID=e3c9e5d160562dd4fb7d8944f46b66429b23b5aeb301ff166d780197c1b84b0eabe6c79a622fe09b95533a0b5a3d3684

これをCookieにセットしてサイトにアクセスするとadminとしてログインでき，Flagが得られる．

Flag: CTF{lettuce.3njoy.our.f00d.puns}

Wolf Spider　[Crypto 125pt]

Task

Continuing on from Eucalypt Forest - can you break Message Authentication in Wolf Spider

Overview

この問題はEucalypt Forestと姉妹問題であり，Eucalypt Forestをよりセキュアにしたブログとなっている．具体的には，以下の実装により改ざん検知用のハッシュ値を付加されており，前問のようにobjの値の一部を書き換える，といったことが不可能になっている．

@staticmethod
def make(dct):
	tcd = urllib.urlencode(dct)

	# Use RFC1321 to hash our data, so it can't be tampered with.
	h = SHA.new()
	h.update(Storage.mac_key)
	h.update(tcd)
	s = h.digest()

	coded = CookieCutter.encode(tcd)

	return s.encode('hex') + "." + coded.encode('hex')

@staticmethod
def unmake(st):
	pieces = st.split(".")
	if len(pieces) != 2:
		return None

	s = CookieCutter.decode(pieces[1].decode('hex'))
	if s == None:
		return None

	h = SHA.new()
	h.update(Storage.mac_key)
	h.update(s)
	f = h.hexdigest()

	if pieces[0] != f:
		# print "hash comparasion failed :("
		return None

	kv = urlparse.parse_qsl(s)
	ret = {}
	for k, v in kv:
		ret[k] = v
	return ret

ソースコードより，UIDの値は以下のように決定する．

UID = Hash(key + tcd) + '.' + IV + Encrypt(tcd + padding)

URL enocodeにより，例えばユーザー名がhogeのとき，tcdの値はusername=hogeとなる．

Solution

まず，改ざん検知のためのハッシュ関数ではRFC1321が採用されているが，これにはLength-Extension Attack（伸長攻撃）の脆弱性がある．Length-Extension Attackとは，ハッシュ関数Hについて，H(secret+x)のxとyが既知であるとき、secretの逆算はできなくても、H(secret+x+z)が求めることができる，といった攻撃手法である．ハッシュ関数が入力を先頭から処理していくので、yからsecret+xの処理が終わった状態を求め、その状態からzの計算をすれば良い。

今回の問題では，Hash(key + tcd)において，keyの値を知ることができないが，Hash(key + tcd + x)のハッシュ値を作ることができる．このことを利用してどんなことができるだろうか．ここで，tcdをusername=hoge，xを&username=adminとすることを考えてみる．Length-Extension AttackのツールとしてHashPumpを使い，ハッシュ値を算出してみる．

• GitHub - bwall/HashPump: A tool to exploit the hash length extension attack in various hashing algorithms

単純にhogeとしてログインした時のハッシュ値はd16edda3f35fbb1cac1f9381ff1c263e60143511だったので，コマンドは以下のようなる．

# hashpump -s d16edda3f35fbb1cac1f9381ff1c263e60143511 -d 'username=hoge' -a '&username=admin' -k 32
b78ca576701807fc18e64db090aa4f6939232416
username=hoge\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01h&username=admin

Length-Extension Attackの結果，

Hash(key + "username=hoge\x80\x00\x00....\x01&username=admin") = b78ca576701807fc18e64db090aa4f6939232416

を得ることができた．

URLパラメータは同じ変数名が&で続いた場合，後ろの値に上書きされる（usernameの値はadminになる）．つまり，username=hoge\x80\x00\x00....\x01&username=adminの暗号文がわかりさえすれば，adminのUIDを作ることができる．ただし，"Signup"から入力した値はURL Encodeによって&や=などの特殊文字がエスケープされてしまうため，この暗号文を作るのは一筋縄ではいかない．

ここで用いるのが，Padding oracle attackである．Padding oracle attackは，ブロック暗号のPadding部分にPadding長の情報が埋め込まれることを利用し，任意のブロックの情報をブルートフォースで1byteずつ特定していく手法である．ちなみに，SSL v3.0の重大な脆弱性である"POODLE"も，このPadding oracle attackを利用したものである．

• SSL v3.0の脆弱性「POODLE」ってかわいい名前だけど何？？ - Padding Oracle On Downgraded Legacy Encryptionの仕組み - — Mobage Developers Blog

今回の問題においても，上記の暗号化・復号処理のプログラムを見ると，Padding oracle attackの脆弱性があることが分かる．Padding oracle attackは主に暗号化前の平文ブロックを特定するために使われるが，今回はこの攻撃を暗号ブロックを特定するために使用する．

特定したい暗号ブロックの，元の平文ブロックは以下のとおりである．

P1: 'username=hoge\x80\x00\x00'
P2: '\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01h'
P3: '&username=admin'

また，P1~3に対応する暗号ブロックをそれぞれC1~3と呼ぶことにする．IVおよびC1~3が特定できれば，先ほどLength-Extension Attackで求めたハッシュ値と合わせてadminのUIDを作ることができる．

まず，C2，C3を特定する（ここではまだPadding oracle attackは使わない）．
平文P'（16byte）を暗号化したとき，IV'+C1'+C2'を得たとする（C2'はPaddingの分）．ちなみにP'の値は何でもいい（16byteに収まるように "username=aaaaaaa" とでもしておけばよい）．このとき，暗号ブロックC1'をC3として利用することを考える．

ここで，C2 = IV' ^ P' ^ P3と定めると，C1'がP3として復号される．なお，記号^は排他的論理和を表す．

ここまででC2とC3の値が決定した．次にC1を決定したいのだが，C2の復号器にかけた直後の値（これをR2とする）がわからない．このR2を特定するために使うのがPadding oracle attackである．

Padding oracle attackのために，さきほどのIV'+C1'+C2'を使い回す（Validであればusernameはなんでもいい）．これらの暗号ブロックに2つの攻撃ブロックを付加してサーバに送信する．一つはブルートフォース用のブロック(mid)，もう一つがC2である．midの最下位バイトを0x01~0xffまでブルートフォースしていくと，1度だけHTTP Status Codeが200で返ってくる時がある（それ以外は500）．これは，復号の結果Paddingが0x01になり，サーバに受理されたことを示す．仮にmidの最下位バイトが0x12のとき，R2の最下位バイトは0x12 ^ 0x01 = 0x13と計算できる．

このようにして，R2の他のバイトも特定していく（例えばPadding長が2byteのとき，Paddingは\x02\x02となり，R2の後ろから2byte目を特定できる）．

これにより無事R2を特定することができた．あとはC2を特定した時とおなじ要領でC1を特定する．また，もう一度同じようにPadding oracle attackを適用するとR1の値がわかり，IVの値も特定できる．以上で必要なブロックをすべて揃えることができた．ここまでの手順をまとめると以下のようになる．

1. C3 = C1'
2. C2 = IV' ^ P' ^ P3
3. R2 = Decrypt(C2)
4. C1 = R2 ^ P2
5. R1 = Decrypt(C1)
6. IV = R1 ^ P1

Decrypt()はPadding Oracle Attackにより実行可能

あとはこれらをくっつけてUIDにすればadminのCookieの出来上がりである．

Solver

Result

UID: b78ca576701807fc18e64db090aa4f6939232416.dc3cd1cc0697b720cd117bb4f59b7b71ccb94738c7f771ba5af213666f00f9a21c3c2097b3a786e80eb9c56aba7d4b9f03e5b64f4174f1752ab93ac24a78257f

このUIDをCookieにセットしアクセスするとセッションハイジャックが成功し，adminとしてログインできる．

Flag: CTF{++How+do+you+fix+a+cracked+pumpkin+++With+a+pumpkin+patch++}

参考

• CBC modeに対するPadding oracle attackをやってみる - ももいろテクノロジー
• Google CTF - Wolf Spider [CRYPTO/WEB]
• Google CTF – Wolf Spider (Crypto 125) | More Smoked Leet Chicken