RSA or DSA? That's the question

[Robert J. Hansen]

Werner Koch wrote:
> I have not heard of a SHA-1 collision yet.  IIRC it still takes
> something in the range of 2^60.

Rechberger and Cannière had some interesting things at CRYPTO 2006--I
don't recall the details, but it sounded like a partial preimage attack,
not just a simple collision.  They only demonstrated it against SHA-1
reduced to 64 rounds, but drew a pretty clear roadmap for how to extend
it to 80.  I'm expecting more results soon.

SHA-1 is facing some scary times.

> symmetric and public key encryption.  OTOH, the improvement in breaking
> public key schemes are foreseeable for quite some time now and thus we
> can estimate how long it will take to break an n-bit key.

I don't know I'd agree with that.  In the early '90s when I first
started using PGP 2.6, a 1024-bit key was considered to be ridiculous
overkill.  Most keys of that era were only 512 bits, and were considered
of suitable strength for a great many years.  A generation prior to
that, Ron Rivest's original late-1970s predictions on necessary key
lengths turned out to be wildly optimistic.

We've got two full generations of crypto prophets who have badly
overestimated the long-term security of algorithms and badly
underestimated the unpredictable advances in computing power.  It seems
reasonable to me to ask why the current round of prophecy should be
believed, given the failures of the past.

When Schneier wrote _Applied Cryptography_ in 1992, the Chinese Lottery
Attack was speculative fiction at best.  Today, distributed.net is doing
them every single day.  It makes you think about what William Gibson
said--"the future is already here, it's just unevenly distributed."