lardbucket: hacks

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…)

9/1/2012

Getting Complicated, Embedded YouTube Videos

Filed under: Hacks, School, Technology — Andy @ 3:29 pm

So, earlier today, Karl Fisch asked for a copy of an Olympics video from NBC’s website to use in his school. A number of the “standard” ways of getting the video didn’t seem to work, so I figured I’d pitch in. By the way, the first thing to try (if whatever addons you might have to download YouTube videos don’t work – although I don’t use any myself, I’m told they didn’t work in this case) is to click the YouTube button.

The YouTube button will usually open the video up into YouTube’s website, where most addons for downloading a video will work better, and there are plenty of other websites happy to help you.

In this case, clicking the button only got to the NBC Olympics home on YouTube. A quick search of the channel showed that the video I was looking for wasn’t on the NBC Olympics channel, and I’d have to find another way to download it.

(more…)

6/29/2010

Leaderboard with Movement Tracking

Filed under: Hacks, Programming — Andy @ 9:00 pm

In putting together SLV Scav with Dan Meyer, I ended up writing a (relatively) simple script for generating a scoreboard with rankings, as well as the amount the rankings had changed. It looks something like this: (picture from Dan Meyer, names blurred to protect the innocent)

Dylan Faullin asked for more information, so I’m posting most of the relevant code here.

(more…)

11/13/2009

Notes: Time, USPS

Filed under: General, Hacks — Andy @ 4:30 pm

Time

For some reason my computer’s clock got set a good 12 minutes ahead. I’m not exactly sure why, but it appears to have happened around a restart, perhaps due to a hardware clock that’s off, and the NTP daemon didn’t correct it. To manually reset the time based on a time server in Ubuntu, run

sudo /etc/init.d/ntp stop
sudo ntpdate ntp.ubuntu.com
sudo /etc/init.d/ntp start

If you don’t stop the NTP daemon first, you’ll get “ntpdate[pid]: the NTP socket is in use, exiting”. Notably, don’t do this in a cron job, as ntpd should be enough. (It’s not clear why ntpd didn’t resolve the issue in the first place, but I’m blaming that on some configuration bug.)

BOINC and Time

BOINC seems to have had a bit of a problem with the time shift. (It was normally set at 80% usage, and jumped to 100% with absurd remaining times.) That turns out to be pretty easy to fix:

sudo /etc/init.d/boinc-client restart

And it should be good to go. It may still have some strange estimates for time (it would likely be safer to stop boinc-client before updating the time and then start it afterward, if I realized that would be an issue), but that’ll be fixed after the current workunits complete.

USPS Tracking

If you have a label number for a USPS package you want to track, you can bookmark this URL (obviously, put your number at the end) or keep it open in a tab. It’s not the result of a form submission, so refreshing won’t prompt for a resubmit, and loading the page again won’t ask for the tracking number.

http://trkcnfrm1.smi.usps.com/PTSInternetWeb/InterLabelInquiry.do?origTrackNum=[Your tracking number]

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

7/7/2009

PvPGN for a Private LAN

Filed under: Hacks, Programming, Technology — Andy @ 10:43 pm

A few notes on setting up PvPGN (the continuation of bnetd) for a private LAN. (The reason I’m setting it up is that I don’t expect to have an Internet connection for connecting to Battle.net proper, and would like to have the capabilities it provides, especially ladder games.) This post is generally much more technical than most of my previous posts, so you may want to skip it if you’re not really sure what’s going on. You won’t miss much.

So, my setup involves a router with DD-WRT, and an OLPC XO. The XO is set up using Ubuntu Intrepid on an SD card.

(more…)

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!

11/10/2008

New.

Filed under: General, Hacks — Andy @ 1:47 am

Hey, new stuff!

(If you’re reading via RSS, you really need to head over here.)

So, it’s a new design. That only took, what, four years? The last month or so of delays was mostly because I couldn’t get the headers to be in the right font (DejaVu Sans) too easily. I ended up using sIFR 3 for it, but despite it being a completely free (in both senses) font, Linux is the only major operating system to include it by default. So, I ended up using sIFR. We’ll see how it works, and I’ll decide whether the fraction-of-a-second increase in page load times is worth it. I think so, but any comments would be appreciated.

The layout itself is a bit complicated, and I spent a week or so working on the CSS to get it to work in various browsers. Interestingly, it does appear to work (mostly) in most browsers (recent versions of Firefox, Safari, Opera, and (eek) Internet Explorer are all fine). The ground along the bottom rises up on short pages in Internet Explorer 6, but not 5.5 or 7. (Though, really, if you’re using Internet Explorer, you should at least upgrade to version 7, or preferably Firefox, or even Safari.)

The images for the layout were created using entirely free software, mostly the GIMP (on Ubuntu). Anything that looks hand-drawn actually is hand-drawn, using a Wacom Bamboo Fun (except the dirt and vine, as those had to be tiled, so those are Bezier curves).

So, if something in the layout seems out of place, or horribly wrong in general, please leave me a comment and let me know so I can investigate. Mention which browser you’re using, and which operating system, if possible. Thanks!

(more…)

7/7/2008

Launching Recycling Reminder

Filed under: General, Hacks, Programming, Technology — Andy @ 10:37 am

Well, this was written way back when it seemed like a good idea, and it’s finally polished enough to actually release. Yay, something I actually finished!

On the off chance you might have some recycling that needs to be taken out (and you should..), this random little tool will let you set up a weekly reminder (an SMS message, actually) to actually get it out to the curb. It’s been working for me (and a few others) for several months now, so I’m fairly sure it’s stable.

So, if you’re (partially) responsible for getting your recycling out, go head over and sign up right now at Recycling Reminder. You’ll need a standard cellphone of some sort. It’s completely free, though clicking the ads now and then gets me a few pennies, if you’d like.

Please email me or leave a comment (or something) if you happen to find it useful, have a problem, or anything else. Thanks!

Andy

12/10/2005

Nightly Gaim 2.0.0 CVS Builds!

Filed under: Hacks — Andy @ 12:58 pm

<geek>

Presumably you know about Gaim, the awesome open-source, multi-protocol instant-messenging program. Maybe not. Anyway, check it out. I use it for Yahoo, AIM, and, of course, GTalk.

So, I saw that version 2.0 is supposed to have a bunch of new features. And it’s open source, so I can get CVS builds. And nobody knows how to build it. So, after a few days of frustration with Windows and Cygwin and GNU Make and others, I got Gaim to build on Windows. With a script. Nightly.

So now, anyone who wants bleeding-edge Gaim (though it’s usually fairly stable) can get it from my website at http://gaim.lardbucket.org/builds. If the download goes slowly, that’s because it’s going through Coral Cache to insulate me from any linking that others might do.

Also, the builds have been spotty the last few days and I’m not sure why. I’m looking into it, but if the builds aren’t there for certain days, that’s probably why.

I only keep builds for a week, then they get deleted. You can always get the newest one by going to cvs-latest.exe if the last day’s build succeeded.

</geek>

Next Page »
My Stuff
Blog Stuff
Categories
Archives