How to quickly detect incorrect password in encrypted file without compromising security? I am developing a software to encrypt/decrypt files/streams using symmetrical encryption algorithm. During encryption phase data wil be compressed and encrypted.

When decrypting data, I want to be able to check whether supplied password is correct. For that purpose encrypted file contains header (which I would like to keep as small as possible), where some signature derived from password is going to be stored.

There are several condition that must be met:

A. Password checking must be as fast as possible and it should not require excessive CPU/memory resources. Risk of using weak/guessable password is NOT present as we declare in advance that only secure, long, random passwords are going to be used for encryption.

B. If we encrypt the same plaintext file twice with the same password, the header and encrypted text must not be the same.

I assume that a theoretical attacker has complete source code of my software. The one and only thing that the attacker does NOT have is password.
My question is - what kind of signature should I use so the security is not compromised?

Here are possible options that I was thinking about and my commentary to them:


Password hash (SHA, MD5, etc.). Probably not a good idea because of risk of precomputed dictionary attacks.
Hash of the salted password. Salt is going to be generated using pseudo-random number generator (PRNG). The initial seed of the PRNG is derived from the password. I suspect this won't help at all since we know that the attacker has access to the source code - so the attacker will always be able to generate salt for the given password and, hence, generate the hash. Then the attacker can write proprietary software which will be able to perform dictionary attack agains files encrypted with my software using our own hash-generating algorithm.
Using key derivation function (KDF), like PBKDF2. This does not meet condition A, because all good key derivation functions should deliberately use excessive CPU/memory resources.
Using HMAC. I am not very good at understanding HMAC, but I think that in this case HMAC would not be used for what it was designed. I don't need to verify integrity of the password AND the encrypted file (or, in cryptographical terms, key and the message). I just need to verify whether the password is correct.
Other options?


I would be grateful if someone who understands cryptography better than me could give me some ideas or comments.
This is a perfect job for a Key Based Key Derivation Function or KBKDF. Generate two keys from the input (salt and password). One is stored directly in front of the ciphertext and one is used as encryption key. Because the KBKDF is based on PRF it cannot be reverted, so the keys are not related as far as an attacker is concerned.

Currently the best KDF is arguably HKDF. It contains both an extract functionality (to handle long passwords) and can take a salt and OtherInfo structure as input. The OtherInfo can be used for inserting an ASCII string identifying the key, e.g. "KCV" (key check value) and "ENC" (encryption). It is possible to derive the IV by using "IV" of course, in case the salt is already random for each encryption. You may want to perform only one extract and three expands of HKDF.

I would strongly recommend authenticated encryption. Make sure you use a fresh salt for each encryption procedure.