Title         : Schneier's PasswordSafe password validation flaw
Date          : November 16, 2005
Product       : PasswordSafe 1.x, 2.x
Discovered by : ElcomSoft Co.Ltd.


Overview
======================================================================

PasswordSafe is a program originally written by security expert
Bruce Schneier (http://www.schneier.com) that allows one to store
users' passwords in single file (called "safe") which is
encrypted and protected by user's master password (called "Safe
Combination") with the Blowfish encryption algorithm. As noted on
PasswordSafe web page, "the program's security has been thoroughly
verified by Counterpane Labs under the supervision of Bruce Schneier,
author of Applied Cryptography and creator of the Blowfish algorithm."

As noted in "Password Safe FAQ", "there is no back door in
PasswordSafe to recover your Safe Combination, but there is a
password-guessing program that some people have used successfully.
The program works by going through a list of possible passwords
and checking each one".

However, there is a design flaw in PasswordSafe, that allows to
perform Safe Combination validation a several times faster than it has
been conceived by the author, which makes brute-force and dictionary
attacks much more effective.

Details
======================================================================

As described in PasswordSafe documentation, the PasswordSafe database
has the following format:

RND|H(RND)|SALT|IP|Name1|Password1|Notes1|...|NameN|PasswordN|NotesN 

where

RND    : 8-byte (64-bit) random value
H(RND) : hash value which depends on password, used along
         with RND to check password (Safe Combination) validity
IP     : 8-byte (64-bit) initial vector involved in
         encryption/decryption process
SALT   : 20-byte random value used involved in key derivation

PasswordSafe verifies password validity in following way:

bf_key = sha1 (RND | { 0x00, 0x00 } | PASSWORD);
bf_block = RND;
for (i=0; i<1000; i++)
  bf_block = blowfish_encrypt (bf_block, bf_key);
finalhash = sha1_mod (bf_block | {0x00, 0x00});

Then, the 'finalhash' is compared to 'H(RND)' and, if the're
equal then the password is correct.

In pseudocode above sha1_mod() denotes usual SHA-1 computation
with zeroed initial state (this seems to be an implementation
error).

The above key derivation function (KDF) uses so-called
key-stretching method to withstand password-guessing attacks.
This method was introduced in 1997 by Schneier, Kelsey, Hall
and Wagner in "Secure Applications of Low-Entropy Keys" paper.

However, PasswordSafe contains design flaw which allows
attacker to verify password validity without computing
(relatively slow) KDF.

All records in PasswordSafe database are encrypted with
Blowfish algorithm in CBC (Cipher Block Chaining) mode.
According to the documentation, the first block contains the
length (in bytes) of encrypted data stored as 32-bit (4-byte)
unsigned integer, fifth byte holds type value for current
record (in PasswordSsafe 1.x, it is always zero), and three
remaining bytes are zeros.

Encryption key is derived from user's password simply by
computing sha1(PASSWORD | SALT). Note that this is much
simpler and faster than KDF described above.

To check password for validity, the attacker can simply
calculate the encryption key, decrypt first encrypted block
and check if three most significant bytes are all zero.
The probability for this to occur on random password is
about 2^(-24). If this is true, then the attacker can check
candidate password with full KDF. Since full KDF will be
called rarely (approximately 1 time per 16 million passwords),
this protection against password-guessing attacks becomes
absolutely useless.

With PasswordSafe 2.x, slightly more effective attack is
possible. The first record of PasswordSafe 2.x database
always has fixed length and type (i.e. full plaintext block
is known), and this allows to check passwords with
probability 2^(-64).

Impact
======================================================================

PasswordSafe is used to store sensitive data, and so the presence
of such flaws may help attacker to disclose user's logins,
passwords and PINs by implementing fast and effective brute-force
and dictionaery attacks.

Solution/workaround
======================================================================

No known solution is available at the time of publishing this
advisory.

Users should use strong passwords or passphrases. We recommend to use
random alphanumeric passwords that are not shorter than 8 characters.

References
======================================================================

Bruce Schneier - Password Safe
http://www.schneier.com/passsafe.html

Password Safe FAQ
http://www.schneier.com/passsafe-faq.html

SourceForge.net: Project Info - Password Safe
http://sourceforge.net/projects/passwordsafe/

Secure Applications of Low-Entropy Keys
http://www.schneier.com/paper-low-entropy.html

FIPS 180-1 - Secure Hash Standard
http://www.itl.nist.gov/fipspubs/fip180-1.htm

The Blowfish Encryption Algorithm
http://www.schneier.com/blowfish.html

Bypassing the Password Prompt (Washington Post)
http://www.washingtonpost.com/wp-dyn/content/article/2005/10/15/AR2005101500178.html

About ElcomSoft Co.Ltd.
======================================================================

Since 1990, ElcomSoft Co.Ltd. (http://www.elcomsoft.com) has been
developing and marketing password recovery, forensics, and security
software for Windows. The company offers a comprehensive line of
password recovery software for more than 80 popular file and document
types, email clients, compression programs, instant messengers, and
other applications. ElcomSoft tools are used by most of the
Fortune 500 corporations, many branches of the military all over the
world, foreign governments, and all major accounting companies.