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

[Alyssa Rowan <[e-mail]>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

On 27 January 2015 21:33:16 GMT+00:00, Tony Arcieri <[e-mail]> 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
-----BEGIN PGP SIGNATURE-----
Version: APG v1.1.1

iQI3BAEBCgAhBQJUyKmdGhxBbHlzc2EgUm93YW4gPGFrckBha3IuaW8+AAoJEOyE
jtkWi2t6XYAP/176s3n9Qdx7seGzVrGbsnPegyBTbTDRrgRa3XMg84S/QQ4MR+JY
0pbsykqqQiICs2qEixF3T6wdYW/c/1VUC0OX8g2gp/z2wle1qMHAqLRA3GJtKvny
s9RkJR5Y9cQBrjwBTE47kiNF0pCZeEdOKN+gBqxtcF9Rt2wHeHipCoyWSmCfdeOw
sAlCsJt6ePZ9yKQP3ldJkq6s6Nb7A+4dqRTKKdafli+ut9FevVYImBBIX5Xydd64
QJ/wfX0OWkT+J6I0tB2RgqEXFQl4tVOtR0wm5jwi/t2Wsfk6c2/MFTGDl4d4hv7L
uI21XU+mP/2PGleKjsnJe7kaVeHgqFZB9+6oYtSzVDnZOAfDLhtryhORzKv8sKaV
fZoBSXDirapout9zJuVHMPJaoDbwpHn3Mh7HHmoYd9g96HlXfEK9LNdruO++BbaT
GHXiEapeVDIq4cdR0ElKlxP/3NT68A/P2rjl9B6+GKoAiB6fV7IXyOKTjUlEoNYn
q+BGoLh9Y4sgVgVp5FBEUYKrqgX+9af23IaDum/av/iqNEaFza6ZXsD/xTlZOrhZ
LKEnfTnNYPHNkK1MAaVDXd1QFgciDvU9CFWTBB9/ihoxnghUGvasGv+A9p7ibHEC
4UozyKVudnmTOBfHDt3HdUBbJJcK11JiKxZyN+EjcV9gfE5i8bz4rvO1
=GPdY
-----END PGP SIGNATURE-----