Re: [Cfrg] Elliptic Curves - signature scheme: randomised or not (ends on May 13th)

[Watson Ladd <[e-mail]>]

On Sun, May 3, 2015 at 9:24 AM, David Jacobson <[e-mail]> wrote:
> On 5/3/15 4:14 AM, Alexey Melnikov wrote:
>
> CFRG chairs are starting discussion of the next topic.
>
> The consensus view of the mailing list was that NIST compliance of our
> selected
> signature scheme is not necessary, opening up the opportunity for us to
> consider a rich class of signature schemes beyond ECDSA.
>
> Most if not all signature schemes defined over elliptic curves can be
> de-randomised by generating the "random" value used during signing in a
> pseudorandom manner from the message to be signed. This ameliorates some
> catastrophic failure modes for these schemes. The generation could involve
> using a PRF such as HMAC with a key designed solely for this purpose
> (resulting in an augmented private (signing) key). An alternative could be
> to hash a string consisting of a concatenation of the private (signing)
> key with the message to be signed. There are other possibilities too.
> Several methods are described in detail in RFC 6979
> (http://tools.ietf.org/html/rfc6979).
>
> To determine the way forward, we are going to conduct a poll to determine
> how we should tackle the question of de-randomisation. Please pick one of
> the
> options specified below:
>
> 1. CFRG should stick to randomised signature schemes only.
>
> 2. CFRG should adopt deterministic signature scheme only.
>
> 3. De-randomisation should be an optional feature for implementers to
> decide upon (i.e. both choices 1 and 2 allowed).
>
> Please address only this specific topic of de-randomisation at this time.
> Further topics will follow.
>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>
>
> If everyone did encrypt then sign (the recommended procedure), or sign then
> encrypt, identical plaintext would still be different in what was sent
> (assuming an nonce-like IV is supplied to the encryption).  If someone was
> foolish enough to do encrypt and sign, then there would be a need to make
> identical plaintext not have identical signatures.  If anyone feels that we
> need to accommodate this, then it would be good to allow an optional random
> input  (#4 as suggested by Andy Lutomirski in his response).

Is encrypt then sign really what is recommended? Remember that
public-key encryption is CCA2 secure, and that signatures are about
non-repudiability, not simply authentication The correct picture is
much more complicated: see
http://world.std.com/~dtd/sign_encrypt/sign_encrypt7.html for a
partial analysis. The correct constructions depend on the exact
security requirements.

Unlinkability of different signatures for the same messages is not
part of the standard security definition for signatures. It's not
enough to demand randomization: RSA signatures are trivially linkable,
even when randomized, and so are ECDSA signatures. The property you
claim is important isn't provided by today's signatures: either its
not important, or all sorts of things are broken.

Sincerely,
Watson Ladd

>
> A counter argument is that if you want to do something like that, you should
> just have your application include an application-level nonce in the
> plaintext, and not burden the signature standard with making identical
> plaintext have different signatures.
>
> So, amongst those listed I choose #2, but perhaps Andy's #4 should be
> considered.
>
>   --David Jacobson
>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.