Rainbow Tables
The Shmoo Group is pleased to be mentor the Rainbow Tables project as part of Google's Summer of Code 2006 mentor program. The project is being developed by Keith Larimore, and mentored by Michael Gady.
Project Information
Our rainbow tables are generated by RainbowCrack, Zhu Shuanglei's software implementation of Philippe Oechslin's cryptanalytic time/memory trade-off technique. In 2005, members of The Shmoo Group generated the largest possible rainbow table set for all of the valid input characters to the LANMAN password hash function, to complement previously generated smaller table sets. And then we give them away for free, via BitTorrent.
Instead of requiring everyone to have their own personal copy of all of the passwords, we'd much rather make them available for free. To do this, a number of things need to be developed:
- A queuing system to take requests and serve results asynchronously
- Rate-limiting in the requests, to prevent deinal of service attacks
- A distributed query client, since we even though we have all of the passwords, having all of the passwords on one disk is quite a big disk. Having it spread across multiple hosts would help spread the load, and allow us to service more requests.
- A notification system, to alert users when their lookup request has been fulfilled, and details on how they can get their results (perhaps email based?)
- Possibly implementing a batch query/lookup option and support system to service users who would like to query significant numbers of hashes at once and in one result set (you'd need to identify the minimum and maximum numbers of hashes accepted by the batch system, and factor in the weight of a batch request into the queuing system as well)
- Would it be worthwhile to design and document a query analyzer and/or service log analyzer to identify the most common hashes and cache them? If so, how would you do it, and can you implement it as part of the service and interface?
- An interface to submit queries via DNS and return results in TXT records, using the same backend data store as the web interface. Dan Kaminksy has done similar work with other data sources that might be helpful to look at. This should work with DNS tools like DiG, e.g.:
$ dig -q txt 053C5215FC9CECC0ADF0D6E011E11FBD.rainbowtables.shmoo.com ; <<>> DiG 9.2.3 <<>> -t txt 053C5215FC9CECC0ADF0D6E011E11FBD.rainbowtables.shmoo.com ;; global options: printcmd ;; Got answer: ;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 43329 ;; flags: qr aa rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 2, ADDITIONAL: 2 ;; QUESTION SECTION: ;053C5215FC9CECC0ADF0D6E011E11FBD.rainbowtables.shmoo.com. IN TXT ;; ANSWER SECTION: 053C5215FC9CECC0ADF0D6E011E11FBD.rainbowtables.shmoo.com. 7200 IN TXT "ohgawdIhatepasswords"