how long should a password be?

[Sven Radde]

Hi!

Am Montag, den 05.05.2008, 22:58 -0400 schrieb Faramir:
> >> So there are only 64 bits in an 8 character password, which can be
> >> cracked quite quickly using rainbow tables for any password.
> >
> > That is unlikely to work because gpg uses a random 64 bit salt as well
> > as extended hashing.
> 
>    I never knew how does salt work, but I am not sure if I should ask
> here, or in the PGP-Basics list...

A salt essentially makes precomputed rainbow tables useless.

A rainbow table consists of two columns, "password" and "hashed
password" and is filled by hashing a great number of passwords. Now, if
you know only the hash of a password, just look it up in the rainbow
table to get the original password.

If a salt is being used, the hash is not computed as, e.g.,
SHA1(password), but rather SHA1(salt+password). The salt is a random
number that does not need to be kept secret.
This way, even if you have a rainbow table for SHA1 ready, and even if
the password is in there, you cannot find it by looking up the hashed
value of the password, as a given password can hash to many different
values, depending on the salt used.
You would have to extend your rainbow table by a third column that
contains salt values, which would tremendously increase the size of the
table. Say, if you want 1 million passwords in your rainbow table, a
table without salt would simply have 1 million entries. With a 64 bit
salt, the table would have to be expanded to 1 million * 2^64 entries,
because you need to take every combination of hash+password into
account.

HTH, Sven