# Brute Force on Key

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".

• 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. – Stephen Touset Jun 3 '15 at 18:35

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>).