An Implementation of Diceware

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 77765 = 28,430,288,029,929,701,376 ≈ 264 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 ixth 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

This entry was posted in Programming and tagged . Bookmark the permalink.