[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: IKE entropy issues with long keys
Hilarie Orman noted:
>
>Hilarie> The AES requirements have more to do with cryptanalysis than
>Hilarie> brute force key search. The real enemy of 128 bits is
>Hilarie> quantum computers*.
I checked with Peter Shor -- *the* expert in quantum computing -- on
this. Here's his answer:
That's essentially the case. For symmetric cipher keys,
the best known speed-up is a square root factor, so doubling
the key length will give security against quantum computers
(using known algorithms). For standard RSA, quantum
computers can crack RSA in essentially the same number of
steps that classical computers take to encode. So it's
not a good idea to use RSA against quantum computers (unless
they're NMR quantum computers, which right now have REALLY
slow clock rates).
In other words, Hilarie is right -- 192-bit or 256-bit AES is needed
if you think that quantum computers are (or will be) a threat.
(Note, of course, that we're still talking a brute-force attack
of order 2^96 or 2^128, which implies a really fast, massively-
parallel quantum computer -- and that's almost certainly much further
off than a simple quantum computer.)
But note the second part (I didn't ask about discrete log, though I seem
to recall that it's similar to factoring in its complexity on
quantum computers): factoring becomes *much* cheaper. Going to
an RSA modulus size whose factoring would require O(2^128) operations
by today's algorithms doesn't do the trick. In fact, nothing would
do the trick; if you can afford to encrypt it, the guys in quantum
black helicopters can decrypt it.
We *still* don't have any rationale for making the symmetric key size
comparable in number of operations to the D-H size.
--Steve Bellovin, http://www.research.att.com/~smb