Re: [Cfrg] Elliptic Curves - signature scheme: friendliness to low memory implementations (ends on June 3rd)

["D. J. Bernstein" <[e-mail]>]

Watson Ladd writes:
> It seems as though determinism, one pass schemes, and avoiding
> collision resistance are at odds, unfortunately

Probably one can split a message into

   * packet p0 plus a signature s0 of ("start",p0);
   * packet p1 plus a signature s1 of ("middle",s0,p1);
   * packet p2 plus a signature s2 of ("middle",s1,p2);
   * ...;
   * last packet pn plus a signature of ("end",previous s,pn).

I'm saying "probably" because this sort of thing needs formal security
analysis. But it's known how to do this sort of analysis, either
producing an attack or producing a convincing proof of security.

This is deterministic. It's resilient to collisions in the underlying
hash function. It's one-pass. Most importantly, it allows a one-pass
verifier to immediately reject any forged packet. The attacker can
truncate at any point---and sometimes this by itself is a big problem,
inherent in the concept of streaming, worse than having no message at
all---but (assuming the security analysis works) the attacker can't
forge any packets.

On the other hand, since the fans of streaming crypto interfaces have a
long history of building "verification" software and hardware that
blithely spews out forged packets directly from the attacker into other
components that can't handle it, I'm not sure what exactly is being
accomplished by providing a cryptographic algorithm that _can_ remove
all forged packets. Is the cryptographic user supposed to suddenly start
trusting these interfaces?

What _definitely_ improves security is switching to the much more robust
world of all-in-one crypto interfaces. In this world streamability is
clearly a bad idea: it provides no benefit, and trying to secure it
creates a serious cost in simplicity (not to mention performance).

More to the point, it's clear that these decisions should be made at a
layer above the basic signature algorithm. The basic algorithm---the
algorithm that everyone should use by default---should not allow
security and simplicity to be corrupted by the pursuit of streaming.

---Dan