Savannah.gnu.org compromised
Savannah.gnu.org compromised
Posted Dec 2, 2010 16:43 UTC (Thu) by anselm (subscriber, #2796)In reply to: Savannah.gnu.org compromised by madscientist
Parent article: Savannah.gnu.org compromised
Being a variant of DES, the traditional Unix password encryption scheme can only distinguish a fairly small number of passwords (256, to be exact – a password consists of eight seven-bit characters, and if you enter something longer it will be truncated to length eight). In the decades since the scheme was originally put forward, computers have become fast enough so that it is no longer a big deal to work through all 256 possible passwords. It has also become reasonable to precompute and store tables of encrypted passwords, so if one gains access to a list of encrypted passwords it becomes trivial to find the corresponding unencrypted ones.
The more modern schemes use hash functions with much longer results (128 bits for MD5) and also allow longer unencrypted passwords, so precomputed tables are a lot less feasible. As far as brute-force attacks go, people have made progress doing those using cloud-based services or botnets, so even the weaker »strong« hash functions like MD5 or SHA-1 probably ought to be on their way out.
Posted Dec 3, 2010 16:36 UTC (Fri)
by tialaramex (subscriber, #21167)
[Link] (3 responses)
"no longer a big deal" might be a fair description of something which utterly collapses when reasonable resources are engaged, like say the LM hash where you can use pre-computed rainbow tables that fit easily on an ordinary desktop PC, then have password recovery take a few seconds (for disk seeks and re-computation) per hash.
But for crypt you could pick the sweet spot of CPU power per dollar, spend hundreds of thousands of dollars, and still take months per hash. If you can afford petabytes of storage to go with those CPUs you could pre-compute, and only do the work once, but that's yet more hundreds of thousands of dollars because now you're building a SAN as well as a compute farm.
Knowing this, and given that nobody thinks the NSA broke into Savannah, it's no surprise that the reason the passwords were trivially determined is that they used unsalted MD5, which is far worse than crypt despite the apparent improvement of 128 bits vs 56. Partial rainbow tables (covering e.g. "HaRdPwD" or "linux98") for unsalted MD5 are freely available anywhere files of dubious legality are traded and probably the black hats went from the list of hashes to their first few dozen passwords in seconds, with nothing more than a home PC.
Posted Dec 3, 2010 18:23 UTC (Fri)
by paulj (subscriber, #341)
[Link] (2 responses)
Posted Dec 4, 2010 15:26 UTC (Sat)
by tialaramex (subscriber, #21167)
[Link] (1 responses)
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.
Savannah.gnu.org compromised
Savannah.gnu.org compromised
Rainbow tables - not well suited to crypt(3)
Rainbow tables - not well suited to crypt(3)