# How long would it take a single Processor with the AES-NI Instruction Set to bruteforce an AES Key?

I know that it seems like a stupid question - since it's note feasable to break AES without a quantum computer but I'm curious anyway.

I read on wikipedia that the best known attack on AES-128 takes 2^126 operations. How long would it take a modern processor to bruteforce the key?

I continiously lose my train of thoughts when I try to compare the 3.5 cycles per AES-bytes ( AES-NI instruction set ( see wikipedia) to the Ghz a modern processor delivers. Wolfram Alpha cannot convert those units.

How many operation can one high-end processors to per second?

• Since you mention quantum computer: I am not aware that quantum computer could have particular advantages in breaking a block cipher like AES, though it could in cases of e.g. RSA. Commented Oct 21, 2012 at 13:28
• A quantum computer can do multiple operations in one cycle. Which would give it a competitive advantage while Bruteforcing AES. I think I read something in the line that it could reduce the amount of time to bruteforce AES twofold. Commented Oct 21, 2012 at 18:44
• If I don't err, quantum computers could break RSA because there has been discovered a special algorithm that exlpoits the capabilities of quantum computers in that case. So as long as there is no corresponding special algorithm for breaking block ciphers on quantum computers, one would IMHO be fairly safe with the current good block ciphers in the quatum computer age. If you or others have literature references saying otherwise, I should appreciate to know them. Note that twofold is not much, one needs exponential difference. Commented Oct 22, 2012 at 12:43
• Twofold meant that a quantum computer would need as much time for a 128bit key like we need today for a 64bit key. It would be a huge improvement. Thomas Pornin describes it pretty good in his answer: security.stackexchange.com/questions/6141/… Commented Oct 22, 2012 at 12:56
• @Mok-KongShen Quantum computers being able to find keys with cost \$2^{n/2}\$ is a generic attack using Grover's algorithm. Commented Mar 15, 2013 at 11:25

To calculate this you need:

• The block-size (16 bytes)
• Cost per byte (1.30 cycles per byte)
• Frequency of the CPU (3.8 GHz)
• Number of cores (2)
• Number of keys (2^128)

I'm using "amd64; Piledriver (610f01); 2012 AMD A10-5800K; 2 x 3800MHz; hydra9, supercop-20121016" from eBACS as my example CPU.

To calculate the keys tested per second you calculate:

``````(cpu-frequency * number-of-cores) / (block-size * cost-per-byte) =
(3.8E9 * 2) / (16*1.3) =
6.70E8 =
670 million
``````

To get the keys tested per year you get:

`````` keys-per-second * seconds-per-year =
6.70E8 * (365 * 24 * 3600) =
2.11E16
``````

This corresponds to breaking a 54 bit key in a year.

To get how long it takes, you divide half the number of total keys by the number of keys you try per-year, which gives you about 10^22 years, which is pretty much forever since the universe is only about 10^10 years old.

But no sane attacker would use such a CPU. He'd use specialized hardware that is much more efficient than a general purpose CPU. But even with such hardware, brute-forcing AES is far beyond what humanity can currently afford.

• Even with a multi-trillion dollar budget, custom ASICs, a nuclear power station on-site and a solid near-zero-cost way to identify when a resulting plaintext is in fact the correct one (AES doesn't fail with the wrong key, it just gives you the wrong data), and constantly compensating for Moore's law, you're still looking at beyond the heat-death of the universe. Bruteforcing 256-bit keys is simply beyond the capability of classical computing, and potentially still impossible even after the advent of efficient quantum computers. Commented Oct 20, 2012 at 15:35
• @Polynomial We're talking about 128 bit keys. It might be possible to brute-force those with classical computing in a several decades if you're willing to spend a lot. Breaking a 256 bit key with conventional computers is clearly infeasible. Commented Oct 20, 2012 at 15:51
• Even 128-bit keys are ridiculously infeasible with conventional computers. You're looking at hundreds of thousands of years or more, even if you extrapolate 100 years' worth of Moore's law. Commented Oct 20, 2012 at 15:58
• See this answer for a more detailed analysis. A 128-bit key brute force can be envisioned in a very distant, but not totally preposterous, sci-fi future. It would require a lot of energy. Commented Oct 20, 2012 at 17:33

To get the keys tested per year you get:

``````keys-per-second * seconds-per-year =
6.70E8 * (365 * 24 * 3600) =
2.11E16
``````

Yes - that would be if the CPU were to go headon and try all the permutations of the key expansions.

But - there is another way - attempting to guess by trying each possible password - there is a significant setup-time however everytime you move to a new password - as there is the key-expansion process that needs to be done, where each password is stretched out from the password characters to a uniform length - its this expanded key thats used to decode the stream.

How long would it take a single Processor with the AES-NI Instruction Set to brute-force an >AES Key?

Because the way AES encodes blocks - the attacker would only need then to try every possible password to try decode the first few bytes of the encrypted data, rather than the whole file - and only if it looks like a good file-header or plain text - then he can test a few more blocks to verify the password is ok.

Using the new AES instructions on a low spec Intel laptop CPU- about 10 to 15 Million passwords attempts (Key Expansion + decrypt 16 bytes) per second per thread is easily achievable.

There are optimisations that can be applied (like doing several passwords at a time - using threading or pipelined mode) - and you have up to 12 threads to use in some really high power pcs.

So, its all down to the password that was chosen - a 6 digit password could be broken in a few minutes or even seconds - 7 digit in less than a day.

``````characters password can contain:    67   (a-z A-Z and usual 'leet' special characters)
Typical 7 digit password:       67 ^ 7