Fortune favors the bold

by goulov and L0rdC0mm4nd3r and mvs

Level: Level 5/5 (last level)

Description:

We found a weird fortune cookie server. It appears to serve “standard” and “premium” fortune cookies. We are not sure what a premium fortune cookie is, but we know we want them.We tried all sorts of trickery to get to those delicious premium cookies, but the result has been a lot of fail. The only “premium” cookie we found, is a stale, expired, session cookie:

session=6AMAAAHNdHRcAAAAAAJ9ugke57/TjsBvqandi1/WZsDapigQl2S7kCy0AqSCOSBmG7/592sUIy0i6C2BxCSmyQ6wpAI8Bjy3NoZXqszg/I4JuIi/NsA/4h2iXxkThP3lL6+vHuXjenm2UpyCZcZ12MoKbBS08OFydka93zeY6Fn1QQ6EponYE7C8sqic4Jp3++iEgn7NwEL63wfrrrNfnYEB1YV3hMK2GhynVIiuKyXCaepiBgmyjrJ6r9H36RYSricOwLjSVw0VNNZLcacq0VO7FSW4C8kvlcKrd456yRWpiLNkokPVl0edmOkv8BpHH8JE676HRoFbDeLRvsLFwKmwk0n2utkyOKC/GEM=

Maybe it can help you in getting a fresh premium session cookie.If you feel you are stuck, maybe try looking around a bit?

Given: Server

Solution

TLDR

  1. Check robots.txt for folder backups. There you’ll find the server code.

  2. Notice that they don’t use OpenSSL.RSA_verify(), and implement it manually.

  3. Find that the signature is verified with strncmp, and exploit it using null bytes. Find a collision of two hashes (one premium, one standard) that start with null byte and you are done

Description

First we are given a link to a website with two tabs: standard and premium. While the standard yields fortune messages, the premium returns permission denied.

The standard tab returns a session cookie each time we visit. If we send a previously received cookie, then it stays the same, otherwise we are given a new cookie.

By trying the expired premium session cookie, we are also given permission denied. So now, we experiment with this cookie and see what we get. But we get nothing… Eventually we try other approaches.

Checking the robots.txt file should have been one of our first moves… Well… now we found it, and with it the code the server was running.

Most interesting stuff is in auth.c. From this code we learned the following (|| is string concatenation):

  1. The cookie is composed of four fields uid || b || time || sig
  • uid is the id of the user running, 1001 for regular, and 1000 for admin.
  • b is a bit describing the privilege 0 for standard, and 1 for premium.
  • time is the current timestamp in unix time.
  • sig is the RSA signature of the hash of the previous 3 fields. I.e. RSAsign(H(uid || b || time)).

  1. The signature is implemented using OpenSSL, calling RSA_sign and RSA_public_decrypt. And using the standardized PKCS1 SHA256 identifier.

  2. The timestamp has a max duration of 24h. Which is why the old cookie is expired.

  3. VERY IMPORTANT: The privilege level is only checked against b, not uid.

So, we start by looking at the cookie and signature, and, since we are given an unlimited number of unprivileged cookies, try to find some malleability that allows us to turn the expired cookie into a valid one. Unfortunately, the message that we want to sign (uid || b || time) is hashed before it is signed, so no luck here. Also, we are not given neither the public or private key of RSA, or even the modulus.

Then we notice the following: While the message is signed using the function RSA_sign, strangely, the verification isn’t done with RSA_verify. It is actually calling a low-level function RSA_public_decrypt and implementing rsa_verify by hand. Checking OpenSSL’s documentation we read that

When generating or verifying PKCS #1 signatures, RSA_sign(3) and RSA_verify(3) should be used.

This looks like an issue to us…

The attack

It turns out, their implementation of the rsa_verify function was a good example of why you shouldn’t implement your own crypto.

To check if the signature is valid, the strncmp function is used. Between many properties of this wonderful function, there’s the infamous string handling capabilities of C stopping at the null byte \x00. Thus, strncmp-comparing two strings that start with this byte, yields TRUE. And this is all we need. Below are the steps we now do:

  1. Craft a (uid,b,time) of a cookie with b=1 and a valid timestamp t (pick a random uid), such that the hash H(uid || b || time) starts with the null byte. Since the hash give a uniform random result, we have a probability of 1/256 of the first byte to be 0. Simply brute-force uid until getting the desired outcome.
  2. Keep asking the server for unprivileged cookies (once per second at most) until we get one whose hash also starts by zero. Again, this happens with probability 1/256. We can even predict what is the second that we want to receive the cookie, if we want…

  3. Submit the header (uid,b,time) crafted in 1., appended with the signature from 2. This gives us a privileged cookie that we submit… And the flag appears

    flag{I_am_the_Cookie_Monster!}

Resources

The code we used can be found in …. Well sometime we’ll manage to put it here.