Let me preface this post by saying that I’ve only begun to scratch the surface of the world of cybersecurity—I don’t claim any expertise in the field. That said, I’ve been going through the cybersecurity wargames at OverTheWire, namely the Natas wargame, which features challenges related to server-side security. The game consists of a number of levels, where each level is a password-protected webpage. The goal for each level is to leverage some security vulnerability in the webpage to obtain the password for the next level. In particular, this post deals with Natas level 11 (username: natas11, password: U82q5TCMMQ9xuFoI3dYX61s7OZD9JKoK), which simply looks like this:

The page proudly states, “Cookies are protected with XOR encryption.” XOR refers to “exclusive OR,” a logical operation that returns true when only one of its two inputs is true, and false if both inputs are true or both inputs are false. In XOR encryption, input data is encrypted by choosing a repeating key and applying a bitwise XOR operation between the key and the input.

For example, suppose we wanted to encrypt the following 8 bits of data, `11101011`

. To encrypt our original data, we might choose a short key consisting of 3 bits, `101`

. This key is repeated as many times as necessary—to encrypt our 8 bits of data, `101`

, `101`

, `10`

. This would look as follows:

The encrypted result, `01011101`

, can be decrypted again to obtain the original data by applying the same XOR key to the result. Returning to the Natas level 11 page, if we open up the browser console, we find a cookie named `data`

:

Note that the `%3D`

at the end of the value in the screenshot is a URL-safe percent encoding that actually stands for the equals sign, `=`

. Thus, the value of the `data`

cookie is actually `ClVLIh4ASCsCBE8lAxMacFMZV2hdVVotEhhUJQNVAmhSEV4sFxFeaAw=`

. To understand what this value means, we can look at the page source code.

```
<html>
<?
$defaultdata = array( "showpassword"=>"no", "bgcolor"=>"#ffffff");
function xor_encrypt($in) {
$key = '<censored>';
$text = $in;
$outText = '';
// Iterate through each character
for($i=0;$i<strlen($text);$i++) {
$outText .= $text[$i] ^ $key[$i % strlen($key)];
}
return $outText;
}
function loadData($def) {
global $_COOKIE;
$mydata = $def;
if(array_key_exists("data", $_COOKIE)) {
$tempdata = json_decode(xor_encrypt(base64_decode($_COOKIE["data"])), true);
if(is_array($tempdata) && array_key_exists("showpassword", $tempdata) && array_key_exists("bgcolor", $tempdata)) {
if (preg_match('/^#(?:[a-f\d]{6})$/i', $tempdata['bgcolor'])) {
$mydata['showpassword'] = $tempdata['showpassword'];
$mydata['bgcolor'] = $tempdata['bgcolor'];
}
}
}
return $mydata;
}
function saveData($d) {
setcookie("data", base64_encode(xor_encrypt(json_encode($d))));
}
$data = loadData($defaultdata);
if(array_key_exists("bgcolor",$_REQUEST)) {
if (preg_match('/^#(?:[a-f\d]{6})$/i', $_REQUEST['bgcolor'])) {
$data['bgcolor'] = $_REQUEST['bgcolor'];
}
}
saveData($data);
?>
<h1>natas11</h1>
<div id="content">
<body style="background: <?=$data['bgcolor']?>;">
Cookies are protected with XOR encryption<br/><br/>
<?
if($data["showpassword"] == "yes") {
print "The password for natas12 is <censored><br>";
}
?>
<form>
Background color: <input name=bgcolor value="<?=$data['bgcolor']?>">
<input type=submit value="Set color">
</form>
<div id="viewsource"><a href="index-source.html">View sourcecode</a></div>
</div>
</body>
</html>
```

Let’s break down the source code, which consists mostly of PHP. First, it defines a variable `$defaultdata`

, which is an array consisting of two fields, `showpassword`

and `bgcolor`

. Next, it defines a function, `xor_encrypt()`

, which applies a bitwise XOR operation to an input and a hidden XOR key, as described earlier, and returns the encrypted value. The array `$defaultdata`

is supplied to another function, `loadData()`

, which checks to see if a cookie with the name `data`

has already been set. If it has, it applies several operations to the value of that cookie via the following statement:

`json_decode(xor_encrypt(base64_decode($_COOKIE["data"])), true)`

From this, we can determine that the cookie’s value is first decoded from base-64 to UTF-8 via the PHP function `base64_decode()`

. Data is often encoded to base-64 for URLs and cookies, since the characters in base-64 can be displayed on virtually every system. Next, the `xor_encrypt()`

function is applied to the byte string to decrypt it into a JSON string. Finally, the built-in function `json_decode()`

converts the JSON string to a PHP array.

That array is returned and stored in the variable `$data`

by the line `$data = loadData($defaultdata);`

. The `$data`

array is updated with a new `bgcolor`

from the page’s form request, if applicable, after which the array is encrypted by the function `saveData()`

via a process that is the reverse of that described above. If the value of `showpassword`

is `yes`

, the password is displayed on the page.

In other words, we know two things: 1) what the original unencrypted data looks like, i.e., a JSON string of the form `{"showpassword":"no","bgcolor":"#ffffff"}`

, and 2) what the resulting encrypted cookie looks like, i.e., `ClVLIh4ASCsCBE8lAxMacFMZV2hdVVotEhhUJQNVAmhSEV4sFxFeaAw=`

. Our goal is to determine the XOR key so we can create our own encrypted cookie with the value of `showpassword`

set to `yes`

. If this were our original simplified example, we would have the following situation:

In fact, with this information, obtaining the repeating XOR key is a trivial matter of computing the bitwise XOR of the encrypted result with the unencrypted original data:

By inspection, we can (hopefully) determine that the original XOR key is `101`

. Once we have the original XOR key, we can fabricate our own original data, apply the XOR key to encrypt it, and spoof a valid cookie.

How do we actually accomplish that with the Natas level 11 webpage and cookie? I wrote a little PHP script to compute the bitwise XOR of the original unencrypted data (encoded to a JSON UTF-8 string) and the encrypted cookie (decoded from base-64 to a UTF-8 string):

```
<?php
$data = array("showpassword" => "no", "bgcolor" => "#ffffff");
$cookie = "ClVLIh4ASCsCBE8lAxMacFMZV2hdVVotEhhUJQNVAmhSEV4sFxFeaAw=";
$repeated_xor_key = json_encode($data) ^ base64_decode($cookie);
echo $repeated_xor_key;
?>
```

Running this on a PHP-enabled server yields the following repeated XOR key:

`qw8Jqw8Jqw8Jqw8Jqw8Jqw8Jqw8Jqw8Jqw8Jqw8Jq`

By inspection, it’s clear that the XOR key is `qw8J`

, which we can verify by encrypting the original unencrypted data and comparing it to the original encrypted cookie (or vice versa). With the XOR key now in our hands, we can create our own encrypted cookie with `showpassword`

set to `yes`

. To do so, let’s write a modified version of the `xor_encrypt()`

function from the webpage source code and apply the XOR key we’ve discovered:

```
<?php
function xor_encrypt($data, $key) {
$out = "";
for ($i = 0; $i < strlen($data); $i++) {
$out .= $data[$i] ^ $key[$i % strlen($key)];
}
return $out;
}
function encrypt($data, $key) {
return base64_encode(xor_encrypt(json_encode($data), $key));
}
$data = array("showpassword" => "yes", "bgcolor" => "#ffffff");
$key = "qw8J";
$spoofed_cookie = encrypt($data, $key);
echo $spoofed_cookie;
?>
```

Running this yields the following spoofed cookie value:

`ClVLIh4ASCsCBE8lAxMacFMOXTlTWxooFhRXJh4FGnBTVF4sFxFeLFMK`

Lastly, to access the webpage with the spoofed cookie, we can open up a terminal and send the request via `curl`

:

`$ curl --cookie "data=ClVLIh4ASCsCBE8lAxMacFMOXTlTWxooFhRXJh4FGnBTVF4sFxFeLFMK" -u natas11 http://natas11.natas.labs.overthewire.org`

This returns the following response:

Success! The password for the next level is highlighted in the screenshot above.

# Obtaining the key by brute force

Of course, this got me thinking about the case where we *don’t* know what the original data looks like. So, I wrote a Python script to aid in this task.

```
import base64
import itertools
import json
import time
def xor_encrypt(data, key):
out = []
for i in range(len(data)):
xor = ord(data[i]) ^ ord(key[i % len(key)])
out.append(chr(xor))
return "".join(out)
def decrypt(data, key):
return json.loads(xor_encrypt(base64.b64decode(data).decode("utf-8"), key))
def bruteforce(encrypted_data, min_key_len=1, max_key_len=1):
chars = [chr(i) for i in range(48, 123)]
keys = []
start_time = time.time()
for key_len in range(1, max_key_len + 1):
print("[{} s] Trying key length ".format(time.time() - start_time)
+ str(key_len))
for product in itertools.product(chars, repeat=key_len):
key = "".join(product)
try:
decrypt(encrypted_data, key)
except:
continue
else:
keys.append(key)
print("[{} s] Completed".format(time.time() - start_time))
return keys
def test_keys(encrypted_data, keys):
for key in keys:
decrypted_str = str(decrypt(encrypted_data, key))
if decrypted_str[0] == "{" and decrypted_str[-1] == "}":
return key
if __name__ == "__main__":
cookie = "ClVLIh4ASCsCBE8lAxMacFMZV2hdVVotEhhUJQNVAmhSEV4sFxFeaAw="
keys = bruteforce(cookie, max_key_len=4)
key = test_keys(cookie, keys)
if key:
print("Key: " + key)
print("Decrypted data: " + str(decrypt(cookie, key)))
else:
print("No key found")
```

The function `xor_encrypt()`

performs the same task as its PHP counterpart, and `decrypt()`

is the inverse of `encrypt()`

. The function `bruteforce()`

constructs a XOR key from a range of ASCII characters—I’ve arbitrarily chosen characters from “0” (ASCII code 48) to “z” (ASCII code 122). This is done for a number of key lengths: a key one character long would include keys “0”, “1”, …, “y”, “z”; a key two characters long would include keys “00”, “01”, …, “zy”, “zz”, and so on. The `decrypt()`

function is called on each key—however, most keys will not produce a valid sequence of UTF-8 encoded bytes. Only valid byte sequences are added to a list, `keys`

, which the function returns.

The function `test_keys()`

makes an assumption about the original unencrypted data, namely that it’ll be a JSON string that begins and ends with curly braces (`{`

and `}`

). It takes a list of potentially valid keys and returns the one (if any) that produces a decrypted JSON string. Running the script for keys up to four characters in length produces a successful result:

How validating! Of course, this approach has obvious limitations, namely the fact that I chose an arbitrary subset of ASCII/UTF-8 characters with which to construct the key and the fact that I’m assuming the decrypted data will be human-readable and a JSON string.

However, what makes this approach most untenable is that it’s a brute force approach with exponential time complexity, i.e., \(O(k^n)\), where \(k\) is the number of choices for each character of the XOR key and \(n\) is the length of the key. In fact, because my function tracks and displays the amount of time it takes to try all possible keys for a given key length, we can see this in action. Per the screenshot above, it took approximately:

• 0.0015 seconds to try all 1-character key combinations

• 0.11 seconds to try all 2-character key combinations

• 8.0 seconds to try all 3-character key combinations

• 600 seconds to try all 4-character key combinations

Because I’ve limited the choice of characters to 75 (ASCII codes 48 to 122), that means there are 75^{1} = 75 possible 1-character keys, 75^{2} = 5625 possible 2-character keys, 75^{3} = 4121875 possible 3-character keys, 75^{4} = 31640625 possible 4-character keys, and so on. In fact, if we divide the number of 1-character keys by the time it took to try all those keys, we can see how accurate this is. If it took 0.0015 seconds for 75 keys, that’s a rate of 0.00002 seconds per key. Based on this, it should take 0.00002 * 75^{2} = 0.11 seconds to try all 2-character keys, 0.00002 * 75^{3} = 8.4 seconds to try all 3-character keys, and 0.00002 * 75^{4} = 633 seconds to try all 4-character keys. These numbers are almost exactly what I got above. Then, to try all 5-character keys, it would take my system about 47500 seconds, which is about 13 hours, and to try all 6-character keys, 3.56 *billion* seconds, which is 41 days. Hence, a XOR key of decent length can quickly become impossible to brute force.

There are techniques to reduce the search space for decrypting XOR-encrypted data, as well as non-brute force approaches that avoid some of the aforementioned pitfalls, but I’m not well-versed on these. Seems like there’s a lot left to learn.