Slashdot Mirror
The Death Throes of crypt()
dex writes "Tom Perrine and Devin Kowatch of the San Diego Supercomputer Center have issued "Teracrack:
Password cracking using TeraFLOP and PetaByte Resources" (PDF, HTML version via Google). Using SDSC's
prodigious computing facilities, they precomputed 207 billion crypt() hashes in
80 minutes."
In the wake of stories like this, and yesterday's story about RSA-576 being cracked (here), is this a message that we need more secure forms of encryption than we already have? RSA is great so far, but how long until 1024 is broken? Or any other schemes, like the MD5 hashing that's used for digital signatures?
Topics that people with lots of credentials behind their names are going to have to solve. Keeping ahead of the crackers is a big concern not only for security of transactions, but for personal privacy as well.
Erioll
Besides, never underestimate the power of distributed computing by MS worms.
The only thing more dangerous than a file named -rf is renaming it -rf\ /
Even so, using a 10 character input of about 72 possible input chars, isn't 207 billion still only like .0000055% of the total search space?
So that 20000 * 80minutes gives ~1% of the space cracked?
2000000 * 80 minutes = 304 years to fully close the space.
With a perfect distribution, the mean of about 150 years seems like a long time.
Someone please check my assumptions here.
I remember back in high school I had created a bunch of accounts on my linux box and used some program to try and decipher the passwords. 1-4 charecter passwords were found in 30 minutes (on my blazing-fast-at-the-time 200MHz Pentium 1), 5 charecter passwords took 2 days, 6 charecter passwords took... well, forever more or less. I figured at the time, a 7 charecter password would be sufficient forever (at least for my life time), but I guess not. Now I use 10 charecter passwords for most of my stuff... Do I need to move to 15 charecters? A passphrase instead of a password?
The Doormat
If you're not outraged, then you're not paying attention.
also, if you set aside the cpu costs, and need a few terabytes of disk space to store this data, how much does that cost today? according to pricewatch, you're talkinga bout $266 for (about) 300GB of disk. So for just over $1k, you've got 1TB.
Table 7 comes up with 2.263TB of disk space storage, so maybe i'll need a bit more than $2k just for disk. Calcualate your I/O and crypt()/sec, how long would it take for you to generate them all if you generated a distributed application (eg: setiathome-like) and have them be 'uploaded' to you? Obviously you can't do this on your DSL/cable, and you start to see the network performance issues they mentioned, but if you set up a small cluster of your older PCs in a room, use FE to link them up, you'll have that disk and ethernet card spinning (interrupting that is) at a steady clip trying to fill up your disk.
Make a worm/virus that spreads and distributes work units out to other hosts it's able to infect, and you could probally just keep the database in-memory across a wide set of hosts.
as far as i'm concerned, sun's pam configuration and flexible login setup only applies to solaris 9 and above. after trying to come up with a sitewide md5 solution i found solaris 8 to be terribly difficult to work with. dont get me started on their broken ldap libraries.
several datacenters i work with independently only offer solaris 8 so "why aren't you using the latest sun distro's" falls on my deaf ears. the huge body of vendor supplied software which calls for solaris 8 just makes it worse.
nis implementations that pass these crypt values around the network just makes keeping them inaccessible to users a nightmare.
crypt-for-passwords is one of those "standard unix" methodologies that needs to have already died a horrible death. the original title of this topic was hopefully appropriate.
I'm really not all that familiar with the inner workings of cryptography, but it seems like it'd make sense to do more system-specific hashing. (Not in all cases, of course.)
For example, I was looking at the MySQL tables on a site I run, and realized that my password hash there is the same as on other boxes I have accounts on. For example, 5f4dcc3b5aa765d61d8327deb882cf99 is the MD5 sum of "password," anyone with access to a set of passwords could simply skim through looking for this and other well-known hashes.
In many cases, wouldn't it make a fair amount of sense to use machine-specific algorithms for generating password hashes? It could even be something simple, like taking the hash of "$hostname-$username-$password". You could generate all the hashes you wanted, but if you didn't know my username and the hostname, the hash would end up being different. The end result is that, even though I (insecurely, I know) use the same password (and often, the same username), I would have a different password hash on each machine; you'd have to know all three fields before you could brute-force my password.
Is there something I'm overlooking? This idea seems like it'd work out really well; I can't possibly have just described some revolutionary new idea, though.
________________________________________________
suwain_2
But my point still holds. Sun wants to maintain backward compatibility. Period. That's separate from suck-add implementations of the PAM authentication method. And you're lucky. Last time I administrated Solaris boxes (other than my home workstation), I was stuck with Solaris 7. Trust me, that hurt.
nis implementations that pass these crypt values around the network just makes keeping them inaccessible to users a nightmare.
I feel your pain. That's going to be a difficult one to solve though. How does a user authenticate on a network if they can't pass their hash? One could add public key encryption on top of the authentication protocol, but one slip up in key management and the whole deck of cards collapses. After all, how long will it be until we see a worm that uses distributed power to begin generating all possible MD5 hashes? A daunting task to be sure, but certainly not beyond the current state of computing power.
Javascript + Nintendo DSi = DSiCade
In Jaguar (OS X 10.2) and earlier, type:
.
nidump passwd
In Panther (10.3+) it will not show the hashes, and I believe a different algorythm is used anyway.
W
-------------------
This is my SIG. There are many like it, but this one is mine.
Not a new concept, but novel given the use of modern computing resources.
:-) wrote software in 1991/1992 to do this: unfortunately sun4 MP's and about a gigabyte of disk were the best we had.
:-). The output was also stored in bitwise numerical order - matching divide/2 matching very fast.
:-).
I (and probably others, I claim no novelty, only an inventive step
Rather than precompute the entire crypt() space, we precomputed the space for well known words (and combinations of those words with different prefix and suffix), because for any individual word, there are only 32 [I think from memory - 5 bits?] combinations that it can crypt to given the random salt that was possible.
Because of available disk space, we couldn't store the entire precomputed output: so we chose to only store the first N bits of it. This was configurable. I cannot remember the exact figure - sure I could dig the code up out of an old CDROM archive
So the password cracker would then mmap() the couple of gigabyte file, then easily find (or not find) a candidate prefix. If it found the prefix, it ran a few trial crypt()'s to ensure an exact match. In practice, because of the lack of diversity in passwords, there were few false candidate matches: so the password cracker had some extremely large hundreds/millions of equivalent cracks per second as a result of mostly just not finding comparisons, and a few trial runs for succesful targets (I think the running rate of the other two popular crackers at that time was about 100K cracks/second).
Anyway - that was a long time ago - fun and games as a student. I still have the source code
In the Bell Labs UTS Ninth Edition (V9 Unix) released in 1986, the crypt command was moved to manual section 6, games, along with trek, bridge, boggle, etc. Crypt (the lib in section 3) still existed, however.