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

[Mike Hamburg <[e-mail]>]

On 01/28/2015 02:48 AM, Ilari Liusvaara wrote:
> 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)
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.
>> • Batch verify may exhibit side-channels?
> 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
>> • 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
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg