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

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

In crypto there's a long history of bad API designs (in most cases
allegedly motivated by performance) producing neverending security
disasters. Streaming verification APIs are a perfect example: again and
again we see callers spitting out unverified data directly into software
that can't handle it, because that's the simplest way to use the APIs.

How long are the messages that are actually signed in IETF protocols?
For the protocols where the answer is uncontrolled: Do implementations
allow messages that don't fit into memory? How do those implementations
avoid passing along unverified data? For PGP we know that the answer is
"They do pass along unverified data, and this is a security nightmare."

There are other protocols that don't naturally trigger this problem---
they keep lengths under control, and implementations have no trouble
fitting messages into memory. These implementations should be encouraged
to use a simple, high-security, all-in-one verification API, and the
protocols should be encouraged to use a simple, high-security,
all-in-one signature system.

Nico Williams writes:
> Practical considerations intrude.

Specifying a simple, high-security, all-in-one, deterministic,
collision-resilient signature system doesn't stop higher-level protocols
from deciding to use this core system to sign hashes of messages, with
the obvious consequences. (It also doesn't stop them from using the core
system to sign individual packets, as outlined in my previous message,
with obvious performance effects and _hopefully_ no security impact; as
I said before, formal security analysis is needed.)

The core system should nevertheless be the default: the signature system
that's applied directly to messages in all the situations where
compromise isn't necessary.

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

If a tiny device is capable of doing the job in one pass, great---but
engineers don't say "You want to sort a gigantic file? Inconceivable!"
Most user-visible computing tasks work with large amounts of data in
ways that simply don't fit a tiny-memory single-pass streaming model.
(Much more is possible with multiple passes.)

What's particularly vicious about the verification example is that at
first glance the job _seems_ to fit a streaming model, but doing the job
_securely_ does _not_ fit a streaming model (unless the algorithm signs
separate packets---which, as you note, is incompatible with the common
practice of giving users separate "signatures"; it requires that the
data flow work with "signed messages", as in the NaCl API). So people
provide streaming APIs for verification, and security disintegrates.

---Dan