key security

[Mike Touloumtzis]

On Tue, Apr 09, 2002 at 09:25:18PM -0300, Trevor Smith wrote:
> 
> Which is correct? Is any passphrase, even one 100 - 200 characters
> long consisting of completely random characters, even as remotely
> difficult to break as it is to break a GPG coded message?

It depends on the amount of entropy represented by the passphrase (and the
hash or other technique used by GPG to convert the passphrase to a key).

Assuming GPG's hash is sound: If a passphrase consists of _truly_ random
characters from, say, a set of 64 printable characters such as the ones
used for Base64 encoding, then each character contributes log_2(64) ==
6 bits to the entropy of the passphrase.  So a 22-character passphrase
using this approach represents 132 bits of entropy; thus at this point
the passphrase is not the weak link in a 128 bit cryptosystem.  You can
generate passphrases like this very easily: just base64 encode chunks
of /dev/random:

$ head -c 22 /dev/random | uuencode -m -

In practice, though, it's easier to remember a much longer passphrase
made up of words than a short one made up of random letters--but in a
longer passphrase you have to be careful about whether what you're adding
actually makes the phrase harder to guess.  If you know that the beginning
of my passphrase is "It was the best of times, " then the rest of it
is not contributing a whole lot :-).  Passphrase selection algorithms
should reduce or eliminate the redundancy present in natural language.

The system you use to select a passphrase need not be kept secret if it
incorporates enough truly random choices.  In practice it's hard to pass
up the extra bits of entropy you get by keeping your selection method
a secret :-).

Here are some messages on this subject which I posted to linux-crypto
last July:

http://mail.nl.linux.org/linux-crypto/2001-07/msg00029.html
http://mail.nl.linux.org/linux-crypto/2001-07/msg00142.html
http://mail.nl.linux.org/linux-crypto/2001-07/msg00145.html

No one contradicted them at the time and I still believe the information
given to be correct (corrections welcome, of course).  The third message
implements a simple passphrase generation program in C.

A quote from one of the above messages sums it up:

"Generating strong passphrase data is easy; just choose a truly random
value N bits long.  The challenge is in constructing a useful mapping
from the space of N-bit strings to the space of character strings which
can (a) be typed, and (b) be memorized."

Another quote re practical passphrase storage considerations (lots of
the recommendations in this area come from very hardcore crypto people
who are unwilling to even consider writing down a passphrase):

"You can have as many bits as you want if you're willing to use a long
enough passphrase.  At a certain point you'll have to start writing them
down, though.  This is probably OK if you're the average forgetful Joe and
the risk of irrevocably losing your data outweighs the risk of someone
violating the physical security of your home, office safe deposit box,
etc. order to get the passphrase.

It's not a good idea if you're a hard-core cypherpunk, are at risk of
law enforcement investigation or intrusive subpoena, or are just playing
with crypto because it's fun and don't have any important data under
encryption :-)."

Finally, remember that crypto can turn big secrets into little ones.
One option is always to keep a file containing all your passwords and
passphrases, and encrypt that file using a key which can be unlocked
by your One True Passphrase (something you _know_ you'll never forget).
Mailers with GPG integration are handy for this: every time you sign up
for a Web service or acquire a server password, mail the account info
(including password) to yourself, with all messages encrypted to your
master GPG key.  File them all in a folder and you're happy.

miket