I captured the flag!

Last week, Stripe launched their second capture the flag competition. Unlike the CTF they held in February, this version involved web-based vulnerabilities and exploits instead of lower-level problems. Also unlike the first CTF run by Stripe I was able to complete the last level and capture the flag!

I know that there are many write-ups of all of the different levels already, so I just want to talk about the technical details of my favourite level.

Welcome to the penultimate level, Level 7.

WaffleCopter is a new service delivering locally-sourced organic waffles hot off of vintage waffle irons straight to your location using quad-rotor GPS-enabled helicopters. The service is modeled after TacoCopter, an innovative and highly successful early contender in the airborne food delivery industry. WaffleCopter is currently being tested in private beta in select locations.

Your goal is to order one of the decadent Liège Waffles, offered only to WaffleCopter’s first premium subscribers.

Log in to your account at https://level07-2.stripe-ctf.com/user-xxxxxxxxxx with username ctf and password password. You will find your API credentials after logging in.

Looking at the code for level 7 showed that the /orders API endpoint didn’t have any obvious way to bypass signature verification or order premium waffles as the ctf user. So, I started to look elsewhere. Almost immediately I spotted that although the /logs/:id route requires authentication it doesn’t stop authenticated users from viewing the API request logs of other users. By visiting /logs/1 it’s possible to view the requests of a premium user ordering some waffles. Unfortunately they hadn’t ordered the target Liège waffle so it seems that all that can be done is replay requests for unwanted waffles, right?

At this point I had to leave to walk to work. This turned out to be a good thing, on this ‘ponder wander’ I realised that, whilst investigating the benefits of HMAC in the past, I had read about attacks on the signature creation method that was being employed. If it’s possible to take an old request from a premium user, change the ordered waffle to the target and then create a valid MAC then the password can be found.

Length extension attacks

def verify_signature(user_id, sig, raw_params):
    # get secret token for user_id
        row = g.db.select_one('users', {'id': user_id})
    except db.NotFound:
        raise BadSignature('no such user_id')
    secret = str(row['secret'])

    h = hashlib.sha1()
    h.update(secret   raw_params)
    print 'computed signature', h.hexdigest(), 'for body', repr(raw_params)
    if h.hexdigest() != sig:
        raise BadSignature('signature does not match')
    return True

Above is the code used by the WaffleCopter server to verify a signed request. The signature for a request is calculated by taking the body of the request (the message), appending it to the user specific secret and computing the SHA-1 hash of the result. This is a weak method of creating a MAC because for some hash functions, like SHA-1, it is possible to compute H(m || padding(m) || m') for any m' given H(m) where where m is unknown (|| denotes concatenation).

Length extension is possible on all hash functions that make use of the Merkle–Damgård construction to build a hash function which accepts arbitrarily sized input from a one-way compression function that only accepts fixed size inputs.

Merkle-Damgård hash construction

The image above shows the construction of a hash function from a one-way compression function f which takes fixed size two inputs and produces a fixed sized output the same size as one of the inputs. First, the input message is broken up into blocks of the correct size. The compression function is repeatedly applied to successive blocks of the input message along with the output of the previous function application. The first message block is compressed along with a public initialization vector (IV) that is algorithm specific. The final block is padded as necessary so that it is the appropriate size for the compression function. The result of the final compression is the hash for the input message.

It should now be pretty easy to see how H(m || padding(m) || m') can be calculated for an arbitrary m' given H(m). It is computed by producing H(m') but with the value of H(m) being used in place of the hash function’s standard initialization vector.

With this knowledge it is now possible to create a valid MAC when MAC = H(K M) where K is a secret and M is the message. All that needs to be known is the length of K and any message M and its associated MAC C. This is done by working out the padding that the hash function would add automatically during the computation of C and appending it to M: M' = M || padding. The amount of padding to use is determined by adding the lengths of K and M modulo the block size required by the compression function. Extra data can then be appended to create M'' = M' || extra. The valid MAC for our new message M'' is H(M'') when using C as the value of the IV.

So, back to level 7 of the Stripe CTF. Take one of the signed API requests for a premium user:


M is the piece before the pipe and C is the piece after “sig:”. The extra data to extend the message with is &waffle=liege so that the requested waffle parameter in the original message is overwritten with the name of the target. By using the length extension attack described above it’s possible to create M'':


and a valid MAC:


The password for level 8 could then be found by POSTing the concatenation of M'', “|sig:” and the new MAC to the orders API endpoint. The request will be verified as having been made by user 1 (a premium user) ordering a Liège waffle.

During the CTF I created the extended message and its MAC by taking a Python implementation of SHA-1 and hacking up it’s internal state. This was much harder than it could have been as it turns out that there is an existing tool for creating extended messages and new MACs.

Overall the CTF was thoroughly enjoyable and I hope that Stripe (and others) continue to create these fun security challenges in the future.

This entry was posted on 30 August 2012.