lardbucket: ego

4/20/2015

PlaidCTF 2015: radhos Writeup

Filed under: Ego, Hacks, Programming — Andy @ 6:44 pm

Along with several coworkers, I participated a bit in the PlaidCTF 2015 competition this past weekend. The competition is geared mainly toward binary exploitation, with reverse engineering a secondary priority. There are also a number of challenges which focus on cryptography, forensics, and other security-related issues. Unfortunately, my skills lie more toward the latter category than the former, so I wasn’t as broadly useful as I might have otherwise liked to be. Nonetheless, I was able to contribute solutions to three problems: “RE GEX” (a large regular expression, where it was necessary to find a string that didn’t match the regular expression), “PNG Uncorrupt” (a PNG file with several missing “\x0d” bytes before “\x0a” bytes), and “radhos” (a Python hash collision challenge). I’ve seen good writeups online for RE GEX and PNG Uncorrupt, but haven’t yet seen any good ones for radhos, so I’m contributing my solution here.

You can download the radhos challenge here (or here if the first link has disappeared). If running it locally, replace line 24 with “ return '127.0.0.1'” to keep the server from having errors.

radhos is a simple HTTP server that emulates a small hashtable-based key-value store. Each value is stored using the hash of its key, where the hash is the lower 32 bits of Python’s hash() function. (This appears to be intended to give consistent behavior between 32-bit and 64-bit versions of Python.) The level’s flag is stored in the hashtable’s location for the key “you_want_it_LOLOLOL?”, but the server will reject requests that ask for that key by name. Therefore, the remaining solution is to find something that will generate a collision in hash(key). To encourage players to solve the challenge without simply guessing random keys, the server restarts (and gets a random hash() seed) every seven minutes.

Hash Collisions

Using HTTP requests, you can get the value for a key you select, or alternatively, you can set the value for a key. Setting the value for a key will also return the old value in that location in the hashtable, if any, as well as the value of hash(key). It’s this information leak that allows us to break Python’s randomized hash function, generate a new key that has the same hash value as “you_want_it_LOLOLOL?”, and retrieve the flag.

I initially thought that this would be an instance of the bug described at https://bugs.python.org/issue14621, but that doesn’t appear to be the case. I spent far too long looking at that issue, and trying to replicate similar situations that might allow a collision in this case. However, the issue does have an attachment, hash.py, that gave Python code for the hash algorithm, which was somewhat useful for analysis. The (pre-3.4) Python hash() function used two secret values to obscure the hash value: a “prefix” that affects the whole hash, and a “suffix” that is simply XOR’d in afterward to obscure the result and prevent attackers simply guessing the prefix. If an attacker is able to determine the “prefix”, they can generate hash collisions on their own. (Having the suffix is unnecessary if collisions are the only goal, as it is simply XOR’d on at the end.)

Here’s a bit of code for generating the hash:

HASHMASK = 0xffffffff

def hashbytes32(data):
    if len(data) == 0:
        return 0
    x = prefix
    x ^= ord(data[0]) << 7
    for byte in data:
        x = (1000003 * x) ^ ord(byte)
        x &= HASHMASK
    x ^= len(data)
    if x == -1:
        x = -2
    return x

Finding the prefix

Luckily, there was a talk on hash collisions (Hash-flooding DoS reloaded: attacks and defenses) that referenced a tool that could be used to determine the hash secret in Python. I was able to find the tool at https://131002.net/siphash/poc.py, and verified that it worked.

Unfortunately, it worked based on hashes for “\x00” and “\x00\x00” (one and two null bytes), which we couldn’t submit to the radhos server (as far as I know). A small amount of math allows us to change the target used in the algorithm, however. Let’s say that we have h1 = hash("A") and h2 = hash("B"). Then we know:

h1 = ((prefix ^ (65 << 7)) * 1000003) ^ 65 ^ 1 ^ suffix
h2 = ((prefix ^ (66 << 7)) * 1000003) ^ 66 ^ 1 ^ suffix

Let’s XOR the two, and note that the 1 and suffix terms cancel out, as they are on both sides. Then we have:

h1 ^ h2 = ((prefix ^ (65 << 7)) * 1000003) ^ 65 ^ ((prefix ^ (66 << 7)) * 1000003) ^ 66

The tool I mentioned above uses this fact, and guesses the value of prefix one bit at a time, narrowing down possibilities as it goes. It then performs a verification step, testing those possibilities with a known hash of a third value. I was able to verify that I received the correct prefix value by testing locally, so I was satisfied with that part of the code.

As an aside, if the bit-by-bit guessing didn’t work to determine the prefix, it would be possible to use the h1 ^ h2 math above and several additional hashes to brute-force the prefix, but that would likely take a while. Distributing the problem among multiple cores (or computers) might get a result before the server restarted, however, so it might have been worthwhile if the proof of concept code were not available. (Note that brute-forcing the suffix is unnecessary in this case, as XOR’ing the hashes removes it from consideration.)

Finding an actual collision

Simply having the prefix value is insufficient, as we need to actually generate something that will collide. The obvious solution is a brute-force attack. This is easy to implement, and can be parallelized to get a result before the server restarts. Unfortunately, it’s also fairly slow in general, when another relatively simple solution is available.

Because the hash code is relatively simple, we can perform what is known as a “meet in the middle” attack. In this case, we start with the result we want (we can already calculate the hash for “you_want_it_LOLOLOL?”, because we have prefix and suffix
mask = 0xffffffff
def hashback(instr, target):
val = target
for byte in instr[::-1]:
val = ((val ^ ord(byte)) * 2021759595) & mask
return val

This works because 1000003 * 2021759595 = 1 mod 232, so multiplying by 2021759595 is equivalent to dividing by 1000003. (Note that in this function, for simplicity, we have already removed the suffix and the size of the string to be hashed.)

So we’ve worked backward and determined what the hash state should be for a given suffix. How does this help? Well, we can do the same thing for many suffixes, and have many possible targets for our brute-forcing. The most efficient way to do this is to try 216 suffixes. This turns the brute-forcing from an expected 232 operations with 1 unit of storage into 2*216 operations with 216 storage. RAM is relatively plentiful for this task, so it’s a good trade-off. I’ll let the code below speak for itself, but feel free to leave a comment if you have a question.

Putting it all together

The code I ended up using is below, after some minor cleaning up:
(more…)

10/3/2009

GraphSketch: 30,000 Graphs, and Parametric

Filed under: Ego, Hacks, Programming — Andy @ 9:41 am

Yesterday, GraphSketch passed over 30,000 graphs rendered. That’s quite a few. Thanks to everyone for making it so popular.

It also seemed like a good time to release something I’ve been working on smoothing out for the past few weeks:

GraphSketch ParametricYep, you can now graph parametric equations. Just head over to http://graphsketch.com/parametric (or click the “Parametric”mode just above the equations on the main GraphSketch page).

To keep things simple, you can only graph three parametric sets of equations at the same time. You can choose the range for t, and it defaults to a reasonable -10 to 10.

Also, while I was updating the website, I made the text a bit smaller (about the difference of going from a 12pt font to a 10pt font) and added a (hopefully unobtrusive) section pointing out the availability of posters, should anyone be interested. Polar graphing should come soon, hopefully, but it is somewhat possible using parametric equations by setting x=r*cos(t) and y=r*sin(t), too.

Andy Schmitz

10/2/2009

Posters

Filed under: Ego, Math — Andy @ 11:29 pm

A number of you who know me in real life have probably seen a number of my posters. Three of them currently adorn my dorm room. I had been offering them to friends I knew, but not to everyone, because I hadn’t gotten around to it. But that has changed now, with posters.lardbucket.org.

The website itself is (purposely) a bit sparse, but it will let you browse the four existing posters, and grab one for yourself from Zazzle at fairly reasonable prices. (I really only make a few dollars from each one, depending on size.) Other than taking a while to ship, Zazzle’s processing has been fairly good, and the three large prints I have from them are reasonably high quality, even on their “basic poster” paper.

Each of the posters on posters.lardbucket.org was created by me, using a reasonably high-powered computer to do the rendering. Each of the posters is a mathematically-defined rendering, and could theoretically be rendered at any size and not lose any detail. Therefore, the large posters are still high quality images.

So, if you’d like to get a neat-looking poster and send a few dollars my way at the same time, have a look at posters.lardbucket.org.

Thanks,
Andy Schmitz

5/12/2009

GraphSketch: Ten Thousand

Filed under: Ego, Hacks, Programming, Technology — Andy @ 2:24 pm

In under three weeks since it was launched, GraphSketch has now been used to create (over) 10,000 graphs. It also has had over 3,500 visitors, coming from every continent except Antarctica, though many visitors haven’t graphed anything (and many visitors have graphed far more than average). Work on new features (parametric and polar graphing, among others) will likely resume after school is over, as I still have three finals remaining, and am now off to continue studying for a math final.

At any rate, thanks to everyone who has promoted GraphSketch in one place or another for making it so successful.

Andy Schmitz

P.S. If you have any suggestions for GraphSketch itself, the original post on it is still probably the best place to leave them, as I’ll check back there for ideas when I’m working on it. Thanks!

9/17/2005

In the Correspondent again!

Filed under: Ego — Andy @ 9:08 pm

This time I don’t have a photo or anything, but they did mention the project I’m working on that’s available here, called PeopleFinder. The project attempts to get data from many different websites and combine it into one searchable database. If you can’t find me in the Correspondent, I’m on the front page, bottom half, left column, toward the bottom.

Unfortunately, they implied that I created the website (from scratch), which I most certainly did not. The site and interface itself were entirely done by others. I “simply” found ways to import a few thousand records from other websites and uploaded information for other people.

More news too, but I can’t much talk about that right now. I’m sure I’ll have something else for the blog later as well.

8/22/2005

I’m in the Correspondent

Filed under: Ego — Andy @ 8:06 pm

I appear on the top of the front page on tomorrow’s Correspondent! (The Correspondent is our school paper.) The story is about my schedule website, which is still available at http://schedule.lardbucket.org. I can only say that it mentioned Tommy and I, and that it appeared to be all positive. If I can post more later, I will.

Andy

My Stuff
Blog Stuff
Categories
Archives