Passwords are the most common facet of security that we have control over. They are the beginning and end of our online lives, yet most people pay them no mind. Since the dawn of the web, password rules have been difficult, limiting, and confusing. That has forced us into poor habits when making and storing the most important line of defense we have against online criminals.
BASIC PASSWORD PROTECTION: HASHING
Storing passwords in plain text (i.e. human-readable, without encryption) is the poorest of practices. If security is breached in any manner, passwords have become less than useless—they are a liability. The solution is a one-way hash. This is the process of taking variable-length data (e.g. a password) and storing it as fixed-length data. It is the basis for modern cryptography. A one-way hash has two properties: the process should never be reversible (the password cannot be decrypted), and two different passwords will never have the same resulting hash. If either or both conditions can be proven true, that hashing process (algorithm) is broken.
In the real world, a website’s “forgot my password” function should create a temporary password, and then request a new one be created. If the original password is known and sent, passwords are not being encrypted properly, or at all. One of the original one-way hash functions was the Message-Digest algorithm, which includes the popular MD5. It was eventually replaced with the Secure Hash Algorithm. There have been several iterations in this family as well, becoming incrementally stronger: SHA-0, SHA-1, SHA-2 (made up of SHA256 and SHA512), and most recently, SHA-3. Both of these algorithms were designed to calculate hashes quickly, and with low overhead. Processes faster than brute force methods have developed to find collisions (duplicate hashes) within Message-Digest, SHA-0, and SHA-1, so they are now considered “broken”.
PASSWORDS ARE BROKEN
The brute force method of cracking passwords is the process of iteratively hashing all password combinations until a match is found within a list of passwords hashes (i.e. a stolen list). However, the difficulty of this is measured in exponential scale; it becomes computationally prohibitive after passwords reach five characters (depending on hardware), and after eight characters, even the most powerful computers hit the proverbial wall. Resourceful hackers were able to overcome the brute force limitation by using two different tools: rainbow tables and dictionary attacks. Despite its cheery name, rainbow tables include pre-calculated hash data, eliminating the need to calculate the hash of every possible password, and ultimately decreasing the amount of time and computing resources it takes to crack passwords. Testing for dictionary words also proved to be effective at finding passwords.
In 2009, the breach of one website saw 32 million passwords leaked to the internet. From that list, the dictionary words Password and princess were among the top ten passwords, appearing approximately 62 thousand and 35 thousand times, respectively. That domain only required five-character passwords and stored them in plain text. This negligence is compounded with the “first-day” password problem, which is the practice of using a default password (such as changeme) for all new accounts. The danger lies in that some people will never change this password, exposing not only their own account but others as well. It is also an example of a security hole that is completely preventable by the administrators and goes back to the ignorance or incompetence problem. In response to these threats, the salted password was introduced. The process is relatively simple, in that a string of unique characters is added to the password before it’s run through a hashing function. It was successful in rendering tables useless, and slowing down the dictionary and brute force attacks, because password hashes once again had to be calculated and compared one at a time. But salt was hardly a cure-all for password woes.
To authenticate a user, the salt is added to the provided password to get the final hash, thus the salt itself can never be encrypted. If the hacker has a list of the salts and hashes, it’s just a matter of incorporating the known salt into the brute force and dictionary attack algorithms. Unfortunately, salts are usually found stored alongside the hashes. Ultimately, they will only slow down the cracking process by multiple the number of unique salts in a given list. To be effective, the salts must follow the same rules as user passwords: randomized, of a certain length, and never reused. Naturally, this requires additional complexity and resources to implement. For a long time, the best way to beat the password crackers was to follow a strict ruleset for creating strong passwords: 8 characters, mixed-case letters, numbers, and symbols. Combined with salt, it was near impossible to break. But an unlikely piece of hardware has invalidated all of the old theories.
PUTTING THE VIDEO CARD TO WORK
In the past, testing password hashes was a function of the computer’s central processing unit or CPU. As graphics became more integral to the computer industry, those processes were moved to a dedicated chip on the video card called the graphics processing unit, or GPU. The GPU renders polygons: two-dimensional figures that when combined, make up a three-dimensional image. Better 3D images are made up of more numerous, smaller polygons, a result of having hundreds of “cores” calculating polygons in parallel. Without the overhead of managing the rest of the system, the GPU was perfectly suited to the task of a dedicated password cracker. The AMD Radeon 7970 graphics card is aimed at the consumer-level hardware enthusiast, selling for only a few hundred dollars. It is capable of calculating 4.8 billion MD5 hashes per second, or 2.2 billion SHA1 hashes per second. And those limitations exist only because the hash lists simply can not be fed to the GPU any quicker.
For passwords that can not be cracked with the classical methods described above, attackers have built machines with 8 to 25 GPUs for an increased number of cores. A 25 GPU cluster can churn out 180 billion MD5 hashes per second, 63 billion SHA1 hashes, and 350 billion NTLM hashes (Microsoft’s old cryptographic algorithm, mercifully retired some years ago). Stacking so many GPUs generates a lot of heat, so much so that it can damage equipment. To keep these monsters from overheating, owners go so far as to submerge them in mineral oil. The advantages rainbow tables once had is diminished as it’s now quicker to calculate hashes one at a time; salts are simply cracked through sheer brute force. Furthermore, holistic attack methods that were once too computationally complex are now feasible with the GPU. Password crackers stack multiple dictionary words (a combinator attack) and test for common expressions, phrases, or patterns. For example, the password qeadzcwrsfxv1331 is easily broken because it follows a pattern on the keyboard. Taking Back Security The path to fixing security lies with not only the systems’ designers but the individual as well. Both sides are responsible for combating poor practices and bad habits.
STRONGER HASHING ALGORITHMS
As mentioned earlier, the Message-Digest and Secure Hash algorithms were designed to be calculated quickly, and with low overhead. This makes them attractive to websites that have high traffic and usage; large amounts of users can be authenticated with no discernable lag. But this efficiency has also been their undoing: the speed advantage is exploited by password crackers, as evidenced by the billions of hashes able to be created every second. Thus, the old algorithms were no longer suitable for cryptography. What was needed were more computationally expensive algorithms, designed specifically for encrypting passwords, rather than data integrity checking. Three algorithms have become popular for meeting the demands of modern security: PBKDF2, bcrypt, and script. Their commonality is a concept known as the work factor. The work factor is a variable within the algorithm that allows for adjustments in its computational complexity. As the work factor is increased, the hashing will get slower, and the time an attacker must invest, per password, will increase.
Since the work factor is embedded in the result, the hashes generated are backward and forward-compatible (new versions can read old hashes and vice versa). The hurdle to overcome is the cost in implementing these functions. GPUs are used by attackers to crack passwords, so they could be used just as effectively for legitimate hashing. But servers (web, authentication, etc.) don’t come with GPU hardware—graphics are typically the domain of a personal computer. Implementing a solution on existing servers will undoubtedly carry a non-trivial cost. It may be a cost that website administrators and businesses are unwilling to incur. Properties of Strong Passwords With password cracking being as efficient as it is, it may seem impossible to come up with a perfect password. But it doesn’t have to be perfect, just good enough that it would deter an attacker. Combined with proper habits, it’s possible to keep your data safe and secure. The strength of a password can be measured in bits of entropy. Entropy is a lack of order or randomness, and that is the key to making a strong password. High entropy, lengthy passwords are resilient to dictionary, heuristic, and brute force attacks. There are several properties of a strong password: it needs to be over 9 characters long (but ideally 13-20), mixed-case letters with numbers and symbols, no words, phrases, or patterns, and no common symbol substitution. This ensures a password entropy of at least 50 bits.
A 50-bit password will take 250 (1 quadrillion) brute force attempts to try all possibilities (although on average it would be found in half that many attempts). But if a website is still employing MD5 or SHA1, that password will still be broken relatively quickly. It’s predicted that passwords reaching 65 to 70 bits will require systems that cost over $1 million, for the next few years, regardless of the algorithm used. So the bar for minimally safe passwords has been set. Since entropy is by definition, randomness, it’s impossible to define the exact number of bits of entropy a password has, but there are methods for approximating. Two examples include the liberal Rumkin and the more conservative zxcvbn. Both algorithms analyze the characteristics of a password; some of those methods are found in both, while others may be unique to one or the other. But these differences will result in different bits of measured entropy.
To be safest, always assume the lower number result is correct. Generating Secure Passwords Within the security field, there are competing methods and ideas for creating high entropy passwords. Some are more classical, as stated just above, in that they call for chaotically generated passwords, using numbers, mixed case alphabet, and special characters. Others advocate for simpler, longer passwords rather than shorter, complex passwords, for two reasons: there may not be enough good guessing data for longer passwords (due to the lack of long password requirements), and common long passwords are still less common than common short passwords.
The concept is simple: select a relatively long sentence that you know or can easily memorize, and turn it into a password. For example, the quick brown fox jumps over the lazy dog turn into TqbFoxjotlDog. Then it’s further strengthened with numbers and symbols: TqbF0x,jotlD0g!. The two number substitutions and two punctuation marks are relatively straightforward, aiding in memorization, and work out to be about 70 bits of entropy. This method is captured in Scheiner’s password generator app, Password Safe. To test the latter theory, one study provided people with multiple rule sets for creating a strong password, one which required 16 characters, and a second that required only 8 characters, but also different cases, numbers, letters, and symbols. Based on the results, people created higher entropy passwords under the first rule set (44.68 bits) versus the stricter second ruleset (34.30 bits). If in fact representative of a person’s predilection toward generating passwords, the longer, less complex method would be ideal for two reasons: people are inherently poor randomness generators, and complex passwords tend to be written down as they are easily forgotten.
The most difficult aspect of adopting secure practices is putting those practices into use. There are two roadblocks to fully realizing this goal: arbitrary restrictions on passwords, and memorization. Many websites still impose an eight-character limit, in the hope that people will create passwords with numbers, symbols, and mixed cases, and still be memoizable. However, this is in fact an impediment to that very goal as eight-letter password entropy is likely to be under 55 bits. Many sites also limit special characters (and potentially how many times they can be used) further weakening the resultant password. The issue of individual password memorization was addressed, but trying to remember unique passwords for all sites is near impossible. A possible solution is selecting a strong base password, and coupling it with a personal algorithm for customizing and adding to it based on the website where it’s used (e.g. adding the website URL somewhere in the password). But to make unique, truly random, highest-possible entropy passwords for the number of websites that require accounts these days, a password manager is the best option.