[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: How long would it take?
Its generally unwise to make the assumption that the only possible
attack on your conventional scheme is a brute force attack. Certainly
the attacks used on many previous generations of cryptosystems were
never brute force -- and certainly every generation of naive
cryptographer has said "well, using brute force it would take N years
to break my cypher". A simple vingenere cypher with a 12 letter key
would seem to be very strong indeed (stronger than DES), and yet we
know you can break one in a few moments because there are better
attacks than brute force.
We have suprisingly little in the way of general theory on what would
or would not make a conventional cryptosystem strong. Certainly
differential cryptanalysis will not be the last thing people come up
with. Until we know everything the NSA knows, I will be hesitant to
say "unless something better comes up" and more comfortable saying
"until something better comes up."
Indeed. The key length is a worst-case analysis for the cryptanalyst;
they can do no worse than that. We can be confident that NSA has cracked
DES because an exhaustive search engine is within their means, but we
don't know how much better they can do.
A while back, Shamir gave a talk on differential cryptanalysis here at
Murray Hill. He mentioned Coppersmith's letter, which said that IBM
knew about differential cryptanalysis back when they built DES, and they
designed it to resist the attack. That's obviously the case -- so Shamir
said that he asked Coppersmith to state that in the intervening 18 years,
IBM had not come up with a stronger attack on DES. Coppersmith was
silent, from which you can draw any conclusions you wish.