How key_derivation and key_verification functions are implemented of a 7-zip archive's encryption mechanism?

Question

I am curious about how password recovery works for password protected files. And I want to know the exact flow of the 7-zip encryption mechanism :) !!

7-zip uses the AES-256 encryption algorithm in CBC mode to encrypt files or a folder. The key is generated from the user's passphrase using the SHA-256 hash function. The passphrase is hashed using SHA-256 2^19 (524288) times, to increase the cost of exhaustive search. Also, to help reduce the risk of dictionary attacks, a salt is appended to the passphrase before hashing.

My first question is: how does key_derivation function work to generate a 256-bit key? What is the importance of the IV for AES CBC mode and how it is generated?

My second and most important question is: how is the key is verified to decrypt the 7-zip archive? How does its key_verification function work?

Answer 1

Key recovery works like this. The tool guesses many possible passphrases. For each passphrase, it tests whether that passphrase is correct. It keeps going until it either finds your correct passphrase, or until you get tired and give up.

So, how do we tell whether the passphrase is correct? Normally the method would go like this. We use the key derivation algorithm (the same one that would be used when you decrypt the archive using the 7zip program) to compute the derived AES-256 key. Then, we try decrypting a few blocks of the ciphertext under this key.

Tyipcally, the plaintext has a hardcoded constant at some fixed position, so we can check whether our guess was correct by checking whether this constant appear at the fixed position in our trial decryption. (Sometimes, for some file formats, there is no hardcoded constant, but there is a checksum, so we can try decrypting and see whether the checksum is correct. Or, for some file formats, we may know that the plaintext is typically ASCII, so we can check the trial decryption to see whether it looks like plausible ASCII text.) The exact method used depends upon the file format, but usually this stage is not a serious barrier.

This approach is known as trial decryption, or brute-force dictionary search, or a dictionary attack. All of the smarts come in the part that I didn't talk much about: how to come up with a list of plausible guesses at the passphrase, in some intelligent order.

See also Brute-force heuristics used in password cracking.