clover/hashpan — pull request #4 by O-I (2013-12-01 23:30:58+00:00)
Title: A great example of how not to do this efficiently for posterity

I saw this challenge in a promoted tweet on Twitter and, having always had a fascination with password cracking, thought it would be fun to try my hand at this.

I studied CS briefly from high school to my early years in college (Pascal, C/C++, Java) but never really took to it, electing to concentrate on math and philosophy. Somehow I ended up working in retail for the past 8 years, but my recent love affair with expressive, high-level languages like Python and especially Ruby have prompted me to pursue a career change to web development. Naturally, I had to attempt implementing a halfway decent solution in my favorite language, because if I could do it in Ruby on a MacBook with appreciable speed, it would probably be trivial for a good programmer to do with a top-shelf GPU and a custom-made rainbow table.

I started by converting the PAN's in pans.txt to the base64 encoding of their respective SHA-1 hashes and comparing them to the hashes in hashes.txt. Alas, no matches — it can't be that easy. Another glance at pans.txt seemed to suggest I would only have to look for PAN's prefixed with a 4 or 5. At that point, I implemented a Luhn check to see if these were in fact valid PAN's. Sure enough, they were — great another digit that's essentially fixed.

On further scrutiny (and, honestly, looking at how others were attacking the problem), I noticed some identical 6-digit BIN's in pans.txt. I found 73 unique BIN's and sorted them by frequency. I made the assumption that hashes.txt would contain the same BIN's and conform roughly to the same frequency distribution. That meant checking 73 billion PAN's would be sufficient to crack all the hashes — and focusing on the top 5 BIN's would get me nearly a third. This is where I ran into the wall.

I've never done any parallel programming and was not able to figure out an acceptably efficient way to do this in Ruby by the deadline. I did run through all 5 billion combinations of the 5 most frequent BIN's in 5 separate processes just for kicks on my MacBook Pro. This turned out to be grossly inefficient (taking in excess of 36 hours), but surprisingly, I netted 31% of the hashes in that run, corroborating that the above assumptions are likely true.

I really liked this challenge although it was a little above my threshold as a novice programmer. Although my code is certainly not an optimal solution, I'm motivated to learn more about parallel processing and playing around with this more (gotta start somewhere, right?). I've also really enjoyed looking at how others attacked this problem — some crazy cool ideas. Needless to say, CUDAru and modifying the Cryptohaze source have been added to my to-do-someday list. (-:

Cheers!
O-I