Subject: Re: [Cfrg] Signature question ... [RE: Actual security levels for IETF crypto]

From: Paulo Sergio Licciardi Messeder Barreto <[email-masked]>
Date: Thu, 30 Oct 2014 23:12:27 -0200 (BRST)

> Message: 5
> Date: Thu, 30 Oct 2014 17:16:35 -0700
> From: Michael Hamburg <[email-masked]>
> To: Paulo Sergio Licciardi Messeder Barreto <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [Cfrg] Signature question ... [RE: Actual security
> levels
> for IETF crypto]
> Message-ID: <[email-masked]>
> Content-Type: text/plain; charset="utf-8"

> > On Oct 30, 2014, at 1:17 PM, Paulo Sergio Licciardi Messeder
> > Barreto <[email-masked]> wrote:
> >
> >
> > Date: Thu, 30 Oct 2014 13:55:12 -0400
> > From: David Leon Gil <[email-masked] <mailto:[email-masked]>>
> > To: Watson Ladd <[email-masked]
> > <mailto:[email-masked]>>
> > Cc: Dan Brown <[email-masked] <mailto:[email-masked]>>,
> > "[email-masked] <mailto:[email-masked]>" <[email-masked]
> > <mailto:[email-masked]>>
> > Subject: Re: [Cfrg] Signature question ... [RE: Actual security
> > levels
> > for IETF crypto]
> > Message-ID:
> > <[email-masked]
> > <mailto:[email-masked]>>
> > Content-Type: text/plain; charset=UTF-8
> >
> > On Thu, Oct 30, 2014 at 10:54 AM, Watson Ladd
> > <[email-masked] <mailto:[email-masked]>> wrote:
> > > While the above is certainly interesting theoretically, I doubt
> > > it
> > > matters practically. Schnorr signatures have been intensively
> > > studied
> > > for many years, with no attacks, as have ECDSA.
> >
> > Agreed: But I prefer security reductions to the absence of attacks,
> > where at all possible. The former proves security; the latter only
> > proves a lack of cleverness.
> >
> > > The question is one over how annoyed you want the implementor to
> > > be,
> > > when they have to try to make a constant time inversion modulo an
> > > ugly
> > > prime.
> >
> > Well, doing arithmetic modulo an ugly prime is already necessary
> > for Schnorr.
> >
> > And if you read the Katz et al. paper, you will see that signing
> > does
> > not require performing an inversion mod #K.
> >
> > The Katz et al. scheme is a direct variant of Schnorr, *not* of
> > ECDSA. It also requires *two* exponentiations for signing, which
> > is worse than doing an inversion. It is also inferior on all
> > accounts to Shao's variant of Schnorr [Shao], whose security
> > reduction is as tight as it can be (and it requires a single
> > exponentiation and no modular inversion, just an extra hash, with
> > negligible computational overhead).
> >
> > P.
> >
> > --
> >
> > [Shao] Z. Shao, A provably secure short signature scheme based on
> > discrete logarithms, Information Sciences 177(23), 2007, pp.
> > 5432--5440, Elsevier.
> > <http://www.sciencedirect.com/science/article/pii/S0020025507002757
> > <http://www.sciencedirect.com/science/article/pii/S0020025507002757>>

> That sounds really useful. Do you have a quick description for those
> of us who aren?t at a university?

> Thanks,
> ? Mike

Sure. Here you go (I presume you want to know the algorithmic differences, not the security reduction right now). 

Let <G> be the underlying group (in additive notation) of order q. Key pairs are (s, V) where s is sampled uniformly from Z/qZ, and V = s*G. Let H: {0,1}^* x <G> -> Z/qZ and F: {0,1}^* -> <G> be random oracles. 

To sign a message m, sample k uniformly from Z/qZ; then, while Schnorr would compute R = k*G, Shao computes R = k*G + F(m), and after that both compute h = H(m, R), z = k - h*s (mod q), and the signature is (h, z). 

To verify a signature (h, z) for m, while Schnorr would compute R = z*G + h*V, Shao computes R = z*G + h*V + F(m), and after that both check whether H(m, R) = h. 

There are a few practical considerations here. The computation of F(m) and H(m, .) might involve a single underlying hash whose internal state (assumed to be large enough) is divided in two pieces right after m has been processed; one piece is finalized to yield F(m), the other is extended to process R (a modern sponge could do it more easily). So the overhead is essentially one group mapping and one addition; the cost is less than two scalar multiplications, and it does not require additional randomness. 

Besides, the security reduction only requires H to be preimage-resistant, not collision-resistant, so that its size could in principle be half that of the ECDSA hash size for the same security level; the shorter h may also reduce a bit the verification time. 

P.

---

From: Mike Hamburg <[email-masked]>
Date: Thu, 30 Oct 2014 21:33:07 -0700

On 10/30/2014 6:12 PM, Paulo Sergio Licciardi Messeder Barreto wrote:
>     Subject: Re: [Cfrg] Signature question ... [RE: Actual security levels
>             for IETF crypto]
>     > Cc: Dan Brown <[email-masked]
>     <mailto:[email-masked]>>, "[email-masked]
>     <mailto:[email-masked]>" <[email-masked] <mailto:[email-masked]>>
>     <[email-masked] <mailto:[email-masked]>>
>     > > While the above is certainly interesting theoretically, I doubt it
>     > > The question is one over how annoyed you want the implementor
>     to be,
>     > > when they have to try to make a constant time inversion modulo
>     an ugly
>     > > prime.
>     >
>     > [Shao] Z. Shao, A provably secure short signature scheme based
>     on discrete logarithms, Information Sciences 177(23), 2007, pp.
>     5432--5440, Elsevier.
>     <http://www.sciencedirect.com/science/article/pii/S0020025507002757 <http://www.sciencedirect.com/science/article/pii/S0020025507002757>>
>
>     That sounds really useful.  Do you have a quick description for
>     those of us who aren?t at a university?
>
>     Thanks,
>     ? Mike
>
>
> Sure. Here you go (I presume you want to know the algorithmic 
> differences, not the security reduction right now).
>
> Let <G> be the underlying group (in additive notation) of order q. Key 
> pairs are (s, V) where s is sampled uniformly from Z/qZ, and V = s*G. 
> Let H: {0,1}^* x <G> -> Z/qZ and F: {0,1}^* -> <G> be random oracles.
>
> To sign a message m, sample k uniformly from Z/qZ; then, while Schnorr 
> would compute R = k*G, Shao computes R = k*G + F(m), and after that 
> both compute h = H(m, R), z = k - h*s (mod q), and the signature is 
> (h, z).
>
> To verify a signature (h, z) for m, while Schnorr would compute R = 
> z*G + h*V, Shao computes R = z*G + h*V + F(m), and after that both 
> check whether H(m, R) = h.
This is the same thing as Schnorr with H'(m,R) := H(m, R+F(m)), which is 
indifferentiable from a random oracle anyway.  So, it's exactly as 
secure as Schnorr, but slower.

"Ah, but it's provably secure with a tight reduction!", you might say.  
No it isn't.  A colleague of mine has kindly provided me with a copy of 
the paper.  The argument presented at the bottom of the 7th and the top 
of the 8th page in favor of the tight reduction is, to use a technical 
term, bullshit.  It's not merely wrong: the author knew it was wrong, 
and wrote it anyway.

Essentially, the author says that with some probability delta, the 
attacker forges a message by calling H first and F second (unlike a real 
signer, who always calls F first); this leads to a tight reduction.  
With probability 1-delta, the adversary calls F first. The author admits 
that if delta = 0, the reduction is loose. Intuitively, we would expect 
an adversary to call F(m) before H(m,R), since R is supposed to depend 
on F(m) and m is known anyway when calling H(m,R).  So delta ought to be 
0.  But the author "eclectically" assumes that, since the adversary is 
randomized, you can just let delta = 1/2, in which case the reduction is 
still tight.

In fact, the author knows that the reduction isn't tight, which is why 
the claims throughout the paper are that the signature scheme is 
"closely, if not tightly, related to the difficulty of solving discrete 
logarithms"; that "epsilon' \approx [tight reduction]" instead of 
"epsilon' >= [tight reduction]"; and that the reduction might be called 
"between loose and tight".

Thanks anyway though,
-- Mike
> There are a few practical considerations here. The computation of F(m) 
> and H(m, .) might involve a single underlying hash whose internal 
> state (assumed to be large enough) is divided in two pieces right 
> after m has been processed; one piece is finalized to yield F(m), the 
> other is extended to process R (a modern sponge could do it more 
> easily). So the overhead is essentially one group mapping and one 
> addition; the cost is less than two scalar multiplications, and it 
> does not require additional randomness.
>
> Besides, the security reduction only requires H to be 
> preimage-resistant, not collision-resistant, so that its size could in 
> principle be half that of the ECDSA hash size for the same security 
> level; the shorter h may also reduce a bit the verification time.
>
> P.