Posted on Bugtraq a few hours ago:
Subject: Schneier's PasswordSafe password validation flaw
From: info_at_elcomsoft.com
Date: Thu, November 17, 2005 1:27
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; i1000; 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
