passwd

Over the weekend I read an interesting paper: How to Memorize a Random 60-Bit String. This was probably the first security paper I’d read in quite some time. I discovered this paper via The Morning Paper, which in my opinion is one of the best resources for people interested in computer science research papers. The title of the paper caught my eye and I decided to read the entire paper (this is typically my strategy with The Morning Paper; I tend to use it for “paper discovery”).

This paper builds on the password generation mechanism introduced by XKCD. It modifies XKCD’s approach to work for 60-bit long passwords and also proposes new schemes for English password generation based on random 60-bit strings. We use a lot of online services in our lives, and creating a secure + easy to remember password (especially if you use the same password for all the services. Please don’t do this.) is essential in order to safeguard ourselves.

While XKCD’s scheme is based on a simple dictionary lookup in order to generate a 4 letter phrase, the methods proposed in the paper are more involved. They all use n-gram language models in order to generate English word passwords that, while random, still seem to have the correct structure of a grammatically correct English sentence fragment or phrase.

I think the most impressive scheme proposed is the one in which a 60-bit string is converted into a poem. Yes, you read that right, a poem. This is done using word information from the CMU pronunciation dictionary + FST + FSA for their accepted poem structure. I thought this was the most interesting part of the paper. It was also the part that took me the longest to read.

The paper ends with a section on experiments showcasing user preference and recall for the difference generation schemes proposed. What is interesting is that even though the poetry scheme has the highest recall percentage it has the second lowest user preference percentage (the XKCD method has the lowest preference).

This paper was a fun, short read. I really enjoyed it!