How to remember a provably strong password: a new way using constrained choice

by Stephen Hewitt | Published 7 July 2018

Introduction

Here is a new way to remember a strong password.

Previous popular approaches to passwords have either allowed you as a user to invent a password, which often results in a password that is easy to crack, or assigned you a truly random password, which may then be hard to remember.

In this constrained choice approach you get the best of both worlds. The idea is to use a truly random number as the basis of the password but allow your own creativity the freedom to compose a personal phrase or story within the constraints of that number.

This approach means the task of remembering a password can be more like an exercise in creative writing rather than a chore of rote memorisation.

It also means that existing mnemonic memory techniques can more easily be applied to the problem, as we will see.

It allows you to choose a known, quantified strength for your password by choosing its length.

As long as you follow the rules, you are then free to use personal information, favourite songs or anything you like to help you remember the password without compromising this guaranteed minimum strength.

This article avoids making any recommendation on how strong a password should be, but the practical examples given here are (provably) harder to guess than a random number of 125 bits.

The examples for a second, alternative practical method are harder to guess than a random number of 129 bits.

The main price to pay for a password as strong as these is that it takes an hour or two to create it and can take longer. It's a kind of mental exercise similar in some ways to solving a crossword puzzle but more creative, since there is no defined correct answer.

Memory ability varies with the individual, but experience shows that the subsequent remembering can happen without a great deal of effort provided that the password is recalled often enough. The majority of the work is in the initial creation.

This article is not meant to imply any guarantee of how well you will remember a password. This is something you are encouraged to test for yourself. If something important depends on the password then it would be advisable to have a a plan in case you do forget it. (Keeping a secure written copy might be one way to do this. A future Clarion article will cover the topic of storing a written password more securely by what is known technically as “secret splitting”)

Note that if you use a password as strong as the examples here to encrypt something and subsequently completely forget the password, then you may not be able to ever recover your data. With a weaker password, either you or a professional might sometimes be able to recover data by repeated guessing.

Password strength is discussed further in the “Password Strength” section below.

This article does not cover other aspects of password security except to caution here that however strong your password is, it will be defeated if it is stolen with a key logger, a “phishing” attack or some other means. Discussion of this is outside the scope of this article.

The next article will present a variation of the methods described here in order to apply the same principle of constrained choice to remembering a strong secret that has already been generated elsewhere, such as a cryptographic key or the seed for a bitcoin wallet.

Provable strength and theoretical foundations

The methods of this article are based on the principle of defeating an attack on your password by making sure that the search space facing an attacker is large enough. The “search space” is the set of possibilities through which an attacker must search while trying to guess the password.

Under this principle what is meant here by provable strength is a provable size of this space that an attacker has to search, here with the important condition that the password is equally likely to be at each position in that space. We do not want the attacker to be able to gain an advantage by looking in more likely places first.

So our password's strength is not a novelty in the way that the password is constructed but rather the password's truly random hiding place in a space that is large enough to make a successful search unlikely enough and difficult enough that the risk is acceptable.

This principle is analogous to what in cryptography is now called “Kerckhoff's Principle”.

In a 1883 journal article Kerckhoff wrote six desired qualities of a military cipher system, including

“Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi” La cryptographie militaire, Journal des Sciences Militaires, Jan 1883.

(The system must not require secrecy and should be able to fall into enemy hands without causing problems.)

Under Kerckhoff's Principle only the cryptographic key has to be kept secret.

Similarly we will assume that the attacker knows everything about the system that we are using to create passwords and has read this article. If the attacker is ignorant of this, then that can only help our defence, but we do not rely on it. What our provable strength relies on is something different that (we hope!) the attacker does not know, which is the random results produced by the dice.

In essence this approach using constrained choice fuses together constraint and choice in the form of the following two components:

  1. Mandating a mechanically-generated, truly random number as the basis of the password. This allocated number is the constraint.

  2. A mapping between password and the number which is many-to-one. Such a mapping means that a particular randomly-chosen number maps to many possible passwords but a particular password maps to only one unique number. In other words, given your password created by this method, we know what number you created it from.

The fact that there are many possible passwords representing your allocated random number is what gives you the freedom to make creative choices.

The fact that each password represents only one number gives the password a provable minimum strength. That is because an attacker trying to guess the password would have to make at least as many guesses as if they were trying to guess the random number. Alternatively, to restate it in terms of our “search space”, the search space of the password is at least as big as the search space of the random number. And the search space of a mechanically generated random number is well known.

There is no need for password strength meters if you are using these principles.

This article returns to password strength after the examples introduced in the following sections.

One important principle when using these methods is not to cheat. Do not be tempted to cast the dice again or change one of the numbers to make the perfect story. Anyone doing that may reduce the randomness of their password and weaken it. The theoretical strength proof applies when the underlying number is truly random, as decided by dice, not when it has been manipulated to make a better story.

There is no limit to the number of methods that can be invented based on this principle of constrained choice. Two different tested practical methods are described here, which anyone can use, without a computer.

Constrained choice practical method 1: the Letter Pair method

Summary

With this method, we are going to create a password that looks something like the following example

bxwgftivbvmcmwplploygmctglbwmrpe

This may look like a sequence of letters but actually it is a sequence of pairs of letters. And each pair of letters is an abbreviation of a word.

To illustrate this let's note that, if spaces are allowed in your password, you could decide to include a space between each word abbreviation, as follows.

bx wg ft iv bv mc mw pl pl oy gm ct gl bw mr pe

The way you remember the password is as a sequence of these words. As you recall and type the password you abbreviate each word in your head using the rules of abbreviation, given below.

What method you use to to memorise the word sequence makes no difference to the strength of the password, but the design of the system here is intended to help you use a story or mnemonic to remember the words.

The memorising of the words is closely intertwined with choosing them in the first place. You choose words to fit your story and you write your story to fit the words made available by the dice. And you use your story to memorise the words.

In this method the strength of the password comes from the fact that each of these abbreviations represents the value of a random number which has 225 equally likely values.

As mentioned, you can choose the strength of your password by choosing its length. The example introduced above consists of 16 such numbers, so the password consists of 32 letters and the random number that is its strength will be randomly chosen from 22516 possible values, which is more than a binary number of 125 bits.

The letter pair method in detail

Let's consider on two different levels how this method works.

The first level is the system of rules for creating the password which guarantees the chosen strength of the password. The second level is the human level on which you work within the rules to compose a password that is memorable to you.

The rules are rigid and simple. A pre-defined 225-part list, [225PARTS], contains a collection of letter pairs split into 225 partitions. This list contains most, but not all, of the 26x26 total letter pairs that are possible with the English alphabet. As you compose and write down the password, at each place in the password for the next pair of letters you use dice to randomly select a partition and the letter pair you write at that point must come from that partition. In a partition where there is more than one pair, you have the freedom to choose which one.

On the second, human level we interpret each letter pair as an abbreviation for a word. And we remember the sequence of letter pairs by remembering the sequence of corresponding words. So as we create the password we are interested in choosing the right word for our story or mnemonic rather than directly caring about its abbreviation.

Experience shows that usually not all the possible words for a given abbreviation spring to mind while creating the story. For this reason [225PARTS] lists for each partition not just the its abbreviations, but also a good selection of the words those abbreviations represent.

The rules for abbreviating a word to a letter pair

The following abbreviation scheme is used in [225PARTS]. Of course other schemes would be possible, but this one has been developed because it gives a more even number of words in each partition while being reasonably simple. For future reference, let's call it call it the “Y special abbreviation scheme”.

The first letter of the abbreviation is always the first letter of the word.

Having used the first letter of the word as the first letter of the abbreviation, the second letter of the abbreviation is the next letter in the word that satisfies the following rules:

  1. If the word starts with a more than one consonant then the second letter in the abbreviation is the next letter in the word that is either a vowel or 'y'. So for example fly => fy, string => si, school => so, shed => se, cream => ce, squirrel => su, tray => ta, style => sy

  2. Otherwise the second letter in the abbreviation is the next letter in the word that is either a consonant or 'y' So for example eel => el, aisle => as, seam => sm, fate = > ft, fig => fg, sight => sg, pyramid => py, eye => ey, dyke => dy, dike => dk, ely => el

How to create a password with the letter pair method

Download [225PARTS] and print it out. The reason for printing it is so that no information about which words you are looking at can leak out while you are creating the password.

Decide how strong you want your password to be, which is reflected in how long it is. In the example demonstrated here, we are going to use 16 words, which means it will be 32 characters long.

Take a piece of lined paper, a pen and a pair of good dice that will give true random results. The dice can be identical in appearance because there is no need to to distinguish between them.

When you are finished, this paper will contain your password, so it should be destroyed or kept secure.

The strength of the password depends on the randomness of your number generation and it is very important that you use a mechanical method such as dice. Do not make up numbers in your head and imagine that they are random. Be wary of taking random numbers from a computer too.

You are going to repeatedly cast the pair of dice and write down the result, but cast them obeying a certain rule. The rule is that a double does not count. That means that every time the number on both dice is the same, you ignore that result and cast them again.

We will write the result of casting a pair of dice using a notation like “23” which means that one die showed a 2 and the other showed a 3. Write the lower number first. It does not matter which of the two dice shows which number. Since we have excluded doubles, this means we have 15 equally likely outcomes for each cast.

We are going to cast the pair of dice twice for each word in the password and write the result on it's own line of the paper. This means we have 15x15 = 225 equally likely outcomes for each word.

The notation used here and in [225PARTS] is to put a semicolon ';' between the first cast of the pair and the second cast of the pair. Note that although the order of the dice within the pair does not matter, the order of the pairs does matter and for example result “12;45” is different to result “45;12”.

So start by casting the dice, ignoring any double as described before, and write down the result on the top line of your paper, followed by a semicolon, for example “23;”. Then cast the dice again and write down the result after the semicolon, so now you have for example “23;24”.

A pair of dice under a clear plastic cup.
A pair of dice under a clear plastic cup. Casting dice repeatedly can be faster if you keep them confined all the time

Repeat this until you have 16 lines of results, one for each word in the password. If you have chosen to make your password a different length to our example 16, then your number of lines should reflect the length of your password.

TIP: Casting the dice this many times takes 10 minutes or so and is mildly tedious. I found that it is made easier by keeping the dice confined to a transparent beaker with a lid and shaking it while inverting it a few times before placing it down to read the dice without taking them out, as in the photo here.

In the example presented here, the outcomes from the dice castings were as follows: 23;24 46;23 24;35 34;13 25;34 35;36 35;15 13;16 13;16 34;45 46;13 15;26 24;12 46;35 14;23 14;24

The next step is to look up the dice outcome for each of your 16 lines in [225PARTS]. Write down the allowed letter pair or pairs on each line and some candidate words from the words listed that you initially find potentially memorable.

So for our example here the outcome of the dice castings for the first word was “23;24“. We look up “23;24” in [225PARTS] and find the following entry:

23;24 = F;G = 81 { bx cs }

This means that we may use either “bx” or “cs”. as the first two letters of the password. We will remember these letters by finding a word to memorise which abbreviates to either “bx” or “cs”.

The “F;G” is to allow the use of letter beads instead of dice.
Using letter beads to create random numbers or outcomes is described in a previous Clarion data security article (see “Related”, below) The “F;G” is the equivalent of the dice outcome but expressed in the first 15 letters of the alphabet ABCDEFGHIJKLMNO.

To apply the methods of the letter bead article to your password you would draw a random letter bead from your container and write down the letter followed by “;”. Naturally you have to put the bead back into the container each time you draw it out. Then you would draw a random bead for the second time and write down the letter. You have to write down the first bead drawn first, then “;” then the second bead. Again order is significant and “F;G” is not the same as “G;F”. This two letter sequence appears in alphabetical order in the partitions listed in [225PARTS], so you can find the correct partition.

Since you know the rules of abbreviation you may be able to think of words that are not included in [225PARTS]. The final goal is to select for each line a word that you can remember, whose abbreviation is a letter pair that is allowed on that line.

TIP: Note that because it is intended to be printed on paper, [225PARTS] has been kept short. So in each partition a group of related words might be represented by only one word. In particular when you see a verb the intention is that it also reminds you of any corresponding nouns, and vice versa. For example when you see “manage”, hopefully you also think of “manager” and “management”. For any word in the list, it is often worth pausing to consider whether it could be used as a different part of speech or in a different meaning to the one that first springs to mind. For example “row” could mean a row of houses, a loud noise or an argument, or the sport on the river that is so popular in Cambridge.

Which word is potentially memorable will depend on which memory technique you decide to use. The two described here are the Memory Walk and the story. Experience shows that the Memory Walk is the easier to compose, at least in part because there is not much interaction between the choices made for each word.

In contrast the story method makes the choice of word at each point depend on the story which itself depends on the possible words before and after the word in question. Creating a good story may therefore be an iterative process in which it is necessary to backtrack and try a different twist.

The memory walk: a personal example

In the memory walk you memorise a sequence of words by taking a journey in the mind but a very familiar real journey, such as the walk to your favourite coffee bar or your route to work.

For each word in the sequence you make an association with a particular point in the journey. These points are chosen so that the words in the sequence are encountered in the correct order as the journey progresses.

TIP: The points in the journey had better be far enough apart that there is no doubt about their relative order.

The following personal example illustrates this with an imaginary journey along a real route through Cambridge. To use this method you have to chose your own familiar route, one where no effort is needed to recall all its details. This route is very familiar to me because it's part of the way I cycled to the office for several years.

We're going to walk from outside Queens' College Cambridge through town and out along the river on Jesus Green heading towards the Green Dragon bridge. If we haven't managed to place all sixteen items by then we will cross the bridge and continue through Chesterton towards the Science Park.

TIP: You should choose your route before casting the dice. If you are thinking of choosing the route to try to make it fit the particular dice outcomes you have, you are unlikely to find that it helps, unless your password is very short. Instead consider making mental associations that are more free. The reason that changing the journey is unlikely to help is that even if you find a route to fit the first word or two, as you progress and the possibilities multiply, you will be back to the same problem.

One reason that does justify changing the route is finding that it is not long or varied enough, as you may learn by experience in your first password or two. When stuck for inspiration for a particular word I have always found an answer by going further on the journey. But if you repeatedly need to go a long way to make the next association you might eventually reach the end of the journey without having used all your words.

Table 1 illustrates word-by-word my personal mnemonic for this journey with the dice outcomes above. The table lists for each word the dice outcome and the allowed abbreviations that you find by looking up that dice outcome in [225PARTS].

When looking up dice castings in [225PARTS], note the entries are in numerical order with the “23;24” treated as if it were just a four digit number. Naturally there are many gaps in the sequence compared to a true 4 digit counter because we only use digits 1-6 and because of our convention of writing the smaller digit first.

Dice Allowed pairs Chosen word A Memory Walk through Cambridge PW
23;24 bx cs box We start near the porters lodge of Queens' in Silver Street. The punt ticket touts on the bridge are standing round a large box which has posters on the side reading “Punting tours”. bx
46;23 hb jw wg wig In the barbers further up Silver Street (Mr Polito's) someone is having the hair on his wig cut while he wears it. This is unusual. By the way, sometimes absurd associations can be more memorable than plausible ones. wg
24;35 ft gv faithful As we turn left into Trumpington Street, we hear the faithful singing hymns in St Botolph's church across the street. ft
34;13 iv ry ss ivy Passing the garden outside Catz we see some ivy growing up the wall (actually the creeper is not ivy, but never mind). iv
25;34 bc bv bovine Continuing along King's Parade, King's itself is on our left. When I first lived in Cambridge, King's used to have cows in the Backs, and in fact last year I saw one there again, so I approvingly decide it is the most bovine-friendly of the colleges. I like to imagine a large cow grazing on the striped suburban flatness of its front lawn. bv
35;36 mc qc vx michaelhouse Further along is michaelhouse - the name of the cafe possibly connected with St Michael's Church opposite Caius in Trinity Street. mc
35;15 hy mw rw mow If you stand facing Trinity then to the right of the entrance there is small lawn. A portion of that lawn is not mowed, and in season there is instead a blaze of wildflowers (a contrast to King's front lawn). mw
13;16 pl pilgrim Reaching the junction with Bridge Street, we notice pilgrims entering the Round Church. More details in the next item on the list... pl
13;16 pl polish Years ago at the Basilica della Santa Casa in the Italian hill town Loreto in Marche, I saw a pilgrim shuffling on her knees a complete circuit, following a smooth channel worn in the stone, presumably by thousands of her predecessors over the centuries. I like to think that pilgrims are coming to Cambridge's more modest Round Church to avail themselves of its roundness by polishing the floor with their knees in perpetual circles. As noted above, for the memory walk it is usually helpful to space the objects along the route so that there is no doubt about the order. In this case however, I can put both pilgrims and polishing in the same place because their relative order does not matter, since they both represent “pl”. pl
34;45 aw lg oy oyster As we continue down Bridge Street to the river there is a man on Quayside selling oysters from the river. I think he grows them on ropes hanging under the bridge, although I'm not sure that oysters grow on ropes anywhere else. oy
46;13 gm mo nv yh game Continuing along the walkway next to the river we emerge on Jesus Green near the tennis courts where a game of tennis is underway. gm
15;26 ct cottage A few hundred yards further down the river by the footbridge to Chesterton Road is a house on Jesus Green which is known as the lock keeper's cottage. It stands next to a lock that separates the rowers from the punters of the Cam. ct
24;12 gl ho wy gulp A few yards further at Jesus Green Lido some beginners in a swimming class are accidentally gulping down water. gl
46;35 bw it js bowtie Following the river under the Victoria Road bridge past the Fort St George pub, we pass Midsummer House, one of the few Michelin-starred restaurants in Cambridge, where the waiter is wearing a bow tie. bw
14;23 mr marina Following the river out of Midsummer common, we see on the opposite side a small marina, the only one in Cambridge. mr
14;24 pe precipitation Next to the marina, Elizabeth Way passes overhead and we stop under the bridge for a while to shelter from a sudden shower. (I've done this in real life more than once). pe
Table 1 A complete example of creating a password using dice with the Letter Pair method. From left to right in each row we have the dice result, the allowed abbreviation(s) for that result as defined in [225PARTS], the word we eventually chose, its supporting association in our familiar walk, and in the final column the password itself, remembered by abbreviating the chosen word, constrained to be an allowed abbreviation.

The Story

An alternative to the memory walk is to write a story which uses, in the correct order, the words you have chosen from your allocated candidates.

For the story method we introduce rules called “padding” rules. The motivation is that we will need to use words in the story or sentence that are not in the sequence of words to memorise because otherwise without being allowed to add these words it would be very difficult or impossible to create a grammatical sentence that fits the words we are trying to memorise. At the same time we need a clear rule so that we can easily take them back out again when recalling the word sequence.

So we use the rule that only certain parts of speech in your sentence are used in your word list and the others are ignored. The ones that contribute to the word list are nouns, verbs, adjectives and adverbs.

Furthermore, although in general verbs are significant, common verbs like “to be”, “to have”, “to do”, “to go”, “can” are also ignored and all verbs used as auxiliaries are ignored, including words like “use” in “used to go”. We also decide to ignore all indefinite words like “someone”, “some”, “no-one”. Importantly, all negation is ignored.

So examples of words that can be freely added because they are ignored when recalling your word sequence are the following: articles (“a”, “the”) conjunctions (like “and”, “but”, “because” etc), prepositions (“in”, “on”, “out” etc) and negation (“no”, “not”, “never”) and common verbs like “can”, “to be”, “to have”, “lets” and words like “some”, “any”, “somebody”, “one”, “all”, “here”, “there” and indefinite words like “somebody”, “nobody”.

For example

I know that you are in there because I saw you walk in => know saw walk

The cat sat on the mat and said it was content => cat sat mat said content

One way to proceed is to start to think of a story outline and write possible words on each line, and then make your way down the page selecting the best combination to make the story.

A royal marriage

The custodian of the jewels gave the royal bachelor a mace, as a reward for pole-vaulting over the palace, which was lagged with gems and coated in gold after which he bowled over for marriage the pretty (student)

An example of a story, an alternative to the Memory Walk for remembering a sequence of words. This example is based on the same dice results as our earlier walk through Cambridge.

Constrained choice practical method 2: the single letter method and the poetry of passwords

In this method the rules of abbreviation are different to the previous method. It uses the well-known technique of taking only the first letter from each word.

The major disadvantage of this method with respect to the Letter Pair Method is that you have to remember almost twice as many words to get the same password strength. Its major advantage is that there are far more candidate words to choose from for each of these words. A lesser advantage is that while you are composing the password you do not need a printed list to map words and their abbreviations to partitions.

Instead Table 2 provides a simple mapping from dice outcome to allowed letters.

Outcomes 11-25
Dice Letters
11/22vwS1
12knC2
13ouP3
14ijA4
15gqM5
16fzB6
23lyT7
24exD8
25hR9
Outcomes 26-66
Dice Letters
26rH0
33/44dEX
34tLY
35bFZ
36mGQ
45aIJ
46pOU
55/66cKN
56sVW
Table 2 This table defines the letters allowed for each outcome of casting a pair of dice in the Single Letter Method. The digits in the last column are also allowed, but may be less amenable to being woven into a story than letters.

The rules for casting the dice are different to the Letter Pair Method. What is the same is that you cast a pair of dice, you do not need to distinguish between the two dice and instead you write the result with the lower number first. What is different is that doubles are allowed. Table 2 is designed so that every time you cast the pair of dice under these rules, each of the 18 rows is equally likely to be selected.

For example if you cast a one and a six with a pair of dice, then we write this “16”. Looking this up in Table 2 we see that the allowed characters are “f”, “z”, “B” or “6”. There is no distinction between the two columns which are both under the heading “Letters”. The first column simply makes it easier to pick out the preferred, lower-case letters.

The “padding” rules for words that you can freely add in your story are the same as for writing a story in the Letter Pair method above.

TIP: Experience shows that using a dictionary helps inspiration and may quickly bring possibilities to mind that you had not thought of. For maximum security the dictionary had better be a printed one rather than an online one.

Stories about people can be the most interesting and therefore memorable. But the following story also turned out to be memorable.

Bears in the Woods

bears love moments in the woods when all they can hear are the bees humming and the rivers running. These moments provide time to extract the weevils from their toes and sleep before hunting for honey bees but weevils face future extinction. In india today elephants outgribe in response to the depredations of man.

An example of a story about animals, using the Single Letter Method to remember the 31-letter password blmwahbhrrmptewtshhbwffeiteordm

With only the first letter as a constraint in choosing each word, the almost limitless possibilities for composition can lead to a kind of writer's block. One possible solution is to introduce a further constraint that also helps with remembering. If you have a favourite song that you know by heart then you can try to base your story on that. Sometimes the amusing contortions and circumlocutions that are necessary help to make the result even more memorable.

As an example, here is what I and the dice did to Suzanne, with apologies and respect to the late, great Leonard Cohen.

Suzanne

catherine eggs you on
to her uboat by the stream
and you can acoustically comprehend the dinghies floating by
you can gain a century beside her
and chai she produces and oranges from china
and just when you're about to utter a protest
she inducts you into her outlook
and the harbour declares
that you've always gained emotion from her being

And you long to obtain motion with her
and maybe navigate blind
and you expect that she'll be veracious
because you've grasped (her perfect body with your mind)

ceusacdfgccpocupiohdgeblomnbevg

The Love Song of J Alfred Prufrock

come, as evening oozes across the sky
like someone anaesthetised on the counter,
through deserted forecourts
past guesthouses with casual customers
and pubs with oyster crusts
down utcas* that press onwards
with insidious objective
to a highly demanding question
Do not expect a briefing on what it is...
The ladies opine on michelangelo
while I have noticed the Footman eternal waiting with my gown
(and snickering).

* An utca is a Hungarian word for street.

ceosacdfgccpocupiohdqeblomnFewg
The freedom of the Single Letter method: Two very different alternatives for a mnemonic poem, composed from the same dice outcomes. Notice how the resulting 31-letter passwords are similar but not identical.

In real life of course you should never use your random numbers for more than one password, but purely to demonstrate that it is usually possible to make a song fit whatever random numbers the dice allocate you, presented side-by-side with Suzanne is an alternative password composed from the same dice results but based on the T.S. Eliot poem Prufrock.

TIP: Capital letters can be useful for additional alternatives but switching to a capital arbitrarily leads to the problem of remembering which words you have capitalised. In the Prufrock example the capitalisation of “Footman” was easy to remember because the same word is capitalised in the original. One of the choices you could make is to reserve capital letters for names. So for example instead of catherine you could choose “Natalie” with a capital N as the first word. Stories involving people you know can be more memorable and you might be able to work someone's name into your story using a capital.

Note that in general inventing a password based on published song lyrics would be a very bad idea but here we are doing something quite different. The dice have already given the password its randomness and providing we follow the rules and stay within the constraints set by the dice outcomes, nothing we can do as a way of remembering it can compromise that.

What you find memorable reflects your personal experiences, knowledge and taste and within the constraints you can choose your password accordingly. In the Prufrock password I used the Hungarian word “utca” because I could not find a better word for street. I considered “underpass” but rejected it. This is typical of the compromises that you have to make. That particular word may not be memorable to most English speakers, but I happen to have spent enough time in Hungary to know it. It turns out that at least sometimes this kind of contrivance makes remembering easier rather than harder.

Password Strength

This section makes some general observations on password strength and relates the power of cracking techniques to the strength of the example passwords from this article. Making recommendations about password strength is outside the scope of this article.

Grains of wheat on a chess board.
Grains of wheat on a chess board, with double the number on each successive square, a centuries-old story. The annual wheat production of the whole world is not enough to continue this doubling for the rest of the board.

The photograph illustrates a centuries-old traditional legend about grains of wheat on a chessboard. The gist of the story is that the king wanted to reward the man who invented chess. The king asked the inventor what reward he would desire. The reply was an apparently modest request for some wheat. “Could I have one grain on the first square of my chess board and then two grains on the second square and then four grains on the third square and so on until you have covered all the squares?”

The king laughed and called for a bag of wheat. But his laughter soon turned to astonishment as he discovered that his whole kingdom could not provide enough wheat.

In fact, if we assume that a grain of wheat weighs about 40mg and that global annual wheat production is about 750 million metric tonnes then it would take around a thousand years of the entire modern world's wheat harvest to satisfy that request.

This story illustrates the counter-intuitive power of exponential growth, counter-intuitive to those who are new to it.

With passwords, this power offers the hope for a human David to withstand the Goliath of modern super computers.

The story, with its doubling on each square, is also apt for the modern age of digital computers that work with “bits” or binary digits. If you increase the length of a binary number by one bit, then you double the the number of possible values it can represent. A one bit number can be either 0 or 1. A two bit number can be 00,01,10 or 11 and so on.

There are two kinds of attack on your password that you might be concerned about: the so-called “online” and “offline”.

“Online” means that the attacker tries for example to log into your email account across the internet in the same way that you would.

A news report from 2017: Parliament cyber attack: Data breach under investigation after hackers target MPs' emails, Lizzie Dearden, Independent, 21 July 2017

‘Investigators found that under 0.5 per cent of 9,000 accounts were compromised during the “sustained and determined” attempt last month, which resulted in part of the parliamentary email system being taken offline.’

One circumstance that would be called an “offline” attack is when the attacker has stolen a cryptographic hash of your login password and keeps making a guess at the password, generating the hash of the guess, and checking for a match with your hash.

Theft of the hashes has repeatedly been reported in the news, with compromises of millions of people's passwords stored by large corporations like Yahoo.

For example:

“Yahoo has confirmed the passwords were hashed, a one-way transformation which allows the site to check that an entered password is correct without needing to store the actual password.”

Yahoo faces questions after hack of half a billion accounts, Alex Hern, Guardian, 23 Sep 2016

“At the time Dropbox practiced good user data security practice, encrypting the passwords and appears to have been in the process of upgrading the encryption from the SHA1 standard to a more secure standard called bcrypt.”

Dropbox hack leads to leaking of 68m user passwords on the internet, Samuel Gibbs, Guardian, 31 Aug 2016

“Hackers posted a file containing encrypted passwords onto a Russian web forum. They have invited the hacking community to help with decryption.”

LinkedIn passwords leaked by hackers, BBC, 7 Jun 2012

“The file posted online reportedly contains 6,458,020 so-called "SHA1 unsalted password hashes", which would be straightforward for a skilled hacker to link to a user's details.”

LinkedIn investigates hacking claims, Josh Halliday, Guardian, 6 Jun 2012

Another “offline” scenario occurs when the purpose of your password is to generate a cryptographic key, usually also by hashing the password. In this case the attacker keeps guessing your password, generating the key and checking whether decryption is successful.

An example of this is a WPA2 PSK WiFi connection where an attacker can receive by radio the initial “handshake” packets which are broadcast during the establishment of a secure connection. The attacker can take these packets away for later offline guessing.

In these “offline” cases the rate of guessing passwords can be very high, because no data has to be transmitted across any network.

A 2013 article explains cryptographic hashes and attacks on them:

“Armed with a single graphics processor, they can cycle through more than eight billion password combinations each second when attacking “fast” hashes.”

Anatomy of a hack: How crackers ransack passwords like “qeadzcwrsfxv1331”, Dan Goodin, ars technica, 28 May 2013

Suppose you had chosen a length of 32 characters for your password and created it using the letter pair method, exactly as for the “Cambridge Memory Walk” example above. How long would it take that 2013 graphics processor to search through your password's the proven minimum search space?

As discussed in the example, we know that with 16 letter pairs, there are a least 22516 different possibilities to try, all equally likely. We know that the probability of finding your password cannot be higher than whatever proportion of that space the attacker is able to search.

Now dividing 22516 by 8 x 109 and assuming a year to be 60x60x24x7x52 seconds, we can calculate that to cover the entire search space at 8 billion hashes per second would take around 171,480,671,961,642,276,453 years.

If the hash is not “fast” then it will take longer.

Obviously there are attacks with more powerful hardware than a single graphics card.

Bitcoin “miners” are constantly generating cryptographic hashes as they try, by a process of trial and error, to generate a hash which happens to fall within a certain range, in a concept called “proof of work”. This process is very similar to cracking a password, where the attacker repeatedly hashes guesses and compares the result with the stolen hash.

The scale of this hashing is such that it uses a significant amount of electricity

Bitcoin will use 0.5% of world’s electricity by end of 2018, finds study, Anthony Cuthbertson, Independent, 16 May 2018

According to the website blockchain.com in July 2018 the global hash rate had recently been almost as high as 45,000,000 tera hashes/second, where a tera is 1012. So let's take the hash rate as ~5 x 1019 hashes/second.

Could the same 32-letter password withstand the combined world-wide cracking power of the bitcoin machine?

Like the wheat grains on a chessboard, the answer might be surprising to those coming to it for the first time.

Note that the following makes the approximation of not taking into account any difference in the kind of hash used for a password and the kind generated by bitcoin. The bitcoin one is a standard SHA256. Some of the hashes used for passwords have been designed deliberately to be slow to compute, in order to defend against attacks.

We can calculate the total time in for the July 2018 global bitcoin computing power to perform an exhaustive search of the provable minimum password space by dividing 22516 by 5 x 1019 and dividing again by 60x60x24x7x52 to get the answer in years.

The result of that calculation shows it would take 27,436,907,513 years.

References

See below for links.

[225PARTS]
A 225-part list for creating passwords based on constrained choice, Version 1, Stephen Hewitt, July 2018.

Comments

Please post comments or questions on Twitter #pw128bit until such time as cambridgeclarion.org gets the ability to host its own comments.

Related

External links