Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?
Security Encryption

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."
This discussion has been archived. No new comments can be posted.

The Death Throes of crypt()

Comments Filter:
  • Solaris (Score:5, Insightful)

    by CrankyFool ( 680025 ) on Monday December 08, 2003 @03:52PM (#7661686)
    I wonder if this will spur Sunto finally make the default password encryption algorithm on Solaris something other than crypt...
    • Perhaps not (Score:5, Informative)

      by AKAImBatman ( 238306 ) <{akaimbatman} {at} {gmail.com}> on Monday December 08, 2003 @04:08PM (#7661823) Homepage Journal
      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 (Score:2, Informative)

        by Anonymous Coward
        Shadow passwords work sometimes. Sometimes you can just do "ypcat -k passwd" and get the hashes anyway.
        • Re:Perhaps not (Score:3, Informative)

          by AKAImBatman ( 238306 )
          Sometimes you can just do "ypcat -k passwd" and get the hashes anyway.

          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:Perhaps not (Score:3, Informative)

          by Tony Hoyle ( 11698 )
          Sometimes you can just do "ypcat -k passwd" and get the hashes anyway.

          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.
        • on OS X (Score:4, Interesting)

          by VValdo ( 10446 ) on Monday December 08, 2003 @04:57PM (#7662306)
          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.

          • Re:on OS X (Score:4, Informative)

            by Permission Denied ( 551645 ) on Monday December 08, 2003 @09:00PM (#7664550) Journal
            nidump passwd .

            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:Perhaps not (Score:5, Informative)

        by Ancil ( 622971 ) on Monday December 08, 2003 @04:58PM (#7662318)
        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.

    • Re:Solaris (Score:5, Informative)

      by hackstraw ( 262471 ) * on Monday December 08, 2003 @04:09PM (#7661826)
      Solaris uses PAM, so its trivial to add any kind of authentication method that you want.
    • Re:Solaris (Score:5, Informative)

      by FireDoctor ( 11071 ) on Monday December 08, 2003 @04:21PM (#7661961)
      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 [sun.com]

      and System Administration Guide: Security Services [sun.com]

      • Re:Solaris (Score:3, Informative)

        by jonabbey ( 2498 ) *

        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.

  • by grub ( 11606 ) <slashdot@grub.net> on Monday December 08, 2003 @03:53PM (#7661693) Homepage Journal

    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.
    • by Leffe ( 686621 ) on Monday December 08, 2003 @03:59PM (#7661735)
      Not many pieces of code will be able to boast that lifespan.


      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.
      • Depending on your distribution its either crypt or MD5 hashing. Most modern distributions give you a choice: MD5 hash for long password support and security, crypt for supporting legacy applications that don't use standard calls for checking the password in whatever format.
      • by Carnildo ( 712617 ) on Monday December 08, 2003 @04:10PM (#7661844) Homepage Journal
        DES is the Digital Encryption Standard. IIRC, it's a 56-bit symmetric-key encryption method, and is considered insecure, as a high-end desktop machine can crack anything encrypted with it in under 24 hours.
        • by Anonymous Coward on Monday December 08, 2003 @05:00PM (#7662343)
          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.
          • by Vellmont ( 569020 ) on Monday December 08, 2003 @06:57PM (#7663406) Homepage

            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]
            • by LuYu ( 519260 )

              However, according to the article you posted:

              1. it was not a single computer,

                ...a worldwide coalition of computer enthusiasts, worked with the Electronic Frontier Foundation's (EFF) "DES Cracker," a specially designed supercomputer, and a worldwide network of nearly 100,000 PCs on the Internet...

              2. it was not a "high-end desktop" (in response to Carnildo's post),

                ...the Electronic Frontier Foundation's (EFF) "DES Cracker," a specially designed supercomputer...

              3. the time where desktop computers pose
      • OK, I am making a calculate d guess here , but I may be wrong.<P>For any system that takes password inputs from users i.e. the password is entered from outside the system, It really doesn't need to store the password even in encrypted format.<P>
        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 progressive
        • by oh ( 68589 )

          OK, I am making a calculate d guess here , but I may be wrong.

          Your not wrong, just not all right

          If I am not wrong these days, the password is stored in MD5 hash. And since hash value is theoretically irreversible, it can be stored in plain text

          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 exploit

      • I've also got a question; What is the default/general password encryption scheme used in most GNU/Linux distributions?

        If I recall correctly, Debian defaults to MD5. The traditional way is offered as an alternative if you need it for compatibility.

      • by panaceaa ( 205396 ) on Monday December 08, 2003 @04:44PM (#7662166) Homepage Journal
        20 GOTO 10

        Haha! Now it's a denial of service algorithm! Bet you wish you had

        11 END

        now, eh?
    • I think this more shows that reliance on a password being hashed is a futile means of obscuring the source. If a password file is compromised, than it can easily be a short matter of time before it is cracked. The moral of the story, don't let your system be compromised, or at least not the security subsystem.
    • even though it took 30 years...how many haX0rs do you know that have machine capable of running TeraFLOPs per second?
      • 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.

      • by Mysticalfruit ( 533341 ) on Monday December 08, 2003 @04:12PM (#7661863) Homepage Journal
        Here's the more important question...

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

        Answer: Lots...
      • by jaredmauch ( 633928 ) <jared@puck.nether.net> on Monday December 08, 2003 @04:22PM (#7661970) Homepage
        lets see, if ms-sql(slammer) and w32.nachi were built to hide passwords and the crypt() result in their icmp messages, and provide a distributed database of this information, how hard would this be?

        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.

    • 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.
    • by hackstraw ( 262471 ) * on Monday December 08, 2003 @04:13PM (#7661873)
      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).
  • But... (Score:5, Funny)

    by jchawk ( 127686 ) on Monday December 08, 2003 @03:54PM (#7661704) Homepage Journal
    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:But... (Score:4, Informative)

      by UnderScan ( 470605 ) <jjp6893&netscape,net> on Monday December 08, 2003 @03:59PM (#7661736)
      Read the PDF. The first page tell us that:
      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.
      • for about 10k anyone should be able to do the same in a few months time, using one uniprocessor machine

        so how fast could they do it with 10 1k uniprocessor machines? or 20 $500 machines?

        partciularly with an easily segmented problem like this, the most likely 'wild' resource would be @home-ish.
        • Re:But... (Score:2, Informative)

          by Frymaster ( 171343 )
          so how fast could they do it with ... 20 $500 machines?

          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.

    • Re:But... (Score:3, Interesting)

      by LilJC ( 680315 )
      It's more than proof of concept. They did this in 80 minutes. Sure, you and I can't do it in 80 minutes, but even if it took us weeks we'd have a shot at cracking something that hadn't yet changed. Maybe not the first time, but eventually someone would get a start on it shortly after it been changed and considered "safe" long enough to be cracked.

      Besides, never underestimate the power of distributed computing by MS worms.

    • by morcheeba ( 260908 ) on Monday December 08, 2003 @04:04PM (#7661782) Journal
      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?
    • Wait a year or three and this kind of computing power will be available in game consoles in bedrooms across america.
  • by pvt_medic ( 715692 ) on Monday December 08, 2003 @03:54PM (#7661706)
    80 Minutes? Obviously we just are not using enough power.
  • by Erioll ( 229536 ) on Monday December 08, 2003 @03:56PM (#7661725)

    In the wake of stories like this, and yesterday's story about RSA-576 being cracked (here [slashdot.org]), 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.


    • 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?
    • by gorilla ( 36491 ) on Monday December 08, 2003 @04:07PM (#7661815)
      Remember that every bit approximatly doubles the type to break it. RSA-1024 is about 10^134 times harder to break than RSA-576.
      • 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.

    • 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

    • by Anonymous Coward
      The real threat to cryptography as we know it is quantum computing. Barring attacks on the algorithms themselves, most algorithms in use today can easily be scaled to be unbreakable for the rest of the lifetime of this universe. By "normal" computers, that is. Quantum cryptography provides "perfectly" secure transmission of data, so quantum computing's detrimental effect on current cryptographic communication schemes isn't really problematic. The real problem lies in secure storage and digital signing. AFAI
    • by AnotherBlackHat ( 265897 ) on Monday December 08, 2003 @04:23PM (#7661984) Homepage

      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
  • Mirror. (Score:5, Informative)

    by themassiah ( 80330 ) <scooper@coopster.net> on Monday December 08, 2003 @03:57PM (#7661728) Homepage Journal
  • by jrexilius ( 520067 ) on Monday December 08, 2003 @03:59PM (#7661737) Homepage
    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.
  • by peyote ( 9579 ) <pcg-/.@ais.cx> on Monday December 08, 2003 @04:01PM (#7661753) Homepage
    Remember that many glibc2 "overloads" crypt() to be able to deal with MD5 hashes. I wonder how many MD5 hashes they can generate...
    • 340282366920938463463374607431768211456 is a rough guestimate [16^32] :-)
    • bash-2.05b$ md5 -t
      MD5 time trial. Digesting 100000 10000-byte blocks ... done
      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. :) This computer is also running X, mozilla, a few rxvt+ssh terms, and gaim.

      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
  • The reality is (Score:5, Insightful)

    by phorm ( 591458 ) on Monday December 08, 2003 @04:02PM (#7661765) Journal
    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:The reality is (Score:3, Informative)

      by MikeCapone ( 693319 )
      How many drones working P2P-style (you create these hashes, I'll create these ones) would it take to equal this supercomputer?

      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].
  • by Wyzard ( 110714 ) on Monday December 08, 2003 @04:03PM (#7661776) Homepage

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

    • Ironic advice (Score:2, Interesting)

      by baadfood ( 690464 )
      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.
  • by dbavirt ( 543160 ) on Monday December 08, 2003 @04:08PM (#7661824)

    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.

    • by coyote-san ( 38515 ) on Monday December 08, 2003 @07:34PM (#7663825)
      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.)
  • Still (Score:5, Interesting)

    by mugnyte ( 203225 ) * on Monday December 08, 2003 @04:10PM (#7661837) Journal
    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 (Score:3, Insightful)

      by Anonymous Coward
      There isn't a unique hash value for every possible password... that's the way hashes work.
    • Re:Still (Score:4, Interesting)

      by Detritus ( 11846 ) on Monday December 08, 2003 @04:26PM (#7662006) Homepage
      You're assuming that the passwords are random. They aren't. Even with rules like a password must include upper-case characters, numerals and punctuation, they are not even close to being random.
    • Re:Still (Score:3, Informative)

      What!?!?!? How did the parent get modded up so high? Are people that unaware of how hashes work?

      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:Still (Score:5, Informative)

        by ^MB^ ( 153039 ) on Monday December 08, 2003 @05:43PM (#7662742)
        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.


        *cipher text is refering to the initial 64 zeros cipher text used in the DES password encryption.
  • 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.

    • Re:Getting there... (Score:5, Informative)

      by tep-sdsc ( 218375 ) on Monday December 08, 2003 @04:28PM (#7662036)
      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 :-)

  • by doormat ( 63648 ) on Monday December 08, 2003 @04:16PM (#7661911) Homepage Journal
    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?
  • Too Late (Score:5, Funny)

    by sirReal.83. ( 671912 ) on Monday December 08, 2003 @04:18PM (#7661934) Homepage
    I've already rooted all your boxen and converted them to a worldwide Beowulf cluster.

    Time to crack some pr0n passwords...

  • by PxT ( 26449 ) on Monday December 08, 2003 @04:19PM (#7661938)
    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.
  • by vondo ( 303621 ) * on Monday December 08, 2003 @04:24PM (#7661986)
    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.

  • by dmccartney ( 528270 ) on Monday December 08, 2003 @04:40PM (#7662130) Homepage
    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.
  • Storage. (Score:3, Interesting)

    by Greger47 ( 516305 ) on Monday December 08, 2003 @04:41PM (#7662147)
    Using SDSC's prodigious computing facilities, they precomputed 207 billion crypt() hashes in 80 minutes.

    Yes, yes, but where did he store them?


  • by Isao ( 153092 ) on Monday December 08, 2003 @04:44PM (#7662170)
    A quarter.
  • Cheating the Crypto? (Score:3, Interesting)

    by suwain_2 ( 260792 ) on Monday December 08, 2003 @04:45PM (#7662175) Journal
    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.
    • by DukeyToo ( 681226 ) on Monday December 08, 2003 @05:28PM (#7662593) Homepage
      You're overlooking the random salt value, which is different on each machine, or even the same machine for different accounts. So, generally you would have a hash of "$salt-$password".

      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.
  • by i_r_sensitive ( 697893 ) on Monday December 08, 2003 @04:58PM (#7662315)
    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.

  • by Duncan3 ( 10537 ) on Monday December 08, 2003 @05:19PM (#7662522) Homepage
    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!!!
  • by sir_cello ( 634395 ) on Monday December 08, 2003 @05:20PM (#7662531)
    Not a new concept, but novel given the use of modern computing resources.

    I (and probably others, I claim no novelty, only an inventive step :-) wrote software in 1991/1992 to do this: unfortunately sun4 MP's and about a gigabyte of disk were the best we had.

    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 :-). The output was also stored in bitwise numerical order - matching divide/2 matching very fast.

    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 :-).
  • Crypt was in "games" (Score:3, Interesting)

    by twenex ( 139462 ) on Monday December 08, 2003 @05:27PM (#7662582)
    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.
    • by raytracer ( 51035 ) on Monday December 08, 2003 @07:57PM (#7664049)
      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.

      That's because the two items (crypt(1) and crypt(3)) utilize entirely different algorithms. The crypt(3) library is of course your everyday average DES, which as this thread notes, has gotten a bit long in the tooth. The crypt(1) command however was an entirely different algorithm based upon the idea of a rotor machine. It only has a single rotor however, which makes cracking it pretty darned easy, probably _way_ simpler than the original German 3 rotor enigma machine. The implementation that is still distributed in FreeBSD (/usr/src/usr.bin/enigma) is from the Crypt Breaker's Workbench, a near automated cracking utility for this code.

      Cracking ordinary DES isn't a game quite yet, but it's certainly not the best choice for a password scheme.

  • by phkamp ( 524380 ) on Monday December 08, 2003 @07:48PM (#7663982) Homepage
    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" :-)

    • Yes Solaris does have it. When I integrated it into Solaris (along with help from Alec Muffett & Casper Dik) we made it a pluggable framework by building on the data format you created - thank-you for having the foresight to use the $ char as a "magic" switch.

      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

Loose bits sink chips.