2

Usual password verification schemes stores a salted password hash and the salt. If the hash is good and computational costly, it is considered secure.

However an alternate version (used in Microsoft Office and probably other places) generates N random bytes (eg 16 bytes) and a M byte hash of the N bytes (say an additional 16 bytes), concatenates them and encrypts the concatenated N+M bytes using some encryption algorithm and a key derived from the password.

To verify the password, the N+M bytes are decrypted, the first N bytes are hashed and compared to decrypted M bytes. If they match, the password is considered verified.

To my untrained eyes, the introduction of random data (of sufficient length) makes this system secure against any table look up scheme even if the hash is weak. It only seems to depend on the strength of the encryption and the key length.

Am I wrong? Where?

Moose
  • 21
  • 1
  • Just to be clear: I'm not proposing this scheme should be used for anything real (although I do belive MS still uses some variant of it), but it was introduced in 1997 and it seems like it still would be a secure scheme, immune to all types of lookup table attacks. – Moose Sep 23 '14 at 19:44

2 Answers2

3

This scheme is ok, but it's basically just a variant of a salted hash. These are generally considered old practice. Furthermore, this scheme is more complicated (more surface area for potential bugs) and relies upon multiple cryptographic algorithms being unbroken.

Modern good practice is that passwords should be stored using a slow key derivation algorithm such as PBKDF2 or bcrypt. These ensure that lookup tables are infeasible, and that cracking all but the weakest and most common passwords is extremely expensive.

I wrote an answer a while back explaining a bit of the history of password hashing and why we now use slow KDFs.

Community
  • 1
Polynomial
  • 133,763
  • 43
  • 302
  • 380
  • I realize bcrypt is a simpler and possibly better solution, but this is a scheme that MS has been using since 1997. It seems a far better solution than using a simple MD5 hash. Interesting enough, a few companies (like Elcomsoft) offers software that cracks this scheme in Office 1997-2003 using rainbow tables. But that must also be through some error in Microsoft's implementation – Moose Sep 23 '14 at 19:28
0

The attacker do not brute force the entire search space for breaking the passwords. The attacker begins by trying the dictionary which is the collection of the most probable passwords.

Let us consider 3 attacks, according to the strategy used to protect the password database.

case 1: Passwords protected with Hash.
For every word 'w' in the dictionary
i. Compute the hash of 'w'.
ii. Compare the hash with the entries in the password database.
In this case the same dictionary can be used to break the entire password database.

case 2: Passwords protected with Salted Hash.
For every word 'w' in the dictionary
i. Append the salt 's' to 'w'.
ii. Compute the hash of 'w'+'s'.
iii. Compare the hash with the password to be broken.
In this case, the attacker has to modify his dictionary according to salt used for hashing the password. Thus the same dictionary can not be used to break the passwords. The salt is not known in advance and if the size of salt is say 32 bits, pre-computation of the dictionary can also be prevented.

case 3: Passwords protected with Microsoft scheme.
For every word 'w' in the dictionary
i. Decrypt the 'N+M' bytes using 'w'.
ii. Hash the N bytes.
iii. Compare the hash with 'M' bytes.
In this case the value of N is not known in the advance and the attacker can compute the encrypted version of 'N'+'M' using every word in the dictionary and for the every possibility of 'N'. However, if the size of 'N' is large, then the pre-computation of the dictionary can be prevented.

Analogously, random 'N' in the Microsoft Scheme serves the same purpose as that of the random salt 's' in the salted hash. However, if the same value of 'N' is used for protecting every password in the database, then it's security is equivalent to the passwords protected with hash(case 1).

Curious
  • 1,452
  • 2
  • 14
  • 26