Rainbow tables - not well suited to crypt(3)
Rainbow tables - not well suited to crypt(3)
Posted Dec 4, 2010 15:26 UTC (Sat) by tialaramex (subscriber, #21167)In reply to: Savannah.gnu.org compromised by paulj
Parent article: Savannah.gnu.org compromised
Rainbow tables are a bad choice for traditional crypt(3) because it has salt. Not enough salt by modern standards, but still a 12 bit salt means your time-space tradeoff in choosing Rainbow tables just got 4096 times worse. You will need to crack many tens of thousands of equally valuable passwords to amortize the additional cost compared with brute force.
[NB the lwn article you linked is about a Windows hash scheme which uses unsalted DES, Microsoft chewed through three or four different lousy password hash schemes before finally getting one that doesn't suck worse than the one they could have cloned from Unix 30 years ago...]
To give some idea of what that 4096 number means in the real world:
If you can afford disk space and CPU time to build a Rainbow table for MD5 that covers the alphabet plus digits (A-Za-z0-9) for up to 8 characters (a lot of work, but enough to reverse many passwords), then if you try salted crypt(3) instead you'll only have resources for up to 6 characters instead.
You will miss any half-way secure passwords this way, which makes it of very limited value.
But the story gets better yet, because the above assumed the two hashes were equally expensive to calculate. But this isn't true unless you have the resources to use custom hardware; on general purpose CPUs crypt(3) was deliberately pessimised, and remains annoyingly expensive in CPU time for brute forcers or calculating Rainbow tables.
So the difference between traditional crypt(3) and MD5 ends up being way more than a constant factor 4096 for Rainbow tables. Enough more that I've never seen a public project to attempt even the somewhat useless six alphanumerics I described above for crypt(3).
Is it possible there's a private project? Yes. Is it likely? Hard to say, ask someone with more relevant expertise. Would it be expensive? Undoubtedly yes. So then is it likely script kiddies would use it to break into Savannah? No.
Posted Dec 4, 2010 16:57 UTC (Sat)
by paulj (subscriber, #341)
[Link]
I take your point on salting, but I still don't think it's infeasible for DES crypt, given that the 2^12 fold increase is still of a significantly lower scale than the size of botnets that are readily available for sale on the black-hat market. I'd agree DES crypt() isn't a sufficiently juicy target anymore (what uses it anymore?) and , but if someone /did/ care enough to brute-force DES crypt and if they expected to do this regularly enough, wouldn't they be daft to NOT store the results? E.g. if you needed O(100)GB of space for the total rainbow table, and if you could risk stealing 10GB from each computer in your botnet, then obviously you're looking at O(40k) size botnet to store it. That seems well within realms of feasibility... If lower probabilities of password recovery suffice (cause you're not interested in recovering specific ones), you can use less space and/or a smaller botnet.
And just generally, regardless of the size of the salt, if you're going to spend time computing it, you might as well store the result. The multiplicative increase of the salt need /not/ apply fully to your storage requirements, because you can trade storage space for computation with longer chains.
Rainbow tables - not well suited to crypt(3)