This application generates random passphrases of configurable strength:
- Randomly choose words from a large dictionary
- English, Polish and Russian dictionaries currently built-in, easy to add new
- Client-side only generation with HTML5 off-line support
- SJCL for strong random numbers in any browser
- Additional transformations to thwart dictionary attacks
There's an on-line prototype at Passphrase.Today that also works off-line. Android application is planned to be issued soon.
The theory of operation is similar to a well-known Diceware scheme, where six words are selected randomly from a dictionary of almost 8000 words using a pair of traditional dice. This application works on the same principle, it just uses much larger dictionaries (140-300k words), words are selected using a software random number generator and additional transformations are applied.
Passphrase length is determined by the target entropy, which by default is set to 35 bits — this usually produces passphrases of around 2-3 words. You can change the target entropy to get shorter or longer passphrases. The passphrase goes through additional transformations, lie adding special characters, to increase resistance to dictionary attacks.
High quality randomness is critical in passphrase generation so that the selected words are not biased in any way and are uniformly distributed in the dictionary. All possible precautions have been taken to make the generation process as resistant to bias as possible in a web browser environment.
The application does not use the standard Math.random() function but relies on
Stanford Javascript Crypto Library to maintain an in-session entropy pool
and feed it from the cryptographic API offered by the browser. If this can't be done in secure manner, the generator
will warn the user and refuse to work.
There's just one configurable parameter in this generator: the target information entropy, which is the metric most commonly used to describe strength of passwords. If your entropy threshold is set to 35 bits the application will randomly generate candidate passphrases until it finds one that is measured above this level. You can increase or decrease the threshold to get stronger or weaker passphrases.
The application uses three methods for candidate passphrase estimation:
- Shannon entropy over words. The passphrase is treated as a string of whole words randomly chosen from the dictionary
and the entropy is equal to
math.log2(len(dictionary)), so for an English dictionary of around 250'000 words each of them will contribute around 17 bits of entropy. This method reflects the resistance to attacks where all combinations of the words in the original dictionary are tried, mimicking how this generator works, and tends to produce the lowest number — it's also the most conservative of the estimates. - NIST entropy. In SP 800-63 the NIST has proposed an algorithm that is based on actual password strength research and takes into account the fact that if natural language words are used to generate passwords the entropy quickly decreases with each character. Because our passphrases are quite long, it will still give high result, usually higher than the Shannon word entropy.
- Shannon entropy over characters. We treat the passphrase as a string of characters chosen from the dictionary, but not
quite randomly: it's because the characters in the words in the dictionary have very different and non-uniform frequencies,
typical for natural language. Entropy is calculated according to the "full" Shannon formula where
-p * math.log2(p)is calculated for probability of each character in the dictionary, and then they are summed. This method reflects the resistance to brute-force guessing all character combinations and tends to produce very high values.
Let's take one generated passphrase as a sample:
wood alcohol
Remember, methanol is highly poisonous! Apart from that it's rather typical passphrase composed of two words. Now, applying the entropy estimation algorithms gives the following results:
| Method | Entropy | Details |
|---|---|---|
| Shannon word | 36 | The passphrase has 2 words and each word in this dictionary on average provides 18.44 bits of entropy |
| NIST | 24 | 12 characters, decreasing entropy per char |
| Shannon char | 50 | The passphrase has 12 characters and each character in this dictionary provides on average 4.21 bits of entropy |
To make things simpler, this example doesn't use the transformations described below. It also wouldn't pass the default entropy threshold set at 35 bits - the estimator will look at the lowest value, which is 24 by the NIST algorithm. This passphrase wouldn't be thus presented to the user and the generator would continue to produce new candidates until a stronger one is found.
Treating the passphrase as a string of characters and applying a brute-force guessing attack won't be in most cases
feasible because the passphrases tend to be longer than typical passwords. Take a sample passphrase of
wood alcohol on the table (longer than the previous example): it's 25 characters long and let's assume for simplicity
it's built from an alphabet of only 26 characters (a-z and space).
This gives a keyspace of 2e35. Then, let's assume we can employ the
current Bitcoin hash rate to crack
passwords (which is around 3.5e17 in Q2 2015). This gives around 1e10 years to
search the keyspace (while it would take only 7 seconds if the password was 13 characters long).
The actual alphabets used by this generator are however much larger than the 26 characters from the example: they can range from 62 unique characters in Russian to 71 in English. This significantly increases the search time (1e21 years).
The exhaustive keyspace search model assumes characters selected randomly from the alphabet, but with natural language dictionary it's not random at all: not only unique characters occur at different frequencies, but also follow certain statistical patterns on how one characters tend to follow others. This allows to implement much faster Markov attacks (see John the Ripper and HashCat).
A naïve brute-force attack would try the following combinations, spending a lot of time on sequences
that never appear in natural language (like aaaa):
aaaaa
baaaa
caaaa
...
Markov attacks will try the more frequent character sequences first. Sample of strings tried by Markov algorithm (HashCat implementation):
serera
seaner
seller
...
So even though the keyspace remains the same, chances are they will hit the right combination much faster: in my testing on 6 character passwords Markov cracking tried all natural-language-looking strings in just 0.24% of the keyspace (5e5 instead of 2e8). This doesn't guarantee a hit, but with natural language words it makes it very likely.
However, for full length passphrase, even with this reduction it's still in unreachable regions (4e18 years) so character-by-character brute force attacks on passphrases aren't very practical.
Instead of guessing the passphrase character by character the attacker may choose to try to reproduce the approach used by this generator: take the same dictionary and try all possible combinations of words. Take this passphrase for example — it's just two words:
niepoprzekłuwany niewybębniany
This attack may be still quite effective — for example, for two-word passphrases selected from a 300'000 words long dictionary there will be 90 billions of combinations (9e10), which can be searched... in a minute using a GPU-powered crackers like oclHashCat on a middle-class gaming computer:
7cd687bbabf32e577f901f3876618258:niepoprzekłuwany niewybębniany
Session.Name...: oclHashcat
Status.........: Cracked
Input.Left.....: File (pl.txt)
Input.Right....: File (pl.txt)
Hash.Target....: 7cd687bbabf32e577f901f3876618258
Hash.Type......: MD5
Time.Started...: Tue Apr 07 23:21:19 2015 (24 secs)
Speed.GPU.#1...: 2213.7 MH/s
Recovered......: 1/1 (100.00%) Digests, 1/1 (100.00%) Salts
Progress.......: 53030907904/90406658329 (58.66%)
Skipped........: 0/53030907904 (0.00%)
Rejected.......: 0/53030907904 (0.00%)
Restore.Point..: 300677/300677 (100.00%)
Started: Tue Apr 07 23:21:19 2015
Stopped: Tue Apr 07 23:21:46 2015
In the above example a keyspace of 9e10 is searched at speed of 2213e6 hashes per second, which theoretically should take 40 seconds, but as they key is found after searching roughly half of the keyspace it only takes 27 seconds.
The difficulty grows quickly with each word: if the passphrase was built using 3 words it would take 141 days to crack on the same machine, and if it was 4 words the time would increase to 116'000 years and so on. This looks good, but remember we're modelling this now for a medium class gaming computer.
The Bitcoin hash rate surge has taught us that building GPU and ASIC-based hashing farms can be relatively inexpensive. As of 2015 the Bitcoin mining rate (which is technically SHA256 hashing rate) is in the regions of 3.5e17 hashes per second. Today's cost of reproducing this hash power can be estimated at around $157m, which is again not something completely unreachable.
Note: this would be 437k ButterflyLabs Monarchs at $360 each, providing 800e9 h/s per unit
So, taking the BTC hash rate as reasonable limit of human capabilities, the times to crack would be now as follows (assuming 3e5 words dictionary):
| Words | Keyspace | Time to crack (s) | Difficulty |
|---|---|---|---|
| 2 | 9.00e+10 | 2.57e-07 | seconds |
| 3 | 2.70e+16 | 7.71e-02 | seconds |
| 4 | 8.10e+21 | 2.31e+04 | hours |
| 5 | 2.43e+27 | 6.94e+09 | hundreds of years |
| 6 | 7.29e+32 | 2.08e+15 | thousands of years |
| 7 | 2.19e+38 | 6.25e+20 | thousands of years |
| 8 | 6.56e+43 | 1.87e+26 | thousands of years |
| 9 | 1.97e+49 | 5.62e+31 | thousands of years |
The problem with longer passphrases is human ability to remember them. While humans can easily remember even long text because of the semantic links between the words, what we're looking for is exactly opposite: words that are completely randomly chosen. So just increasing number of words in passphrase doesn't seem like a viable solution.
To render the dictionary attacks useless this generator applies transformations to the dictionary words. Currently there are two of them:
- case switching
- injection of non-dictionary characters (digits, punctuation etc)
The transformations are applied randomly: i.e. each character in the whole passphrase can be modified by each of them. The parameters are set so that it's almost certain that out of every 10 characters at least one will be most likely modified.
W2ood alcohol on the table
wood Alcohol on the t7able
3wood alcohol on the table
Wood alcoh*ol on the table
The case switching transformation adds as many variants as many characters there are in each word (on average words in the dictionary are 12 characters). The character injection multiplies the number of variants by word length and number of special characters (38). This adds almost 5500 variants to each word in the dictionary.
The dictionary of 300'000 words used in examples above is inflated to estimated 1.6e9 and the crack times grow accordingly:
| Words | Keyspace | Time to crack (s) | Difficulty |
|---|---|---|---|
| 2 | 5.78e+14 | 1.65e-03 | seconds |
| 3 | 1.73e+20 | 4.95e+02 | minutes |
| 4 | 5.20e+25 | 1.49e+08 | years |
| 5 | 1.56e+31 | 4.46e+13 | thousands of years |
| 6 | 4.68e+36 | 1.34e+19 | thousands of years |
| 7 | 1.40e+42 | 4.01e+24 | thousands of years |
| 8 | 4.21e+47 | 1.20e+30 | thousands of years |
| 9 | 1.26e+53 | 3.61e+35 | thousands of years |
