Weaponizing Dictionaries and Other Hacker Tricks Quite often an attacker succeeds in obtaining encrypted passwords or password “fingerprints” (which I will discuss more fully later) from a system. If the hack has not been detected, the interloper may have days or even weeks to attempt to derive the actual passwords.
To understand the subtle processes exploited in such cases, take another look at the possibility space. When I spoke earlier of bit size and password space (or entropy), I implicitly assumed that the user consistently chooses passwords at random. But typically the choice is not random: people tend to select a password they can remember (locomotive) rather than an arbitrary string of characters (xdichqewax).
This practice poses a serious problem for security because it makes passwords vulnerable to so-called dictionary attacks. Lists of commonly used passwords have been collected and classified according to how frequently they are used. Attackers attempt to crack passwords by going through these lists systematically. This method works remarkably well because, in the absence of specific constraints, people naturally choose simple words, surnames, first names and short sentences, which considerably limits the possibilities. In other words, the nonrandom selection of passwords essentially reduces possibility space, which decreases the average number of attempts needed to uncover a password.
Below are the first 25 entries in one of these password dictionaries, listed in order, starting with the most common one. (I took the examples from a database of five million passwords that was leaked in 2017 and analyzed by SplashData.)
1. 123456 2. password 3. 12345678 4. qwerty 5. 12345 6. 123456789 7. letmein 8. 1234567 9. football 10. iloveyou 11. admin 12. welcome 13. monkey 14. login 15. abc123 16. starwars 17. 123123 18. dragon 19. passw0rd 20. master 21. hello 22. freedom 23. whatever 24. qazwsx
If you use password or iloveyou, you are not as clever as you thought! Of course, lists differ according to the country where they are collected and the Web sites involved; they also vary over time.
For four-digit passwords (for example, the PIN code of SIM cards on smartphones), the results are even less imaginative. In 2013, based on a collection of 3.4 million passwords each containing four digits, the DataGenetics Web site reported that the most commonly used four-digit sequence (representing 11 percent of choices) was 1234, followed by 1111 (6 percent) and 0000 (2 percent). The least-used four-digit password was 8068. Careful, though, this ranking may no longer be true now that the result has been published. The 8068 choice appeared only 25 times among the 3.4-million four-digit sequences in the database, which is much less than the 340 uses that would have occurred if each four-digit combination had been used with the same frequency. The first 20 series of four digits are: 1234; 1111; 0000; 1212; 7777; 1004; 2000; 4444; 2222; 6969; 9999; 3333; 5555; 6666; 1122; 1313; 8888; 4321; 2001; 1010.
Even without a password dictionary, using differences in frequency of letter use (or double letters) in a language makes it possible to plan an effective attack. Some attack methods also take into account that, to facilitate memorization, people may choose passwords that have a certain structure—such as A1=B2=C3, AwX2AwX2 or O0o.lli. (which I used for a long time)—or that are derived by combining several simple strings, such as password123 or johnABC0000. Exploiting such regularities makes it possible to for hackers to speed up detection.
As the main text explains, instead of storing clients’ passwords, Internet servers store the “fingerprints” of these passwords: sequences of characters that are derived from the passwords. In the event of an attack, the use of fingerprints can make it is very difficult, if not impossible, for hackers to use what they find.
The transformation is achieved by using algorithms known as cryptographic hash functions. These are meticulously developed processes that transform a data file, F, however long it may be, into a sequence, h(F), called a fingerprint of F. For example, the hash function SHA256 transforms the phrase “Nice weather” into:
(64 hexadecimal, or base 16, characters, which is equivalent to 256 bits)
Changing a single character in the file completely alters its fingerprint. For example, if the first character of Nice weather is changed to lowercase (nice weather), the hash SHA256 will generate another fingerprint:
You can do these calculations yourself and check them at or
Good hash functions produce fingerprints that are similar to those that would be obtained if the fingerprint sequence was uniformly chosen at random. In particular, for any possible random result (a sequence of 64 hexadecimal characters), it is impossible to find a data file F with this fingerprint in a reasonable amount of time.
There have been several generations of hash functions. The SHA0 and SHA1 generations are obsolete and are not recommended. The SHA2 generation, including SHA256, is considered secure.
The Take-Home for Consumers Taking all this into account, properly designed Web sites analyze the passwords proposed at the time of their creation and reject those that would be too easy to recover. It is irritating, but it’s for your own good.
The obvious conclusion for users is that they must choose their passwords randomly. Some software does provide a random password. Be aware, however, that such password-generating software may, deliberately or not, use a poor pseudo-random generator, in which case what it provides may be imperfect.
You can check whether any of your passwords has already been hacked by using a Web tool called Pwned Passwords (). Its database includes more than 500 million passwords obtained after various attacks.
I tried e=mc2e=mc2, which I liked and believed to be secure, and received an unsettling response: “This password has been seen 114 times before.” Additional attempts show that it is difficult to come up with easy-to-memorize passwords that the database does not know. For example, aaaaaa appeared 395,299 times; a1b2c3d4, 113,550 times; abcdcba, 378 times; abczyx, 186 times; acegi, 117 times; clinton, 18,869 times; bush, 3,291 times; obama, 2,391 times; trump, 859 times.
It is still possible to be original. The Web site did not recognize the following six passwords, for example: eyahaled (my name spelled backward); bizzzzard; meaudepace and modeuxpass (two puns on the French for “password”); abcdef2019; passwaurde. Now that I’ve tried them, I wonder if the database will add them when it next updates. In that case, I won’t use them.
Advice for Web Sites Web sites, too, follow various rules of thumb. The National Institute of Standards and Technology recently published a notice recommending the use of dictionaries to filter users’ password choices.
Among the rules that a good Web server designer absolutely must adhere to is, do not store plaintext lists of usernames and passwords on the computer used to operate the Web site.
The reason is obvious: hackers could access the computer containing this list, either because the site is poorly protected or because the system or processor contains a serious flaw unknown to anyone except the attackers (a so-called zero-day flaw), who can exploit it.
One alternative is to encrypt the passwords on the server: use a secret code that transforms them via an encryption key into what will appear to be random character sequences to anyone who does not possess the decryption key. This method works, but it has two disadvantages. First, it requires decrypting the stored password every time to compare it with the user’s entry, which is inconvenient. Second, and more seriously, the decryption necessary for this comparison requires storing the decryption key in the Web site computer’s memory. This key may therefore be detected by an attacker, which brings us back to the original problem.
A better way to store passwords is through what are called hash functions that produce “fingerprints.” For any data in a file—symbolized as F—a hash function generates a fingerprint. (The process is also called condensing or hashing.) The fingerprint—h(F)—is a fairly short word associated with F but produced in such a way that, in practice, it is impossible to deduce F from h(F). Hash functions are said to be one-way: getting from F to h(F) is easy; getting from h(F) to F is practically impossible. In addition, the hash functions used have the characteristic that even if it is possible for two data inputs, F and F', to have the same fingerprint (known as a collision), in practice for a given F, it is almost impossible to find an F' with a fingerprint identical to F.
Using such hash functions allows passwords to be securely stored on a computer. Instead of storing the list of paired usernames and passwords, the server stores only the list of username/fingerprint pairs.
When a user wishes to connect, the server will read the individual’s password, compute the fingerprint and determine whether it corresponds to the list of stored username/fingerprint pairs associated with that username. That maneuver frustrates hackers because even if they have managed to access the list, they will be unable to derive the users’ passwords, inasmuch as it is practically impossible to go from fingerprint to password. Nor can they generate another password with an identical fingerprint to fool the server because it is practically impossible to create collisions.
Still, no approach is foolproof, as is highlighted by frequent reports of the hacking of major sites. In 2016, for example, data from a billion accounts were stolen from Yahoo!
For added safety, a method known as salting is sometimes used to further impede hackers from exploiting stolen lists of username/fingerprint pairs. Salting is the addition of a unique random string of characters to each password. It ensures that even if two users employ the same password, the stored fingerprints will differ. The list on the server will contain three components for each user: username, fingerprint derived after salt was added to the password, and the salt itself. When the server checks the password entered by a user, it adds the salt, computes the fingerprint and compares the result with its database.
Even when user passwords are weak, this method considerably complicates the hacker’s work. Without salting, a hacker can compute all the fingerprints in a dictionary and see those in the stolen data; all the passwords in the hacker’s dictionary can be identified. With salting, for every salt used, the hacker must compute the salted fingerprints of all the passwords in the hacker’s dictionary. For a set of 1,000 users, this multiplies by 1,000 the computations required to use the hacker’s dictionary.
Survival of the Fittest It goes without saying that hackers have their own ways of fighting back. They face a dilemma, though: their simplest options either take a lot of computing power or a lot of memory. Often neither option is viable. There is, however, a compromise approach known as the rainbow table method (see “Rainbow Tables Help Hackers”).
In the age of the Internet, supercomputers and computer networks, the science of password setting and cracking continues to evolve—as does the relentless struggle between those who strive to protect passwords and those who are determined to steal, and potentially abuse, them.
Say you are a hacker looking to exploit data that you have acquired. These data consist of username/fingerprint pairs, and you know the hash function (see “Making Hash of Hackers”). The password is contained in the possibility space of strings of 12 lowercase letters, which corresponds to 56 bits of information and 2612 (9.54 x 1016) possible passwords.
At least two strong approaches are open to you:
Method 1. You scroll through the entire space of passwords. You calculate the fingerprint, h(P), for each password, checking to see whether it appears in the stolen data. You do not need a lot of memory, because prior results are deleted with each new attempt, although you do, of course, have to keep track of the possibilities that have been tested.
Scrolling through all the possible passwords in this way takes a long time. If your computer runs a billion tests per second, you will need 2612/(109 x 3,600 x 24) days (1,104 days), or about three years to complete the task. The feat is not impossible; if you happen to have a computer network of 1,000 machines, one day will suffice. It is not feasible, however, to repeat such a calculation every time you wish to test additional data, such as if you obtain a new set of username/fingerprint pairs. (Because you have not saved the results of your computations, you would need an additional 1,104 days to process the new information.)
Method 2. You say to yourself, “I’ll compute the fingerprints of all possible passwords, which will take time, and I’ll store the resulting fingerprints in a big table. Then I’ll have to find only a password fingerprint in the table to identify the corresponding password in the stolen data.”
You will need (9.54 x 1016) x (12 + 32) bytes of memory because the task requires 12 bytes for the password and 32 bytes for the fingerprint if the fingerprint contains 256 bits (assuming an SHA256 function). That’s 4.2 x 1018 bytes, or 4.2 million hard disks with a capacity of one terabyte.
This memory requirement is too large. Method 2 is no more feasible than method 1. Method 1 requires too many computations, and method 2 requires too much memory. Both cases are problematic: either each new password takes too long to compute, or precomputing all possibilities and storing all the results is too large a task.
Is there some compromise that requires less computing power than method 1 and less memory than required for method 2? Indeed, there is. In 1980 Martin Hellman of Stanford University suggested an approach that was improved in 2003 by Philippe Oechslin of the Swiss Federal Institute of Technology in Lausanne and further refined more recently by Gildas Avoine of the National Institute of Applied Sciences of Rennes (INSA Rennes) in France. It demands less computing power than method 1 in exchange for using a little more memory.
The Beauty of the Rainbow Here is how it works: First, we need a function R that transforms a fingerprint h(P) into a new password R(h(P)). One might, for instance, consider fingerprints as numbers written in the binary numeral system and consider passwords as numbers written in the K numeral system, where K is the number of allowable symbols for passwords. Then the function R converts data from the binary numeral system to the K numeral system. For every fingerprint h(P), it computes a new password R(h(P)).
Now, with this function R, we can precompute data tables called rainbow tables (so named perhaps because of the multicolored way these tables are depicted).
To generate a data point in this table, we start from a possible password P0, compute its fingerprint, h(P0) and then compute a new possible password R(h(P0)), which becomes P1. Next, we continue this process from P1. Without storing anything other than P0, we compute the sequence P1, P2,... until the fingerprint starts with 20 zeros; that fingerprint is designated h(Pn). Such a fingerprint occurs only once in about 1,000,000 fingerprints because the result of a hash function is similar to result of a uniform random draw, and 220 is roughly equal to 1,000,000. The password/fingerprint pair [P0, h(Pn)], containing the fingerprint that starts with 20 zeros is then stored in the table.
A very large number of pairs of this type are computed. Each password/fingerprint pair [P0, h(Pn)] represents the sequence of passwords P0, P1,… Pn and their fingerprints, but the table does not store those intermediate calculations. The table thus lists many password/fingerprint pairs and represents many more (the intermediates, such as P1 and P2, that can be derived from the listed pairs). But, of course, there may be gaps: some passwords may be absent from all the chains of calculations.
For a good database with almost no gaps, the memory needed to store the calculated pairs is a million times smaller than that needed for method 2, as described earlier. That is less than four one-terabyte hard disks. Easy. Also, as will be seen, using the table to derive passwords from stolen fingerprints is quite doable.
Let us see how the data stored on the hard disks makes it possible to determine a password in a given space in just a few seconds. Assume that there are no gaps; precomputation of the table takes into account all the passwords of a designated type—for example, 12-character passwords taken from the 26 letters of the alphabet.
A fingerprint f0 in a stolen data set can be used to reveal the associated password in the following way. Calculate h(R(f0)) to arrive at a new fingerprint, f1, then calculate h(R(f1)) to get f2, and so on, until you get to a fingerprint that begins with 20 zeros: fm. Then check the table to see which original password, P0, the fingerprint fm is associated with. Based on P0, calculate the passwords and fingerprints h1, h2,... that follow until you inevitably generate the original fingerprint f0, designated hk. The password you are looking for is the one that gave rise to hk—in other words, R(hk – 1), which is one step earlier in the chain of calculations.
The computation time required is what it takes to look for fm in the table plus the time needed to compute the sequence of fingerprints from the associated password (h1, h2,…, hk)—which is about a million times shorter than the time needed to compute the table itself. In other words, the time needed is quite reasonable.
Thus, doing a (very long) precomputation and storing only part of the results makes it possible to retrieve any password with a known fingerprint in a reasonable amount of time.
The sequences below represent separate chains of calculations leading from passwords (Mo, No,..., Qo) to fingerprints and other passwords, until the desired fingerprint (and thus the password that precedes it) pops out. (The long dotted line represents may other lines similar to the top two.)
To summarize, by knowing the beginning and end of each chain of computations (the only things that are stored during precomputation), a hacker can retrieve any password from a fingerprint. In somewhat simplistic terms, starting from a stolen fingerprint—call it fingerprint X—a hacker would apply the R and h functions repeatedly, calculating a series of passwords and fingerprints until reaching a fingerprint with 20 zeros in front of it. The hacker would then look up that final fingerprint in the table (Fingerprint C in the example below) and identify its corresponding password (Password C).
Sample Table Excerpt Password A—Fingerprint A Password B—Fingerprint B
Password C—Fingerprint C
Password D—fingerprint D Next, the hacker would apply the h and R functions again, beginning with the identified password, continuing on until one of the resulting fingerprints in the chain matches the stolen fingerprint:
Password C → fingerprint 1 → password 2-- → fingerprint 2 → password 3…. → password 22-- →fingerprint 23 [a match to fingerprint X!]
The match (fingerprint 23) would indicate that the previous password (password 22), from which the fingerprint was derived, is the one linked to the stolen fingerprint.
Many computations must be done to establish the first and last column of the rainbow table. By storing only the data in these two columns and by recomputing the chain, hackers can identify any password from its fingerprint.
A Cryptanalytic Time-Memory Trade-Off. Martin E. Hellman in IEEE Transactions on Information Theory, Vol. IT-26, No. 4, pages 401–406; July 1980.
Making a Faster Cryptanalytic Time-Memory Trade-off. Philippe Oechslin in Advances in Cryptology—CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17–21, 2003. Edited by Dan Boneh. Springer, 2003.
Characterization and Improvement of Time-Memory Trade-off Based on Perfect Tables. Gildas Avoine et al. in ACM Transactions on Information and System Security, Vol. 11, No. 4; Article No. 17; July 2008.
How to Handle Rainbow Tables with External Memory. Gildas Avoine et al. in Information Security and Privacy: 22nd Australasian Conference, ACISP 2017, Auckland, New Zealand, July 3–5, 2017, Proceedings, Part I. Edited by Josef Pieprzyk and Suriadi Suriadi. Springer International Publishing, 2017.
Digital Identity Guidelines. Paul A. Grassi et al. NIST Special Publication No. 800-63-3. National Institute of Standards and Technology, June 2017. (PDF)
Jean-Paul Delahaye is professor emeritus of computer science at the University of Lille in France and a researcher at the Center for Research in Computer Science, Signal and Automation of Lille (CRIStAL).
- How Airlines Decide What You’ll Eat and Drink On Board
- Things You Should Know Before Renting A Car & Driving In Morocco
- Bidding a Fond and Reluctant Farewell to the Itinerant Dirtbag Life
- Rick Steves: Edgy, artsy Glasgow is Scotland's most underrated destination
- How to Spend Your Time in Tokyo: A Suggested Itinerary for 2019
- The Mathematics of (Hacking) Passwords
- Seeing Inside the Israeli Ultra-Orthodox Community on the Netflix Series “Shtisel”
- Space Is Hard, Beresheet Israeli Lunar Crash Proves Again
- Physicists Scramble to Understand the Extreme Crystals Hiding Inside Giant, Alien Planets
- How Did Nearsighted People Manage Before Glasses Were Invented?
The Mathematics of (Hacking) Passwords