AES-128 (CBC) brute force given 90+ rightmost bits of key, known IV and Ciphertext?

Question

Given: Known ciphertext (in hex) (ciphertext is the exact length of the message (i.e. non-padded). It is known that the cipher was developed using CBC. There is one and only one ciphertext message that was grabbed. The exact ASCII range of the plaintext is known.

Known IV in Hex

Known partial key! (in binary) 91 bits (rightmost) of the key--meaning the first 37 bits are unknown. This key is: XXXXXXXX.XXXXXXXX.XXXXXXXX.XXXXXXXX.XXXX1100.00000000.00000000.00000000.00000000.00000000.00000000.00000000.00000000.00000000.00000000.00000011

This should translate to 00000000_0C000000_00000000_00000003 in hex unless I've done something wrong. In the translation the 0's to the left of the "C" should be unknown (so F's in keymask). The zeros between the x and the 3 are known "0s" and should be there.

Key mask to search this should be something like "FFFFFFFF_F0000000_00000000_00000000"

What would a method try to brute this? Is this even realistic? Is there software already developed (open source) that already has the ability to plug in a known portion of a key, the cipher, and IV to try to brute without re-inventing the wheel?

As for complexity, wouldn't the complexity be something like $n^{37}$. since the other 91 of the key are known? Or is there another mathematical factor that I am missing here?

Answer 1

We can say that you need to search 37-bit keyspace that is $2^{37}$.

Brute-forcing:

You will set up a counter starting from 0 to $2^{37}$. With the given key part at each step concatenate them givenKeyPart||counter before the key schedule.

Run the key schedule, then perform the encryption to see that the ciphertexts are matching. You don't need to perform the x-or with the IV for every encryption. Do it once.

You can easily reach $2^{37}$ encryption, or say the key search for AES. You have multiple options;

1. You can parallelize the search over the cores or PC's
2. You can use AES-NI if available.
3. Also, if available you can use GPU's

Here a benchmark for 32-bit search with AES-NI. It takes 40.3497s to search $2^{32}$.

In my test computer the 32-bit search with AES-NI took 14.1762s with 8 core.

Performances:
    1477815830 AES128 operations done in 14.282s
    9ns per AES128 operation
    103.47 million keys per second

Therefore the expected seconds for $2^{37}$ key space is $$2^{37}/2^{32} \times 14s = 448s$$

---

How to identify the plaintext: One general rule when only ciphertexts are given; one can check the result is valid (English) language. Looking at the ASCII range and/or using a function similar to string can enable to eliminate the candidates. However, there might be still many candidates to eliminate. To reach the solution one may need more than one ciphertext blocks (not a new message). There was a historical RSA challanges that gave more information than these contestants. However, your case still achievable in a very short time.

Update for the comment

Given 4 Bytes, IV and 3 Ciphertext blocks, exactly 16*3-byte plaintext with no padding and ASCII range is known.

For each of the candidate key check

1. All characters of the first decrypted plaintex are in ASCII range
2. If so check the second and if so check the last.
3. If all in the range then it is a good candidate.
4. Otherwise, skip the next key.

You can use a string search mechanism or select by your eyes. If you prefer your eyes better to write all of the candidates into a file with the key information.