On 01/30/2015 08:32 AM, David Leon Gil
wrote:

Some brief notes:Which hashing step, the nonce derivation or the challenge? And what's s?

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.

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.

--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.

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?)

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.

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

Cheers,

-- Mike

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?

On Thu, Jan 29, 2015 at 9:27 PM Damien Miller <djm@mindrot.org> wrote:

On Tue, 27 Jan 2015, Tony Arcieri wrote:

> 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

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

_______________________________________________

Cfrg mailing list

Cfrg@irtf.org

http://www.irtf.org/mailman/listinfo/cfrg

_______________________________________________ Cfrg mailing list Cfrg@irtf.org http://www.irtf.org/mailman/listinfo/cfrg

--------------070909020406030201030505--