Note: This post was written quite some time ago, but originally not published because I never could convince myself that the order insensitivity was actually useful. Publishing it now due to yet another person asking about it.

At DEFCON 22, Dan Kaminsky and I talked a little bit about something I built which he dubbed "Storybits[1]". Storybits can reversibly transform short strings of binary data into a series of words designed to produce a mental image. Order of the words does not matter, and many typos can be corrected automatically. I already had working code at the time of that talk, but since then it's just been sitting around on my computer. People have been asking about it, so I put it up on GitHub, though it's still a hacky prototype. I've thrown together a demo and written a bit about how it works.

Human brains have enormous storage capacity, but they work very differently from computers. Let's try a little experiment. I'm going to pick a random number between 0 and 2¹³ and give you both the binary representation of that number and the word at that position in a list of common English words. I got "1101000110000" and "radius"? Which is easier to remember? They both represent the same information, but memorizing the binary would take some real effort, whereas a single word is no problem. Our memory works on "chunks" not bits.

While we've got lots of long term memory, deliberately storing anything specific in it can be a challenge. Often people use mnemonics, such as "Please Excuse My Dear Aunt Sally", to transform complicated information into a form that is easier to memorize and recall. Most often this is used to memorize lists of things, but it is possible to generalize the technique to other kinds of data.

When information is encrypted, a large number known as a key is used. The security of a key is based on the number of operations (work) that an attacker would need to do to find the correct key. For anything even remotely secure, this value is so large that it's meaningless to most people. For convenience, a log₂ scale (bits) is used to talk about key security. Doubling the strength of a key adds one bit, increasing it a thousandfold adds about ten bits. For most threat models, 96 bits should be good enough[2]. We can use a trick called key stretching to make guessing up to about a million times slower, bringing that down to 76 bits. In human terms, this would be a random sequence of 23 decimal digits, 17 letters or 7 words (from a list of about 2000).

Many mnemonic systems have been proposed[3] and generating syntactically valid sentences is a really good idea, but implementation is far from trivial. Storybits is my iteration of that. Rather than actual sentences, it generates a series of adjective, noun, verb tuples. Building good wordlists for such a system is fairly tricky. I gathered up lists of common English words split up by type of speech, then filtered out words that were too long, too short or too similar[4]. Finally, Dan and I manually removed words that were semantically similar to other words, had high potential to combine offensively with other words or were hard to spell. We stopped somewhat arbitrarily at 256 words per list. Combined with some clever algorithms, we get a mnemonic passphrase system that handles typos and allows the words to be entered in any order.

How it works

Encoding

1. Start with an integer x in the range [0, m)[5] — cracking the encoded output will take the same amount of work as guessing x.

   Example:

   Select m = 2²⁰ and randomly choose x = 901713.

2. Run a parameter search to find the smallest number of tuples that can represent m. The result will depend on the number wordlists in use and how many words each contains. The algorithms work with any number of wordlists of arbitrary size, but any given word cannot appear in multiple lists.

   Example:

   Use three wordlists containing 11, 13 and 7 words respectively.

   The notation _nC_k refers to the number of ways k items can be chosen from a list of n items[6].

   ₁₁C₁ × ₁₃C₁ × ₇C₁ = 1001 < m
   ₁₁C₂ × ₁₃C₂ × ₇C₂ = 90090 < m
   ₁₁C₃ × ₁₃C₃ × ₇C₃ = 1651650 ≥ m

   So three tuples of are needed, nine words total.

3. Break down x into smaller ones, each corresponding to a combination of words from one of the wordlists.

   Example:

   t = x = 901713
   ₁₁C₃ = 165; c₁ = t mod 165 = 153; t = t div 165 = 5464
   ₁₃C₃ = 286; c₂ = t mod 286 = 104; t = t div 286 = 20
   ₇C₃ = 35; c₃ = t mod 35 = 20; t = t div 35 = 0

   So c = (153, 104, 20).

4. Convert the combination number for each wordlist into a set of positions using a combinatorial number system.

   Example:

   t = c₁ = 153
   ₁₁C₃ = 165 > t
   ₁₀C₃ = 120 ≤ t; p₁ = 10; t = t − 120 = 33
   ₉C₂ = 36 > t
   ₈C₂ = 28 ≤ t; p₂ = 8; t = t − 28 = 5
   ₆C₁ = 6 > t
   ₅C₁ = 5 ≤ t; p₃ = 5; t = t − 5 = 0

   So p = (10, 8, 5) for this wordlist.

5. Words taken based on those computed positions are grouped into tuples.

6. A canonical string representation of those word tuples is returned as the output passphrase.

Decoding

1. Start with a typed passphrase.
2. The typed passphrase is converted to lowercase and any character that's not a letter or space is removed. Wherever possible typos are corrected and missing spaces are restored.
3. The words are converted into sets of positions for each wordlist using lookup tables. These tables also have alternate spellings and verb tenses for many words.
4. The sets of positions are turned back into a number for each wordlist by reversing the combinatorial encoding.
5. Those numbers are combined back into the original integer.

Efficiency

The number of bits represented by w words from a set of n wordlists W₁…W_n respectively containing |W_i| words, where w is an integer multiple of n, can be computed as follows:

In other words, take the sum of the binary logarithms of the number of possible ways to choose w ÷ n words from each wordlist, rounding down. With the wordlists used in this demo, we get the following values:

Words	3	6	9	12	15	21	30	36	51	60	90	141	288	369
Bits	24	44	64	82	99	130	173	200	260	293	389	516	720	754

Notice that as the number of words increases we get diminishing returns on the number of bits represented — this is the price of order insensitivity.