Chapter 5. Picking Locks: Password Attacks

IN THIS CHAPTER

Typical Password Mechanisms
Testing Password Security
Improving Password Security, and Alternatives to the Standard Password Mechanisms in Mac OS X

Passwords ”what an idea. Using a small word as a shared secret to identify the bearer. In the security world, one often hears of identifying oneself by either what you have, what you know, or what you are. A password is an attempt to prove identification through proving what you know, and passwords have been a standard at the gates to castles , the doors to clubs, and the prompts of computers for years . Unix passwords can be a bit more complex than spoken passwords, but the standard scheme limits them to 8 characters in length. When extended to upper and lower case, nonsense words and special characters, there are 6,634,204,312,890,625 passwords enterable from a Pismo PowerBook keyboard available for use in the standard Unix authentication scheme (that is, 95 possible keyboard characters in each of 8 positions ”95x95x95x95x95x95x95x95 = 6,634,204,312,890,625 possible passwords).

That's almost seven million billion possibilities ”sounds like a lot, right? Perhaps in the days when passwords were spoken, and the consequences of giving the wrong one at the castle gate was that someone took a swing at your head with an axe, seven million billion possibilities was a serious deterrent. Unfortunately, although we keep using the idea of passwords to identify ourselves , computers can make the act of testing passwords much faster, and much safer for an intruder. Initially, the Unix password authentication system was designed to make randomly testing passwords difficult. The algorithm was intentionally designed to be extremely slow, so that although the consequences of trying a password and getting it wrong might be less drastic, it still required a very long time to crack passwords by simple guessing. Unfortunately, it didn't take long for people to write faster versions. Now, a simple brute-force approach to password cracking can test anywhere from fifty thousand (G3, 450Mhz, our test results drawn from using John the Ripper on a Sage iMac DV+), to millions ( reported speeds on top-end P4 Intel boxes by ZDNet.com) of possibilities in less than a second. It still takes upwards of a half billion seconds (that's over ten years) to crack every possible password on a high-end desktop processor. But, as machines become more powerful, that time period inevitably will be reduced. In fact, if processor speed increases continue to track the trends that have been established over the last 20 years, in 5 or so years we'll be able to explore the entire password space with an investment of less than a single year of CPU time. More discouragingly, shorter passwords, or passwords chosen from a smaller character set or using predictable patterns can be guessed in a correspondingly shorter time period. Kurt Hockenbury estimated in 1997 that a 10-machine flock of then high-end Pentium Pro computers could crack every 8-character password composed of lowercase and numeric characters in just over half a year. By now, with both faster processors and faster algorithms available, that password space should fall easily with less than a month of processor time expended. http://attila.stevens-tech.edu/~khockenb/crypt3.html details his findings.

Of somewhat more concern, if someone really wants to break into your system, it doesn't take a top-secret government agency to bring mountains of computing power to bear on a problem. Like the SETI@home project, which linked spare CPU cycles on millions of users' computers together to scan deep space for signs of alien intelligence, today's crackers can harness the power of computers all over the Internet. Most recent computer viruses have been distributed via the Internet (predominantly through poorly designed email clients ), and have been designed to take over the targeted computer and give control of the "zombie" machine to a "master" system that can direct its actions over the Internet. The payload in the recent viruses has been software intended to knock other computers on the Net offline with denial of service attacks (see Chapter 9, "Everything Else"), but it could just as well be a password-cracking application. In one of the recent viral incidents, it is estimated that the Code Red worm (technically a worm, because the only action it takes on the user 's part is ignorance) managed to infect 360,000 machines within its first 14 hours of life (http://www. mcafee .com/aboutus/bus_dev/retail_users/newsletters/feb2002/classof2001.htm). If the payload had been a password cracker, that could have been 360,000 machines working simultaneously on cracking your password. Somehow, a year of CPU time doesn't sound like that much when it's spread over 360,000 machines. Actually, it comes out to something under a minute and a half.

To make matters worse , people don't naturally make use of anything resembling the entire password space. A statistician might express the randomness available in that 6.6 million billion possible password choices as saying that a password chosen from the space has approximately 53 bits of entropy . That is, 2 raised to the power 52.558844 6,634,204,312,890,625.

Using entropy in this fashion is a way of expressing the actual randomness in what is intended to be a random string. For example, if you know that your users have chosen passwords that are eight characters long, you might suppose that they've randomly chosen amongst the full 6.6 million billion possible passwords in the password space. If, in fact, your users have chosen passwords composed of only lowercase a and b characters, they would still be chosen from the full password space, but only out of a 256-member subset. In this case we would say that the users' passwords display 8 bits of entropy ( 2^8 = 256 ).

If the users enter any of the 128 characters in 7-bit ASCII, the result is 8-character passwords with 64 bits of entropy. Each character, having 95 possible choices, therefore has ~6.6 bits of entropy available, but it is quite common for less than that amount of entropy to show up in final password choices. The written English language, for example, because it tends to use certain characters more frequently than others, and certain character combinations much more frequently than others, appears to have roughly only 1.3 bits of entropy per character. ( Applied Cryptography: Protocols, Algorithms, and Source Code in C , by Bruce Schneier, covers Shannon's famous estimate, as well as other cryptographic statistics and plain old interesting theory and practice.) This means that if a user chooses, as many do, a dictionary word for their password, they've accumulated only some 10.4 bits of total entropy ”a much smaller amount of randomness (10.4 bits, assuming they used the full 8 characters available for the password, that is ”shorter passwords are logarithmically weaker). Because clever password-guessing software can make use of the predicted character-use patterns to search the most likely combinations first, a badly chosen password can reduce the problem of searching for passwords from one that takes several years to accomplish to one that takes only a fraction of a second. Put another way, to create a password that is as strong as one using 8 characters of completely random data, a password composed of English-language words would need to be over 40 characters in length ”a large fraction of the length of one of the lines of text in this book. Of course, any sentence -like structure in the password would significantly reduce the entropy available, again making it easier to guess.

Even people trying to be random don't produce particularly random results. Several studies have determined that strings of characters "randomly" chosen by people, aren't actually all that random, and the variability in each position does not approach the ~6.6 bits of available entropy. This most likely has to do with the unconscious associations we form with respect to letter patterns and usage in written language, and manifests itself in "randomly" chosen strings displaying significant word-like structure when constructed by a person.

This chapter covers the flaws in the basic notion of password protection for services, files, and other resources, as well as what you can do to limit your vulnerability when picking passwords. Not all password schemes will necessarily conform to the exact encryption or storage standards we'll cover here, but they're all subject to the same basic conceptual flaws.

Top