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

[Andrey Jivsov <[e-mail]>]

On 05/20/2015 02:16 PM, 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.

What if M'=HMAC( K, M ) gets signed, where M is the input message, K is 
some derivation of the signing key, and size(M') is collision-resistant 
size (e.g. it's HMAC-SHA-256 for Curve25519)? For example, for EdDSA one 
would feed M' into its hash-twice method, not M or Hash(M).

This means that the hash size will need to be matched with the double of 
the equivalent symmetric bit length, but this is a well-accepted assumption.

This maintains the benefit of the IUF. The practical benefit of this 
method is that the attacker doesn't get to play with two arbitrary M1 
and M2 of his choice hoping to find a collision. The attacker must use 
the signer as an oracle.

I believe that the above idea can be tweaked to maintain IUF (perhaps 
change the HMAC, save a few hashings, etc...).

I vote for #1, and if not #1, then #3,

How can a protocol that uses smartcards in untrusted environments, a 
protocols without hard limit of message size, adopt #2 (see the attack 
in http://www.ietf.org/mail-archive/web/cfrg/current/msg06759.html ) ? 
This likely means that TLS is out, due to smartcard client 
authentication. I can see that #2 is helpful in X.509 certificates, but 
#1 with a tweak is an improvement that might be acceptable.

Major OpenPGP implementations use streaming mode to sign (e.g. in 'cat 
InFile | gpg --clearsign'), just as with encryption, without writing 
sensitive data to a temporary file. They depend on IUF. I haven't seen 
this with SMIME/CMS -- this is harder, but possible.