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."
I wonder if this will spur Sunto finally make the default password encryption algorithm on Solaris something other than crypt...
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.
Trolling is a art,
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!
80 Minutes? Obviously we just are not using enough power.
30% Troll, 50% Underrated, 10% Interesting
Score:5, Troll
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
Mirrored here:
http://home.twcny.rr.com/scooper2/teracrack.pdf
- Sometimes you're the pidgeon, sometimes you're the statue.
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.
Remember that many glibc2 "overloads" crypt() to be able to deal with MD5 hashes. I wonder how many MD5 hashes they can generate...
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?
Clearly, crypt() was meant to die: just look at its name!
As Schneier says on the first page of Chapter 1 of "Applied Cryptography",
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?
HIV Crosses Species Barrier... into Muppets
MD5 is what most modern Linux distros use.
... no, I'm not gonna say it!
Fight hunger. Filet a politician and send him to a 3rd world country of your choice.
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?
Javascript + Nintendo DSi = DSiCade
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.
Why not do the same thing for crypt as was done for DES. DES became triple DES. just iterate it 3 times with different salts at each step. Unless there is something insecure about crypt itself, and the sandiego study does not say this, then this should foil any brute force attack like this for another hundered years.
Some drink at the fountain of knowledge. Others just gargle.
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 may be mistaken, but I thought crypt() used 56 bit DES encryption. They can brute-force 207e9 hashes per 80 minutes, but the total key space is about 72e15 (2^56).
This means that the key space will be exhausted in ((2^56/207e9)*80)/60/24/365.24 years, which is about 52 years.
I do agree that this is still a little too close for comfort. Fortunately no-one I know is still using classic crypt() for password protection.
I choose to remain celibate, like my father and his father before him.
thats how I read the subject too.
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.
Open Sesame..
for the last time people, I am "frodo from middle eaRTH", not "middle eaST".
Wait a year or three and this kind of computing power will be available in game consoles in bedrooms across america.
I've already rooted all your boxen and converted them to a worldwide Beowulf cluster.
Time to crack some pr0n passwords...
Heheh... the paper actually talks about them putting a searchable front-end to the results online but then says they decided not to, in part due to the "dreaded 'slash-dot' effect". Nice.
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.
when you have access to the brute. Sheesh!
The DEFAULT is still DES/crypt. Why not change it?
And now the important question,
are they storing it in MySQL or Postgres???
Moral of the story: Pick a good password.
Will it take for such a thing to be done with (put in your favorite encryption scheme). Dictionary attacks will become easier everyday because computing power and hard drive space are becoming more abundent. Is the answer just to move to a bigger set of prime number each time computing power get bigger or to move to a another type of encrytption scheme all together well only time will tell.
Get Movie Posters
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.
1 2 3 4 5 6. Dammit, they already hacked my password!
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.
Some drink at the fountain of knowledge. Others just gargle.
Confidential data being sent across the Internet should be looked at even more closely. Using an encryption method that is considered secure today may not be enough.
You may get lucky and not find anyone patient enough, but someone could very easily snoop the encrypted data, wait 5 (or 10) years, and crack the encryption scheme on his/her personal computer.
The tougher the encryption, the more time before they will be able to crack it. Eventually, however, it will be easily cracked. Just like anything else, there are pros and cons. You need to decide which encryption level will benefit you the most (processing power/time required to encrypt/decrypt VS amount of time before it's crackable).
If you are interested, you can take a look at a paper I wrote (back in 1997) on the power of cracking with ten 200MHz Pentium Pro machines.
I am going to go convert two of my physical binary decision devices into a cup of coffee.
Yes, yes, but where did he store them?
/greger
A quarter.
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.
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.
"Talk minus action equals nothing" - Joey Shithead, D.O.A.
"Talk minus action equals
So that's something on the order of 5 TB of data just to store the hashes? Ok, so we need about 5,000 volunteers to host a gig of the hash data each and a standard that addresses how to look up the host that holds each piece of the data just so we can search the system. Unless of course you know of someone willing to volunteer a system that can search through 5 TB of data in a reasonable timeframe. How many systems can even hold that much in memory?
Zombies, demons, cyrpt, etc.
Were all the original unix inventors Goths?
Not Goths, but if you had lived in Murray Hill, NJ at the time (the AT&T Getto) you might have wanted for this type of excitement!
This is just hearsay from a very recent OPEN-DOOR Washington meeting.
.... We have the keys to paradise. The ultimate knowledge that comes from having access to all knowledge is ours. Yippidy-dippidy-doodaa we control all the world now including the slums, sluts, and slackers of the Internet Kingdom. Now we get the needed Linus brain transplant half for John and half for Don (zombies need brains, dead men don't) should make US twice as smart". //GW//
"THANK Goad, PRAISE Ollie, GORY-B2 Yoho-Way,
Unaccountable leaders are masters, and unrepresented people are slaves. How do US and EU fare?
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!!!
- Adam L. Beberg - The Cosm Project - http://www.mithral.com/
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.
I have calculated the time it will take any of these guys behind this paper to pick up the hotest lady in any given bar at any given time. The results are astounding: infintite.
Its stories like this that remind us that Big Brother would chew through any encryption a user might have.
"Oh, 2048 bits? *yawn* We'll have the results for you in a month."
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.
Where were they when we started calling things "master" and "slave" ?
One of the libraries' uses was a project by a research guy there who aimed to store every possible combination of 8-character ASCII strings. I forget exactly how much storage space it took up, but it was quite a bit more than what you'd expect just from doing the numbers (they might have been storing metadata or something as well, I don't remember). Anyway, I do remember asking what they intended to do with the data: They wanted to use these to compute password hashes so they could crack passwords in near real-time. It looks like they finally got around to do it.
I haven't yet read their paper so I don't know if they used this data or not, but I'd believe them if they say they've computed all the crypt()-able hashes. Hopefully they'll put up a search interface so you can break your own password. They've got the computing horsepower to spare...
-B
Ash and Hickory, straight-grained and true, make excellent bludgeons, dandy for the cudgeling of vegetarians.
A 1.7 GHz celeron blows doors off an E10K.
And it's like 1% the cost, too!
mirror of pdf
0 GOTO 10
Karma: It's all a bunch of tree-huggin' hippy crap!
It becomes relevant if the attacker has (limited) physical access to your machine.
: ... ... /etc/shadow on bootdisk
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.)
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
Why don't we just build the gigantic reverse lookup table into a P2P network? I mean, we already have a mechanism for searching for hashes, the content of each of the 'files' could just be the original password used to generate the hash.
Karma: It's all a bunch of tree-huggin' hippy crap!
Looks like its the crypt for crypt() I couldn't resist, someone had to say it.
Damn! That must take more memory to store than the average slashdotter's mp3 and porn collections combined!
"Freedom means freedom for everybody" -- Dick Cheney
Maybe if they were running Gentoo it would have taken 60 minutes instead. :-)
Must've been. Look at the terminology for processes: parents have to wait for their children to die and then reap them, so they don't become zombies.
It's actually "daemon", not "demon", but that reminds me of a funny story. You know how when an email bounces, the returned message often comes from "mailer-daemon" at whatever domain your message was addressed to? Back when I was in high school, I once heard a teacher who was checking his mail exclaim, "mailer demon???", clearly thinking (at least until he read the text of the bounce message) that some sort of devilish creature was interfering with the delivery of his email.
Simply walk out the building with the entire mainframe!
Karma: It's all a bunch of tree-huggin' hippy crap!
We are bad@$$! I want a t-shirt that says, "I've been slashdotted." How much geek-cachet would that have? =)
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"
Poul-Henning Kamp -- FreeBSD since before it was called that...
You're lucky, to me the whole article was a bit cryptic.
Karma: It's all a bunch of tree-huggin' hippy crap!
The loop of the parent process will execute exactly once. It will execute one more time in the child, thereby making it a parent and terminating it too. How can you call that "as many children as possible"?
And what do you mean by "each program forks as many children as possible and then exits" ? When, "then"?
"Using SDSC's prodigious computing facilities, they precomputed 207 billion crypt() hashes in 80 minutes
and are now offering the results on DVD for only $19.99! Call now, operators are standing by!
-Adam
All slashdot members: 3. The reckless disruption or denial of services to any authorized user (Class 4 felony = 2.5 years/$150,000).
Practically this doesn't change anything. Crack was available for a long time, and any cracker who gets access to a password file has the time to run crack on it. If it takes a day or two usually doesn't matter at all. In the end a password is dead if crack can find it, otherwise not.
$ perl -le 'print crypt "SEEKETH.","1/"'
1/ChERhgHoo1o
$ perl -le 'print crypt '"'"'$'C4U1N3R"'"',"1/"'
1/ChERhgHoo1o
Can't they set up a torrent?
Someone bring me that file, I pay for the 300 DVD-Rs
+ shipping!
while (fork() || !fork())
As long as people continue to use easy to guess passwords and protocols like POP3 which send clear text passwords, it just doesn't matter what algorithm you use to encode or encrypt passwords. It's just another example of the screen door on the submarine with the really expensive titanium lock.
Mark my words boy, and mark them well "SECURITY IS AN ILLUSION!" When is the last time you changed your password?
Ahhh wh111o n333eeded cr5421ypt an%%yway?
Don't you understand how computers WORK?
-- 'The' Lord and Master Bitman On High, Master Of All
How to crack a (user) account with a 386SX machine in 5 minutes... :-)
Mail to: cluelessstudent@uni.edu
From (spoofed): sysadmin@uni.edu
Reply-to: (some obscure e-mail address - preferably not hotmail or yahoo, because of possible limitations on the degree of cluelessness of the target student)
Text: "Your account has been compromised. Ugly gruesome child porn trading, nuclear weapon smuggling, MP3 downloading, Al Qaeda financed Elbonian hackers have exploited the nfs system to remotely mount the storage device containing the shadow password file(BOFH DRONE MODE ON for a few lines). Please change your password to "12345678" AS SOON AS POSSIBLE. Failure to do so may result in widespread damage to the computers, exclusion from university, seven-digits fines, lifelong emprisonment and various kind of gory sexual diseases."
Plus details about how to change their password.
Obviously the problem with this attack is that it can not be used as a root exploit (well except maybe in some specific organizations...)
Technologies come and go. Social engineering remains. Never underestimate the power of Mighty Cluelessness.
(PDF, HTML version via Google).
..., then we know that there is at least one thing Google can't do.
If Google really cared they would fix Android Chrome to reflow text, instead of discriminating
I just had a thought.
Given the nature of hashes, where it is possible for more than one input to result in the same hash, wouldn't it be really annoying if my password of
'Th!$,1sA]T0&gh(Pa^S$WoRd~9' came to the same hash as 'secret'.
Are there any statistical or other methods which can be employed to determine the likelyhood of your strong
password matching a simple one>
Vs lbh pna ernq guvf, ybt bss abj. Tb bhgfvqr. Syl n xvgr.
Deliberate misspelling :)
Years ago someone told me that they spelled it daemon because the fundamentalists went nuts when they tried to spell it demon. No idea of the truth of that though.
Unfortunately, it doesn't go online for about a month, and even then, you'll need a member password to view it online, but I imagine enough /. readers have access to ;login: to make it worthwhile to point this out.
Mencken had it right. So glad that's old news.