CodeGate 2012 Quals – Vuln 400

Here’s a web-based crypto challenge.

Summary: padding oracle attack, bit flipping

We are given a bunch of ‘citizen’ certificates. Our aim is to login as ‘king’. Let’s analyze the certificate:

M8EdPtY517M=cACNHQhdH/I=

Looks like it’s a splitted pair of base64:

$ echo M8EdPtY517M= | base64 -d | xxd
0000000: 33c1 1d3e d639 d7b3                      3..>.9..
$ echo cACNHQhdH/I= | base64 -d | xxd
0000000: 7000 8d1d 085d 1ff2                      p....]..

Let’s try to change some bits and submit it:
vuln400submit.py

$ py vuln400submit.py '33c11d3ed639d7b3' '70008d1d085d1ff2'
LOG: LOGIN OK
$ py vuln400submit.py '33c11d3ed639d7b0' '70008d1d085d1ff2'
LOG: PADDING ERROR
$ py vuln400submit.py '03c11d3ed639d7b3' '70008d1d085d1ff2'
LOG: CLASS ERROR

Oh, we see some errors. But the most interesting is PADDING ERROR. It means we have a padding oracle, which says if the decrypted message correctly padded.

Usually a correct padding is filling the remaining bytes with the value = count of the remaining bytes. E.g. “plain” message in 8-byte block will be padded as “plain\x03\x03\x03”.

We changed the last byte in the first block to get padding error, but padding is usually at the end of the message, right? Looks like the second block depends on the ciphertext of the first, which most probably means it’s CBC chahining mode.

CBC means that the plaintext of the second block is xored with the ciphertext of the first.

How we can use that?

Let’s suppose that the second block is “XXXXXX\x02\x02”. We can flip some bits in the last byte by xoring the last byte of the first block.
If we xor it with 2 ^ 1 then the last byte of the decrypted message will be 2 ^ 2 ^ 1 = 1 and the padding should be right.
If we xor it with another values (except 0), we’ll get a PADDING ERROR, because padding will be broken.

By analogy, if the second block is “XXXXX\x03\x03\x03”, we won’t get PADDING ERROR only when we xor with 3 ^ 1.

So, if we xor the last byte with N ^ 1 and we don’t get PADDING ERROR then the last byte of the plaintext is N.

We can extrapolate this to all byte of the second block, and get a plaintext of it:
full script

alpha = "\x01\x02\x03\x04\x05\x06\x07\x08abcdefghijklmnopqrstuvwxyz"
vals = []
key = ""
for j in xrange(8):
	for i in map(ord, alpha):
		a = "33c11d3ed639d7b3".decode("hex")
		b = "70008d1d085d1ff2".decode("hex")
 
		a = map(ord, a)
		b = map(ord, b)
 
		for k in xrange(7, -1, -1):
			a[k] ^= j + 1
			if 7-k >= len(vals): continue
			a[k] ^= vals[7-k]
 
		a[7-len(vals)] ^= i
		a = "".join(map(chr, a))
		b = "".join(map(chr, b))
 
		res = get_result(a, b)
		if "PADDING" not in res:
			vals.append(i)
			key = chr(i) + key
			print "Got byte:", key
			break

$ py vuln400.py 
Got byte: 

Got byte: c

Got byte: ic

Got byte: tic

Got byte: itic

Got byte: zitic

Got byte: ezitic

Got byte: nezitic

Yeah, it’s the plaintext! Let’s remember our goal: we need to login as “king”. It’s easy: we need second block to be “gnik\x04\x04\x04\x04”.

"gnik\x04\x04\x04\x04" -> 0x676e696b04040404
"nezitic\x01" -> 0x6e657a6974696301
0x33c11d3ed639d7b3 ^ 0x676e696b04040404 ^ 0x6e657a6974696301 = 0x3aca0e3ca654b0b6

from base64 import *
open("king.ctf", "wb").write(b64encode("3aca0e3ca654b0b6".decode("hex")) + b64encode("70008d1d085d1ff2".decode("hex")))

Let’s login with king.ctf
:

The flag: MYL0_V3_SCARLET