0x07D1: A Base Odyssey

I recently dived into the deep and not altogether pleasant rabbit hole of cryptography for my online game service Sagittarius. What follows is an account of my adventures.

To start off, I must be brutally clear: I am NOT a cryptographer, or a math whiz, or anything like that. I have implemented Rijndael in Java as part of one of my computer science classes, and we did have to learn about hashes and salts and the like. I’d like to imagine that one day the NSA will be knocking at my door for SHA-15 or something (with paychecks in tow, of course), but we both know that’s highly unlikely.

The Dilemma

For Sagittarius, I faced a unique problem: finding an encryption algorithm that I could code in a variety of languages, one of which happened to be UnrealScript. Given that I had had experience with Rijndael I tried to port it to UnrealScript only to find out how advanced the algorithm truly is — and how primitive UnrealScript’s bit twiddling support is in comparison.

It’s not that an UnrealScript Rijndael implementation isn’t possible, only that a working one is terribly inefficient and hacky in all sorts of bad, not-so-secure ways. For one thing, trying to transform a string (which is immutable and Unicode-defined in UnrealScript) into a byte array, which must then be sliced into blocks, padded, and run through the bit-shifting grinder, then transformed back into a hexadecimal string representation…well, you get the idea.

Rijndael would be great, but performance-wise it wasn’t going to cut it.

Coding from the Basement

Anyone who calls themselves a cryptographer should cringe at the thought of a “basement algorithm” going into production (for those of you who don’t know, a basement algorithm is exactly what it sounds like: something made by a coder late at night in a sleep-deprived and energy-drink-fueled state of oh-this-isn’t-going-to-look-good-in-the-morning). I don’t have a basement, but I decided to make my own encryption algorithm anyway. Cryptographers, cringe away.

For starters, I wanted to make things simple. Given a string to encode and a key/password to encode it with, I wanted to turn that string into a jumble of bits. I also wanted to be able to take that jumble of bits and the same key and recover my original string. This sounded like a job for an XOR cipher:

PT:  All your base are belong to us
Key: passwordpasswordpasswordpasswo
CT:  f[??+?ZjtL$?E?????+s??uc??!???

One huge problem with this method is that the key is completely recoverable by a simple dictionary attack. So then I thought, why not jumble the key before using it? A simple way to do this is via the following formula:

\sum_{i=0}^{n} k_i2^i

given that n is the length of the key and k_i is the i-th character of that key. What this will spit out is an integer which can be used just like the key itself in the XOR cipher and (so far as I know) requires polynomial-complexity time equivalent to the length of the key to break.

A Bit of Chaos

Another problem with our cipher is that the key is repeated if the string to encrypt is longer. A better solution is what’s known as a stream cipher: we use the key as the seed to a pseudorandom number generator (PRNG), then use the random numbers for the XOR.

Great, I thought. Awesome! So now, what PRNG to use? Thankfully someone in the UDK community had the answer. This is the random number function from Microsoft Visual C/C++ — not the best function in the world, but passable for our purposes.

I should also mention at this point that using a non-cryptographically-secure PRNG in an encryption algorithm is a really bad idea. But hey, if you think implementing Rijndael in UnrealScript is hard, try the Mersenne Twister! And seeing as how we’re already going down the dark road of homemade algorithms, we may as well venture a little further.

Unfortunately, using a PRNG for a stream cipher brings up another problem. Given a starting key (what is know in the business as a “seed”), the random number generator will always spit out the same sequence of “random” numbers. That’s because it’s not really random, but a perfectly deterministic algorithm made to look random. To a computer, a PRNG is no different than an algorithm that doubles a number at every step: if you start with a key of 17, you’re always going to get 34, 68, 136…

We can fix this by introducing a bit more randomness in the form of a pad. Because this is a simple algorithm, I decided to have a pad of exactly one byte in size; I chose a random number between 0 and 255, added it to our key, and used the sum as the key instead. With this new technique we can get 256 different possible random sequences for our stream cipher. Not cryptographically secure by a long shot, but definitely better.

Why It Works…For Now

Most basement algorithms like this one work because of the Don’t-Care Conjecture:

If an application is breakable, the only reason it hasn’t been broken yet is because the people capable of it don’t care enough about it to try.

By the time Sagittarius becomes popular enough that people do try, I will have hopefully moved on to something far more secure.

In the meantime, my own solution benefits from several key bottlenecks. Although recovering the actual encrypted data is fairly simple (*cough* dictionary attack *cough*), recovering the original key is fairly hard. That’s because the key itself is masked behind our random pad and the random number stream, which must be reversed to obtain the original integer — and even then, there’s some pretty weird polynomial math to do. This is a great side effect, because it means that the security of your application itself is ensured.

Be on the lookout for this stuff in a Sagittarius release soon.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s