Irreal

Last time I presented an implementation of the Diceware method for generating a secure password. Today I’d like to finish up with a few details.

First, the careful reader might wonder why I generated 4 random bytes with RAND_bytes instead of 2. After all, 2 bytes is more than enough to express 7,776 so we’ve wasted two bytes worth of entropy. The reason is that the modulo operation gives a slight bias against the higher numbers and this bias is more pronounced when the modulus and largest random integer are closer together. For example using 2 bytes, the 65,536 integers results in the numbers 0–3,326 being generated 9 times but the numbers 3,327–7,775 are generated only 8 times. That means that the lower numbers are generated 1.125 times as often as the high numbers. That’s a significant bias.

By using 32-bit random integers we get the numbers 0–2,558 generated 552,337 times and the numbers 2,559–7,775 generated 552,336 times. Thus, while there is still a bias it is much less: the lower numbers are generated 1.0000018 times more often than the high numbers.

Second, Apple has deprecated RAND_bytes as of Lion but Google doesn’t know why or what they anticipate will replace it (or at least my Google-fu is insufficient to discover these things). If anyone knows what’s going on here, please leave a comment.

Third, RAND_bytes uses /dev/urandom to seed the PRNG. If your system doesn’t have /dev/urandom (RAND_bytes will return 0) you must seed it yourself with RAND_add.

Fourth, compile the C code with

gcc -Wall -lcrypto diceware.c

Finally, a word about master passwords. As I said in the previous post, you really want to have one master password that is strong but reasonably easy to remember that protects all your other passwords. The question is, how do you store those other passwords safely? The obvious answer to is use a password manager such as 1password or KeePass but if you don’t want to spend money or deal with third party software, you can keep them in an encrypted Org file as explained in this Minor Emacs Wizardry post. This is what I do and it works out fine except that it isn’t integrated into my Web browser the way some of the password managers are. If you roll your own with Emacs and Org mode, make sure you generate strong passwords for your other accounts. You can use something like the makepw utility that I wrote about in my old blog, for instance. If you do use makepw, you might want to have it generate 20 characters instead of 10.

In any event, once you choose a way to manage your passwords, you can use a master password generated by the Diceware method.

A few of my recent posts (1, 2, 3) discussed the Diceware method of choosing a password. The idea is that you roll a die 5 times to get a 5 digit number and use that number to look up a word in a list of 7,776 words. If you do this 5 or 6 times you end up with enough random words for a strong password that is reasonably easy to remember. All of this discussion, here and elsewhere on the Web, were precipitated by this XKCD cartoon, which explains the rationale for the idea well.

As an amusing little side project that might be useful to some, I implemented a software version of the Diceware method. You just run the utility specifying how many words you want and out pop that many words. Although the Diceware page recommends against doing a software implementation, mine uses a cryptographically strong pseudo-random number generator and should be at least as secure as actually rolling a die.

Before we begin, there are 2 points worth mentioning:

1. This is a good way to generate a “master password” that is used to protect your other passwords (I’ll say more about this in the next post). As Troy Hunt pointed out you shouldn’t use this method or any other to try to remember all your passwords.
2. People find it very difficult to believe that 5 random words from a list of only 7,776 could constitute a strong password. One commenter on Hunt’s post even claimed that such a system could be broken in a matter of seconds. The key here is that the words are chosen at random. How many ways are there to choose 5 words from that list? Well, you can choose the first one 7,776 ways, and the second one 7,776 ways and so on so that there are 7776⁵ = 28,430,288,029,929,701,376 ≈ 2⁶⁴ ways. That is, those 5 words have 64 bits of entropy. Because they were chosen randomly there are no patterns to exploit so the entire search space must be examined. How long would that take? Assuming (very generously) that you could check 1,000,000 passwords a second, it would take over 900,901 years. Throw in another word and it would take over 7,005,409,781 years.

First, I downloaded the word list from the Diceware site. A typical line of the list looks like

21124 clip

so I cut out the numbers leaving just the list of words, one to a line, and renamed it diceware.txt.

Here’s the actual C code.

 1:  #include <stdio.h>
 2:  #include <string.h>
 3:  #include <stdint.h>
 4:  #include <openssl/rand.h>
 5:  
 6:  #define NWDS    7776
 7:  #define MAXWDSZ 10
 8:  #define ERROR(m) {puts(m); exit(1);}
 9:  
10:  /******************************************************************************
11:   * get_words -- read the dice words into an array                             *
12:   ******************************************************************************/
13:  
14:  void get_words( char **wds )
15:  {
16:      static char buf[ NWDS * MAXWDSZ ];
17:      char *s;
18:      char *p = buf;
19:      int i;
20:      int len;
21:      FILE *dicewds = fopen( "diceware.txt", "r" );
22:  
23:      if ( !dicewds )
24:          ERROR( "Couldn't open diceward.txt" );
25:  
26:      for ( i = 0; i < NWDS; i++ )
27:      {
28:          s = fgets( p, MAXWDSZ, dicewds );
29:          wds[ i ] = s;
30:          len = strlen( s );
31:          *( s + len - 1 ) = '\0';
32:          p += len + 1;
33:      }
34:  }
35:  
36:  /******************************************************************************
37:   * main -- generate n random Diceware words                                   *
38:   ******************************************************************************/
39:  
40:  int main( int argc, char **argv )
41:  {
42:      char *wds[ NWDS ]; /* list of Diceware words */
43:      int i;
44:      int dwords;        /* number of words to generate */
45:      int ix;            /* random index into list of words */
46:      union
47:      {
48:          unsigned char rand_buf[ 4 ];
49:          uint32_t rand_int;
50:      } u;
51:  
52:      if ( argc != 2 )
53:          ERROR( "Incorrect argument count" );
54:      dwords = atoi( argv[ 1 ] );
55:      if ( dwords <= 0 )
56:          ERROR( "Incorrects number of words requested" );
57:      get_words( wds );
58:      for ( i= 0; i < dwords; i++ )
59:      {
60:          if ( !RAND_bytes( u.rand_buf, 4 ) )
61:              ERROR( "Couldn't get enough entropy for secure generation" );
62:          ix = u.rand_int % NWDS;
63:          puts( wds[ ix ] );
64:      }
65:      return 0;
66:  }

The get_words function on lines 14–34 reads the list of words into the wds array and chops off the newlines. Surprisingly, get_words is more complicated than the actual random word generation that takes place in main (lines 40–66).

First the number of words to generate is retrieved from the command line and put in dwords on line 54. Then get_words is called on line 57 to fill the wds array. The actual generation take place in the for loop on lines 58–64. First RAND_bytes is called to get 4 cryptographically strong random bytes. Those four bytes are reduced modulo 7776 to get a number (in ix) between 0 and 7,775. Finally, the ix^th entry of the wds array is printed. This is done dwords times.

This post is already too long, so next time I’ll finish up with a few technical details.

Update: chops of → chops off