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

[Ilari Liusvaara <[e-mail]>]

On Wed, Jan 28, 2015 at 09:19:26AM +0000, Alyssa Rowan wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
> 
> On 27 January 2015 21:33:16 GMT+00:00, Tony Arcieri <[e-mail]> wrote:
> 
> >- 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.

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.

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

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

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.

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

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