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

[Taylor R Campbell <[e-mail]>]

   Date: Wed, 20 May 2015 22:16:16 +0100
   From: Alexey Melnikov <[e-mail]>

   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.  Let's not repeat the error of RSASSA-PSS's reliance on collision
resistance which led to certificate forgery in the real world with MD5
collisions[1], and let's discourage anyone from designing denial of
service against verifiers into new protocols.

Given a deterministic signature scheme S_k(m) built on a hash function
F_r(m) needing only target collision resistance, it is easy to imagine
a randomized long-message signature scheme satisfied either by
signing-time entropy or by collision resistance of F_r: for a secret
key k and message m, randomly generate r and yield as the signature
`F_r' || S_k(`F_r' || F_r(m)).  The reverse is not so easy.

But while this scheme may be useful to put band-aids over legacy
protocols, it encourages designing protocols that admit denial of
service for verifiers.  Practical protocols involving large messages
should split them into parts that can be verified independently.

The best way to split signed messages likely varies from application
to application: signing numbered parts individually in sequence or
computing a Merkle tree of the parts using F_r and then signing the
root[2] are both plausible.  But there's no need for recommendation of
the basic underlying signature scheme to wait on standardizing these.


[1] Bellare & Rogaway's original PSS proposal, in `The Exact Security
of Digital Signatures -- How to Sign with RSA and Rabin' from
Eurocrypt'96, would have avoided the problem by relying only on target
collision resistance of a keyed hash function.  But RSA, Inc. broke it
when standardizing RSASSA-PSS for PKCS#1 in 2003, by unkeying and
derandomizing the hash function.

[2] For example, Tahoe-LAFS uses a signed Merkle tree for random
access to mutable files.  However, rather than randomly choose F_r per
message, it uses the fixed hash m |---> SHA-256(SHA-256(m)), so it
relies on collision resistance of SHA-256.