# AES CTR mode is insecure if key is chosen from a tiny keyspace

Given AES-128 with a 128 bit key, but the key is chosen such that its only last 16/32/48 bit are random rest are 0, how can i exploit this to know the key being used, given i have access to oracle that gives cipher for any chosen plaintext.

Brute force can be using all the key and checking cipher, can someone suggest a better approach?

• Brute force is totally feasible, and no there's no better approach.
– fgrieu
Jan 21 at 11:38
• This is much worse than improper choice of key, you have only 16 bits or less entropy in your key! And $2^{16}$ encryptions in a brute force attack can be mounted almost instantly. Jan 21 at 14:39
• yea for 16 bits brute force is best but for 32 or even 48 bits thst would not work, so is there any other approach? Jan 22 at 5:09
• We need only one query to the oracle with one block (16 bytes) of (say) all-zero, and $2^{16}$ offline computations to compare to the one result produced by the oracle. Probability of false positive is very low ($2^{16-128}$). A single PC with AES-NI can test like $2^{27}$ keys per second, thus we are talking milliseconds for 16 bits, seconds for 32 bits, weeks for 48 bits. Even the later is considered very feasible by cryptographic standards.
– fgrieu
Jan 22 at 7:21
• Even when one only has an old android smarthpone, a 64-cores cloud compute instance can be rented for about 4\$ an hour. It is easy to ssh into and run the search task in parallel. So the numbers in the question are totally practical. Jan 22 at 13:18

For keys restricted to $$k\le48$$ useful bits as in the question, we need only one query to the oracle with 16 bytes of all-zero plaintext. If the oracle if for CTR mode, it outputs* the IV and 16 bytes of ciphertext. We translate the IV into the 16-byte initial value of the counter (by right-padding it with zeroes to 128-bit). We then perform (at most) $$2^k$$ offline computations encrypting the counter with incremental keys and compare to the ciphertext, until there's a match, in which case we most likely have recovered the key. Probability of false positive is about $$2^{k-128}$$, and negligible for $$k$$ less than say $$80$$ (above that we probably want to submit more plaintext, that will let us comfort our finding).

A single PC with AES-NI can test at least $$2^{26}$$ keys per second, thus we are talking negligible effort for $$k=16$$ bits, seconds for $$k=32$$ bits, weeks for $$k=48$$ bits. Even the later is considered very feasible by cryptographic standards. Further, the work is trivial to share among several PCs, and ideally suited for ASICs, which would allow well-funded organizations to target $$k=80$$ or more.

We know no better way, up to $$k=127$$ bits of key at least, which is way beyond feasible with current technology.

* Alternatively, the oracle accepts an IV as input, in which case we set it at zero.

• The oracle in my case does not give out the IV, just the cipher text Jan 22 at 8:11
• An encryption oracle for AES-CTR (as in the question, per title) usually produces the IV, since that's part of encryption. Alternatively, it can accept the IV. I have modified the question to cover that later case. If the oracle does not handle the counter at all, then it's not for AES-CTR. That does not change the rest of the answer.
– fgrieu
Jan 22 at 8:22

No, there is no way to exploit information about the key without using that information directly, which means sending messages to an oracle with the key that is tried. AES and block ciphers in general are designed in such a way that information about a key allow other attacks to find the missing information.

As indicated, sending at most $$2^{16}$$ plaintext messages to an oracle to find a key is not considered a lot of effort.