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

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?

• Unfortunately, The coding part belongs to StackOverflow even if related to Cryptography. Commented Feb 17, 2019 at 20:41

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.

• This doesn't account for identifying a plausible ASCII plaintext, but since 2^37 isn't unreasonably large it's possible to simply store most plausible plaintexts produced and evaluate them afterwards. Also, the evaluation process can be done in parallel. Commented Feb 17, 2019 at 12:16
• @Natanael Yes, I've added how to identify. Ironically, The RSA Challenges gave more information to identify. Commented Feb 17, 2019 at 12:28
• Amazing information! I was not aware of AES-NI at all, and reading through some of what I found added quite a bit of value to what I've learned. I'm still trying my hand at implementing code to take the values that I know and get a result. I know I could probably just modify the code given (in your benchmark example), but I'm not a great programmer and its always good to learn. Thank you so much for your help-thus far! Commented Feb 17, 2019 at 14:04
• @RAnderson Welcome. I've just wondered, how many blocks do you have? Commented Feb 17, 2019 at 14:07
• That library can only give you some coding insight. You don't have plaintext. for each output, instead of comparing with the plaintext you need to identify it is an ASCII text or not. You may prepare a sample test for a small key search to reduce your development time. Commented Feb 17, 2019 at 20:40