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/AR200510 1500178.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.