Google CTF – Wolf Spider (Crypto 125)

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

wolf.py

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

    • Giltech on May 2, 2016 at 05:38
    • Reply

    I don’t understand this bit of your code would you mind explaining it?

    hash = "a" * 40
    pref = hash + ".b1d3ba9e9ec44cfb92bc8910907d6be46c0d482fe9d46e7966161e9a17368eef"

    1. 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.

    • Giltech on May 2, 2016 at 17:45
    • Reply

    Thanks for clarifying nice write up

Leave a Reply

Your email address will not be published.