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

[Stephen Farrell <[e-mail]>]

I'd hate to miss one of Alexey's polls:-)

I'm almost neutral on this one. While we have historically preferred
#1 for the reason noted in the subject line, there are really very few
cases where that turns out to be a real issue, as opposed to being a
theoretical one.

So I think we could probably live with #2, and that could suffice for
TLS and DNSSEC and other applications, even though #2 would mean
that users of the signature scheme (e.g. IETF protocol developers) may
need to learn something new, which is a downside.

While #3 seems superficially attractive, my guess is it'd cause more
confusion and interop issues, and is of course offering a choice to
users of the scheme and so I don't like that one:-)

So put me down for (#2 or #1) for this one, with a very very tiny
preference for #2 and documenting that one ought not use this for
signing large things directly (which one probably ought not do in any
case). But #1 would also be an acceptable outcome from my POV since
we're in practice already dependent on the collision resistance of
all the relevant hash functions and that won't ever really go away
as long as there are RSA/SHA256 certificates out there which'll be
the case for years and maybe decades to come. So the security
benefit of #2 isn't so great, although it's real.

If, later on, there is a real need for signing a large thing in a very
memory constrained device, or for verifying such a signature in such a
device, then we could always just define another set of codepoints
and OIDs, etc. for that and treat it as just another signature scheme
that happens to involve the same curve and hash function but used in a
different manner. (And I would guess there'll be more work to do in
this space, if not for that, then for a signature scheme with message
recovery, probably for the just-forming cose wg would be my bet at
the moment, but we'll see what we see.)

Cheers,
S.

On 20/05/15 22:16, Alexey Melnikov wrote:
> Signature schemes have, traditionally, hashed the message to be signed to
> a representative value and then actually signed that value. This has led
> to APIs that follow the Init, Update*, Final (IUF) pattern that allows for
> fragmented or very large messages to be signed with constant memory usage.
> 
> 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.
> 
> Penalising large messages might be seen as a positive by some because
> signing arbitrarily large messages invites implementations to process
> unauthenticated data because of its potential size. Also, designs that
> really wish to do this can always define that the message to be signed is
> actually a hash of the data. In doing so they would reintroduce the
> requirement that the hash function be collision resistant, but can
> implement an IUF API in constant space again.
> 
> On the other hand, if we wish a signature primitive to be easy to
> substitute into existing protocols then supporting a constant-space IUF
> API might be seen as a requirement.
> 
> 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.
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>