[tahoe-dev] Down with ECDSA

[Jack Lloyd]

On Wed, Aug 19, 2009 at 06:55:49PM +0100, Paul Crowley wrote:

> I recommend against the use of ECDSA in new systems.  It is widely used 
> and has survived many years of cryptanalysis, but for a public key 
> primitive that's a rather low bar to set.  What one wants is a tight 
> reduction to a problem that is believed hard.  We can often place more 
> trust in a relatively new scheme that has such a reduction than an older 
> scheme that lacks one; in many cases, we can infer from the proofs that 
> any attack which breaks the newer scheme necessarily leads to an attack 
> that breaks the older scheme, but not vice versa.

Devil's advocate: This assumes the proofs are correct. As has been
seen a number of times, proofs of security are hard to get right and
may be incorrect. The number of people with the mathematical and
crypto background to fully understand and check such a proof is very
small, and their time is precious - thus the chances that such a
person will check a proof of any random crypto scheme is relatively
small. Consider how long the errors (being IND-CCA1 vs IND-CCA2) in
the OAEP proof lived before being noticed - and OAEP is a major piece
of work, standardized by a number of major bodies and used in real
live software.

Also, the schemes presented are proven secure in the random oracle
model - there is little assurance the proofs will remain valid when
instantiated with any particular concrete hash function, say SHA-256d.

Adopting a new and relatively untested public key scheme for a real
software system reminds me of how penguins will push each other into
the water to test for hungry seals. In the end, someone has to adopt
the scheme, to help attract the analysis that will show if the scheme
is secure or not. So one has to ask

- Am I willing to be the first penguin in the water?

- Even if I am, am I fat enough to attract the attention of the best
  seals? OK, silly metaphor aside, I think this is real problem - is
  Tahoe important enough that Real Cryptographers(tm) will examine
  this scheme, just because Tahoe uses it? If so, Tahoe could choose
  to become the test subject/target. But if not, then Tahoe might
  adopt this scheme, then years and years down the line, someone with
  the relevant skills finally gets around to noticing the huge flaw in
  the scheme by chance, and break Tahoe more or less by accident.

All that said, the paper is quite interesting. Thanks for the link.

-Jack