読者です 読者をやめる 読者になる 読者になる

sonickun.log

備忘録

Google CTF 2016 Writeup - Eucalypt Forest, Wolf Spider

CTF セキュリティ

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モードの復号処理は以下のようになっている.
f:id:sonickun:20160506225403p:plain
暗号利用モード - 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が得られる.
f:id:sonickun:20160506230538p:plain

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を使い,ハッシュ値を算出してみる.

単純に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を利用したものである.

今回の問題においても,上記の暗号化・復号処理のプログラムを見ると,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として復号される.なお,記号^排他的論理和を表す.
f:id:sonickun:20160507130540p:plain

ここまででC2とC3の値が決定した.次にC1を決定したいのだが,C2の復号器にかけた直後の値(これをR2とする)がわからない.このR2を特定するために使うのがPadding oracle attackである.
f:id:sonickun:20160507015054p:plain

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と計算できる.
f:id:sonickun:20160507021053p:plain
このようにして,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としてログインできる.
f:id:sonickun:20160507134931p:plain

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