PDA

View Full Version : Experience with AES-128

friedo
January 22nd, 2007, 11:14
Hello.

Does anybode have experience of AES-128 brute force (plaintext) attack?

1. Are there already tools doing this

2. Does anybode know how long it would take to do 2^128 calculations with comparing plaintext?

Extremist
January 22nd, 2007, 18:19
Longer than you want to wait.

naides
January 22nd, 2007, 19:03
Lets see:

2^128 = 3.4 x 10^38 operations

With a Cray, doing ~ 1 PFLOPs or 10^15 float operations per second

being generous lets say that integer ops go 1000 times faster, ergo 10 ^18 op per second

time to finish:

3.4 x 10^38 ops divided by 10 ^18 ops/second equal 3.4 x 10^20 seconds.

The age of the universe is 4 x 10^17 seconds, so far

so you will have to wait a little

dELTA
January 22nd, 2007, 19:33
Friedo, let me guess, you read (and did not fully understand) some of the info on the recent HD-DVD/Blu-ray encryption cracks?

In that case, a tip:
They did not bruteforce the entire theoretical keyspace...

friedo
January 23rd, 2007, 08:04
Hi.

No,nothing to do with HD-DVD encryption... I only need some ideas for a Tool with encryption.

For example i have one System with Key,Sbox,Plain,Crypt etc. A second System with changed Key (SBox same as first) and i can produce some/less Plain/Crypt examples... So i need Ideas regarding best attack.

I thought there where some more attacks which are faster than brute forcing (something like this: http://www.dice.ucl.ac.be/crypto/files/publications/pdf119.pdf) - brute force was only last instance. I did not calculate but i believed already in a time longer than universe even i implement i in distributed form.

I think better is to open "black box" and get out the key...

dELTA
January 23rd, 2007, 18:13
That's the "problem" with secure crypto algorithms, they're specifically designed to be resistant against all other attacks except key bruteforcing. Of course in many cases some better attacks than bruteforcing are found along the way, but I believe AES has resisted it so far, at least for all but extremely theoretical/unusable such that has not received enough attention for me to notice them).

mike
January 23rd, 2007, 19:49
I was a coauthor on what I believe is still the best attack against AES. It was able to distinguish 7 rounds of AES from random with 2^128-2^119 chosen plaintexts.

Doug Whiting of Hifn presented a little calculation at the rump session of a crypto conference I was at; he said that if you had a magic machine a micron wide that could test a key in the time that it takes light to cross it and you buried the earth a thousand kilometers deep in the stuff, you would still need a bazillion years to brute-force 2^128 keys.

Maximus
January 24th, 2007, 07:39
The true advantage of a quantum machine (rumor says its on the air...) is not 'speed' but the fact it can take advantage of the non-locality to perform massive all-in-one parallel calculations -where massive stands for "solving np problems by exhausting the whole solution's space" (np=>p)
(all the possible light states are overlapped and so 'computated' until you reduce it)

this is the little I know on the subject -said this, my congratulations!! Now I do really understand why you got addressed as the Crypto-Wizard of the board

mike
January 24th, 2007, 11:42
There are two main quantum algorithms that might be useful against crypto. The first is Shor's algorithm, which (with probability very close to 1) allows factoring in a polynomial number of quantum operations in the length of the number to be factored.

The other one is Grover's algorithm, which effectively cuts the keysize in half. That's why the 256-bit variant of AES: it's conceivable that someday they could bute-force an effectively 64-bit keyspace using a quantum computer.

Maximus
January 24th, 2007, 12:39
mmh... the 1st should be enough as long as any np problem can be formulated in the terms of a factorial problem. Is this has been proven? for all i remember, this was a supposition and the strength/weakness of RSA too.

(please note I'm not a crypto expert, just curious on this point)

mike
January 30th, 2007, 12:37
No, there's no evidence that arbitrary np problems can be converted to the factoring problem. But you're right that RSA depends on the hardness of factoring.