- Campuses :
- Twin Cities
- Crookston
- Duluth
- Morris
- Rochester
- Other Locations
Introduction
The Algorithms
Brute-Force Attacks
Dictionary Attacks
Brute-Force Attacks Against Network Services
Combined Attacks
Rainbow Tables
Passwords vs. Passphrases
Parallelization
Wrapup and Additional Thoughts
Raw Benchmark Output
When I talk about search space below, I'm referring to all possible passwords given the character set limitations and the algorithms involved. As most departments at the University of Minnesota use US-style keyboards, my write-up assumes the standard 95 characters found on that style of keyboard. (Yes, some systems can use extended characters, but I believe the majority of users don't use them. Also, they're not universally available on all OSes.) I use "Enn" to represent scientific notation, as large numbers tend to get somewhat cumbersome at times. As this is an original work, I claim all the mistakes made below; let me know if (when!) you find one.
Consider the number of possible seven character passwords made exclusively from letters, i.e., no numbers or symbols. For a case-insensitive algorithm (like LANMAN) this means there's a total of 26 possible values for each character position in the password. Here's how a case-insensitive algorithm's search space compares to one for a case-sensitive algorithm:
| Number of possible characters | Number of possible seven character passwords |
|---|---|
| 26 | 267 (8,031,810,176 or about 8.031E9) |
| 52 | 527 (1,028,071,702,528 or about 1.028E12) |
All other factors being equal, the doubling of possible values in the character set translates into a search space increase of a couple orders of magnitude, which translates into up to a couple orders of magnitude in delay before a password can be discovered through a pure brute-force attack.
So, assuming that LANMAN can use every character on the keyboard (and I'm not completely sure that it can), this means it has a character set of 69 possible characters.
| Count | Class |
|---|---|
| 26 | all letters (upper and lower combined) |
| 10 | digits |
| 10 | shifted symbols from digit keys |
| 22 | remaining symbols and their shifted counterparts |
| 1 | space |
|
|
|
| 69 | total |
Case-sensitive algorithms (e.g., the password hashing algorithm on most Unix variants, and MSFT's NTLM) give us an additional 26 characters per position, or a character set of 95 possibilities.
To calculate the total number of possible passwords for a given algorithm, you add the total number of passwords for each valid password length (or at least each valid password length for the password space you're searching). LANMAN's maximum effective password length is seven characters (more on this in a bit) for a total search space of 7,555,858,447,479 possible passwords (about 7.556E12).
| # characters in password | Number of possible passwords |
|---|---|
| 1 | 69 (691) |
| 2 | 4,761 (692) |
| 3 | 328,509 (693) |
| 4 | 22,667,121 (694) |
| 5 | 1,564,031,349 (695) |
| 6 | 107,918,163,081 (696) |
| 7 | 7,446,353,252,589 (697) |
|
|
|
| 7,555,858,447,479 total | |
A case-sensitive algorithm would give us an additional 26 characters, for a total of 95. With the larger character set (but sticking with the seven character password limit for the moment), the total search space is 70,576,641,626,495 possibilities (about 7.058E13).
| # characters in password | Number of possible passwords |
|---|---|
| 1 | 95 (951) |
| 2 | 9,025 (952) |
| 3 | 857,375 (953) |
| 4 | 81,450,625 (954) |
| 5 | 7,737,809,375 (955) |
| 6 | 7,350,918,906,25 (956) |
| 7 | 69,833,729,609,375 (957) |
|
|
|
| 70,576,641,626,495 total | |
An algorithm that's case-sensitive has a password search space about nine times larger than LANMAN's.
A second problem with LANMAN is that it's effectively limited to only seven characters. This is a well-known design issue whose details are somewhat out of scope here, but suffice to say that LANMAN can accept passwords up to 14 characters in length and treats any values in the eighth through fourteenth character position as a second, completely independent password (characters beyond the 14th are ignored). For example, given a password of nine characters, LANMAN hashes the password's first seven characters and stores the result, then hashes the remaining two characters and stores them as well.
When attacking LANMAN, an attacker can immediately tell which accounts have seven characters or less because they will all share the same value for the second half of the password. While it's true that passwords of 8-14 characters effectively require examination of two separate hash values, this is a relatively cheap operation and not one which has great impact on speed (as we'll see below).
This occasionally leads people to ask, "aside from limitations in the password hashing algorithm (like those in LANMAN), does adding an eighth character really make that much of a difference?" The short answer: absolutely! If LANMAN could actually hash eight character passwords (as opposed to the effective seven character limit imposed by its design), its total search space would be noticeably larger, as shown here.
| # characters in password | Number of possible passwords |
|---|---|
| 1 | 69 (691) |
| 2 | 4,761 (692) |
| 3 | 328,509 (693) |
| 4 | 22,667,121 (694) |
| 5 | 1,564,031,349 (695) |
| 6 | 107,918,163,081 (696) |
| 7 | 7,446,353,252,589 (697) |
| 8 | 513,798,374,428,641 (698) |
|
|
|
| 521,354,232,876,120 total (or about 5.214E14) |
|
5.214E14 really is larger than 7.556E12. The additional character increases total search space by about a factor of about 69, a notable difference. Case sensitivity becomes even more important when you use algorithms capable of handling passwords with more than seven characters.
| # characters in password | Number of possible passwords |
|---|---|
| 1 | 95 (951) |
| 2 | 9,025 (952) |
| 3 | 857,375 (953) |
| 4 | 81,450,625 (954) |
| 5 | 7,737,809,375 (955) |
| 6 | 7,350,918,906,25 (956) |
| 7 | 69,833,729,609,375 (957) |
| 8 | 6,634,204,312,890,625 (958) |
|
|
|
| 6,704,038,042,500,000 total (or about 6.704E15) |
|
Modern password hashing algorithms can use more than eight characters, so the search space involved rapidly becomes—to put it mildly—VERY LARGE. However, even comparing the old Unix crypt() algorithm (which accepted case-sensitive passwords up to eight characters long) is hugely better than LANMAN.
One of the characteristics of strong authentication algorithms is that they're computationally expensive. The idea is that a few iterations through the algorithm won't be painfully slow, but trying to iterate through them a large number of times (like when someone's grinding through a dictionary) is supposed to take a while. LANMAN's third weakness is that it's computationally cheap, at least compared with other password hashing algorithms. Here are some password calculation rates for several algorithms as implemented in John the Ripper (a well known password "cracker") on a low-end Athlon64 and a 3.2GHz Xeon. Note that this instance of John has been patched to be able to handle "NT MD4" (NTLM):
| "crypts/sec" | ||
|---|---|---|
| Hashing algorithm | Athlon64 2800+ | 3.2GHz Xeon |
| DES, one salt | 569,313 | 319,960 |
| FreeBSD MD5 | 4,079 | 8,950 |
| OpenBSD Blowfish | 292 | 448 |
| NT MD4 (NTLM) | 1,101,000 | 991,817 |
| NT LM DES (LANMAN | 5,180,000 | 4,524,000 |
DES (the old Unix crypt() function) is only a tenth as fast as LANMAN (remembering that this is one area where speed is BAD). OpenBSD's Blowfish-based hashing algorithm gets the tortoise prize; its computational expense makes it a very unappetizing target for brute-force attacks. These rates will be used in the sections on attacks below.
Finally, LANMAN uses no salt, which is an essentially random value tossed into the computational mix when generating a password hash. The idea behind using a salt is it perturbs the output of the hash function, making it much more difficult to simply compare hashes to determine if passwords are identical. For example, the value "testing" hashes as "jyOCKiECE7Q" when using the salt "Hf" and hashes as "joVBHOq2SNk" when using the salt "3R". So, if two users happen to pick the same password, an algorithm that uses salts will make it harder for an attacker to detect that.
It also means that an attacker has to calculate a hash for each salt belonging to a target account. If there are ten accounts (each with a different salt) that an attacker is interested in, then the workload required just increased by an order of magnitude. LANMAN, unfortunately, lacks this feature; a maximum of one computation per possible password value is all that's required.
Note that none of these are cryptographic weaknesses in the sense that LANMAN hashes have been found to be reversible. Indeed, such a discovery would be big news. It's also why I've tried hard to steer clear of describing this process as password "cracking." A more accurate description for the process is "password guessing."
We've already determined the total number of possible passwords with LANMAN is something like 7.556E12. We also know that an Athlon64 can chew through these possibilities at a rate of around 5.180E6/second. A rough estimate puts the time needed to chew through all the possibilities (using the Athlon64 benchmarked above) in about 1.5E6 seconds. A possibly more accurate estimate is:
(7,555,858,447,479 passwords) / (5,180,000 passwords/sec) = 1458660 seconds
That's somewhat under 17 days to grind through all possible passwords given LANMAN's available search space. However, since the odds are that an attacker will guess your password within the first half of all possibilities (assuming a completely random search, even distribution, etc.), the halflife (about eight days) is a better number to use for planning a password's usable lifetime.
Here's how LANMAN stacks up against the old Unix crypt() function and NTLM, using the timings and password spaces shown above (and limiting the other algorithms to a maximum of eight characters, even if they might be able to use more):
| Algorithm | Size of password space | Halflife length in seconds |
|---|---|---|
| LANMAN | 7.556E12 | 1.459E6 (~8 days) |
| NTLM | 6.704E15 | 3.045E9 (~95 years) |
| crypt() | 6.704E15 | 5.888E9 (~185 years) |
| *FreeBSD MD5 | 6.704E15 | 7.491E11 (>11,000 years) |
| * - This algorithm ran much faster on the Xeon, so I cheated and used it instead of the Athlon64. | ||
Most users change their passwords often enough that crypt(), even though it's definitely showing its age, still provides quite a bit of protection against brute-force attacks. It's also pretty clear that a smaller password search space plays a BIG role in successful attacks.
The search space for dictionary attacks can be built in a variety of ways. Most attackers (including me) will grab word lists for a variety of languages and topics (English, Vietnamese, German, Star Trek and Tolkien words, technical jargon, etc.). Other things tossed in a targeted word list would probably include usernames relevant to the site being attacked (if known). This list may seem large but, for the purposes of password guessing, it really isn't.
I don't know exactly how many words there are in the English language, but I've seen collegiate dictionaries claiming to contain 100K words. Let's assume, for the purposes of discussion, that a word list used for an attack will contain words from other languages, and will have a base size of FIVE MILLION words. This gives us enough room to possibly add in artificially generated "words" like dates ("2005/11/14" as an example), as well as a wide variety of other words not normally found in dictionaries, e.g., proper names, technical jargon, and terms from fictional literature.
Many users pick passwords that are based on dictionary words, but won't appear on a list I've described. However, the variations usually follow fairly simple rules, e.g., replace "s" with "$," spell the word backwards. While not all variations apply to all words (for example, entries without an "s" won't use the s/$ substitution), let's say we'll try up to a thousand of these variations per word on average. This leaves us with a five billion word search space. While this sounds large, the time needed to search it is relatively small.
| Algorithm | Time needed to try entire dictionary |
|---|---|
| LANMAN | 965 seconds (about 16 minutes) |
| NTLM | 4,541 seconds (about 1.25 hours) |
| crypt() | 8,783 seconds (under 2.5 hours) |
| FreeBSD MD5 | 1,225,791 seconds (under 15 days) |
| Note: These are all based on the Athlon64's benchmarks | |
Because the search space starts out targeting words and includes variations on those words, it is likely to catch passwords like "na1ra7nemHs!lb4tse$id" ("disestablishmentarian" spelled backwards with some common letter substitutions), even though such a word is considerably longer than the typical seven or eight characters a regular user might use. Also, because users tend to use the same password for multiple systems, passwords that have been guessed for one system tend to find their way into dictionary lists more often. More sophisticated attackers will tend to order their dictionaries in such a way that frequently discovered passwords are used first. They may also tailor their dictionaries to more closely match their target, e.g., placing words like "golden" and "gophers" near the top of a password list when attacking the University of Minnesota.
While attacking services, e.g., doing a brute-force SSH attack, an attacker has to contend with the fact that account names aren't necessarily known. However, if the attacker is attempting to break into a single, known account, this isn't a factor.
When attacking a single account, the timing of brute-force attacks against services is calculated very much like brute-force or dictionary attacks described above. Instead of a "crypts/second" rate, you have "connections/second." For example, suppose an attacker is attempting to brute-force the "root" account on a Unix system. I personally think 10 connections/second is a fairly high rate, but let's suppose the attacker is targeting a system that can handle a rate ten times higher. Over eight hours, the attacker would be able to try 2,880,000 possible passwords for that single account. In terms of dictionary attacks, this is a relatively small dictionary (but a huge number of SSH connection attempts!).
In an attack targeting multiple accounts, the attacker has to spread effort over those accounts. For a finite number of connections, this means the list of possible passwords is approximately equal to the total number of connections divided by the number of accounts being probed. Continuing with the SSH example above, let's assume the attacker is going after five accounts on the target system: root, httpd, operator, admin, and administrator (ones I've seen commonly used in attacks in the wild). Assuming that all words in the password dictionary are being tested for each account, that means that the password dictionary can't be larger than 576000 words.
This is an extreme example. As of this writing (November, 2005), most hosts would exhibit some sign of stress if attempting to handle SSH connections at the rate used in this example. Then there's the fact that 100 connections/second would tend to represent a sizeable portion of the number of SSH connections normally being established at the University of Minnesota.
A more sophisticated attacker may also use attacks against one service to improve the odds of success in another attack, even if the first set of attacks aren't successful. Consider an attack against a service where the host responds differently when a username/password pair for a non-existent username is used vs. when a bad password is used with an existing username. A sophisticated attacker aware of these timing differences may use the difference in timing to enumerate usernames, then use that refined list of usernames for a more carefully targeted attack against a different service.
Both of these styles of attacks have been repeatedly observed in the wild.
| characters in password |
number of dictionary entries |
bytes per entries |
total bytes |
|---|---|---|---|
| 1 | 69 | 2 | 138 |
| 2 | 4,761 | 3 | 14,283 |
| 3 | 328,509 | 4 | 1,314,036 |
| 4 | 22,667,121 | 5 | 113,335,605 |
| 5 | 1,564,031,349 | 6 | 9,384,188,094 |
| 6 | 107,918,163,081 | 7 | 755,427,141,567 |
| 7 | 7,446,353,252,589 | 8 | 59,570,826,020,712 |
|
|
|||
| 60,335,752,014,435 (about 56,200GB) |
|||
Limiting search space certainly helps; a table of LANMAN hashes for passwords with only letters and numbers comes out to around 600GB. In comparison to a Rainbow table for an algorithm like crypt(), which can use up to eight characters, LANMAN's table is pitifully small; crypt()'s table would occupy about 55,000 terabytes! Note that it may be possible to reduce the amount of space used by such a list through data compression, but this will have an effect on speed. (The actual effect is also a bit out of scope, as quantifying it would require detailed analysis of possible compression methods, which is also out of scope. Suffice to say that compression may reduce storage needs at the expense of speed.)
Computational expense is also something that must be considered. While LANMAN is relatively cheap in terms of computational cost, other commonly used password hashing algorithms aren't. This becomes more important when trading speed for space, as hinted at above; whatever compression may be used will have a performance cost greater than zero.
So, while storage is definitely getting cheaper and making these attacks more feasible than they were in the past, I think this sort of thing is also not too much of a threat, at least where sites that don't use LANMAN are concerned (and assuming your potential adversaries don't include nations or other entities with vastly superior resources than your own). The longer your password/passphrase, the larger the possible password space. I believe that, combined with making routine password changes (thus making your password a moving target), will continue to make other avenues of attack (social engineering, for example) much more lucrative than attacks directly on reusable passwords.
This isn't a new attack, but it's become more feasible as storage has gotten faster and cheaper.
1) Passphrases must contain six words. 2) Words must be taken from an approved, widely published list of 2048 words. 3) Words may be repeated in the passphrase. 4) Words may NOT be altered (i.e., they must appear exactly as they do on the approved list). 5) The six words must be separated by exactly one space. 6) The words MUST use ONLY capital letters.
At first glance this sounds like it'd be easy to attack. After all, the length is well known, the possible words are published, and no variance is allowed. Since passphrase are known to contain exactly six items, this is essentially the same as a fixed-length, six character password... except that the character set in this case is 2048 "characters" for a total of 20486 possibilities (that's 73,786,976,294,838,206,464, or 7.378E19), considerably more possibilities than all possible 1-8 character passwords that can be generated using a standard keyboard.
For those that are curious, the rules listed above are derived from one-time passwords used by OPIE ("One-time Passwords in Everything"), a system derived from Bellcore's S/Key and available on a wide variety of operating systems. It's in use on some of the systems I manage.
Parallelization can also help during some brute-force attacks on services. Consider a large computer lab where accounts are shared across all systems. An attacker with multiple hosts can split username/password guessing across all the lab targets. Not only might this shorten the time needed for such an attack, but it might also make it less noticeable to the (legitimate) users or administrators of the lab.
Most modern systems work with passwords much longer than eight characters and also accept more than just alphanumeric characters. Because of the constant danger of service attacks (of particular importance to a largely open network like the University of Minnesota, but important wherever network services requiring authentication are used), I think it's pretty clear that use of longer, complex passwords is a reasonable requirement. Since they are demonstrably harder to attack via brute-force, I think the use of passphrases (especially if they include uncommon words, punctuation, and other oddities) is probably the way to go for single-factor authentication for the foreseeable future.
I'm not sure a grammatically correct passphrase is a good idea for the long run, though. I think the next generation of attacks in this style will be against passphrases, but will include software that has some grammatical awareness. This is a bit far-fetched now, but computerized tools for processing natural language continue to improve.
One thing that does stand out to me when I look at the numbers above is the sheer lunacy in attempting an SSH-based attack against an institution that universally practices good password selection. SSH attacks are resource intensive (for the attacker and the victim), and they're slow. I don't believe anyone who's using strong passwords (i.e, ones that aren't likely to fall to a dictionary attack) would suffer a system break-in through an SSH brute-force attack. (Note that a vulnerability in SSH itself is another matter so, as a side note, make sure you've got support for SSHv1 completely disabled.)
Anyway, I think my numbers are correct. If not, I'd appreciate corrections.
Instead, these are the benchmarks for a pair of machines I maintain and that are common enough that the typical attacker will probably have access to similar equipment. No doubt the numbers will vary somewhat if you do your own tests.
Basic descriptions of the hosts and sample benchmark output are provided below.
| CPU | OS | Software | |
|---|---|---|---|
| Host #1 | Athlon64 2800+ | FreeBSD 5.4-RELEASE-p8 (amd64) | John the Ripper v1.6.39 (with NTLM hash support patch) |
| Host #2 | 3.2GHz Xeon | FreeBSD 5.4-RELEASE-p8 (i386) |
% john -testBenchmarking: Traditional DES [64/64 BS]... DONEMany salts: 617793 c/s real, 621368 c/s virtualOnly one salt: 569313 c/s real, 572959 c/s virtualBenchmarking: BSDI DES (x725) [64/64 BS]... DONEMany salts: 18570 c/s real, 18715 c/s virtualOnly one salt: 18387 c/s real, 18488 c/s virtualBenchmarking: FreeBSD MD5 [32/64 X2]... DONERaw: 4079 c/s real, 4099 c/s virtualBenchmarking: OpenBSD Blowfish (x32) [32/64]... DONERaw: 292 c/s real, 294 c/s virtualBenchmarking: Kerberos AFS DES [48/64 4K]... DONEShort: 251313 c/s real, 252733 c/s virtualLong: 695386 c/s real, 702667 c/s virtualBenchmarking: NT LM DES [64/64 BS]... DONERaw: 5180K c/s real, 5199K c/s virtualBenchmarking: NT MD4 [TridgeMD4]... DONERaw: 1101K c/s real, 1110K c/s virtual
% john -testBenchmarking: Traditional DES [24/32 4K]... DONEMany salts: 348569 c/s real, 349115 c/s virtualOnly one salt: 319960 c/s real, 320962 c/s virtualBenchmarking: BSDI DES (x725) [24/32 4K]... DONEMany salts: 12336 c/s real, 12355 c/s virtualOnly one salt: 12033 c/s real, 12052 c/s virtualBenchmarking: FreeBSD MD5 [32/32]... DONERaw: 8950 c/s real, 8978 c/s virtualBenchmarking: OpenBSD Blowfish (x32) [32/32]... DONERaw: 448 c/s real, 448 c/s virtualBenchmarking: Kerberos AFS DES [24/32 4K]... DONEShort: 304537 c/s real, 305014 c/s virtualLong: 689099 c/s real, 692339 c/s virtualBenchmarking: NT LM DES [32/32 BS]... DONERaw: 4524K c/s real, 4545K c/s virtualBenchmarking: NT MD4 [TridgeMD4]... DONERaw: 991817 c/s real, 993369 c/s virtual