lardbucket: programming

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

3/3/2013

Calcsy – See your calculator on your computer

Filed under: Education, Math, Programming, School, Technology — Andy @ 9:17 pm

Calcsy LogoCalcsy is a tool you can download and use on your computer to show (and save) the screen of your TI-84+ or TI-89 Titanium calculator.

It’s useful for projecting the screen large enough for other people to see, or for taking a screenshot to use in instructions. For example, I’ve used it in teaching how to graph functions on a calculator, and I suspect it will be similarly useful to other people.

I first wrote Calcsy almost two years ago, and have been (very) slowly making it better since then. It’s now to a state where I think it’s reasonable to release. At the moment, it’s only available for Mac OS X, although it should be possible to port to Windows if there’s enough demand. Hopefully it’s pretty self-explanatory, but feel free to let me know if you have any questions.

All you need is a TI-84+ (or TI-84+ Silver Edition) or TI-89 Titanium and a USB cable to plug it in to your computer. The program is free, and you don’t need any special software on your calculator. (You also don’t need one of the special “Presentation Link” adapters – your computer and a normal USB cable works just fine.)

Other details of note: I suspect it won’t work with the very new TI-84+ Color calculators, but I’m happy to try to make it work if someone wants to send me one. Also, the logo was made by David Felice, so thanks are due to him.

Anyway, it’s free, go check it out. Let me know if you have any questions/comments/problems/etc.

Andy Schmitz

2/27/2011

FABridgeC: A smaller FABridge

Filed under: Open Source, Programming — Andy @ 12:31 pm

I was working with some JavaScript libraries this week, and happened to have a use for Adobe’s Flex Ajax Bridge (also known as FABridge). However, I’m trying to work with Closure, and the most common FABridge.js is a rather large 18 KiB that doesn’t really work very well with Closure’s compiler.

So, I took a few hours to go through and make it work with Closure, and then to make it work compiled outside of Closure in case anyone else wants a smaller version of FABridge. I’m calling the result FABridgeC, and you can read more about it on the project’s GitHub page. For most users, this is a minified FABridge.js (or if you prefer Closure’s terminology, a compiled FABridge.js) in just 5.4 KiB that can be dropped in instead of FABridge.js, and should work in exactly the same manner as the original for almost everyone. (There are a few minor caveats explained on the project page.) If you’re using FABridge at the moment, try dropping it in place of your existing FABridge.js, and let me know how it goes!

Feel free to send me a message via GitHub (I’m aschmitz, the repository’s owner) or leave a comment here with any questions, problems, or other comments.

Andy Schmitz

10/11/2010

Announcing scavhunt

Filed under: Open Source, Programming, School, Technology — Andy @ 5:48 pm

Since the end of Dan Meyer’s SLV SCAV, it’s been in the back of my mind to get the source code available to more people, and there was at least some interest from others about running their own copies.

As a result, I took the time to go through the code, remove any references to the school, students, or teachers that I could find, and generally cleaned the code up for release. I changed the name to “scavhunt,” and made a working version that I can release. I’m happy to say that the code is now available as open source (AGPL v3), from GitHub as scavhunt.

Unfortunately, I haven’t yet had the time to properly document things. As it is, if you pull the code down (either use git if you’re comfortable with it, or download a tarball/zipball with the “Downloads” button in the upper-right corner of the GitHub page), it should be a working scavenger hunt, although a bit sparse. There are a number of files you should modify, and some directories that need to be writable by the web server, but those are all documented on the README.md file (and also on the GitHub page for the project). It comes with two example questions as a basis for writing your own, although additional question types exist in the code as well.

So, the code is now available for your use, however you see fit (as long as it complies with the AGPL v3, which is pretty relaxed in terms of usage). If anyone has any questions, feel free to contact me at andy [dot] schmitz [at] gmail [dot] com, or potentially file an issue on GitHub (although I’m new to GitHub, so it may take me a while to figure out how to respond). Unfortunately, at the moment, I don’t have enough time to necessarily improve the code in the ways I would like to, but I can certainly answer questions and respond to pull requests from those who would like to improve it on their own. Contributing your improvements back would be greatly appreciated. And hey, if you use it, I’d appreciate an email or tweet (@aschmitz) to see where it’s in use.

Andy Schmitz

P.S. This is indeed where the scoreboard movement tracking code came from, so that section is rather well-commented. Unfortunately, the rest is less documented, but hopefully understandable.

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

5/19/2010

VP8, WebM, and FFmpeg

Filed under: Programming, Technology — Andy @ 8:06 pm

So, today at Google I/O 2010, Google announced that, along with a number of other groups, they were releasing WebM, a video container and codec. (WebM itself specifies the container, which is a variation of Matroska, as well as the video format, the newly-released VP8, and the audio format, Ogg Vorbis.) I won’t get into the technical details of the codec, as I’m not really qualified to do so, but a developer for x264 has a reasonably thorough review of a prerelease version of the code here.

The interesting part of VP8 / WebM is that it is a reasonably good video standard that may be theoretically free to use. (The currently popular “best” video format, H.264, is riddled with patents and requires licensing for most uses, although encoding video that’s available for free doesn’t require payments until at least 20151.) It doesn’t appear as though anybody is claiming that WebM is the best video format available, but it’s reasonably good, and potentially free to use. (It’s impossible to know whether someone else has patented parts of the standard, because that would require examining every software patent ever granted, which is not going to happen.) For some background, the video codec, VP8, was produced by a company named On2 before Google bought them last year. Its predecessors, VP6 and VP7 were used for video in Flash2 and the video in Skype3, respectively.

Most of this will be fairly boring to anyone who normally reads this blog, but if you’re interested in a way to encode WebM videos yourself in Ubuntu, read on.

(more…)

  1. The press release PDF from MPEG LA, the group licensing the patents for H.264
  2. An Adobe article on encoding video for Flash using VP6. An earlier version of this post claimed VP6 was the original codec for Flash, which is false.
  3. A press release

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!

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

Next Page »
My Stuff
Blog Stuff
Categories
Archives