Or: Love is randomness and entropy

In the summer of 2012, a friend of mine, Kai Mayer, and I were working as system administrators for the Grinnell College Mathematics Local-Area Network (MathLan). After we had learned the basics, such as writing and running scripts, installing and configuring software, etc, our mentor, Dr. John Stone gave us the freedom to pursue any projects that interested us.

What started as a conversation about password strength and security (virtually every user/customer service requires passkeys and the MathLan is no exception!) developed into this project, the pass-phrase generator. This is a simple pass-phrase generator which is intended to produce passkeys which are more secure than an ordinary password in terms of entropy and length, yet easy to remember due to their natural sounding grammar structures. New MathLan users were previously issued an 8-character password composed of both upper and lower case English alphabet letters and numeral digits. For each of the eight characters in a given password, there are 26 + 26 + 10 (62) possibilities. Across all eight characters this gives us a total of 62^8 total guesses an attacker would have to make at most in order to guess the password.

Of course many other factors go into determining password strength, such as how the passwords are used, stored and transmitted, as well as the nature of the random function which picks one character out of the set of possible characters (i.e. is it really random? Do all 62 characters have an equal probability of being chosen?). We can't address all of these issues in the MathLan, and don't really need or want to. The MathLan is an academic environment where openness and sharing within proper academic procedures is encouraged.

What we are interested in considering though is, how can we create memorable pass-keys of considerably high entropy? Our solution is pass-phrases. For ordinary passwords to be strong, each character ideally should be chosen randomly, but words constructed randomly, letter by letter, are not necessarily easy to remember. Well, what if we construct phrases of about four-eight words with each word chosen randomly? If each word in the eight word phrase is chosen from a pool of over 62 words, then we have already beaten the brute-force strength of our previous eight-character passwords.

However, as it turns out, these phrases are not much easier to remember than our passwords, if at all, because they make no sense as a cohesive unit. Any person who has ever been to school and struggled with the rigors of academia will be able to tell you that things are always easier to remember if they make sense. And this is why we introduced grammar to our project.

Grammar is the study of the classes of words, their inflections, and their functions and relations in the sentence (Merriam Webster). We can also think of grammar as the rules of a language governing its morphology, syntax and semantics (Concise Encyclopedia). No wonder then, that grammar and Linguistics are so closely tied with ideas in Computer Science and programming language concepts. Naturally, being computer scientists, we were interested in the idea of creating random, yet grammatically correct phrases. These phrases are constructed used one of several common grammatical templates, such as a plural noun phrase, which can then take the form of an assertion or a question, etc.

We were able to obtain a dictionary of English words, already grouped according to their grammatical function, from the free and open source Gnu Aspell spellchecker project, maintained by Kevin Atkinson. The choice of which grammatical template to use for a particular pass-phrase, as well as which word is picked from a grammatical group is based on a random number function which uses environmental noise from our Linux machines to set a random seed, via the /dev/urandom file. The original word lists we adapted from Aspell have been modified to remove any offensive words, and we added more words as well! Our pass-phrase generator is currently being used to distribute new pass-keys to incoming Grinnell MathLan users.