Algorithms for the Masses by Julian M Bucknall

I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there’s an Xmas issue as well — so it’s a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so. What I’ll do is publish the article from a year ago or so here when I purchase the current issue.

February 2009’s article was a "’commission’ in the sense that Martin Cooper, the Editor of PCPlus, wrote to me asking what I knew about rainbow tables and wouldn’t it be a good idea if I wrote an article on them. I don’t know about you but, but when the Head Honcho says wouldn’t it be a good idea, you take it as do it now. So I did.

Actually I didn’t know much about them to begin with and the research proved interesting and pleasurable. In essence, rainbow tables are a technique using large pre-computed tables that help you crack hashed passwords. The way it works is to use a class of functions called reduce functions that calculate a contender password from the hash. These reduce functions are used alongside the hash functions, applied in a chain: hash followed by reduce followed by hash. You end up with a candidate password and a final hash, but that chain covers all the intermediary passwords that were also hashed. Given enough reduce functions (thousands of them) and enough time, you’d create a large table of initial passwords and final hashes.

To crack a password, you get its hashed value and check that hash to be in your table. It it is, reproduce the chain until you get to the point where you can read off the password. If not, reduce the given hash with that final reduce function, hash the results, and check that new hash to be in the table. Continue this cycle until you find a match of the computed hash and an entry in the table (and therefore the password from regenerating the chain), or run out of reduce functions. For a more complete description, read the article.

This article first appeared in issue 278, February 2009.

You can download the PDF here.

(Quick aside: PCPlus used to put part of their archive as PDFs on the DVD in the back of the magazine. They’ve now moved to a CD instead of a DVD, presumably to save on costs, and the archive is no longer on there. I hear they’re going to publish it online instead, sometime in the near future.)

Posts on similar topics...

• PCPlus 277: Dictionaries and hash tables
• PCPlus 279: JPEG compression
• PCPlus 281: Indexing the Internet

Share it: