Subject: [Cfrg] Signatures: curves, algorithms, etc

From: Tony Arcieri <[email-masked]>
Date: Tue, 27 Jan 2015 13:33:16 -0800

I would like to hear the opinions of the chairs and other CFRG participants
on the following:

- Ed25519 and EdDSA
- FrankenECDSA (ECDSA in Edwards)
- ECDSA with Edwards keys on the wire (converted to Weierstrass to do ECDSA)
- Other interesting thoughts on digital signatures

-- 
Tony Arcieri

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 28 Jan 2015 09:19:26 +0000

On 27 January 2015 21:33:16 GMT+00:00, Tony Arcieri <[email-masked]> wrote:
>I would like to hear the opinions of the chairs and other CFRG participants on the following:

Not to detract from the other fascinating discussions, but yes, I do think it is a good idea to get some groundwork discussion started to avoid *too much* delay.

>- Ed25519 and EdDSA

Well, *I* like it. Seems to have attained some external traction, too: OpenBSD, GnuPG, OpenSSH, for a start.

Positives:
• Already fast, high-quality, constant-time existing implementations in software (and some hardware, too).
• Deterministic signatures = test vectors!  No need for signer or verifier themselves to have random sources! Win.
• As deployed uses SHA-512, a well-known mature hash function with plenty of hardware and software support that's weathered fairly well. (Can potentially use any other.)
• Potentially batchable.

Negatives:
• As deployed uses SHA-512, an NSA algorithm, not the fastest or best now that SHA-3 competition is over, with some potential length-extension issues to watch for. (I'm not too worried about this. SHA-2 is not backdoored, to the best of my knowledge.)
• Hash double width of curve. I get why, and I think it's very careful and sensible, but this complicates extending EdDSA to other curves (say, a >=WF192 curve), as hashes with outputs that large are uncommon. SHAKE256 might be suitable, but I'm not too sure how I feel about that.
• Batch verify may exhibit side-channels?
• Old hardware hard-coded (i.e. not firmwared) to ECDSA is SOL. (I don't see this as a significant negative, if we want something new and better, we make it.)

>- FrankenECDSA (ECDSA in Edwards)

I'm not totally clear on the details of what this suggestion actually *is*, or its relative advantages/disadvantages. Someone fill me in?

>- ECDSA with Edwards keys on the wire (converted to Weierstrass to do ECDSA)

Ugh. All the disadvantages of ECDSA and few, perhaps none, of the advantages of new curves. I don't like this option much.

Positives:
• Existing hard-coded hardware can perhaps be jury-rigged to do it

Negatives:
• That means we can't mandate/test deterministic nonces
• Carries trust of existing 'validated' hardware forward, though that is in external doubt
• Overhead of wire format conversion

>- Other interesting thoughts on digital signatures

Can whatever we do please be (mandatory) deterministic with test vectors, at least?

Do we have any better ideas?

Feel free to correct me/discuss!

- --
/akr

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 28 Jan 2015 12:48:31 +0200

On Wed, Jan 28, 2015 at 09:19:26AM +0000, Alyssa Rowan wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
> 

When I implemented something that captures Ed25519 as special case, I
used more aggressive rule of 64 extra bits rounded up to hash output
size, which can just use 512-bit hash even with Ed448-Goldilocks.

But for E-521, it overflows 512 bits (uses 1024 bits (505 extra
bits) with 512-bit hash).

For when one needed output exceeding blocksize, that implementation
caluclated: H(0x00|<data>)|H(0x01|<data>)|H(0x02|<data>)|... with
however many hashes required.

It also did implement one 1024-bit hash (Skein-1024, was a SHA-3
finalist)

> • Batch verify may exhibit side-channels?

I think it definitely does have side-channels.

> I'm not totally clear on the details of what this suggestion actually *is*, or its relative advantages/disadvantages. Someone fill me in?

Basically, taking x-coordinate mod l of Edwards point as r, instead of
x-coordinate mod l of Weierstrass point, like ECDSA itself does.

+ All curve calculations in Edwards domain.
- Still has the annoying scalar inversion.
- Non-deterministic (as specified)
 
> • Overhead of wire format conversion

Actually, I don't think it will work with existing hardware. The problem
is dealing with the Edwards keys.

I have actually implemented full ECDSA (complete with SEC1 Weierstrass
keys, but using deterministic nonces) with Curve25519 (and some other curves).
Coding up the conversion of Weierstrass points to Edwards points wasn't
pleasant, but still lots more pleasant than trying to implement Weierstrass
arithmetic (even with no sidechannel protection).

Booby traps:
- Signing: Random nonces.
- Signing: Sidechannels from trying to use generic curve.
- Signing: Sidechannels from sclar inversion.
- Verification: Weierstrass is complicated and pretty easy to get wrong.

> Do we have any better ideas?

I looked what it would take to add EdDSA to TLS (AFAICT):

- Defining EdDSA itself.
- Adding TLS SignatureAlgorithm codepoint for it (Expert Review)
- Adding Signature Algorithm OIDs for it (IANA considerations).
- Adding OIDs for the curves (IANA considerations).

Also, here is the interesting question: Is it worth staying "in bounds"
here or just revamp the whole thing all at once (something like EdDSA
or so)?

-Ilari

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 28 Jan 2015 09:54:28 -0800

> It also did implement one 1024-bit hash (Skein-1024, was a SHA-3
I think SHAKE256 is a good idea.  I'm planning to experiment with it in 
the Goldilocks source code, mostly so that I don't need H(data), 
H(H(data)) for E-521.
> I think it definitely does have side-channels.
Verification code usually has side-channels, because none of the inputs 
is usually considered secret.  Depending on how you're using the 
signature, that could be a concern though.

-- Mike
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Watson Ladd <[email-masked]>
Date: Thu, 29 Jan 2015 19:45:16 -0800

> - Other interesting thoughts on digital signatures

Batch verification is potentially a real win for performance in common
uses of X509.3. This isn't possible with ECDSA. Of course, it requires
issuing the root, intermediate, and end-party cert with the same exact
curve. I can imagine where we use a short-lived (1 year or so)
intermediate with Ed25519, and cache it to enable batch verification
without the concerns with roots with Ed25519.

On the other hand the security issues of existing software are less
significant for signing.

I think we will need to parameterize over hash functions, potentially
with output smaller than liked.
Sincerely,
Watson Ladd

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

---

From: Damien Miller <[email-masked]>
Date: Fri, 30 Jan 2015 16:27:28 +1100 (AEDT)

> - Other interesting thoughts on digital signatures

As you probably already know OpenSSH is already using Ed25519 for
user and host authentication. We chose it because:

1) It's secure; well-reviewed and based on good "bones" (e.g. Schnorr sigs)
1a) It avoids the terrible failure modes of DSA/ECDSA
1b) It's hard for implementors to get wrong
2) It's fast
3) There are excellent reference implementations available

We're not interested in adding more DSA/ECDSA variants unless there is some
compelling reason (and I don't see any). EdDSA just seems a better algorithm.

We're not super-interested in WF >2^128 EdDSA either, but would possibly
consider EdDSA at ~WF 2^256 if our users start asking for it.

We aren't likely to benefit from batch signing/verification.

-d

---

From: David Leon Gil <[email-masked]>
Date: Fri, 30 Jan 2015 16:32:01 +0000

Some brief notes:

1. Hash functions. I'd really like to see a better hash function for any
options besides Ed25519. Two options for Ed25519:

1. Same point format. Keep the hash the same. Don't break compatibility.

2. New point format. Replace SHA2 with Blake2 or Prefix-MAC(SHAKE128).

For higher security strength curves, the EC-Schnorr security proofs suggest
2s hashing. Only SHAKE256 seems to work for that.

I mildly prefer EC-Schnorr to ECDSA, Franken- or not.

--

2. Signature schemes with coupons and tight reductions to CDH. Hashing to
an EC group is really easy with a variable-output-length keyed PRF. (Does
this have to be done in constant time?)

Pointcheval(?) has an interesting scheme involving 'coupons', in which all
scalar muls can be done *before* signing a message. The scheme has a tight
reduction to CDH.

This strikes me as potentially much more efficient than even Schnorr-EC for
signers: The scalarmuls are no longer in the critical path. So you get
asymmetric signatures for (very slightly more than) the latency of
computing a MAC[*]

[*] Note that this means you can compute coupons at periods of low
computational demand, which may be a substantial cost savings.

David Leon Gil
Senior Paranoid
Yahoo!

PS. Sending via Gmail because the CFRG mailing list software attempts to
forge @yahoo-inc.com FROM addresses. And Yahoo sets a DMARC p=reject. Could
a list admin please configure the IRTF listserv to not blatantly violate
the IETF DMARC standard?

---

From: Mike Hamburg <[email-masked]>
Date: Fri, 30 Jan 2015 09:29:27 -0800

On 01/30/2015 08:32 AM, David Leon Gil wrote:
> Some brief notes:
>
> 1. Hash functions. I'd really like to see a better hash function for 
> any options besides Ed25519. Two options for Ed25519:
>
> For higher security strength curves, the EC-Schnorr security proofs 
> suggest 2s hashing. Only SHAKE256 seems to work for that.
Which hashing step, the nonce derivation or the challenge?  And what's s?

The nonce needs to be close to uniform, but if the curve's order is 2^n 
+ ~2^(n/2) then even n bits would be enough.  Otherwise 1.5n bits are 
enough.

Is there a strong bound on the challenge?
> I mildly prefer EC-Schnorr to ECDSA, Franken- or not.
I also prefer EC-Schnorr, though I don't have a strong preference 
between Bernstein's formulation (kP, s) and Schnorr's (r,s).

I also think some users will be annoyed if we specify a Schnorr variant 
which precludes a streaming API.
> --
>
> 2. Signature schemes with coupons and tight reductions to CDH. Hashing 
> to an EC group is really easy with a variable-output-length keyed PRF. 
> (Does this have to be done in constant time?)
Not for signatures, though it leaks information about the (hash of) the 
message to be signed.  But you'd want to implement it in constant time 
so that SPEKE, SPAKE2 EE, Dragonfly and possibly EKE EE can use the same 
function.

By the way, usually for schemes where you hash to the curve, the hash 
doesn't need to be uniform or onto, just kinda-almost-onto and 
not-too-nonuniform.  (It's where the discrete log challenge is injected 
through the ROM, but ECDLP is randomly self-reducible so the challenger 
can easily rejection sample.)  As a result, a single call to either SWU 
or Elligator (1 or 2) is good enough.  This is pretty easy to do in 
constant time, with a single exp, and with only a field element's worth 
of hash output.

If you need a uniform hash, the BCIMRT solution is to hash twice and add.

See for example:
http://sourceforge.net/p/ed448goldilocks/code/ci/decaf/tree/src/decaf.c
http://sourceforge.net/p/ed448goldilocks/code/ci/decaf/tree/include/decaf.h
"decaf_point_from_hash_[non]uniform".
> Pointcheval(?) has an interesting scheme involving 'coupons', in which 
> all scalar muls can be done *before* signing a message. The scheme has 
> a tight reduction to CDH.
Link?  I'm most familiar with 
https://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf, but it's not by 
Pointcheval and its couponized sigs are only reducible to DDH.
> This strikes me as potentially much more efficient than even 
> Schnorr-EC for signers: The scalarmuls are no longer in the critical 
> path. So you get asymmetric signatures for (very slightly more than) 
> the latency of computing a MAC[*]
>
You can use coupons with Schnorr or even with ECDSA.  I've suggested its 
use in my company's products to reduce latency.  Though a tight 
reduction to CDH would be nice.

Cheers,
-- Mike
> David Leon Gil
> Senior Paranoid
> Yahoo!
>
> PS. Sending via Gmail because the CFRG mailing list software attempts 
> to forge @yahoo-inc.com <http://yahoo-inc.com> FROM addresses. And 
> Yahoo sets a DMARC p=reject. Could a list admin please configure the 
> IRTF listserv to not blatantly violate the IETF DMARC standard?
> On Thu, Jan 29, 2015 at 9:27 PM Damien Miller <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     [email-masked] <mailto:[email-masked]>