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

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()

[Leffe]

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

10 PRINT "HELLO WORLD"

The most secure piece of code, even on Microsoft(r) Windows(tm) platforms.

I've also got a question; What is the default/general password encryption scheme used in most GNU/Linux distributions? DES? Is DES an algorithm or a collection or interface or something... I don't know anything :(

I did write a program that worked exactly as crypt did though, it included certain unspoken functions from -lcrypt, especially one named crypt.

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.

Re:A testament to crypt()

[Anonymous Coward]

This statement starts off true and ends up totally false. A high end desktop machine cannot "crack" DES in under 24 hours. It can't even "crack" DES in under 24 years.

1) DES has never been "cracked". It has been brute forced.

2) A single machine would take on the order of 600 to 1200 years to brute force a single 56-bit key. Obviously, this number changes with the method used to brute force and the machine used.

There has never been a machine demonstrated capable of cracking 56-bit DES in under 24 hours. The EFF built a DES Cracker which could search the entire key space in 9 days.

DES is not considered insecure. Many applications would likely benefit from another choice however.

But...

[jchawk]

Unless they release these hashes out into the wild, the average cracker/hacker does not have access to this type of resource...

Definately cool though for proof of concept!

Re:Need more power

[grub]

Obviously we just are not using enough power.

Yup, if they ran this on the 220-230V systems in Europe this would have taken only 40 minutes. :)

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

Re:Change of Methods Needed?

[An Onerous Coward]

Actually, it's worse than that. You don't have to test every number between 1 and sqrt, just the primes.

I recall reading somewhere that it takes about ten bits to double the security of a public key, rather than one. I don't know if that's actually true.

Mirror.

[themassiah]

Mirrored here:

http://home.twcny.rr.com/scooper2/teracrack.pdf

Proof that this was MEANT to happen! :-P

[Wyzard]

Clearly, crypt() was meant to die: just look at its name!

As Schneier says on the first page of Chapter 1 of "Applied Cryptography",

(If you want to follow the ISO 7498-2 standard, use the terms "encipher" and "decipher". It seems that some cultures find the terms "encrypt" and "decrypt" offensive, as they refer to dead bodies.)

ftp site seems slow

[morcheeba]

They've got the tables on their ftp server, but it seems slashdotted because it's going really slow... my computer says "downloaded 4194304 bytes of 1209462790550 bytes (0.00034%)"

Anyone have a bit torrent for this thing?

Perhaps not

[AKAImBatman]

If I understand the article correctly, they're using serious computer power to develop a database of all passwords and their resulting hashes. In doing so, they can reverse engineer any hash back into a password via a 1 to 1 lookup. The only problem is that the attacker still needs physical access to your password hashes. In other words, this is much more serious for "insider" hacks where a system user wants root control.

Correct me if I'm wrong, but wasn't the point of moving the hashes from passwd to another root protected file (like "master.passwd") to prevent this sort of problem?

Re:Perhaps not

[Ancil]

Sorry, but you are wrong.

By moving to a hash like MD5, you can use a much larger "salt". This makes pre-encrypted dictionaries infeasible. Current crypt()-based scemes use a mere 12 bits of salt. A more advanced hash lets you use any length salt you'd like (though anything longer than the hash size is worthless).

Quick primer for those wondering what "salt" is. UNIX stores not only your encryped password, but also a 12-bit salt. The salt is essentially part of your password, which the OS stores in plaintext. Its sole function is to make pre-encrypted password databases difficult. The crypt function is not a true "hash", so UNIX cheats by permuting the encryption boxes using the salt. The effect is the same as adding the salt to a password before hashing it with MD5.

The scheme was developed for the express purpose of defeating attacks like this one. However, 12 bits ain't what it used to be. With only 4096 salts available, pre-encrypted dictionaries are now becoming feasible.

The Solution (TM) is to use a modern hash like MD5, and store a salt which is as long as the hash itself. In essence, this renders encrypted dictionaries worthless -- it's just as easy to brute-force a password from scratch.

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:Still

[^MB^]

hummmm, i would beg to differ with the 'iamdrscience' post.
You are thinking about normal computer science hashes not cryptographic hashes.

207 billion is a very small portion of the possible hash relations.

I worked on a project similar to this, a distributed password cracker.

They calculated 50million passwords and 4096 salts this gives ~207Billion hashes.

There are ~7.32*10^14 possible passwords (quick approximation) with the 4096 possible salts.
That gives ~2.99*10^18 possible hashes.

I think the author of the other post was thinking there would be a lot of collisions.
There are 2^64 possible permutations of the DES 'cipher text' which gives ~1.8*10^19 possible 'cipher text' final state.

This means there are six times as many theoretical hashes as there are actual password hashes.
That and the nature of the DES algorithm would make colusion not very likely.

Anyway back to the point... 207 billion hashes would be 2.07*10^11.

2.07*10^11/2.99*10^18 = .000007%

This is NOT a substantial portion of the search space.

-Nick

*cipher text is refering to the initial 64 zeros cipher text used in the DES password encryption.

Too Late

[sirReal.83.]

I've already rooted all your boxen and converted them to a worldwide Beowulf cluster.

Time to crack some pr0n passwords...

Re:Solaris

[FireDoctor]

crypt() is just an interface to an underlying algorithm. In Solaris 9 12/02, there is an option to use Blowfish or MD5:

Enhanced crypt() Function Password encryption protects passwords from being read by intruders. Three strong password encryption modules are now available in the software:

* A version of Blowfish that is compatible with BSD systems

* A version of MD5 that is compatible with BSD and Linux systems

* A stronger version of MD5 that is compatible with other Solaris 9 12/02 systems

Solaris 9 12/02 Release Notes

and System Administration Guide: Security Services

Re:Getting there...

[tep-sdsc]

Funny, we did this work almost a year ago, and someone finally notices :-(

Yes, this is a very small part of the total theorectical key space.

But its exactly the part of the space that is most "interesting"; this is the part that will most likely be searched by an attacker AND the part that is most likely to have a real, user-selected password.

The original goal (years ago) was to allow us to verify that our users weren't using passwords that would be likely to be found by an attacker.

Yes, passwords are *supposed* to be stored in shadow files that are not accessible, except by root, but in practice, it is often discovered out in the Real World, especially at larger multi-vendor sites, that user password hashes are copied between machines, stored in databases, and in general available to an attacker who does not yet have root.

These are the same sites that often can't or haven't converted to md5() hashes, as they have older legacy OSes that don't do md5(). Note that even though Sun "supports" md5() hashes, they don't support them everywhere and it certainly isn't seamless. Don't get me started about AIX. Linux and the *BSD folks are way ahead of most of the commercial UNIX variants.

As for the scalability, read the whole paper. We used the largest single machine at SDSC, but its rather dated in terms of crypt() performance. A distributed.net-style project using typical home machines would win, IF you could get a thousand or so people to cooperate.

The Terabytes of storage in a single filesystem didn't hurt in the sort/merge phases either.

Personally, I'm a Kerberos fan :-)

Re:So much for longer passwords being more secure?

[thedillybar]

Well, for starters, you should avoiding telling people the length of your password...

That's what I like to see...

[dmccartney]

From the article:

In cases where two sets of options produced insignificantly different speeds, a physical binary decision device (U.S. quarter coin) was flipped to determine which would be used.

That had to be fun for them to write up.
I am going to go convert two of my physical binary decision devices into a cup of coffee.

I wrote the MD5 based crypt() for a reason...

[phkamp]

Back in 1994 I wrote the MD5 based crypt() which it seems almost everybody has adopted from FreeBSD by now: *BSD, Linux/GLIBC, Cisco and appearantly even Solaris.

The important properties of a good crypt() algorithm are still:

1. Input password is not length or charset restricted.

2. The algorithm is complex enough to not lend itself easily to hardware implementations (FPGAs etc).

3. The Salt is big enough that precomputing dictionaries is not feasible.

You will notice that apart from #1, these are not quantified, DES-based crypt() fulfilled #2 and #3 back in its days, but no longer does so. In a similar way, some day we will declare my MD5 based password scrambler as failing one or both of those criteria because password scrambling is not a case of finding "the" algorithm and putting a checkmark in the box, it needs to on periodically evaluated and improved every decade or so.

That is why I put the $1$ prefix on my MD5-based crypt(), so that you can update to a better algorithm when you need to. OpenBSD has already added a couple of stronger SHA based algorithms ($2...) and more can be added in the future.

In the absense of any other "IANA" for this, I would appreciate if you would register your "magic strings" with me so we don't have collisions.

If you're still using DES-based crypt(), switch to MD5 based crypt() now. Don't wait any longer, you are already 9 years late (IMO).

It's even "free as in free beer" :-)

Re:interesting system integration issues

[Permission Denied]

Actually to compare a value to a crypt()ed value you can't just pass the hash because you don't know in advance what salt was used to create the hash. In all these cases the plain password is probably sent instead...

In standard crypt() format, the salt is the first two characters of the hash.

The canonical way hash a password using crypt():

% perl
$pass = "hello";
$hash = crypt($pass, 'xo');
print "hash: $hash\n";
hash: xoqGBOjl8JQ8I

The characters "xo" are chosen at random when the password is first hashed. Note how they are the first two characters of the hash. The canonical way to check if a given password matches a hash is:

% perl
$hash = "xoqGBOjl8JQ8I";
$pass = "hello";
print "they match\n" if $hash eq crypt($pass, $hash);
they match

Note how I use the entire hash as the salt. Only the first two characters of the salt are actually used by crypt(). Actually, only twelve bits from the first two characters are used for the salt:

% perl
print crypt("hello", ";!") . "\n";
print crypt("hello", "#*") . "\n";
;!dR0/E99ehpU
#*dR0/E99ehpU

Two different salts resulted in the same hashes: this shows that crypt() does not use the entire 16 bits of the two characters (indeed, not even the entire 14 bits of the characters as US-ASCII). Only twelve bits are in fact used.

Also, the entire password is not used: in fact, only the first eight characters of the password are used:

print crypt("12345678", "xo") . "\n";
print crypt("123456789", "xo") . "\n";
xoUgvoME1De5c
xoUgvoME1De5c

Since slashcode strips un-american characters, I cannot demonstrate the the top bit of each character in the passphrase is discarded.

Now, we can do some math: if 12 bits of salt is used, we have 4096 possible salts (2 ^ 12). If 7 bits of 8 characters are used, we have 7 * 8 = 56 bits of possible password. Thus, we have 2 ^ 56 * 4096 = 295147905179352825856 possible passwords (295 quintillion).

Now, these numbers don't match up with what's reported in the article description (207 billion hashes). It's possible that some combinations of passwords and salts produce identical hashes, but I would never expect nearly this many...time to read the article.

OK, I skimmed the article. They did not cover the entire keyspace of passwords. They only created a list of candidate passwords from a system dictionary using Crack's password generation routines. There are 1425835290 (1.4 billion) times more possible passwords than they tested. If they tried hashing all possible passwords, it would have taken them 217022 years at the rate they're going (80 minutes per 207 billion passwords). The storage of these hashes is out of the question (I don't know my metrics that high :).

Actually, on second thought, I can imagine a compression scheme that could drastically cut down on the storage involved: but this is irrelevant, the CPU time is still overwhelming.

Lesson learned: worry more about the quality of your passwords than the quality of your password hashing algorithm.

[Perhaps I missed something? Anyone care to check my arithmetic?]