Re: Someone said 256 bits is not enough

On Fri, 29 Feb 2008 03:33:31 +0000
Guy Macon <http://www.guymacon.com/> wrote:

Assuming (and this is a big assumption, but you do not *know* it to
be false) that a Quantum Computer can be invented that can search
for a solution among 2^N possible keys in N time (It is far from
clear whether this is possible even if a Quantum Computer is
possible, but again you do not know it to be false), and further
assuming that it can test the first key in one second (a 1Hz clock
rate), it would be able to:

Test one key in one second
Test 2^16 keys in 16 seconds
Test 2^32 keys in 32 seconds
Test 2^64 keys in 64 seconds
Test 2^128 keys in 128 seconds
Test 2^256 keys in 256 seconds
Test 2^512 keys in 512 seconds
Test 2^1024 keys in 1024 seconds
Test 2^2048 keys in 2048 seconds
Test 2^4096 keys in 4096 seconds

...and so on.

4096 seconds is a little over an hour.

I'm pretty sure quantum computers won't be able to do that. From
what I've read as it relates to symmetric ciphers, a quantum
computer would reduce a 2**2N complex problem to 2**N complexity.
That's where he was getting the 2**128 -> 2**64 thing. And from
what I understand, if you had an algorithm that could search
exponential space in polynomial time, you'd be able to use that same
algorithm to automate the processes of discovery and innovation.

I am also pretty sure Quantum Computers won't be able to do that. I
am not, however *100% certain* that no Quantum Computers will ever be
invented that will be able to do that, and neither is anyone else.

Well, that's going to be an algorithm to specifically break AES (with
our current knowledge). I don't know, whether there is a general
purpose polynomial time searching algorithm in BQP, but I doubt it.


I keep imagining a trained cryptographer in the year 1908 calculating
how many bits a key must contain to make a brute-force attack
impractical for the next 100 years, all based on his knowledge of the
Burroughs Adding Machine. Could he possibly have imagined a
calculating machine would exist in 2008 that can execute 478 trillion
calculations per second? (See [ http://www.top500.org/ ].)

This is very true.


Regards,
Ertugrul.


--
http://ertes.de/

.

Relevant Pages

  • Re: AES supports long keys
    ... > I heard in '98 that there were some worries that quantum computers would ... > become practical with the AES lifetime, ... Moore's law is a bigger threat to 128-bit keys, ...
    (sci.crypt)
  • Re: Checking a foolproof algorithm.
    ... > We have the same interest in encryption/decryption and programming. ... > I send my friend the encrypted message along with the 2 prefixed keys. ... > then attempts to write a decryption program to break the coded message ... your keys known to your attacker but not the algorithm... ...
    (sci.crypt)
  • Re: a few questions about AES
    ... algorithm that it uses. ... trivially insecure. ... establishes an upper bound on the cipher strength. ... few keys => a weak cipher. ...
    (sci.crypt)
  • Re: fast static alphabetic (order preserving) compression algorithms/implementations
    ... The algorithm must be unencumbered by patents. ... time required to perform key search on the compressed keys (hence the ... compression keywords and you'll be on your way. ... RDF database, where the keys are an array of three 64-bit long ...
    (comp.compression)
  • fast static alphabetic (order preserving) compression algorithms/implementations
    ... The algorithm must be unencumbered by patents. ... time required to perform key search on the compressed keys (hence the ... RDF database, where the keys are an array of three 64-bit long ... standard libraries such as the compression package integrated within ...
    (comp.compression)