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."

Comments

Change of Methods Needed?

[Erioll]

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

Still

[mugnyte]

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.

Re:You missed the point

[dlippolt]

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.

Re:You missed the point

[AKAImBatman]

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.

not a new concept, but a new practical limit

[sir_cello]

Not a new concept, but novel given the use of modern computing resources.

I (and probably others, I claim no novelty, only an inventive step :-) wrote software in 1991/1992 to do this: unfortunately sun4 MP's and about a gigabyte of disk were the best we had.

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 :-). The output was also stored in bitwise numerical order - matching divide/2 matching very fast.

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 :-).