How can I do a brute force (ciphertext only) attack on an CBC-encrypted message?

Question

Given a CBC ciphertext and IV, how can I find the encryption key?

We are limited with an 8 chars key, each char in the range of [a..h], so I can generate every possible key (these are only $8^8 = 2^{24}$ (about 4 million) different possible keys).

How would I go about finding the correct one though?

Answer 1

If (you suspect that) the (plaintext of the) encrypted data is ASCII text, you can check if the high bit of each decrypted byte is zero. As long as you have more than 24 bytes of data to check, the odds of that happening by chance are pretty low (given that you have a 24-bit keyspace).

UTF-8 text is also pretty easy to detect, since all bytes that do have the high bit set can only occur in a very distinctive pattern.

More generally, if you decrypt something with the wrong key, the output will look random, and thus all bytes (and all sequences of n bytes) will appear on average about equally often. If you get output that deviates significantly from this (where significance can be measured e.g. using Pearson's χ² test), it will most likely be the correct plaintext.

For small amounts of data, it may be useful to apply this test not only to the full bytes but also to their highest and/or two (and maybe even three) highest bits. This will detect byte values that cluster together (as e.g. letters and numbers do in ASCII), even if there are not enough bytes in the data to get many exact repeats. You can also try looking at the differences between two successive byte values (modulo 256) to detect correlations. All these (and many other variations of them) should be uniformly distributed for random data, whereas many of them will show distinct deviations from uniformity for most kinds of non-random data.

Answer 2

In addition to the plaintext analysis given in detail by Ilmari, a first step after trial-decrypting is to check the padding mode.

As you are using a block cipher in CBC-mode, the size of the plaintext must be brought to a multiple of the block size. This is done by a padding mode. A common padding mode (being uniquely reversible) is PKCS#5-padding: Append as many bytes as necessary to come to a full multiple of the block size, but at least one, and have all these bytes have the same value, namely the number of appended bytes.

When decrypting, you then can check if the last $n$ bytes all have the same value $n$. For a wrong key, in about $\frac1{256}$ of all cases this will end with $1$, in $\frac{1}{256·256}$ of all cases it will end with $2,2$, and so on, and then you'll have to check the rest of the decrypted plaintext to see if it is plausible (see the answer from Ilmari for details). In all other cases you know immediately that the key is wrong. (Of course, this only useful if you know (or can guess) the padding scheme.)

Note that with CBC, you can decrypt the last block without decrypting all the other blocks - just do Decrypt(key, last block) ⊕ before-last block to get the plaintext.