Re: AESDec 16 2007 11:52PM Scott G. Kelly (s kelly ix netcom com)

Certainly, botnets change the way we must think about such things, and they do put key cracking for many applications within reach, where it was out of reach before. But I was talking about encryptions per second, not encryptions per workstation. Let's plug in some numbers to get a sense of what a huge botnet could do for us here:

Assume each PC in the botnet can do 1Gbit/sec AES encryptions. This is far too optimistic for today's PCs, but it's a nice round figure, so let's see where this gets us.

The estimate I gave below assumed we could test 10^18 blocks per second, and in order to do this with a botnet made up of the very fast PCs we just defined, we would need 10^18/7,812,500 = 128,000,000,000 (yes, 128 BILLION) bots to brute force the 128 bit AES key in 5.39144876 Ã? 10^13 years (which you will recall is older than the universe is estimated to be).

Hmmm. I'm thinking this still seems a bit impractical. A really dramatic breakthrough (a la quantum computing) might change things, but barring this, I don't think we need to worry about brute force attacks against 128-bit keys, and that other sorts of attacks are *much* more likely than brute force to bear fruit.

-----Original Message-----
>From: Ralph.McClurkin (at) do.treas (dot) gov [email concealed]
>Sent: Dec 16, 2007 5:31 PM
>To: scott (at) hyperthought (dot) com [email concealed], geoff.choo (at) zonnet (dot) nl [email concealed], crypto (at) securityfocus (dot) com [email concealed]
>Subject: Re: AES
>
>B ut of course you're talking about from one workstation/CPU, but what if you were able to take over several thousand CPUs, robot Zombies waiting to do youir bidding. How many do you estimate it will take? There are quite a few machines out there that will be quite easy to take over.
>Ralph McClurkin
>
>The purpose of life is a life of purpose
>
>Robert Byrne
>
>----- Original Message -----
>From: listbounce (at) securityfocus (dot) com [email concealed] <listbounce (at) securityfocus (dot) com [email concealed]>
>To: Geoff Choo <geoff.choo (at) zonnet (dot) nl [email concealed]>; crypto (at) securityfocus (dot) com [email concealed] <crypto (at) securityfocus (dot) com [email concealed]>
>Sent: Fri Dec 14 12:13:03 2007
>Subject: RE: AES
>
>An important caveat: the NIST estimate assumes cryptanalytical advances, along with hardware advances, but does not suggest that hardware alone will be sufficiently advanced within that amount of time to _brute force_ 128 bit keys.
>
>Brute forcing a 128-bit key will take, on average, 2^127 encryptions and compares.
>
>2^127 = 1.70141183 Ã? 10^38
>
>If you assume you could check 1 billion (10^9) keys per second, this will still take you 1.7 x 10^29 seconds, or 5.39144876 Ã? 10^22 years. Making your key trials another billion times faster would still take 5.39144876 Ã? 10^13 years. This is longer than current estimates for the age of the universe.
>
>Of course, there is some probability that you will find the key within some small number of attempts, but that probability is very small (n/(2^128) is *vanishingly* small for practical values of n).
>
>-----Original Message-----
>>From: Geoff Choo <geoff.choo (at) zonnet (dot) nl [email concealed]>
>>Sent: Dec 14, 2007 6:52 AM
>>To: crypto (at) securityfocus (dot) com [email concealed]
>>Subject: RE: AES
>>
>>Cristian,
>>
>>From what I know of AES (http://www.cryptosystem.net/aes/), it should be
>>able to withstand most practical cryptanalysis attacks when means that for
>>the meantime, a brute force attack appears to be the most efficient key
>>recovery attack on AES.
>>
>>However, even if you find a suitable crypto brute force tool, I hope you
>>understand what it means to brute force a key at least 128 bits long.
>>Keylength.com gives a good indication how long certain key lengths will
>>afford protection. E.g. according to NIST, a 128 bit AES key should be
>>sufficiently secure against mathematical attacks beyond 2030. This means
>>that depending on how much computing power you have, I think it's still
>>going to take you anywhere from 20 to 40 years to brute force a 128 bit key.
>>
>>-----Original Message-----
>>From: listbounce (at) securityfocus (dot) com [email concealed] [mailto:listbounce (at) securityfocus (dot) com [email concealed]] On
>>Behalf Of Cristian Serban
>>Sent: 14 December 2007 14:50
>>Cc: crypto (at) securityfocus (dot) com [email concealed]
>>Subject: Re: AES
>>
>>Thank you very much guys.
>>I'll have to digg a little bit to get more familliar with this kind of
>>attack.
>>
>>Cristian
>>On Dec 14, 2007 1:29 PM, Brad Hards <bradh (at) frogmouth (dot) net [email concealed]> wrote:
>>> On Friday 14 December 2007 09:44:49 pm Cristian Serban wrote:
>>> > Hi guys and girls,
>>> > I have a quick question, and i thought you might know.
>>> > Do you know if it's possible to find the encryption key if i have a
>>> > file both encrypted and unencrypted using AES?
>>> This type of attack is known as "known plaintext attack".
>>>
>>> > Do you know any tool that does brute forcing on specified algorithms?
>>> There are brute force attacks, but I'm not aware of anything that would be
>>> significant against AES. See wikipedia for a bunch of references.
>>>
>>> For some algos, you might look at http://www.distributed.net/source/
>>>
>>> Brad
>>>
>>>
>>
>>
>>
>>--
>>Cristian
>>
>

Assume each PC in the botnet can do 1Gbit/sec AES encryptions. This is far too optimistic for today's PCs, but it's a nice round figure, so let's see where this gets us.

1Gbps = 7,812,500 AES blocks/second (assuming 128 bit key, 128-bit block size)

The estimate I gave below assumed we could test 10^18 blocks per second, and in order to do this with a botnet made up of the very fast PCs we just defined, we would need 10^18/7,812,500 = 128,000,000,000 (yes, 128 BILLION) bots to brute force the 128 bit AES key in 5.39144876 Ã? 10^13 years (which you will recall is older than the universe is estimated to be).

Hmmm. I'm thinking this still seems a bit impractical. A really dramatic breakthrough (a la quantum computing) might change things, but barring this, I don't think we need to worry about brute force attacks against 128-bit keys, and that other sorts of attacks are *much* more likely than brute force to bear fruit.

-----Original Message-----

>From: Ralph.McClurkin (at) do.treas (dot) gov [email concealed]

>Sent: Dec 16, 2007 5:31 PM

>To: scott (at) hyperthought (dot) com [email concealed], geoff.choo (at) zonnet (dot) nl [email concealed], crypto (at) securityfocus (dot) com [email concealed]

>Subject: Re: AES

>

>B ut of course you're talking about from one workstation/CPU, but what if you were able to take over several thousand CPUs, robot Zombies waiting to do youir bidding. How many do you estimate it will take? There are quite a few machines out there that will be quite easy to take over.

>Ralph McClurkin

>

>The purpose of life is a life of purpose

>

>Robert Byrne

>

>----- Original Message -----

>From: listbounce (at) securityfocus (dot) com [email concealed] <listbounce (at) securityfocus (dot) com [email concealed]>

>To: Geoff Choo <geoff.choo (at) zonnet (dot) nl [email concealed]>; crypto (at) securityfocus (dot) com [email concealed] <crypto (at) securityfocus (dot) com [email concealed]>

>Sent: Fri Dec 14 12:13:03 2007

>Subject: RE: AES

>

>An important caveat: the NIST estimate assumes cryptanalytical advances, along with hardware advances, but does not suggest that hardware alone will be sufficiently advanced within that amount of time to _brute force_ 128 bit keys.

>

>Brute forcing a 128-bit key will take, on average, 2^127 encryptions and compares.

>

>2^127 = 1.70141183 Ã? 10^38

>

>If you assume you could check 1 billion (10^9) keys per second, this will still take you 1.7 x 10^29 seconds, or 5.39144876 Ã? 10^22 years. Making your key trials another billion times faster would still take 5.39144876 Ã? 10^13 years. This is longer than current estimates for the age of the universe.

>

>Of course, there is some probability that you will find the key within some small number of attempts, but that probability is very small (n/(2^128) is *vanishingly* small for practical values of n).

>

>-----Original Message-----

>>From: Geoff Choo <geoff.choo (at) zonnet (dot) nl [email concealed]>

>>Sent: Dec 14, 2007 6:52 AM

>>To: crypto (at) securityfocus (dot) com [email concealed]

>>Subject: RE: AES

>>

>>Cristian,

>>

>>From what I know of AES (http://www.cryptosystem.net/aes/), it should be

>>able to withstand most practical cryptanalysis attacks when means that for

>>the meantime, a brute force attack appears to be the most efficient key

>>recovery attack on AES.

>>

>>However, even if you find a suitable crypto brute force tool, I hope you

>>understand what it means to brute force a key at least 128 bits long.

>>Keylength.com gives a good indication how long certain key lengths will

>>afford protection. E.g. according to NIST, a 128 bit AES key should be

>>sufficiently secure against mathematical attacks beyond 2030. This means

>>that depending on how much computing power you have, I think it's still

>>going to take you anywhere from 20 to 40 years to brute force a 128 bit key.

>>

>>-----Original Message-----

>>From: listbounce (at) securityfocus (dot) com [email concealed] [mailto:listbounce (at) securityfocus (dot) com [email concealed]] On

>>Behalf Of Cristian Serban

>>Sent: 14 December 2007 14:50

>>Cc: crypto (at) securityfocus (dot) com [email concealed]

>>Subject: Re: AES

>>

>>Thank you very much guys.

>>I'll have to digg a little bit to get more familliar with this kind of

>>attack.

>>

>>Cristian

>>On Dec 14, 2007 1:29 PM, Brad Hards <bradh (at) frogmouth (dot) net [email concealed]> wrote:

>>> On Friday 14 December 2007 09:44:49 pm Cristian Serban wrote:

>>> > Hi guys and girls,

>>> > I have a quick question, and i thought you might know.

>>> > Do you know if it's possible to find the encryption key if i have a

>>> > file both encrypted and unencrypted using AES?

>>> This type of attack is known as "known plaintext attack".

>>>

>>> > Do you know any tool that does brute forcing on specified algorithms?

>>> There are brute force attacks, but I'm not aware of anything that would be

>>> significant against AES. See wikipedia for a bunch of references.

>>>

>>> For some algos, you might look at http://www.distributed.net/source/

>>>

>>> Brad

>>>

>>>

>>

>>

>>

>>--

>>Cristian

>>

>

[ reply ]