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

[Nico Williams <[e-mail]>]

I had been concerned with the signing side in my earlier posts.  I agree
that the verification side cannot be online regardless.  An online
signer can be useful because of HSMs and such.

On Sat, May 23, 2015 at 12:41:31AM -0000, D. J. Bernstein wrote:
> How long are the messages that are actually signed in IETF protocols?

There are at least two cases where online signatures are useful:

 - when signing bulk data (e.g., CMS, PGP);

 - when signing a communication transcript of more than two consecutive
   messages and the service needs to be stateless, putting the state in
   an encrypted state cookie.

   (A good example here is Kerberos KDC exchanges.)

In the latter the state cookie's size grows as the exchange grows.  (I'm
not sure that this is actually a problem, or that it will be.)

> For the protocols where the answer is uncontrolled: Do implementations
> allow messages that don't fit into memory? How do those implementations

It's not just memory, but I/O and performance, as well as interface
design considerations.

Signing a file can be done with much less memory than the file's size,
reading a block at a time and reading the file twice (in the case of
EdDSA).

Someone mentioned HSMs, for example.  An HSM interface to support
off-line signatures like EdDSA would require passing the message to the
HSM twice when the message doesn't fit in the HSM's memory.

It's also not just IETF protocols of today.  Imagine a filesystem where
there's a "commit" operation and where files are signed by the last
writer...  Random access writes go out the window with an off-line
signature scheme unless we're using something like a Merkle signature
tree.  You proposed something like that earlier, and pointed out that
we'd need security proofs.  Intuitively a Merkle tree of signatures
should work.  (Filesystems effectively implement a tree, and filesystems
like ZFS implement a Merkle hash tree, so a Merkle signature tree would
fit right in.)

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

No matter what, complete signature verification must be required prior
to processing the signed data.  This means that verification is never
online.  I was only concerned with the signing side in my previous
messages.

The verifier side is easier than the signer side in that at least we
don't have to worry about HSMs.

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

Yes.

Nico
--