A paper by Kurt Hockenbury. Copyright 1997.
In this paper, the author examines brute force UNIX password cracking from the perspective of what resources a non-professional cracker could reasonably be expected to have. Estimations are made of cracker capabilities, and the strength of various passwords to resist attacks.
Password cracking has long been a traditional method of breaking into UNIX systems, with the content of /etc/passwd (or /etc/shadow) being the target of many system attacks. In this day of password sniffers and TCP-hijack attacks, password cracking may seem passe', but given the continued growth in machines' speed and interconnectedness, brute force cracking deserves another look.
Since 1975, UNIX passwords have been encrypted using crypt(3). crypt(3) uses the first 8 characters of a user's password as a key to encrypt a block of zeros using a modified DES encryption. The encryption is further permuted by the addition of a 12-bit random 'salt'.
Because the calculation that crypt(3) does is non-reversible, passwords can not be "decrypted". Instead, a key search is done; potential passwords are encrypted, and the result compared with the list of encrypted passwords. If a match is found, the password is known.
As time has progressed, three trends have made password guessing ever more attractive:
All of these taken together means that the casual cracker now has resources at his disposal that would be the envy of researchers a mere five years ago - yet the basic UNIX password algorithm has not changed in over 20 years. As might be suspected, this is a hazardous situation.
Add to this that vendors continue to ship systems with visible passwords (that is, a world readable "passwd" file that contains encrypted passwords) as the default, rather than protecting the encrypted password in a separate shadow file.
Unshadowed /etc/passwd:
root:fttKB/aG8LYqY:0:0:Super User:/root:/bin/sh
Shadowed /etc/passwd:
root:x:0:0:Super User:/root:/bin/sh
Read protected /etc/shadow for shadowed /etc/passwd:
root:fttKB/aG8LYqY:9955::::::-1
There are two distinct styles of password cracking to examine: the cracking of a single salted password, and the computation of the crypt(3) of a word for multiple salt values. The first would be used when trying to break a particular password (say /root/'s), the second when trying to break any available account in a password file.
Cracking a single password (or multiple passwords with the same salt) by encrypting a list of guesses is a far easier task than doing the same for all possible salts; 4096 times easier, to be precise.
Easier in this case means faster. With a single salt, each word in a guess list only needs to be encrypted once. Each additional salt linearly increases the amount of encryption to be done.
Playing the role of the amateur cracker, I downloaded two publicly available UNIX password cracking programs: "Crack", by Alec Muffett[ref 1], and "John the Ripper", by "Solar Designer"[ref 2].
Both compile easily under Linux[ref 3] on an Intel Pentium Pro 200, though it is worth noting both are portable, and John the Ripper includes pre-compiled DOS and Windows binaries.
Crack uses Eric Young's libdes[ref 4] for its crypt(3) function, a free set of portable DES routines available for general use.
John uses a crypt(3) based off of Crack V4.1's, but re-coded to include a x86 assembly optimizations. This makes John significantly faster than crack on x86 hardware - about twice as fast on Pentium systems (10155 vs 5043.69 crypts/second on a Pentium 133). Alec Muffett is apparently planning to add this fcrypt() routine into Crack5.1 [Muffett1997].
On a Pentium Pro 200 with 256k cache, John's generic routine actually runs faster than its x86 optimized version (13069 vs 10499 c/s) and is faster than Crack's libdes (11460 c/s) as well.
For my test network, I have been granted access to a small lab of 10 such Pentium Pro systems, during their idle times. [Unfortunately, the lab is still in the process of being set up at the time of this writing; my results are thus extrapolated from a single PPro system. This summer I should have full access to the lab on nights and weekends to fully run my calculations.]
I feel that access to 10 PPro machines or a dozen Pentium 166's is not beyond the reach of an amateur cracker. A small university computer lab, or even a small group of friend's machines could easily equal this computing power. Larger universities or businesses could have far more than this available overnight or weekends.
This gives use cracking power of roughly 130,000 crypts/second. Table 1 translates that into meaningful time estimates for passwords of length 5 to 8 characters, using the breakdown of password character set ranges established in [Morris1979] and [Feldmeier1989]. Longer passwords can be ignored, since crypt(3) will discard all but the first 8 characters of a password.
| # of characters | 26 lower case | 36 lower & numeric | 62 alpha & numeric | 95 printable | 128 ASCII |
|---|---|---|---|---|---|
| 5 | 92s | 7.8m | 118m | 16.6h | 73.5h |
| 6 | 40m | 4.7h | 121.4h | 65.6d | 391.6d |
| 7 | 17.2h | 167.5h | 313.6d | 17.1y | 137.3y |
| 8 | 18.6d | 251.2d | 53.3y | 1618y | 175.7c |
I suspect 200 hours would be within a cracker's capability. 200 hours is 8 1/3 days - a little longer than a week, but under a Saturday- to-following-Sunday, say during Christmas break at some businesses or Spring Break at a university.
At that level of attack, we can see that passwords of under 6 characters are quite vulnerable. I have marked the currently vulnerable range of passwords with pink, the possibly vulnerable with yellow, and the not-yet vulnerable with white.
The entries marked with in yellow are beyond my estimate of 200 hours, but if a cracker has access to a few more machines, or a bit more time they are within the realm of attack. In particular, 8-character, all lower case passwords are probably vulnerable, since the payoff is potentially large.
A smarter approach to choosing key guesses is to try words and permutations of words. Both Crack and John the Ripper include options to do this, and many word lists are available online[ref 5].
A word list consisting of English words, technical words, jargon, the Bible, the Koran, the works of Shakespeare and Homer, fable, names of musical groups, Colleges, countries, counties, movies, Star Trek, Monty Python, Lewis Carrol, cartoons, English names, Hindi names, biological terms, asteroid names, deities, and the CIA world factbook makes up a total of 807049 words. All these words can be checked in a mere 6.2 seconds for a single salt. Checking all variations on capitalization [password, Password, pAssword, ..., PASSWORd, PASSWORD] takes under half an hour. Reversed words [drowssap], words with embedded numbers [1passwor, p1asswor, pa1sswor, ...], are all also easily checkable, as are letter -> number mappings [pa55w0rd].
The rule is simple: if a password is a word, any word (even proper names), it is no good. Variations on words are also no good. All-numeric passwords are even worse than all-lowercase, so phone numbers, SSN, ID numbers, and the like are bad password choices as well.
John also includes a character frequency table to improve the odds of brute-forcing a password.
Another method of brute force attack involves pre-computing a list of guesses. This requires a separate calculation for each of the 4096 possible salt values, and a large amount of storage space. For example, the above 807049 word file would require a little over seven hours to pre-compute.
The advantage here is that the computation only has to be done once, up front. After that, password cracking can take place as fast as it takes to read and compare stored passwords.
For my experiments, I downloaded a program called "QCrack" [ref 6] written by "The Crypt Keeper". QCrack consists of two main parts: qinit, which is used to build an initial hash table from a word list, and qcrack, to lookup encrypted passwords in this file.
Using qinit with a 45,402 word /usr/dict/words file took under four hours to build the hash file on a single PPro 200; splitting the load to 10 machines reduces the time to build to 23 minutes. It also took 180MB of disk space.
Once the hash file has been built however, qcrack can be run against a password file. On a single PPro 200, running against 5128 passwords took 256 seconds, doing effectively over 890,000 c/s! The tradeoff is obvious: pre-computation time and storage space in exchange for tremendously fast cracking.
Utilizing all 10 PPro's for 200 hours would allow the pre-computation of 22,851,562 words, but would take 88 Gigabytes of storage. 88 GBs of long term storage is probably beyond the amateur cracker at the present time; 4 GBs most likely is not. 4 GBs of storage would allow for a 1 million word list to be pre-computed.
One million words would let me add 21 "rules" to my 45,402 word /usr/dict/words file, such as the ones mentioned under single salt cracking (reversal, etc.), or allow me to encrypt my 807,049 word mega dictionary. Either way, such a pre-computed dictionary would be likely to get me some passwords in a password file of any significant size, and do so quickly. (As a comparison, the simple 45,402 word pre-computed hash file produced 10 passwords in 70 seconds against a live 626 entry password file.)
As mentioned in the Introduction, machines and algorithm have been getting faster. A single PPro 200 (a fast but not unreasonable home computer) is over 10 times faster at crypt(3) than a Sun SPARCStation of 8 years ago [Feldmeier1989] (a powerful workstation of the time). It is not unreasonable to imagine a home computer 10 times faster than a PPro 200 being available five years from now. Such a computer could do all of the above calculations by itself, without having to involve a network of computers.
But it would be unreasonable to assume that such a computer would exist in isolation; the explosive growth in networking, especially that of the Internet, shows no sign of slowing yet. With the push for wiring the home coming from several directions (ISDN, cable modems, ADSL, etc.), one would assume that a majority of computers in the future will be interconnected (the exceptions being those that are purposely not connected for reasons of security).
This means it is quite possible the cracker of the future will have access to perhaps 100's rather than 10's of machines. Unlikely? Consider a cleverly written Java program embedded in a popular set of web pages. The machine gets tens of thousands of hits an hour, and each time, in addition to the content the person is looking for, sends a small program to run and check some part of the key space. The program only runs when the machine is otherwise idle, and runs for at most one minute.
Such a system is almost possible now. A java applet has already been written to factor a PGP-key, and a call has gone out for volunteers to visit the web page and download it [Bugtraq1997].
Alternately, code to do idle-time cracking could be embedded into a popular Internet-capable game such as Quake. Such a game would then be released as freeware or shareware to try and build up a user base.
This approach is basically "The Chinese Lottery" style of cracking, as described in [Schneier1996], whereby a key-search device is built into a mass-produced product. The Government then broadcasts the problem it wishes to solve, conducting a massive parallel search. The difference here is that it is being done in software over the Internet rather than hardware embedded in TVs and radios.
Of course, I'd suspect the ideal place to insert a idle-cycle-sucker is into a web browser. The web is extremely popular, and a browser-based lottery system would have a number of advantages:
Indeed, were I the U.S. Government or a large corporation, I'd consider talking to Netscape and Microsoft to see if there's a way I could take advantage of all that available CPU power. While it is likely the U.S. Government has hardware based machines that can break crypt(3) in hours or less[Leong1991], surely some problems could benefit from being split across many thousands of machines.
Something like this could not be done covertly; sooner or later, it would leak, or someone would notice it, and there would be a large brouhaha. If it were done openly, there would be some negative reactions ["You want to use *MY* cpu?"], but if one were to make the software free and offer incentives such as a lottery jackpot, this could be overcome.
In fact, even if the government can't or won't do this, I wouldn't be surprised if private industry does. Surely some large company would be willing to spend a few million in lottery prize money in return for access to potentially billions of dollars of hardware. In fact, Netscape or Microsoft could do this and try and re-sell the CPU time to interested clients.
But all this is getting beyond the scope of this paper.
Visible crypt(3) is near-dead now, and will be completely dead shortly. Two orders of magnitude increase in cracking speed (likely available in another 5 years) will make all but 8-character 95-printable and 128-ASCII characters breakable.
Increases in storage space will make even larger pre-computed dictionaries possible, and faster retrieval times will make lookups faster as well. I expect that anything I can crack as single-salt now will be lookup-able within 10 years. Hopefully though, no one will be using crypt(3) passwords by then.
As far as a company or government is concerned, crypt(3) is already dead. The above estimates are for the capabilities of an individual or small group. All the software I used is easily available, and runs on the common IBM PC clone.
Yet vendors are still using visible crypt(3) passwords by default. While most vendors now have in place mechanisms to shadow passwords, the system administrator must enable them. Many sites still rely on NIS (YP) for password sharing - which also allows users to get the list of encrypted password [and likely others as well: NIS maps are often not well protected].
Proactive password checkers have been recommended before, and remain a good idea. Yet no vendor I know of is shipping their OS with one.
Finally, there is the crypt(3) algorithm itself. It is far too fast and is getting faster, and it is too small, with only the first eight characters being significant.
What sort of replacement should be made? To quote Steve Bellovin,
"How should a password algorithm be designed today? I'd use iterated, salted, locally-parameterized SHA or MD5. For the local parameterization, I'd prepend and append a system-specific string to the user's password. [...] I'd use an iteration count stored with the hashed password, as explained above; a nice feature of using MD5 or SHA is that the administrator can unilaterally strengthen all local passwords." [Bellovin1995]
To this I'll add a suspicion I've had that while one should be adding a random salt to a password, the salt should be thrown away, rather than stored. The computer should be required to check all possible salts at login.
The only major drawback I can see to throwing away salts is that the hash algorithm must not have many collisions for different salt/password combinations, or the potential of a false positive arises.
The advantage is that now all salts must be tried, even for a single password. I would also consider storing the size of the salt with the hashed password, so that that could be tweaked as well.
"In practice, physical security of the computer, communications security of the communications link, and physical control of the computer itself loom as far more important issues." [Morris1979]. While this is still true, the weakness of crypt(3) and the need for a replacement can no longer be ignored.
[Muffett1997] "My last word on the "John" question", Alec Muffett,
comp.security.unix, 1997/01/17, Message-Id:
<m3n2u8b59x.fsf@crypto.dircon.co.uk>
[Morris1979] Unix Password Security, Robert H. Morris and Ken Thompson,
Communications of the ACM, November 1979.
[Feldmeier1989] Unix Password Security---Ten Years Later, David C. Feldmeier
and Philip R. Karn, Proceedings of {CRYPTO} '89.
[Bugtraq1997] "PGP Distributed Attack", Aleph One <aleph1@DFW.NET>
http://paranoia.stardot.com/
[Schneier1996] Applied Cryptography, 2nd Ed., Bruce Schneier, p. 156
[Leong1991] Unix Password Encryption Considered Insecure, Philip Leong and
Chris Tham, Proc. Winter USENIX Conference 1991
[Bellovin1995] Re: Crypt for passwords, Steven Bellovin, comp.security.unix,
20 Apr 1995, Message-ID: <D7B600.4Fu@ulysses.homer.att.com>
[ref 1] Crack, http://www.users.dircon.co.uk/~crypto/
[ref 2] John the Ripper, http://www.false.com/security/john/
[ref 3] Linux, http://www.linux.org/
[ref 4] Libdes, ftp://ftp.psy.uq.oz.au/pub/Crypto/DES/libdes-x.xx.tar.gz
[ref 5] Word lists, ftp://ftp.ox.ac.uk/pub/wordlists/
[ref 6] QCrack, ftp://chaos.infospace.com/pub/qcrack/qcrack-1.02.tar.gz