Quantum computing

[David Shaw]

On Wed, Apr 18, 2007 at 09:10:17AM +0200, Anders Breindahl wrote:
> On 200704172359, Robert J. Hansen wrote:
> > 1.  We are unlikely to ever be able to brute-force a 256-bit  
> > keyspace.  Ever.  Not until computers are made of something other  
> > than matter, occupy something other than space, run on something  
> > other than energy, according to rules other than physics.
> 
> I was under the impression that quantum computers were about to provide
> a break in factorization. From quick grep on Wikipedia, I find that:

Robert was commenting on a symmetric cipher (like AES), not asymmetric
(like RSA).  Factoring a 256-bit RSA key is trivial and can be done on
regular home PCs in fairly short order.  However, factoring is not an
attack against symmetric ciphers.

My favorite comment (from Jon Callas at PGP, Inc) about brute forcing
keys is one I think I've posted here before, but still:

  Modern cryptographic systems are essentially unbreakable, particularly
  if an adversary is restricted to intercepts. We have argued for,
  designed, and built systems with 128 bits of security precisely
  because they are essentially unbreakable. It is very easy to
  underestimate the power of exponentials. 2^128 is a very big
  number. Burt Kaliski first came up with this characterization, and
  if he had a nickel for every time I tell it, he could buy a latte or
  three.

  Imagine a computer that is the size of a grain of sand that can test
  keys against some encrypted data. Also imagine that it can test a
  key in the amount of time it takes light to cross it. Then consider
  a cluster of these computers, so many that if you covered the earth
  with them, they would cover the whole planet to the height of 1
  meter. The cluster of computers would crack a 128-bit key on average
  in 1,000 years.

  If you want to brute-force a key, it literally takes a planet-ful of
  computers. And of course, there are always 256-bit keys, if you
  worry about the possibility that government has a spare planet that
  they want to devote to key-cracking.

Note that he's talking about brute-forcing keys here.  If someone
finds a weakness in AES (or whatever), then this math may change
radically.  Pure brute-forcing without such a weakness is just not
viable.

David