# 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:

1. Password hash (SHA, MD5, etc.). Probably not a good idea because of risk of precomputed dictionary attacks.
2. 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.
3. 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.
4. 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.
5. Other options?

I would be grateful if someone who understands cryptography better than me could give me some ideas or comments.

• Is there a specific reason why you can't force this check after decrypting the file? After all, no matter how expensive you make this check, the attacker can decrypt the file (based on a trial password), and see if that decryption is plausible. Hence, any check you force which is more expensive than that can be ignored by the attacker (while the legitimate user still has to pay for it). – poncho Jun 15 '15 at 13:19
• The reason is that I need to know in advance whether provided password is correct. True, I can start decrypting/decompressing file using wrong password - which should end very early because decompression will fail, but would like to avoid this. – Acetylator Jun 15 '15 at 16:38
• Concerning passwords, in my realisation bruteforcing possibility is virtually excluded, since all passwords are long (>64 characters) random sequences of unicode characters. Human interaction (I mean entering passwords) is completely avoided, because data encryption is used for communication between different modules of a bigger software system. I am well aware of the fact that sharing symmetrical keys between system modules is another security problem, but this was not a part of my question. – Acetylator Jun 15 '15 at 16:45

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.

• I think that is valid only if " long, random passwords" is really long and random enough to be a key not needing stretching; e.g. has 22 letters randomly chosen among 0…9A…Za…z, giving next to 131 bits of entropy. I fear this solution (perhaps any) seriously cuts corners on security for anything a human can be expected to memorize, or routinely key-in. – fgrieu Jun 15 '15 at 13:30
• @fgrieu True, if the long random passwords are neither, then the HKDF extract should be replaced by e.g. PBKDF2. The direct use of HKDF here is due to the requirements in the question. Other readers should be especially wary of this. – Maarten Bodewes Jun 15 '15 at 14:27
• Hello Maarten, I have a strong feeling that this is exactly what I am looking for :-) Could you please check my algorithm and tell whether it is correct? I have function HKDF, which takes parameters as defined here: tools.ietf.org/html/rfc5869 Parameter 1: Salt - non-secret random value, will be saved in file header. Parameter 2: IKM - input keying material. This is encryption password in plain text. Parameter 3: Info - optional context and application specific information. Not used. – Acetylator Jun 15 '15 at 18:59
• Encryption: 1. I generate completely random Salt using some source of entropy (PRNG) 2. Using HKDF, I generate a fairly long sequence of output keying material (OKM), let's say it is at least 1024 bytes. 3. I construct file header by placing two pieces of data in it: A) Salt B) First 32 bytes of OKM 4. I encrypt plaintext file using the rest of OKM bytes as key and initialization vector for my symmetrical cipher. 5. Done. – Acetylator Jun 15 '15 at 19:00
• I think the authenticated encryption sounds like a good idea. That may eliminate the need for any other password validation, since using an incorrect password would cause the authentication to fail. – kasperd Jun 17 '15 at 11:28

Hash the original text, store the hash along with other auxiliary data. Check decrypted text against the hash. This will check the overall integrety of the process, not just the use of the correct key.

This is an addition to the answer of Maarten Bodewes. I have found RNCryptor, which is file encryption/decryption utility. IMHO, anyone who is trying to solve problems similar to mine (checking passwords, encrypting files) will benefit from studying algorithm and specification of encryption/decryption process of RNCryptor. Not sure what would cryptography experts would say about their algorithm, but it looks good to me - at least for the task I am trying to solve.

• I do not see that this RNCyptor solves the problem of fast check for incorrect password in its password variant (or that it can be done). Incidentally, there's a funny security near miss in rnc_isEqualInConsistentTime, supposed to compare the equality of bytestrings of variable length with resistance to timing attack: if self.lengthwas 256 (or a multiple of that), then empty otherData would be a match. It does not degenerate into a security problem in the context, since we do not use 2048-bit MACs. – fgrieu Jun 17 '15 at 7:14
• Well, RNCryptor is able to check password before the encryption starts - and this is exactly what I need. It generates "validator" sequence using specified password and then compares it to the validator from the file header. If both validators are the same, the password is correct. So it solves the problem of password checking. Concerning the bug in rnc_isEqualInConsistentTime - that's interesting, good that you noticed it, in my implementation I'll take care of it. Thank you! – Acetylator Jun 17 '15 at 14:33
• Ah, so likely you are talking about RNCyptor (draft) v4. In the password mode, my reading is that checking a password using the validator still requires the expensive password-entropy-stretching with PBKDF2 (which BTW is far from state of the art, we have scrypt giving orders of magnitude more stretching) – fgrieu Jun 17 '15 at 14:53
• Exactly, I was talking about draft v4. My bad, should have specified that. Concerning PBKDF2 - this is not a problem in my case per se, since all I wanted to know how to check password before trying to decrypt data. I will also have to check scrypt, I agree that it would be a better choice than PBDKF2. – Acetylator Jun 17 '15 at 16:51
• I'm glad that your problem seems solved, but I do not understand how if you use RNCyptor's Password-based encryption: the validator in RNCyptor (draft) v4 does NOT much help to quickly check if the password is correct. It does save computing HMAC, but except for very large packets or small PBKDF2 parameters it is not a significant time saver, since the running time is dominated by the stretching of PBKDF2, which (as apparent here) must be performed before the validator check. – fgrieu Jun 17 '15 at 17:10