Subject: [Cfrg] FW: [TLS] Schnorr Signatures

From: Dan Brown <[email-masked]>
Date: Wed, 25 Jun 2014 19:28:58 +0000

Hi Nigel,
I'm forwarding a portion of your message to the CFRG list, to discuss some 
details which might be too theoretical for TLS to hear a debate upon.
See below for discussion points.
Best regards,
-- Dan

> From: Nigel Smart
> Sent: Wednesday, June 25, 2014 4:29 AM
> To: [email-masked]
> Subject: [TLS] Schnorr Signatures
>
> As we are moving to TLS 1.3 I wondered why not include EC-Schnorr signatures
> in the standard as a possible addition to EC-DSA for the signing.
> Some notes...
>
> iv) Has a proper proof of security and not "tainted" by NSA design
>             - Unlike EC-DSA in both instances.

iv-1) What's improper about the ECDSA security proofs?
iv-2) Can you cite the proofs for Schnorr?  I'm aware of Pointcheval-Stern, 
which uses random oracle model, with forking lemma, which is rather a loose 
reduction.  Is there a standard model proof, or a tighter reduction?  Iv-3) 
Long ago, I wrote up a proof for Pintsov-Vanstone signatures, on which 
Certicom has IPR and which can viewed as an extension of Schnorr signatures. 
I must doubt your referring to that.

>   v) Protects against hash collisions. i.e. any hash function break 
> involving
>       collisions does not provide an attack on the signature scheme.

v-1) NIST has recommend randomized hashing for when collisions are a risk.
v-2) I've always presumed that the way TLS uses signatures to authenticate the 
handshake does not expose the signer to a chosen message attack and hence hash 
collision risk: the signer (usually the server) has enough influence over the 
message content to render a generic collision attack infeasible.  On the other 
hand, MD5 collisions have been used to forge certificates: I think that attack 
somehow exploited the attacker's freedom of choosing the tail of the signed 
message.  Perhaps, some details in the way that TLS sign things allows 
chosen-message attacks. I will into it, though perhaps somebody here knows 
off-hand.

---

From: Nigel Smart <[email-masked]>
Date: Thu, 26 Jun 2014 08:22:38 +0100

Hi Dan

Comments embedded below...

> iv-1) What's improper about the ECDSA security proofs?

I would say that whilst the proofs of ECDSA in the generic group model 
are correct,
the problems that are reduced to etc are a bit "unnatural". That is a 
personal preference
I admit.

Having the proofs for ECDSA is better than nothing, but schemes with 
more natural
proofs I think should be preferred.

> I must doubt your referring to that.

The P-S proof is I think a good design validation for Schnorr. Basically 
Schnorr is designed
following general principles; take an ZK identification scheme and apply 
the Fiat-Shamir
heuristic. ECDSA on the other hand is an ad-hoc one off design. The P-S 
proof has been
improved by various people; Neven and Bellare I think looked at it a 
while back (might
be wrong re authors here).

A generic group based proof, along the lines of your proof for ECDSA, 
was done by
Neven, Warinschi and myself. We reduce to relatively "natural" problems 
associated
to the hash functions (and not collision resistance). Some of these 
problems are
related to the categorization of hash function properties of Rogaway and 
Shrimpton
if memory serves me correct.

> chosen-message attacks. I will into it, though perhaps somebody here knows

I think the main benefits of Schnorr are
    i) Cleaner design
   ii) Shorter signatures (you dont send r you send half the hash value)
  iii) No division by k in the signing equation (both easier to 
implement, and allows other
        things to be done on the signing side to enhance security)
  iv) Better proofs (although this is a subjective statement)

For these reasons we recommended Schnorr for use in the new EMV 
standard, which
seems to be what they are going to adopt.

I am not saying REMOVE ECDSA for TLS 1.3, just it would be good to 
include Schnorr
as an option.

Yours

Nigel

---

From: Dan Brown <[email-masked]>
Date: Thu, 26 Jun 2014 15:44:37 +0000

As ECDSA and other ECC signatures become more widely deployed, it makes
sense for theorists to revisit the security proofs (*), so I will go into
some gritty detail below.  I won't go into the proofs themselves, but I will
discuss the claims proved, including the assumptions that are made.

(*) I'm not implying that theory and proofs are everything: they are just
one dimension to consider.

> From: Nigel Smart 
> 
> I would say that whilst the proofs of ECDSA in the generic group model are
> correct, the problems that are reduced to etc are a bit "unnatural". That
is a
> personal preference I admit.

It sounds as though you're giving me the benefit of the doubt on the proof
correctness, but addressing deficiencies in the quality of results proved
(or claimed).  So, I discuss the latter here.  

I'm not sure if you're just saying that that the generic group model itself
is unnatural.  I regard it and the random oracle model as equally unnatural,
but I agree that it is party a matter of preference.  I also strongly prefer
standard model proofs, and well-studied assumptions.  

But you say above "reduced" above, which suggests to me that you are *not*
referring to the generic group model, but rather standard model assumptions
about the hash function, i.e. these hash function problems are reduced to
forging ECDSA.  In that case, you're saying that the hash assumptions are
unnatural, so I discuss these assumptions.

Specifically, I refer to the three generic-group model ECDSA security proofs
from

http://eprint.iacr.org/2002/026   

These make use of 5 standard model assumptions about the hash function,
which I discuss below:

1)2)3) Three of these assumptions: preimage-resistance, second-preimage
resistance and collision resistance seem well-known and natural.  I presume
you are not saying these are unnatural.

4) The fourth is zero-finder-resistance, which concerns the problem of
finding a message M such that h(M) = 0 mod n (where n is the order of G).

Zero-finder-resistance hash assumption is needed to avoid an attack.
Alternatively, ECDSA could be amended to consider the signature of any such
message to be invalid, by truncating the hash by an extra bit to force it
smaller than n.

It's true that zero-finder-resistance property is not usually considered for
hash functions and that its use of n in its definition is unnatural.
Nonetheless, it seems very reasonable for secure hash functions *provided* n
was chosen in advance of M.  If n is chosen after M, as in Vaudenay's domain
parameter attack, then it becomes a property of the group.  Hence it is
necessary to provide countermeasures to this attack in the choice of group,
or the signature as alluded to above.

This raises the question to me: how does EC-Schnorr avoid requiring
zero-finder resistance?  It would seem to depend specific details of
EC-Schnorr, which I don't know off-hand.  I will check your
generic-group-proof paper and the standard, but perhaps you already know the
answer.  

In one back-of-the-envelope version of EC-Schnorr that I'd imagine, suppose
the hash h' has the odd property that for some key k0 and message M0, we
have h( [k0]G , M0) = 0.  If the signing equation is s = k + de, where k is
the ephemeral and d the static private key, then (0,k0) is a valid signature
for any public key.  This is about the same situation for ECDSA.  But maybe
some detail saves EC-Schnorr from this hypothetical attack.  If not, then
maybe your security proofs have found some natural hash function property
that implies this zero-finder-resistance property.  If so, then maybe I will
look into applying that property to ECDSA.

5) The last assumption is uniformity of the hash function, which is used in
Theorem 3.  This is not a usual assumption, but still seems a very modest
assumption. Often some variant of this assumption implicit assumed, for
example, in arguments that collision resistance implies some forms of
preimage resistance.  For example, Stinson notes a similar assumption in his
study of hash function properties.  So, as far as I can tell, this property
is not needed to avoid an attack, but rather just for making a proof go
through.  In hindsight, I would have tried harder to re-do the proof without
using the uniformity assumption.

Finally, the proofs are stated in a generalized way that includes both DSA
and ECDSA, which requires making assumptions about the "conversion"
function.  The paper shows that these assumptions hold for ECDSA, so they
are no longer just assumptions.

---

From: Dan Brown <[email-masked]>
Date: Fri, 27 Jun 2014 15:47:50 +0000

I've been looking at the Neven-Smart-Warinschi (NSW) paper:
http://www.neven.org/papers/schnorr.pdf
I recommend other CFRG members here interested in signature algorithms look
at this paper too.
First of all, I quite like the paper: it's very clear.  It discusses
conditional attacks, not just security proofs, which I think is helpful. I
discuss the conditional attacks below.

The NSW paper proves that the hash in Schnorr signature must be (chosen
target) random-prefix preimage (RPP) resistant.  
I agree with the NSW paper that this seems a plausible and natural
assumption, and noteworthy in that it has already been studied by Kelsey and
Kohno in the "herding" attack on hash functions.
I wish to emphasize here that if the hash falls to an RPP attack, then
Schnorr falls to a universal no-message forgery, which is the nearly the
most severe attack possible (more severe would be private key recovery if
that private key is used for other applications).

Though I only looked today, I did not see how an RPP attack could be used to
get a universal no-message forgery attack on ECDSA.  So, on that theoretical
aspect, ECDSA may fare better than Schnorr.  
But, conversely, ECDSA falls to a universal no-message forgery if the hash
can be inverted, for random preimages, or if a zero (mod n) can be found in
the hash.  Such a hash attack does not seem to lead to a universal
no-message forgery against Schnorr, as far as I can tell so far.  So, in
that regards, Schnorr fares better.
 
To summarize, for the most essential form of security, ECDSA and Schnorr
require different properties of the hash given respectively below (using
comparable names):
random-target preimage resistance + special-fixed-target preimage resistance
(for ECDSA)
chosen-target random-prefix preimage resistance (for Schnorr)
Questions: which is more reasonable?  Can one be proved in terms of the
other?  
I'm not hopeful that the answer will be found in the Rogaway--Shrimpton or
Andreeva--Stam followup work on hash functions, because these focus of keyed
hash functions.

Aside 1: as to provable security, in the general group model these hash
functions properties have been to the universal no-message unforgeability.
One can also look at how "tight" these reductions, and so on.  I have not
looked at that issue yet.  Anyway, I digress, since I wanted this email to
stay on the topic of conditional attacks.