Habitual Automisation: Diceware Passwords
Send us your comments.
This is a little report that exemplifies a few things that can go wrong with coding a very simple algorithm in Haskell.
Diceware passphrases are a approach to create a complex password that is hard to guess but easy to remember. It is actually not recommended to use a computer to generate those passphrases, but “what I cannot create I cannot understand” (Feynman). If you actually want to use a computer for random selection of words from a list, there are much simpler algorithms for much more generic list than diceword lists.
Diceword lists, for example, are size restricted. The number of words must match a power of six.
You’ll have to download a diceword list from the above webpage or create your own. And then provide the name and a number after the -n parameter to hasdicepass.
A diceword list is a line-oriented file. Each line starts with a sequence of numbers in the range [1,6] and a word (letters and numbers without spaces). For this current version you’ll have to ensure that all lines consist the same number of digits and that every combination of digits is included. Strange errors might occur otherwise.
There are three parts that could be used for computer programming lessons. I invite you to get your own version build. I would be interested in improvements or different solutions.
- Parsing of diceword lists
- Generating a diceword tree
- Locating a word given a sequence of random numbers (of the correct length)
After parsing the diceword list the program compiles the list into a tree, ordered by numbers. This is, for the practical problem at hand, definitely overengineered and probably increases the runtime for most practical number of output words. But if you happen to require a million words, it probably runs a little faster. More important, it is a more beautiful way to store the decision tree that essentially is the thing a diceword list resembles.
I chose an implementation that is at all points oblivious to the number of dices thrown (the length of the diceword list, i.e. the number of digits in each line in the diceword file). Thus, in theory you could use it with unbalanced diceword trees, but this would obviously reduce the randomness of results.
Word location (implemented in the diceword function) turned out to be rather complex due to error handling. If a word is not found the error will provide you with the exact location where your list is lacking a word.
If you take a closer look at the Wordlist parser, you’ll find that there are two versions. After fiddling with generating generic parser DSL and some (yet unknown) problem with the parsing of sequences, I went for a very simplistic parser. The distinction is the difference between using psequence to parse a sequence of Int or to utilise Data.List function takeWhile and dropWhile to parse the leading digits.
I would actually like a parser that could handle errors, but then, the intention of this project has been to have a shot at Dicewords.
Lazieness in Strict Evaluation
The final problem while coding turned out to be the seemingly simple function that collects the results from the diceword function, and prints a chosen number of dicewords from the beginning of this infinite list. Lazy evaluation ensures that the infinite list of dicewords, generated by Data.List.repeat, is actually not created until needed. The function take provides us with the chosen number of words at the start of the list which then is generated using the systems random number generator.
You might obseve, that the call to randomRIO produces some time within the IO Monad. The resulting list thus is of type [IO String]. This is a rather difficult type to pass around, and sequence:: t (m a) -> m (t a) reverses the order of Monad and List within the type. Sweet stuff. But also part of the lesson I learned on strictness.
sequence not only remixes type classes, it also forces evaluation. Thus if you apply sequence before you evaluate the infinite list into a finite prefix of the list, the compiler has no choice but to generate a programm that loops ad infinitum. In this particular case an infinite list of random integers is generated — as you can easily spot with debugging tools. Sadly this means that no word will be printed on the screen.
Thus I had to learn, that it is necessary to first use take to produce a finite list of [IO String] and then, apply sequence to exchange the order of IO-Monad and List-Container.