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

[Nico Williams <[e-mail]>]

On Fri, May 22, 2015 at 09:29:59AM -0000, D. J. Bernstein wrote:
> 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).

Say you're signing code.  Now you have to distribute O(N) additional
signatures, where N is the size of the message.  That's doable.  But to
verify in an online way as code is downloaded requires interspersing the
signatures with the code.  Which means new file formats (or new
protocols).

Say you're signing a large e-mail...  Now we'd need new message formats.

The point is that we're quite accustomed to online signature functions.
We *could* do without, but it will probably take a lot time and work to
get to where we're using deterministic, off-line, collision-resistant
signature schemes.

Which is why I see #3 as a reasonable compromise: we get a
deterministic, online scheme now that fits existing APIs and message
formats, and a deterministic off-line scheme that gives us collision
resistance and which will take time to get adopted.

> On the other hand, since the fans of streaming crypto interfaces have a
> [...]

Being pragmatic about this does not make one a "fan".

Mind you, streaming is a very good thing, and not just in crypto,
because predictable state costs are very useful in engineering...

> 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).

Agreed.  But we won't get there overnight.  And if we can retrofit
deterministic signature schemes into existing APIs and protocols at low
cost, why wouldn't we?

> 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.

That layer is also above CFRG.  All the more reason to give that layer
the tools they need to make the right choices and get deployment sooner
rather than later.

Practical considerations intrude.  That's terrible, but when you're
rebuilding an airplane mid-flight, practical considerations matter.
(With apologies to whoever I stole that analogy from; IIRC I first heard
it from Bill Sommerfeld.)

Nico
--