Continuing on from Eucalypt Forest – can you break Message Authentication in Wolf Spider
Summary: forging signatures by exploiting CBC padding oracle and hash length extenstion
This challenge is a harder version of the Eucalypt Forest from the same CTF. On the website, we can get an encrypted cookie for any user except “admin” and we need to forge such cookie for username “admin” to get the flag. We are also given the code of creating a cookie. Here’s the main part:
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() # AES-CBC coded = CookieCutter.encode(tcd) return s.encode('hex') + "." + coded.encode('hex') CookieCutter.encode({ "username": "blah" }) |
So what we have here is Encrypt-and-MAC, which is insecure. Moreover the MAC is vulnerable to hash length extension attack. Also, there is a padding oracle:
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 def decode(string): if len(string) < 16: return ValueError, "bad string" iv, string = string[:16], string[16:] algo = AES.new(Storage.aes_key, AES.MODE_CBC, IV=iv) plaintext = str(algo.decrypt(string)) 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" raw = plaintext[:-pad] # print "raw is %r" % raw return raw |
When padding is incorrect, CookieCutter.decode raises an Exception and the web server returns code 500. If the MAC is incorrect, the function returns None. If everything is correct, the server says that we need username “admin”.
Let’s start with hash length extension. Assume that we register username “user”. Then the MAC is:
$sha1(key || username=user)$.
By extending it, we can obtain:
$sha1(key || username=user || \text{\x80\x00…} || arbitrary\_data)$,
where “\x80\x00…” is the sha1 padding. In particular, we can set the arbitrary data to “;username=admin” and the signature will be correct. But we won’t have the respective AES ciphertext. And we can’t register user “user\x80\x00…”, because the server uses urlencode and will corrupt our special characters.
What should we do? Usually CBC padding oracle is used to decrypt messages. But actually we can use it to encrypt arbitrary plaintexts! How will we do it?
Let’s set the last cipher block $C_{-1}$ to arbitrary value, let’s say all zeros. Then we use the padding oracle to decrypt it into $P_{-1}$. Now we can exploit the CBC chaining and prepend such IV that the ciphertexts decrypt to our value $M_{-1}$: $iv = P_{-1} \oplus M_{-1}$. We now have that $iv || C_{-1}$ decrypts to $M_{-1}$. Since we want to encrypt more blocks, we can repeat the trick. But now, instead of fixing the cipher block to arbitrary value, we fix it to the last $iv$, and compute a new $iv’ = decrypt(iv) \oplus M_{-2}$. Now we have that $iv’ || iv || C_{-1}$ decrypts to $M_{-2} || M_{-1}$. Obviously, we can extend the process for arbitrarily long messages.
But we need to keep in mind that decryption oracle using CBC padding oracle is quite slow. So we can start with a known plaintext-ciphertext block instead of all-zero block.
The only thing left is to code this attack. The code follows. Note how the blocks look like:
BLOCK 0: 'username=aaaaaaa' BLOCK 1: 'aaaaaaa\x80\x00\x00\x00\x00\x00\x00\x01\xb8' BLOCK 2: ';username=admin\x01' |
I also use very nice tool hash_extender, which supports many hashes. (The github page also explains the attack nicely!).
import sys import requests import hashlib import subprocess def decrypt(todec): """ Decrypt block using padding oracle Written by Yngve """ hash = "a" * 40 # valid query pref = hash + ".b1d3ba9e9ec44cfb92bc8910907d6be46c0d482fe9d46e7966161e9a17368eef" url ="https://wolf-spider.ctfcompetition.com/admin" todec = todec.encode("hex") known = "" while len(known) < 16: s = "" for i in xrange(len(known)): c = known[::-1][i] n = ord(c) ^ (len(known)+1) s = "%02x%s" % (n, s) for i in xrange(0, 256): s2 = "%02x%s" % (i, s) s2 = s2.rjust(32, "0") res = requests.get(url, verify=False, cookies={"UID": pref + s2 + todec}) if res.status_code == 500: sys.stdout.write(".") sys.stdout.flush() continue known = chr(i ^ (len(known)+1)) + known break print print "known", known.encode("hex") return known def getcookiefor(name): url = "https://wolf-spider.ctfcompetition.com/createaccount" data = {"username": name} sess = requests.session() r = sess.post(url, verify=False, data=data) h, ct = sess.cookies["UID"].split(".") return h, ct.decode("hex") def check(h, ct): url ="https://wolf-spider.ctfcompetition.com/admin" uid = h + "." + ct.encode("hex") res = requests.get(url, verify=False, cookies={"UID": uid}) return res.content def hash_extender(data, hash, append, hashname, length=16): '''https://github.com/iagox86/hash_extender''' s = subprocess.check_output([ "hash_extender", "-d", data.encode("hex"), "--data-format=hex", "-s", hash, "-a", append.encode("hex"), "--append-format=hex", "-l", str(length), "-f", hashname ]) lines = s.splitlines() sig = lines[2].strip().split()[-1] s = lines[3].strip().split()[-1].decode("hex") return s, sig def to_blocks(s): return [s[i:i+16] for i in xrange(0, len(s), 16)] def xor(a, b): return "".join([chr(ord(a[i]) ^ ord(b[i % len(b)])) for i in xrange(len(a))]) MAC_LEN = 32 # 9 bytes padding: \x80 + 8 bytes size username = "a" * (64 - MAC_LEN - len("username=") - 9) hash, ct = getcookiefor(username) print "HASH0", hash data_wanted, sig = hash_extender( data="username=" + username, hash=hash, append=";username=admin", hashname="sha1", length=MAC_LEN ) print "FORGED SIG", sig blocks_wanted = to_blocks(data_wanted) # tricky: we need pad but don't need to sign it blocks_wanted[-1] += "\x01" for b in blocks_wanted: print "BLOCK NEED:", len(b), `b` # use known pair to make fewer decryption calls last_plain = xor(ct[:16], "username=aaaaaaa") ciphertext = ct[16:32] for wanted in reversed(blocks_wanted): if len(ciphertext) == 16: plain = last_plain else: print "DECRYPTING", ciphertext[:16].encode("hex") plain = decrypt(ciphertext[:16]) ciphertext = xor(plain, wanted) + ciphertext print "NEW CIPHERTEXT", ciphertext.encode("hex") print check(sig, ciphertext) |
The flag: CTF{++How+do+you+fix+a+cracked+pumpkin+++With+a+pumpkin+patch++}
3 comments
I don’t understand this bit of your code would you mind explaining it?
hash = "a" * 40pref = hash + ".b1d3ba9e9ec44cfb92bc8910907d6be46c0d482fe9d46e7966161e9a17368eef"
Author
We set random hash and a valid ciphertext, which decrypts to “username=something”. Then we can append two blocks and mount a padding oracle attack. If the last two blocks have wrong padding, we will get error 500. If padding is ok we get error message that hash is wrong.
Thanks for clarifying nice write up