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

[Simon Josefsson <[e-mail]>]

Alexey Melnikov <[e-mail]> writes:

> Chairs wish to poll the group on the following topic (please pick one):
>
> #1: The signature scheme should follow the traditional model of hashing
> the message to be signed, thus trivially supporting IUF APIs in
> constant-space, at the cost of requiring collision resistant hash
> functions.
>
> #2: The signature scheme should not depend on collision resistance, at the
> cost of the signing algorithm having to buffer messages to be signed.
>
> #3: option #2, but with an additional "large message" mode defined for
> protocols that feel that they need it, where the message to be signed is
> actually a hash of the true message.

#2: The signature scheme should not depend on collision resistance.

The part "at the cost of the signing algorithm having to buffer messages
to be signed" appears like speculation to me, and I disagree with it.

The majority of use-cases I am aware of sign short messages.

The use-cases that sign large messages I am aware of are those that sign
offline files.  The OpenPGP EdDSA draft already deals with this issue --
see https://tools.ietf.org/html/draft-koch-eddsa-for-openpgp-02 -- since
the OpenPGP framework essentially already provide the #3 "large message
mode".  S/MIME can do the same.  I cannot recall other significant
"large file" signing frameworks.

Thus, I don't think the CFRG has to solve the "large message" problem,
at least not until some other technology requests that from us.  OpenPGP
has already solved it.  Solving problems before they exist is rarely a
good idea.

The "large message" concern and the "low memory" concern are really two
different problems, and they don't necessarily have the same solution.
Thus, I'd like to comment on your text that leads up to the question:

> Alternatively, some signature schemes hash the message to be signed
> twice, where a prefix of the second hash depends on the result of the
> first.  Ed25519 is an example of a scheme of this type. This typically
> allows the signature scheme to require fewer assumptions about the
> strength of the hash function that is employed. However, this approach
> implies that the signing algorithm would have to buffer the entire
> message. That could lead to unacceptable memory usage for applications
> that sign very large messages.

I don't agree with this.  The signing implementation does not have to
buffer the entire message.  There are several ways to solve this:

1) The application could hash the message before signing, using a
traditional hash like SHA256.  Then the signature scheme itself does not
rely on collision resistance, and the signing algorithm does not have to
do buffering.

2) The signing algorithm could have a different API and put the burden
on the caller to deal with this aspect.  By changing how the API looks
and how the application works, it is possible to avoid buffering the
entire message -- for example the application could seek through the
data stream twice when doing the signature.

Still, I believe this is a moot issue since any high-level application
that has the "large message" concern will solve this like OpenPGP does.

/Simon