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

From: Dan Brown <[email-masked]>
Date: Wed, 29 Oct 2014 14:25:56 +0000

> From: Cfrg [mailto:[email-masked]] On Behalf Of Watson Ladd
>Curve choice matters less then point format and signature issues where we are 
>also disappointingly far from agreement. Or maybe we are close enough that no 
>one bothered to respond beyond Andy Lutomirski because the answers were 
>obvious.

Hi Watson,

I didn't respond to your question on signatures because the CFRG chairs asked 
us to focus on curve choice.

Nonetheless, I'll briefly answer your questions, in case you infer too much by 
the lack of response.

I slightly prefer ECDSA over Schnorr for provable security reasons: 
specifically in the generic group model, ECDSA relies on standard hash 
function assumptions whereas Schnorr does not.  I haven't studied other 
options like ECKDSA and ECGDSA and a quite a few others.  I have briefly 
studied a variant of Schnorr called Pintsov-Vanstone signatures, which adds a 
block cipher into the mix.  I've also heard about Goh-Jarecki signatures, 
which rely on the ECDH problem, but I haven't looked closely at it: I don't 
know how efficient it is.

If one worries about collisions and chosen-message existential forgery against 
ECDSA, or one just prefers loose random oracle model proofs, then one can add 
randomized hashing to ECDSA, which seems to combine the best of ECDSA and 
Schorr, in terms of security. There's even a NIST spec for that.

A free specification of ECDSA is available in SEC1 version 2.0, which has some 
additional formatting options that make batching, etc, feasible.

I agree with others that, in many cases, signatures are not needed for 
authentication.  For example, in an interactive setting, or when the recipient 
has a public key (aside: even for RSA public keys).  Actually, I already 
suggested to CFRG that consider using ECMQV for TLS and similar IETF 
protocols, which means no signatures.  There's also the option of using 
implicit ECQV certificates instead, as in SEC4, instead signature-based 
certifcates  -- (but there's one important item of research that I mean to 
write up about that!)

Best regards,

Dan

---

From: David Leon Gil <[email-masked]>
Date: Wed, 29 Oct 2014 13:49:34 -0400

On Wed, Oct 29, 2014 at 10:25 AM, Dan Brown <[email-masked]> wrote:
> function assumptions whereas Schnorr does not.

What are you talking about?

[Neven et al.] give a reduction for Schnorr that is, IIRC, tight for,
e.g., Ed25519-SHA2-512 in the generic group model.

A collision-resistant hash-function is sufficient. Chop(SHA2-512,
256), which is what Ed25510-SHA2-512 uses, satisfies a stronger
property: It is indifferentiable from a random oracle. See [Coron et
al.]

[Neven et al.] on the randomized prefix second-preimage assumptions:
"Both of the above assumptions are directly implied by the collision
resistance of H, a result which we leave to the reader[.]" (Perhaps,
in fact, this is not true?)

And their proof obviously goes through fine with a hash function
indifferentiable from a random oracle; both SHAKE and Blake2 have been
designed to satisfy this property. [Coron et al.]

--

However, the [Neven et al.] reduction is, I think, non-tight for
Ed25519-SHA2-512's parameters with just the RO assumption. [Seurin]

There are, in fact, signature schemes with tight reductions to CDH.
E.g., [Katz et al.] gives a reduction for a variant of
EDL-Chaum-Pedersen which is tight to CDH in the RO model; it requires
hashing to a curve, but recent results have showed this can be done
cheaply.[*]

I'd prefer a scheme of that sort for standardization to Schnorr,
especially given Seurin's meta-reduction for the latter.

--

[Seurin]: http://eprint.iacr.org/2012/029 "On the exact security of
Schnorr-Type signatures in the random oracle model"
[Neven et al.]: http://www.neven.org/papers/schnorr.pdf "Hash function
requirements for Schnorr signatures"
[Katz et al.]: https://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf
"Efficient signature schemes with tight reductions to the
Diffie-Hellman problems"
[Coron et al.] http://www.cs.nyu.edu/~dodis/ps/merkle.pdf
"Merkle-Damgard revisited: How to construct a hash function"

--

[*] The cheapest option to hash onto a curve is, perhaps, to use an
IRO PRF and take the first fragment of its output that is on the
curve; this is fast for all but a super-exponentially small fraction
of points. (So always, in practice.)

---

From: Watson Ladd <[email-masked]>
Date: Thu, 30 Oct 2014 07:54:41 -0700

> designed to satisfy this property. [Coron et al.]

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. The alternatives you
mention are significantly less efficient, for no gain in security.
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.

What I'm much more interested in is the choice of point formats, and
whether to recommend the use of Montgomery form or not. There are real
security benefits to Montgomery ladders: nearly impossible to screw
up. There are similar benefits to the use of compressed points.

There's also the question over how much transmitting Weierstrass
points will improve adoption, and how much it will hurt security due
to incomplete formulas being a natural choice, and the persistent
temptation to use these formulas for everything. I'm increasingly
coming around to the advantages, but this assumes that cofactors won't
be a problem for implementations, which sadly isn't actually true all
the time. Adding the isomorphism is a minor problem, but does make
existing, deployed Curve25519 code incompatible.

We'll need to carefully explain how to eek reasonable performance from
the new curves, which is an area where this WG has fallen flat on its
face before. (See RFC 6090 errata for details, and ensuing discussion
of how the formulas presented weren't the most efficient ones, even if
the correct ones had been presented).

We need to address these questions *regardless* of which formulas get
picked: it's not clear to me we have consensus on *any* of these.

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 30 Oct 2014 17:27:47 +0200

On Thu, Oct 30, 2014 at 07:54:41AM -0700, Watson Ladd wrote:
> temptation to use these formulas for everything.

IMO, none (adotpion) and a lot (security).

Looks like TLS v1.3 will go with fixed-per-group-format DH, which can
easily take even the most bizarre formats (even if there is currently
255 byte limit for ECDH).

And I don't think backport into TLS v1.2 would be difficult (violates
RFC 4492, but one can overrule the offending parts of that without
interop trouble[1]).

As for cofactors, Weierstrass coordinates won't help with those.
And besides, everything important should be able to deal with
cofactors anyway.

[1] Make it work like it does in v1.3.

-Ilari

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Thu, 30 Oct 2014 15:33:00 +0000

>IMO, none (adotpion) and a lot (security).

AFAIK, whatever code exists now in released/deployed products, it uses
Weierstrass points. Thus, IMHO it would improve adoption a lot. As for
security - it could improve it because Weierstrass curves tend to have no
cofactors.

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 30 Oct 2014 17:47:15 +0200

> security - it could improve it because Weierstrass curves tend to have no

No existing software has these new curves nor does any existing software
have TLS v1.3.

And it is really easy to screw up Weierstrass implementation (heck, even
RFC 6090 got it wrong). Also, allegedly some implementations have
a presentation for infinity, which is a VERY nasty surprise.

-Ilari

---

From: Yoav Nir <[email-masked]>
Date: Thu, 30 Oct 2014 17:57:39 +0200

> On Oct 30, 2014, at 5:47 PM, Ilari Liusvaara <[email-masked]> wrote:
> 

+1 about adoption.

Currently my code can do exactly three NIST curves and generates point representations as they are required in IKE and TLS.

Adding anything will require writing or copying a bunch of new code. It’s true that if we keep Weierstrass points I may need to write or copy less code, reducing the time I spend on writing it.  But getting these new curves into the product requires adding support for using the new code in TLS and IKE, UI, testing, documentation, test cycles with other implementations. Every one of those things totally dominates the time I spend writing or copying the code, and none of them is in any way affected by point format.

So without expressing any opinion on which is better, saving the likes of me some work should not be a consideration.

Yoav

---

From: Watson Ladd <[email-masked]>
Date: Thu, 30 Oct 2014 09:02:17 -0700

> a presentation for infinity, which is a VERY nasty surprise.

Furthermore, the small-subgroup confinement attack only works when
transcripts aren't hashed. But this needs to happen anyway. Existing
standards use cofactor 1 for efficiency, not security.

However, some code on HSMs supports specified curves in Weierstrass
form. For PKIX this may be advantage on uptake. But yes, it's marginal
when we talk about specialized per-prime code etc, none of which is
compatible with specified curves.

Really, I feel like I could replace myself with a perl script that
reposts DJB's emails to the list and have a similar effect on the
conversation: I think this email I'm sending now is his email from 2
August.

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Thu, 30 Oct 2014 16:33:22 +0000

>standards use cofactor 1 for efficiency, not security.

I’ve been a *long-time fan* of HMQV-type protocols.

But alas, the patents aren’t likely to allow developers to write and
vendors to deploy them for quite some time. :-(

>form. For PKIX this may be advantage on uptake.

Yes.

>But yes, it's marginal when we talk about specialized per-prime code etc,
>none of which is

I don’t know. Yoav seems to agree with you here. I’d like to hear from
hardware manufacturers though.

>conversation: I think this email I'm sending now is his email from 2

You noticed it too? :-) :-)

---

From: David Leon Gil <[email-masked]>
Date: Thu, 30 Oct 2014 13:55:12 -0400

On Thu, Oct 30, 2014 at 10:54 AM, Watson Ladd <[email-masked]> wrote:
> 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.

> when they have to try to make a constant time inversion modulo an ugly

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.