Storybits: Error Resistant Mnemonics | rya.nc

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”. 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. 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 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. 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.