If you are brute forcing a key and trying trillions of combos, how will you know when you accidentally hit the right answer? Clearly you can't look at each decoded answer to see which "looks right".
1
-
1$\begingroup$ With authenticated encryption modes, it's actually quite easy. You don't decrypt the text; you simply try to verify the authentication tag given the key, nonce, ciphertext, and additional authenticated data. $\endgroup$– Stephen TousetCommented Jun 3, 2015 at 18:35
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
This is only a problem if there is very little knowledge about the plaintext. If the plaintext is fully random, you have no distinguisher and you can therefore not detect if you hit the jackpot. If you do have information about the plaintext then it doesn't take a lot of information to see if you have the correct key. And usually there is a lot of information known.
Take a block cipher in CBC mode. If you know and find a full block of plaintext then you can be relatively certain that you found a key. You are only relatively certain because you only found one relation of the permutation defined by the keyed block cipher. If you have AES-256 (block size 128 bits, key size 256 bits) then there are a lot of permutations that share this relationship. However if you have multiple blocks then finding additional matches will quickly weed out all the other possibilities. Say that you are 25% certain that you found a key per block after a possible match. Then after 4 blocks that match you are $1 - {3 \over 4} * {3 \over 4} * {3 \over 4} * {3 \over 4} = 68\%$ certain that you found the key.
Knowing a full block of plaintext is not as strange as it sounds. Usually there is a lot of meta-information available. Take for instance a Word document. For a normal text document you can already start looking for valid English text. However if I type in no text in a Word document and save it I have $3356 / 16 = 210$ blocks of plain text to compare against, and the contents of these blocks are defined in an ISO standard. Even if it wasn't then I'm pretty sure it is easily distinguished from random data (as Microsoft is very good at <span><span><span>repetition</span></span></span>).
The above scenario shows one important reason that ciphers must not be vulnerable to known plaintext attacks: in most scenarios a lot of plaintext is known to the attacker because the data is well defined.
answered Jun 3, 2015 at 18:39
$\begingroup$
$\endgroup$
We can use various phrases or articles(eg. a,an,the,is,are,no,yes,etc.) used in general English and search them in the file, if search is a hit, then the file is successfully decrypted. Similar approach for different languages also. But if the attacker don't have any idea about the data on the file, then it would be next to impossible to decide for the attacker's program whether the encryption is broken or not.
