1
$\begingroup$

So I'm trying to decrypt AES encryption with a 32-byte key. I know the first 7 bytes, and the final 19. I also have the plain text, as well as the IV and the encrypted text.

I'm currently running python code to try the combinations (for now I'm trying all the combinations of lower case letters), but I was wondering if there was the best way to approach this, instead of just brute-forcing all the combinations, because that would take a long time.

$\endgroup$
1
  • 2
    $\begingroup$ I am unaware of any structural weakness that would allow significant speed up in the case. However, given 26 bytes of the key, the brute force space is now only 6 bytes. This is doable... Some suggestions: 1) run your brute force in rust or c. 2) Trial partial decryption of the plaintext, if you partial knowledge... $\endgroup$ Jun 16 at 6:05

1 Answer 1

1
$\begingroup$

Knowing some bytes of AES's uniform random key doesn't help you recover faster on brute force. Otherwise, we would hear that years ago. So you have $7+19= 26$ bytes for AES-256 which needs 32 bytes for the key. Therefore there are $6$ bytes of the key is missing, equivalently 48 bits of the key are missing.

because that would take a long time.

Not on modern CPUs. For example; on my 7Gen i7, OpenSSL can execute

$openssl speed -evp aes-256-cbc
Doing aes-256-ecb for 3s on 16 size blocks: 119128871 aes-256-cbc's in 3.00s

This means that AES-256-NI runs with 16-byte inputs for 3 seconds. This makes $41227971$ runs on 1 second. AES in ECB has 16-byte input to process. Therefore in one second, we have $41227971 \approx 2^{25.3}$ AES calculations. This means that

second minute hour day
$\approx 2^{25.24}$ $\approx 2^{31.14}$ $\approx 2^{37.05}$ $\approx 2^{41.64}$

This is single-core performance and needs around 84 days to finish. If you have multiple cores ( as most modern CPUs) you can use OpenMP to parallelize your search. My CPU has 8 cores, so a maximum of 8 speed-up is possible to reduce 10 days. If you have more than one computer this can be easily reduced to one day ( all you need is 84 cores to combine in OpenMP)

You need to test it before the long run. Make sure that it finds the key. You may find more than one key for a single known-plaintext pair. Make sure that you run all the space to find all of them.

And you may need your friend CPUs for some time to speed up. OpenMP is great for dynamic grow/shrink of the clients...

Note that if you don' use AES-NI, then you can have lower performance as 13356785 encryption per second. That is approximately $2.75$ times slower.


To see your CPUs performance use;

#For AES-NI
$openssl speed -evp aes-256-cbc
#For software OpenSSL AES 
OPENSSL_ia32cap="~0x200000200000000" openssl speed -elapsed -evp aes-256-cbc

My CPU is listed as 41st on the OpenSSL speed pages. The top is 20 times faster than mine.


As noted by poncho, if we have some information about the key like they are lowercase ASCII then you need to search around $2^{28.2}$ key space that can be achieved in one minute on a single core.

$\endgroup$
3
  • 1
    $\begingroup$ Actually, if you have partial information about what the missing key bits might be, you can do better than what the above tables show. For example, if you know that the missing 6 bytes are all lower case ASCII characters, you need test only $26^6 \approx 300,000,000$ possibilities; that's far less than the $256^6$ you'd potentially need to go through without that information. That said, without such additional information, we don't know how to do better than just checking each possibility... $\endgroup$
    – poncho
    Jun 16 at 21:03
  • $\begingroup$ @poncho well, I implicitly assumed that key is uniform random. If there is such information, obviously, that will reduce the key space. Let me clear about this. $\endgroup$
    – kelalaka
    Jun 16 at 21:13
  • 1
    $\begingroup$ I'd like to add that you may only have to perform one block of decryption initially, and then verify if the key is correct by looking at other blocks (presuming there are any, of course). This is kinda assumed in the answer. If you have AES-CBC with a specific IV then you can perform the XOR with the known plaintext in advance so that you don't have to repeat it. Then you'd just have the AES-block decrypt & compare ops left. $\endgroup$
    – Maarten Bodewes
    Jun 22 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.