Diceware
Diceware is a method for creating passphrases, passwords and other cryptographic variables using ordinary dice as a hardware random number generator. For each word in the passphrase, five dice rolls are required. The numbers that come up in the rolls are assembled as a five digit number, e.g. 43146. That number is then used to look up a word in a word list. In the English list 43146 corresponds to munch. Lists have been compiled for several languages, including English, Finnish, German and Spanish. (A Diceware word list is any list of 6^5 = 7,776 unique words, preferably ones the user will find easy to spell and to remember).
A major advantage of the Diceware approach is that the level of unpredictability in the passphrase can be easily calculated. Each Diceware word adds 12.9 bits of entropy to the passphrase. (That is, ln2( 6^5 ) bits). Five words (slighty over 64 bits) are considered a minimum length.
Some people feel Diceware passphrases are too difficult to remember and recommend other methods, such as using the initial letters of a memorable phrase (e.g. 2bor~2b,titq). Computing entropy with the latter approach is problematic.
Entropy with Variable-Length Wordlists
Diceware passphrases yield less entropy than the ideal 64.62 when used with dictionaries containing variable-length words. This is because the length of the resulting passphrases "leak" information about their composition.
To take an extreme example, say we are using the Beale wordlist and we suddenly got a 5-character passphrase (for simplicity, let's ignore spaces and assume words are just concatenated together). This means our passphrase is comprised of 5 single-character words. Since there are just 51 single-character words in the Beale wordlist, there are only 51^5=345,025,251 possible 5-character passphrases, or a mere ln(354,025,251)=28.36 bits of entropy. We can say that the fact that the passphrase length is 5 "leaks" 36.26 (64.62-28.36) bits of entropy. Sure, the probability we will get such small password is vanishing small: it's 2^-leak = 2^-36.26 = 1.21e-11 or 1.21e-9%.
However, we can proceed these calculations for all passphrase lengths up to 30 characters (5 words x 6 characters, which is the largest word length in the Beale wordlist). As the passphrase lengths increase, we have to keep track of the various possible partitions (for instance, a 7-character passphrase may be comprised of two 2-character words plus 3 single-character words or one 3-character word plus four single-character words) and their respective permutations. The results are summarized in the table below:
length entropy leak % probab 5 28.36 36.26 1.21E-09 6 34.63 29.99 9.33E-08 7 39.62 25.00 2.97E-06 8 43.71 20.91 5.06E-05 9 47.03 17.59 0.0005 10 49.65 14.97 0.0031 11 51.78 12.84 0.0136 12 53.69 10.93 0.0513 13 55.33 9.29 0.159 14 56.76 7.86 0.429 15 58.01 6.61 1.023 16 59.08 5.54 2.145 17 59.99 4.63 4.023 18 60.73 3.89 6.739 19 61.30 3.32 10.016 20 61.71 2.91 13.254 21 61.93 2.69 15.447 22 61.94 2.68 15.58 23 61.73 2.89 13.452 24 61.25 3.37 9.616 25 60.39 4.23 5.305 26 59.04 5.58 2.091 27 57.13 7.49 0.553 28 54.54 10.08 0.0921 29 51.13 13.49 0.00867 30 46.51 18.11 0.000352
The most common passphrase length is 22, covering 15.6% of the cases. This is the situation with minimum leak and maximum entropy, but still 2.68 bits short of the ideal 64.62.
Similar calculations can be performed for other wordlists.
The diceware FAQ does recommend not using passphrases with 14 characters or less, which does cover the larger leaks while making only 0.65% of the keyspace unavailable. Even so, the other leaks may be considered large and frequent enough to cause concern. Contratry to most people's intuition, the longest passphrases have decreasingly smaller entropies.
See also
- Brute force attack
- Cryptographic key length
- Key size discusses how many bits of key are considered "secure".
External links
- English diceware page has the complete description and a word list.
- Wikisource:Diceware word list (en) is another word list
- Dialdice has a nicely-formatted word list.