2

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?

theXs
  • 261
  • 2
  • 8
  • 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. – Mok-Kong Shen Oct 21 '12 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. – theXs Oct 21 '12 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. – Mok-Kong Shen Oct 22 '12 at 12:43
  • 1
    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: http://security.stackexchange.com/questions/6141/amount-of-simple-operations-that-is-safely-out-of-reach-for-all-humanity/6149#6149 – theXs Oct 22 '12 at 12:56
  • ok. I would like to ask Thomas Pornin to provide some literature references for that. – Mok-Kong Shen Oct 22 '12 at 14:37
  • 2
    @Mok-KongShen Quantum computers being able to find keys with cost $2^{n/2}$ is a generic attack using [Grover's algorithm](http://en.wikipedia.org/wiki/Grover's_algorithm). – CodesInChaos Mar 15 '13 at 11:25

2 Answers2

8

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.

CodesInChaos
  • 11,854
  • 2
  • 40
  • 50
  • 1
    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. – Polynomial Oct 20 '12 at 15:35
  • 1
    @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. – CodesInChaos Oct 20 '12 at 15:51
  • 2
    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. – Polynomial Oct 20 '12 at 15:58
  • 4
    See [this answer](http://security.stackexchange.com/a/6149/655) 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. – Thomas Pornin Oct 20 '12 at 17:33
-1

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
Passwords per sec per thread:   15,000,000
(67 ^ 7 / 15M/s )= 112 hours
Now use 4 threads of a I7 CPU:  = 112/4 hours= about 28 hours (MAX time)

Longer passwords and more characters will make it harder You can also get a similar or better result using CUDA (Graphics Card Computing). More PCs of course will also reduce the time needed. He could get lucky and get the password in the first few tries...

Ozmo
  • 1
  • 1
  • 1
    The OP never mentioned passwords, he talked about AES keys. If you want to guess passwords, you incur the cost of the key derivation function, and not just the cost of decrypting a single AES decryption. (Assuming the programmer wasn't incompetent.) Even really weak KDFs are 1000 times as expensive than decrypting a single block with AES. – CodesInChaos Mar 15 '13 at 11:22