The Death Throes of crypt() 388
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."
Mirror. (Score:5, Informative)
http://home.twcny.rr.com/scooper2/teracrack.pdf [rr.com]
Re:But... (Score:4, Informative)
Using the Blue Horizon supercomputer at the San Diego Supercomputer Center, we found that pre-computing the 207 Billion hashes for over 50 million passwords can be done in about 80 minutes. Further, this result shows that for about $10K anyone should be able to do the same in a few months time, using one uni-processor machine.
crypt() not necessarily the crypt algorithm (Score:4, Informative)
Re:A testament to crypt() (Score:1, Informative)
No idea what Linux uses but OpenBSD has used Blowfish for ages, those dang visionaries.
Re:But... (Score:2, Informative)
well, after the week it would take you to get the 20 $500 machines, install all the os's and clustering software and then write yr custom mpi app to do the cracking... you'd have lost the race already.
Perhaps not (Score:5, Informative)
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:Solaris (Score:5, Informative)
Re:Need better crypto (Score:5, Informative)
md5 strings are 32 characters. And most linux distros use md5 for their shadow files already.
Re:A testament to crypt() (Score:5, Informative)
Re:A testament to crypt() (Score:3, Informative)
The system merely stores a hash value of the password , when the user enters the password, the sytem generates the hash of the user entered password and compares it with stored hash value. If they match bingo, if not try again. Also the system progressively delays the next log-in prompt upon match failure to tackel, such a mass brute force attack.<P>
If I am not wrong these days, the password is stored in MD5 hash. And since hash value is theorotically irreversible, it can be stored in plain text. But I guess as an added safety measure, the linux boxes these days store passwords in
Re:Perhaps not (Score:2, Informative)
Re:A testament to crypt() (Score:1, Informative)
The point is you don't have to compute it anymore, just look up the hash in the database they just made, and find the matching password...
They are pointing out that just because the password is hashed, doesn't mean it is safe if you know the algorithm.
Re:Change of Methods Needed? (Score:4, Informative)
Re:The reality is (Score:3, Informative)
I believe that what you are refering to is called "distributed computing".
A good example of crypto-key cracking by distributed computing can be found here [distributed.net].
Re:Solaris (Score:5, Informative)
and System Administration Guide: Security Services [sun.com]
Re:Perhaps not (Score:3, Informative)
Just tried it on my Solaris box. I received the error "the domainname hasn't been set on this machine." A security flaw in NIS domains perhaps? That would certainly make the "insider" problem far worse.
Re:Getting there... (Score:5, Informative)
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:You missed the point (Score:4, Informative)
Because Sun guarantees that every piece of software ever written for Solaris will continue to work in new versions. Some would say that they're penalizing the rest of us for those few users still using 10 year old programs. And yet, there's something to be said for "working out of the box".
You're paying your Unix admins anyway. You might as well have them do something more useful than playing NeTrek all day while the system happily chugs along.
Re:triple crypt lie DES (Score:1, Informative)
This is a method that could be used to break any hashed passwords, but most modern hashes allow for more variation in their input values than crypt() does, making this (currently) unfeasible.
Aside from the fact that 3DES doesn't just run the same process three times (it uses two keys), this is not really comparable. The hashing algorithm was not directly attacked, so doing it multiple times wouldn't change anything. The passwords were still limited to 8 characters and the salts limited to 2. THAT's the weakness of crypt(), not the iterations.
(Okay, TECHNICALLY, you could hash it three times using two salts, and that WOULD increase difficulty--but not by enough to be safe foreven another week!)
Re:A testament to crypt() (Score:2, Informative)
It's official successor is AES, which is a 128/192/256 bit algorithm, which is thought to be very secure.
It's direct successor is triple DES, where you encrypt with one key, decrypt with another, and encrypt again with a third. This is probably what will take over if AES fails.
Re:So much for longer passwords being more secure? (Score:4, Informative)
Re:Still (Score:3, Informative)
A hash is a digest of a piece of data, as such there is more than one possible password for every password hash.
207 Billion hashes is a substantial portion of the possible hash values.
No offense meant to the parent poster, you can't know everything and I suppose this is more obscure than a lot of things, but I'm really really surprised this got modded up like it did.
Re:Change of Methods Needed? (Score:5, Informative)
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.
crypt(3) cracking. (Score:2, Informative)
If you are interested, you can take a look at a paper I wrote [stevens-tech.edu] (back in 1997) on the power of cracking with ten 200MHz Pentium Pro machines.
Re:Perhaps not (Score:3, Informative)
Not unless your actually not using shadow passwords at all...
'ypcat shadow' might do it but nobody with any ounce of sanity would put the shadow file on NIS. I use kerberos auth for the passwords and NIS for the rest of the stuff, which works fine... then again I'm behind a nice tight firewall.
Re:Perhaps not (Score:5, Informative)
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.
Re:A testament to crypt() (Score:5, Informative)
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.
Re:Cheating the Crypto? (Score:5, Informative)
The problem mentioned with crypt() is that the $salt value is very small (1.5 bytes), thus making dictionary attacks feasible. If MySQL is not using salt values, then they risk similar attacks.
Re:A testament to crypt() (Score:3, Informative)
The designers called it "Rijndael", NIST [nist.gov] gave it the name "AES".
Re:Still (Score:5, Informative)
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 =
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.
password reuse ... (Score:1, Informative)
Lab-Computer
1. Insert bootdisk
2. Reboot
3. cp
4. crack hash on a convenient machine
Even then, this wouldnt matter much if the password were unique to the machine.
However people are lazy and reuse passwords. (The recent Debian breach was very likely due to a reused password that was intercepted on another machine.)
So after getting the root password from this lab machine, I can go on and check if it does also work on the server I have no physical access to.
The solution is, of course, to never use the same password twice, or at the very least, to not use the same password on your servers and publicly accesscible lab machines.
However, I might not only retrieve root's password, but also user's passwords that might be reused on another machine. So, unless you can enforce non-reuse of all your user's passwords, you better protect them the best possible, even after root was compromised.
(BTW : I could install a password logger, so if you dont detect the compromise fast, protecting the hashes is useless.)
Re:Cheating the Crypto? (Score:2, Informative)
Assuming the hash itself can't be attacked (i.e. there's a weakness in the hash that lets you know when one password is "close" to another password), there's still a lot of ways to attack a hash.
The first is to run a dictionary attack on it. Solution: disallow dictionary words. The second is to look through all the hashes for multiple users with the same hash (thus the same password). Solution: incorporate the username into the salt so that two users with the same password have different hashes. Lastly, incorporate some "site identifier" in the hash so that the same username/password combo results in different hashes on different systems.
And the last thing is: don't let people get at your hashes. Treat them as if they were passwords.
Oh yeah--and none of this applies to crypt()--because your salt space is so limited, you can't put a username and site id in there. It's better (albeit still crappy) to just choose a random set of two characters and prepend it to the resulting hash. Which is what crypt() does.
Re:A testament to crypt() (Score:5, Informative)
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.
Naw, the EFF machines was later upgraded, and combined with distributed.net was able to crack a DES encoded message in 22 hours [eff.org]
Re:Solaris (Score:3, Informative)
I wonder if this functionality would make it feasible to use md5Crypt hashed passwords on a NIS network with Solaris 9 systems. md5Crypt and scalable blowfish (see the OpenBSD blowfish crypt paper [openbsd.com]) are designed so that you can identify the hash function used by looking for specific prefixes in the hashed text.
Obviously NIS should be dead and buried, but in far too many places it is not, yet. It would be nice if it were possible to use a more worthy hash function in conjunction with NIS.
I wrote the MD5 based crypt() for a reason... (Score:5, Informative)
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:A testament to crypt() (Score:4, Informative)
3DES is a kludge using the original DES in triplicate because alone it was too easy to brute force the keyspace.
Re:I wrote the MD5 based crypt() for a reason... (Score:3, Informative)
Details of the pluggable framework with a policy that allows for automigration on password change are available here: crypt.conf [sun.com] and policy.conf [sun.com]
Solaris source code is NOT needed to add new algorithms all code that uses crypt(3c) should continue to work. Code that changes passwords should use crypt_gensalt(3c) to create the salt.
Re:on OS X (Score:4, Informative)
In Panther (10.3+) it will not show the hashes, and I believe a different algorythm is used anyway.
In 10.3, the netinfo entries contain a reference to a file and this file contains the hashed password. Of course, the file is readable only by root. I was pretty vocal about this problem so I'm glad to see it fixed. Each user has their hash stored in a separate file, which I guess could be useful. At least it cuts down on pointless parsing.
The hash algorithm used is apparently MD5, but they don't store the hashes in the usual textual MD5 representation. I guess they really hate parsing.
Even more fun was if you used netinfo for network authentication, all hashes for all users on the network were available to the world, not just authenticated users. This meant you had to restrict access to your netinfo server to an IP range to avoid advertising your hashes to the Internet. Thankfully they started deprecating netinfo network authentication in 10.2, but this was recommended practice with 10.1 Server.
Re:A testament to crypt() (Score:3, Informative)
It should be irreversible, but by definition it must be "forwardable". I can take every possible password, hash it, and compare the result. If they match, I have figured out the password without reversing the hash function.
This was always possible by exploiting week passwords, but it is feasible to guess all alpha-numeric passwords (a-z,A-Z,0-9 total of 62 characters). An eight character password has 62^8 combinations, (218,340,105,584,896 approx 2.1 x 10^14). Now this is a large number, but do-able on PC hardware. Now there are no more then 256^8 possible values for an eight character password (18,446,744,073,709,551,616 approx 1.8 x 10^20). I don't know if this is do-able on a desktop (yet) but no matter how theoretically impossible it is to reverse a hash, it doesn't stop someone from throwing a dictionary (or a random number generator) at it.
Of course, almost all passwords out there don't contain non-printable characters, so if you a really trying to guess a password you would try more likely passwords first.
Re:interesting system integration issues (Score:5, Informative)
In standard crypt() format, the salt is the first two characters of the hash.
The canonical way hash a password using crypt():
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: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: 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:
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?]