Introduction

This tool is a passphrase generator for use in Unix embedded environments supporting Opie (the Open Palm Integrated Environment), such as the Sharp Zaurus PDA or the Compaq iPAQ.

It was inspired by the Diceware algorithm for generating passphrases, where dices are used to select random words from a list. Instead of throwing dices, this tool uses the Unix entropy pool which is believed to provide randomness of quality at least as good as dice throws. See below for an explanation of the algorithm.

Obtaining this program

The latest version of the program can be obtained from the author's web site.

Manual

Installation

These are required prior to installation:

Of these, the first two usually are already provided by any Linux-based embedded environment for PDAs (this is the case on the Zaurus and the Familiar distribution for iPAQ).

The other two (Opie-SH and gawk) must be installed prior to installation of the Passphrase Generator. Please refer to your Operating System documentation on how to find these programs and how to install them.

Then, install this program from packages (.ipk files) as usual.

Using the program

The Passphrase Generator icon can be found in the Opie-SH application tab (it represents a key over a blue gear, like a key over a blue gear).

When prompted to do so, select a word list, then a number of words. The program then gathers random bits, generates the passphrase which is then displayed in a message dialog box.

Dialog boxes and buttons should be self-explanatory.

Security

When using this program, ensure that no one besides you can read your screen. Never write down the generated passphrase on paper, in a file or other permanent storage. Once you have memorized your passphrase, close the application using the "Quit" button. Do not keep the program running in the background.

The program never stores the generated passphrase in a file, but it keeps it in RAM as long as the application is running. When you quit the application, the passphrase remains in RAM until the operating system reuses the space for another application or storage I/O, which usually happens very fast. If in doubt, do not allow other people to use your system (PDA).

Word lists

Four word list packages are already available:

New word lists can be generated at will using the included ppgen-mklist utility. This tool is used from the Unix command-line as follows:

   $ ppgen-mklist [source] >/usr/share/ppgen/lists/[name]

      [source] : filename of an input word list.
      [name] : filename of the resulting word list for use by the
       Passphrase Generator.

There must be at least 3160 different words of more than 3 characters in the source word list. The resulting list contains exactly 4096 words (containing 936 two letter/letter and letter/digit combinations).

Each word list takes approximately 20-25Kb of storage space. The passphrase generator supports any number of different word lists.

Note that ppgen-mklist requires bash, which is not provided in the base installation of many Linux embedded environments. It should be installed separately, or, alternatively, the utility ppgen-mklist can be run on a desktop computer and the generated word list copied back to the PDA.

The algorithm described

The original algorithm

The initial Diceware algorithm, documented here, works as follow:

  1. Take a list of 7776 (6 to the power 5) different words numbered from 11111 to 66666 (using dice numbering).
  2. To choose the first word, proceed as follows:
    1. put 5 dices in a square box
    2. shake the box thoroughly
    3. make the dices roll off simultaneously from an edge of the box onto a flat surface, so that they are placed in a line
    4. use the displayed dice values as an index in the word list, without changing the order of the dices
    5. take the corresponding word in the list.
  3. Memorize the word, without writing it down.
  4. Repeat as needed to get more words in order, without changing the order of the words.

The advantage of this algorithm is that if the words come from the user's native language, they are very easy to remember, because they can be associated with ideas. Therefore, it makes it ideal for use as a replacement for short passwords of randomly-chosen characters, which are usually hard to remember.

From a cryptographic point of view, each word chosen this way represents about 12.9 bits of entropy. Therefore, a 5-words passphrase generated using this algorithm represents about 64.2 bits of entropy, which is believed to be very hard to break by current (2000-2003) standards, even if an attacker knows the list of word used by the passphrase generation process.

Compare with:

The modified algorithm

Instead of throwing dices, this algorithm takes sequences of 12 random bits from the Unix entropy pool to generate each word. Therefore, it works with lists of 4096 words instead, and each word represents exactly 12 bits of entropy.

Note that it generates passphrases which are a bit less secure than those generated with the original algorithm for a fixed number of words. However, increasing the number of words strill strengthens the passphrase: it takes 6 words using the modified algorithm to get passphrases more secure than 5-words long passphrases generated using the original algorithm (72 bits of entropy against 64.2).

License

Copyright (C) 2003, Raphaël Poss

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License version 2 as published by the Free Software Foundation.