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

Solaris

[CrankyFool]

I wonder if this will spur Sunto finally make the default password encryption algorithm on Solaris something other than crypt...

A testament to crypt()

[grub]

Actually with most Unixish systems going to other password formats such as MD5 and Blowfish I'd think that this goes to show that (NSA notwithstanding) crypt() has had a long, healthy existance. Rather than saying 'crypt() is dead' they should be saying 'it took 30ish years but crypt() is at the end of its useful life'.

Not many pieces of code will be able to boast that lifespan.

Re:A testament to crypt()

[tuffy]

how many haX0rs do you know that have machine capable of running TeraFLOPs per second?

They don't need to own such a machine, only have access to one long enough.

Re:A testament to crypt()

[Mysticalfruit]

Here's the more important question...

In ten years, how many haX0rs will have access to TerFLOP machines?

Answer: Lots...

Re:A testament to crypt()

[hackstraw]

Maybe I'm nop paranoid enough, but I've never been too concerned about the security of people's passwords after root has been compromised, so I don't care what format the hashes are in /etc/shadow.

Also, the method of "cracking" crypt() passwords can generate collisons, so the password that worked on one system may not work on another (because of different salts used).

Re:A testament to crypt()

[MooCows]

Actually, quite a lot of them have it now, in the form of thousands of compromised machines.
Can be used to DDOS, or to compute.

interesting system integration issues

[jrexilius]

This should cause some interesting systems integration issues as crypt has become the defacto standard for cross system authentication and password management. (hash it at your web server, compare it with app server, store it in DB, where it is used by samba to auth winblow users, blah blah, I know these arent exact implementation examples but you get the idea). Just a lot of code or libraries to change to make a system secure.

The reality is

[phorm]

That over time, any encryption alghorythm may be broken by superior computer. 50 years from now, normal computers will put anything we have to shame, and supercomputers will make current ones look like calculators.

Crypt is already supplantable by many improved techniques, but even if it is used, are they going to make these keys available to the world?

If not, now that it's known a really faster computer can solve then, perhaps the next step in spammy-crackers' arsenal will be to take their virussed drones away from attacking anti-spam sites and focus them at generating crypt or other password solutions? How many drones working P2P-style (you create these hashes, I'll create these ones) would it take to equal this supercomputer?

Re:Change of Methods Needed?

[the morgawr]

I thought I read that MD5 had some problems as well (that's why OpenBSD uses Blowfish). I think it had something to do with the hashes not being evenly and randomly distributed over the possible space. Anyone who knows more about this care to comment?

Re:Change of Methods Needed?

[gorilla]

Remember that every bit approximatly doubles the type to break it. RSA-1024 is about 10^134 times harder to break than RSA-576.

Only if you have the crypt string

[dbavirt]

The ability to generate lots of crypt strings only helps you if you have the original crypt string to compare against. Most modern UNIX systems store crypt strings in /etc/shadow which is only readable by root. The crypt string is never passed across the net during most auth sequences. (Certain types of LDAP auth being the exception here.)

The problem occurs if someone manages to break into a machine, achieve root, and pick up the /etc/shadow file. They can now brute-force all the passwords given enough time, and it appears that the amount of time needed is shrinking.

This is a good argument for using different passwords on untrusted boxese and changing your password often.

Re:Only if you have the crypt string

[dbavirt]

Sure, but the /etc/shadow file is their key to getting the cleartext of your password for use on other machines. At this point, it may be easier to brute force /etc/shadow than it is to set up backdoors, trojans, network sniffing, etc.

It can be much harder to determine that someone has hijacked your account than it is to note that a root kit has been installed

Re:Only if you have the crypt string

[coyote-san]

How hard do you think it is to write a PAM module that sends off an email with the user name and password?

This won't "crack" inactive accounts, but it will capture any account where somebody uses a password to log in. On most systems the attacker wouldn't even need to hide this function in an existing pam module, they could just provide a new one with an official sounding name (e.g., "pam_audit") and edit the PAM configuration files.

(N.B., not all access requires passwords. E.g., I prefer using SSH DSA authentication instead of password authentication.)

Re:Change of Methods Needed?

[Anml4ixoye]

In a word, no.

As was also discussed yesterday, *nothing* is uncrackable, with the exception of correctly used one-time pads.

The key is to put the appropriate level of security with the data you want protected. For example, if you have data you have to keep secret for 2 months, and they can crack it in 6, you can use that. But if you need to keep data, worth millions of dollars, secret for an extended period, then you should review your security.

However, I think that if you didn't start off with the above concept in mind when you started encrypting your data, then you weren't doing your job. Have 576 cracked shouldn't worry you unless you have older encrypted data using that.

You are right that it is a game. To keep information secure, you have to protect it. Because you protected it, people will want to try to unprotect it. Eventually they will, and if one doesn't keep up, you will lose it.

So, we don't need more secure forms of encryption, we just need to review the current ones and use the appropriate encryption scheme for the data trying to be protected.

Re:Need better crypto

[Anonymous Coward]

It's a pity that the human mind can't be emulated using a computer, otherwise one could store the passwords in the mind of a woman, which is both impossible to understand and decrypt. ;)

Give it some time

[appleLaserWriter]

Wait a year or three and this kind of computing power will be available in game consoles in bedrooms across america.

Re:Still

[Anonymous Coward]

There isn't a unique hash value for every possible password... that's the way hashes work.

Re:Change of Methods Needed?

[AnotherBlackHat]

is this a message that we need more secure forms of encryption than we already have?

No, it's a message that if you're still using stuff that was developed in the 1970s, you should consider upgrading to the stuff from two years ago.

-- this is not a .sig

Only 50 million passwords

[vondo]

Those 207 billion hashes come from only 50 million possible passwords. Using only 10 letters (no upper case) and 8 characters gives 100 million passwords. Bumping the letter pool up to 75 (52 letters, numbers, a few symbols) give you 1E15 possible passwords.

Moral of the story: Pick a good password.

Re:Only 50 million passwords

[ftzdomino]

Computing the entire 7.2e16 values (man crypt) should take about 52 years. Assuming Moore's law, this drops to about 7.2 years.

Re:MD5.

[scheme]

From personal experience with cracking passwords, I wouldn't consider unmodified MD5 to be very secure. My computer can test 5 million MD5 hashes a second, or the entire 8-character password space in ten months.

You're mistaken. If you assume that a 8 character password only has upper and lower letters and numbers there are 218340105584896 possible combinations. That would take your computer about 7 years to test the space completely. If you allow passwords to have punctuation then this increases a lot more.

salt and recursive crypt

[goombah99]

They have a database of all possible hashes. Your scheme would mean that an attacker would have to do three lookups, instead of one.

No its not that simple. If it were just a database lookup then simply increasing the size of the salt a million fold would be all that was neccessary to foil any pre-computed attack. The important point in this article is that they it only takes 80 minutes to compute the crypts given the salt.

thus one way to defeat this is to hide the salt as follows. The attack requires stealing the hashed password file. Each entry will be of the form

SALT, HASH_code

since the salt is given they could run their computer for 80 minutes and test 209 billion inversions of the hashcode. However if the stored item were instead: SALT2, crypt( SALT1, crypt(passwd)) then you would have to crack the first one to get the salt for the second. now iterate this.

Just what is being crtiqued?

[i_r_sensitive]

Sounds more like a stinging indictment of weak passwords than crypt().

Reading the article there is no way that teracrack is going to deal with a strong password, the hash won't be present in it's table.

Regardless of algorithm, the weak passwords will allways be the first to fall. We can all stop using crypt() and start using md5 hashes, but the same techniques can be applied again, and again the first passwords to fall will be the weak ones.

I hate to sound like a Luddite, but technical problems aren't allways best fixed with more technology. The best use of teracrack that I can see, is the same use that it's predecessor had, to identify weak passwords and identify them to the user and admin to ensure that this core problem is addressed.

That's not how it's done...

[Duncan3]

And yet key loggers and social engineering are still exactly as fast and effective as they were when they were invented...

Think of the children, Moore's children!!!