Passwords. The latchkeys of our digital lives. They are seemingly inescapable, yet also surprisingly ineffective at providing the security that forms the basis of our economic and personal activities.
Humans have used passwords for thousands of years. We first see them as watchwords, a secret code one gives to the watchguards in a military situation in order to authenticate yourself as a friendly. These were used in classical times, and even during World War 2. During the D-Day operation disparate airborne forces, some many miles from their intended zones, had to authenticate themselves to other groups of Allied forces on the ground. Hence they developed a password based authentication system, as seen below:
Guard’s Challenge: “Flash!”
Friendly’s Password: “Thunder!”
Guard’s Countersign: “Welcome!”
If any of these parts were missed, either side would know they were not dealing with a friendly, and possibly open fire.
Passwords also served a historic role in secret societies, authenticating yourself to people who you may have never met, such as in the Freemason signal of distress, “O Lord, My God, Is there no help for the Widow’s Son?” given by a Master Mason when his life is in danger to signal to all other Freemasons nearby that he is a Master Mason and demands their aid. However, even in contemporary times, these types of passwords failed for a number of reasons. When the membership of the group is not strictly controlled group passwords can be released and become public, making the authentication that the password is designed to accomplish fail completely. For instance, the secret codes and handshakes of Freemasonry were widely published in the 1800’s.
In the military context, there is the story of the 414 B.C.E. siege of the Syracusan city of Epipole by the Athenians. The Athenians were routed in part due to reliance on their watchword, which was quickly learned and used by their enemies. Thucydides records the rout as follows:
“the Athenians were seeking for one another, taking all in front of them for enemies, even although they might be some of their now flying friends; and by constantly asking for the watchword, which was their only means of recognition, not only caused great confusion among themselves by asking all at once, but also made it known to the enemy, whose own they did not so readily discover, as the Syracusans were victorious and not scattered, and thus less easily mistaken. The result was that if the Athenians fell in with a party of the enemy that was weaker than they, it escaped them through knowing their watchword; while if they themselves failed to answer they were put to the sword.”
These cases demonstrate some of the foibles of authentication using passwords. Of course, these problems are also present in our modern authentication systems. If a site like Rockyou is hacked, and the results are published online (in that case 32.6 million unencrypted email addresses and passwords) all the accounts are compromised. Moreover, due to the disastrously bad habit of password reuse across multiple sites, the impact spirals outwards onto many other sites. The Rockyou hack was especially broadly damaging because it provided attackers with a ready made dictionary of popular passwords for future use in dictionary attacks on other sites. Another hack with a similarly massive impact was the attack on Adobe, wherein 153 million 3DES encrypted passwords alongside unencrypted password hints were released. The inimitable comic xkcd does an excellent job of explaining the impact:
Above was shown the risk posed by publication of passwords. But what about modern Syracusan eavesdroppers? Keyloggers have become an almost ubiquitous tool in the surreptitious theft of login credentials and can take any number of forms, starting with cheap hardware sitting between the input device and the computing device, looking something like this:
More advanced versions of this idea are seen in the NSA’s ANT (Advanced Network Technology) catalog, with a keylogger that can be remotely illuminated by a radar system to receive back the keystrokes as they happen. There are also similar devices that act as a wireless bridge, built into the hardware of peripheral devices (keyboards/mice etc) to allow access even to systems which have been isolated from the internet for security reasons. There are also many types of software keyloggers, operating at different levels and possibly residing in various data storage locations in the computer, making removal very difficult.
One of the more ubiquitous (and tragically weak) password architectures is used by ATM systems. Journalist Brian Krebs has made a lot of progress tracking the physical keylogging and magnetic strip skimming devices used in this field of cybercrime, which vary widely between fake keypads, skimmers and hidden video cameras, capturing the card data and the insecure 4 digit numerical passwords used by these systems.
There is another common vulnerability in the password based authentication systems used today- the “Forgot your Password?” link next to every login box on the internet. These systems, and the ability to call in and have a password reset just by guessing a few personal details, have made the spread of breaches much easier (your email account being comprised lets an attacker also reset many of your other passwords). This is in response to most people not being able to remember long and complicated passwords, especially when those passwords are used rarely or saved in browsers, letting them pass from memory entirely.
Another related issue is the use of password keeping services. These have become a popular method of creating and storing long and complicated passwords for all of a user’s online accounts. One of the online services for this is LastPass. LastPass recently revealed that they have been hacked, and that the attackers gained an encrypted list of all master passwords used by users to access their password vaults. The breach also revealed unencrypted password hints and email addresses. While not as troubling as the Adobe or Rockyou breaches due to better use of cryptography and individual salts, this breach demonstrates the danger of trusting a single point of failure in a user’s password scheme.
The combination of these issues shows fundamental problems in how passwords are employed, and the tenuous grasp most users have on their security. One response to this problem is to use biometric identifiers in place of password systems. This approach is based on the idea that the biometric signs collected and verified by the system are unique to the user. The most prevalent biometric in use today is the fingerprint. Fingerprint biometric systems have been employed on the recent lines of the Iphone (5s and the 6 series) and on a number of other Apple products under a system which they call Touch ID. Biometric Identifiers have also been added to many national passports.
There are a few problems here, and for certain individuals the risk posed by reliance on biometrics is much greater than that posed by properly implemented password systems. Fingerprints are especially problematic in this regard. In 2008 a hacking collective called the Chaos Computer Club published the fingerprints of then German Interior Minister Wolfgang Schauble. The fingerprint was printed on a piece of plastic and distributed with the group’s magazine. The group apparently acquired his fingerprint from a glass of water he had used at a conference. In 2014 the group also published the fingerprint of the Defense Minister, Dr. von der Leyen. They acquired her fingerprint using photos they had taken of her thumb from 9 feet away using a standard camera. Previous to this, Starbug (the researcher who cloned the defense minister’s fingerprint), demonstrated a hack of Apple’s Touch ID less than 48 hours after the release of the Iphone 5s, the first product to carry it. Other systems of biometric identification such as voice detection and retinal scans can be similarly collected and faked, but at greater cost and effort and to start with are much more prone to false negatives. It is also worth noting here that while she was Secretary of State, Secretary Clinton sent a memo (later released by Wikileaks) asking State Department employees to gather biometric data on other world leaders and international diplomats.
Another method towards more secure authentication is the use of Two Factor Authentication (2FA). This is absolutely commendable and should be pursued. A more in-depth analysis of 2FA is somewhat outside of the scope of this essay, but should be engaged in, as there have been a number of cases in recent memory where poor implementation has defeated what is theoretically a superior system to the use of a password alone.
The conclusion that I have reached is that the best authentication solution lies in strong passwords, held in the only electronically inviolate space, memory. This is obviously not an easy task, but avoids many of the pitfalls of other systems. The problem then falls on the two component parts- what is a strong password, and how do we hold it in memory?
Strong Passwords
To address what a strong password is, it is absolutely necessary to begin from an attacker’s perspective. How are passwords attacked? In general there are three common methods (outside of direct theft through eavesdropping as covered earlier). These are: Brute Force attacks, Dictionary (and targeted dictionary) attacks, and Rainbow Table attacks. A brute force attack tries all possible characters for a given keyspace. This attack will always work. However, at longer password lengths it quickly becomes uneconomical or downright infeasible. At less than eight characters it is still entirely possible, as a password that is exactly eight characters long, including upper and lowercase a-z, numbers, and special characters/punctuation will only have 94^8 possibilities, or a total of around 6 quadrillion. Sure, this seems insane, but a brute force attack against even a number that astronomical is well within the capabilities of a dedicated and well resourced attacker. A four character password would only have 94^4 possibilities, or around 78 million. That is very much within the computation abilities of a smartphone or home computer to brute force within a reasonable timeframe. So to defeat the brute force attack, the key is to increase the length of the password. In this case, the attacker cannot usually assume a set password length, and so will try all 4 character passwords, then all five, all six and so on, which does add to the length of time necessary, but once the correct password is found the attack does not need to continue.
Dictionary attacks prey on an inherent weakness of users- the desire for simplicity. If choosing a six character password, an (english speaking) human is much more likely to pick kitten than they are to pick 1h4^B*. If we go by the Oxford dictionary, there are only around 170,000 words in current use. Even when accounting in the dictionary for permutations like k1tt3n or K!tt3N, etc, a dictionary attack will take much less time to find most human generated passwords than a brute force attack. To defeat the dictionary attack: do not use single words, or single words with permutations as a password. However, let’s assume the attacker somehow knows we are only using all lowercase words and no numbers or special characters in our password and can design their attack accordingly. At one word long, the attacker needs to try 170,000 possibilities. At two (randomly chosen) words, they will need to deal with 170k^2 or about 29 billion possibilities. At three words in the phrase they are looking at 4.9 quadrillion. At four words they are already dealing with 835 quintillion, a keyspace that is essentially outside of the capabilities of even governments for the time being. An even more math heavy discussion of keyspace can be found here.
A targeted dictionary attacks preys on known information about the target. A custom dictionary is built and populated with common passwords and words which may be related to the target. To defeat this, passwords should have nothing to do with the user choosing them. No children, spouse, or pet names, no streets, no favorite bands or sports teams, no bible verses or names, etc.
To understand the rainbow table attack it is necessary to backtrack somewhat and explain how passwords are actually used and attacked in our systems. When a user types in their password, unless the system has been designed in a very insecure way (cough cough, Rockyou), that password is not used directly for authentication. The password is put through a one way fuction, called a hash function. This hash function runs on the user password, and only the output of the function is passed to the authentication service. The service then compares this received hash to the one listed in the database for that user, and decides to allow access or deny it. So (kitten) goes into the (hashFunction) yielding (1ad7e0fc), which is then checked against the database. The process with look something like this, of course dependent on the actual hash function used:
Notice here that small changes in the input result in very different output values. The important thing with hash functions is that the value created from the hash function and the hash function itself cannot be reversed to easily find the original input password. Even if the database or traffic of hashes is compromised by an attacker, all they have is the hashes, not the passwords used to generate them. They still cannot log in and gain the access of a normal user or impersonate them (one caveat is pass the hash attacks). To gain access they have to run the hash function themselves, brute forcing or dictionary attacking to find either the plaintext password that creates the hash, or another plaintext password which creates the same hash (called a collision). The Rainbow Table is a way to do the brute force attack beforehand, and simply have a rapidly searchable database of all of the possible hashes and the plaintext password that creates them. When combined with faster data storage methods such as solid state drives, the necessary plaintext password can be found very quickly indeed just by looking up the hash value. Mitigating the Rainbow table requires the system architect to use a system called cryptographic salting. In this system a different random string of characters is added to each password in the hashing process. The salt does not change on individual passwords, but each entry in the database has a different one. This means that to do a Rainbow Table attack, a full brute force table would need to be generated for every possible salt as well. This very quickly becomes impractical for just about all attackers.
The take away from this section is that passwords should be long, not consist of just one or two words even with permutations, and not be related to the user in any meaningful way. If words or a phrase are used, the words should ideally be uncommon, and numbers and special characters should also be used. Additionally, system architects need to use salts with hash functions to prevent Rainbow Table attacks. Password reuse across multiple sites should also be avoided if at all possible.
Memorable Passwords
As seen above, some of the optimal attributes for computer passwords are things like a high degree of randomness and a large character set. This, however, will result in passwords that are difficult for human users to remember; leading to practices such as keeping passwords written down at one’s desk or reliance on a password keeper in the cloud or otherwise. To balance these competing interests users need to develop personal systems for creating passwords that are both strong and memorable.
The “Arts of Memory” as they are commonly understood were first put forward by ancient Greeks. One of the first methods in those arts, the “Method of Loci”, was invented by the poet Simonedes of Ceos, apocryphally after he stepped out of a dining hall moments before the hall collapsed and killed those inside. During the excavation Simonedes was called upon to name the guests that were inside. He was able to complete the task by imagining where each guest was seated. This method works by associating each piece of data (someone’s name) with a location in imaginary space, leveraging natural capabilities for spatial memory. In antiquity and in modernity this method has been used to accomplish incredible feats of memory, such as monks in the Middle Ages memorizing entire books, or Simon Reinhard setting a world record in 2010 by memorizing the order of a shuffled deck of cards in 21.9 seconds.
If using method of loci for passwords, a few methods could be used. One could be imagining your house, and moving through it. Standing at the front door is a jackalope in a coma, holding an “@” sign. On the coffee table there are six big ribbons. Walking to the fridge there are two carrots hanging from it (^^). At the door to your bedroom are 12 pebbles you know are formed from Gneiss. Combined, this imaginary walk through your house would help you remember that your password is jackalope,@6RIBBONS^^Gneiss12. At 29 characters long, this password is a bit unwieldy to type in. However, even if the attacker is only looking for 29 character passwords (unlikely) they would be dealing with 1.6×10^57 or 1.6 octodecillion possibilities, which should be basically unguessable. A computer capable of computing 10 quadrillion hashes per second (or capable of making 10 quadrillion login attempts per second) would need almost 5.27 decillion years to fully complete a brute force attack. In practice, due to probability, a brute force attack only needs to complete half of the possibilities before it is more likely than not that the correct password has been found, reducing expected time to solve to 2.635 decillion years, or about 191 sextillion times as long as our universe has existed. Also in practice this 10 quadrillion hash per second computer attacking your password can be upgraded to be twice as fast every 18 months according to the projection known as Moore’s law, though Moore’s law is not expected to continue to hold up for very long into the future due to physical limitations of computer chips, barring major leaps forward in quantum computing or nanotechnology. Suffice it to say your 29 character password using 94 possible characters should be safe from brute force attacks at least until long after your great-great-grandchildren are dead.
This said, method of loci is hardly even necessary to memorize a complex password, though it could certainly be useful and with dedicated practice even allow one to remember a completely random password accurately. A single complex image in memory can be used. Images that work best in this setting are those that are particularly humorous, macabre, profane or bizarre, as those tend to stick in the mind more than images which are mundane. For instance two komodo dragons fighting over a rubber ducky covered in hollandaise sauce and standing on a giant pound scale is an image that could help you to reliably remember the password 2komodoON#HOLLANDAISEducky, which at 26 characters is quite secure.
Another method of generating long memorable passwords is to create acronyms from memorized songs or phrases. For instance, in this case “row, row row, your boat gently down the stream, merrily, merrily, merrily, merrily, life is such a dream” could create the password 3R,ybgdts,4M,lisad if you remember to put in the commas and add numbers and capitalization for repeated words. This password is only 18 characters long, so not as secure by several orders of magnitude in comparison to some of our others, but is sufficient. Also, general knowledge of this method means that acronyms made from popular songs will be added to dictionary lists for dictionary attacks, including permutations, so well known songs or phrases from Shakespeare, the Bible or famous oratory are generally inadvisable. However if you memorized a song from someone’s b-track, or a random passage from Derrida or Joyce’s Ulysses, this method could prove workable and generally safe, especially if other characters are added in within your capabilities to remember them.
Conclusions
One of the safest systems of authentication we currently have is the use of a secret password. However, there are issues, including eavesdroppers and leak of passwords files, which can be very compromising. The best security strategy is one where a user has long and complex passwords for every login that she or he uses. The best way to maintain these passwords is by keeping them in the only safe space, the inside of your head. To aid in the task of maintaining a long list of passwords in memory, it is very helpful to use memory techniques and methods for creating complex passwords that are memorable.