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."
There are lots of alternatives to crypt, but none that are as simple and straightforward to use as it. What is needed is an unbreakable crypto scheme that is simple to use.
I have been pwned because my
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.
For a book called Applied Cryptography. Perhaps he should have called it Applied Cipherology. Applied Ciphering? Applied Cipherography? I think ill just stick with "crypt", thanks.
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.
Passwords limited to 8 characters. Salts limited to 2 characters. Not exactly a lot of combinations to complicate the brute-force attack now, are there?
The moral to this story is: SHA-1.
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.
The DEFAULT is still DES/crypt. Why not change it?
Are crypt() secret keys limited to certain characters?
If so, change it.
If not, 8 bytes = 64 bits = 2^64 keys = 18.4 quintillion
270 billion in 80 minutes means 18.4 quintillion keys would take 14,296 years.
Pardon me if I don't quake in my boots yet.
Yes, yes, but where did he store them?
/greger
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
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.
bash-2.05b$ md5 -t ... done
:) This computer is also running X, mozilla, a few rxvt+ssh terms, and gaim.
8 171200/8
MD5 time trial. Digesting 100000 10000-byte blocks
Digest = 766a2bb5d24bddae466c572bcabca3ee
Time = 18.865835 seconds
Speed = 53005869.601767 bytes/second
So for that sake of this argument, you have a 10,000 character password, and I have a 500 mhz P3 running FreeBSD 5.
If my math checks out below, in 80 minutes you can do 25 million 10,000 character passwords. I assume you have 8bit bytes, and one byte is one char. If you use the raw speed measurment, then you get 31,803,521,400 8 character passwords. I know that the "raw speed" isn't accurate as there is setup and teardown time involved in any measurement.
My G4-400 running OS 10.3 went at 23 seconds for the same time trial.
bc 1.06
80*60/19
252
252*100000
25200000
80*60
4800
4800*53005869
254428171200
25442
31803521400
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.
A symmetric key is twice as hard to brute-force for every bit you add. Nobody "brute-forces" asymmetric (public) keys by trying all possible keys; rather, they try to reverse the mathematical process used to construct the public key from the private one. In the case of RSA, this is multiplication, so you have to factor a number. Currently, the fastest public method to do this is the Multiple Polynomial Number Field Sieve; to make something twice as hard with this, you have to add something like 0.3 to the cube root of the number of bits.
RSA keys (and elliptic curves, and DH keys) are much more likely to be severely weakened by improvements in mathematics than say Blowfish or Rijndael keys. If someone improves the method to reduce the constant in the exponent of the NFS (which would probably be extremely difficult), the 1024-bit RSA key could fall easily; otherwise, even Moore's law gives it only a decade or so to live.
I hereby place the above post in the public domain.
Based on the fact that we're somewhere around breaking RSA-576 and RC5-72. If we assume proportionality:
576 (asymmetric) / 72 (symmetric) = 8
1024 (asymmetric) / x (symmetric) = 8 => x=128
So I'm guessing it's about 2^(128-72) = ~10^16 times safer. Which should be enough for a while too, but not quite that long.
Kjella
Live today, because you never know what tomorrow brings
Phil Zimmermann says this about MD5:
"The message digest algorithm used by older versions of PGP is the MD5 Message Digest Algorithm, placed in the public domain by RSA Data Security, Inc.
MD5 is a 128-bit hash algorithm. In 1996, MD5 was all but broken by a German cryptographer, Hans Dobbertin. Although MD5 was not completely broken at that time, it was discovered to have such serious weaknesses that no one should keep using it to generate signatures. Further work in this area might completely break it, allowing signatures to be forged.
If you don't want to someday find your PGP digital signature on a forged confession, you might be well advised to migrate to the new PGP DSS keys as your preferred method for making digital signatures, because DSS uses SHA as its secure hash algorithm." [page 234 of the pdf which comes with PGP 6.5.1. int]
However, according to the article you posted:
Therefore, while it is not military grade encryption, it is still good enough for some purposes. It will not protect you from a government or a corporation (if it so happens that they are interested enough in you commit the necessary resources), but it will probably protect you from your next door neighbor.
All data is speech. All speech is Free.