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

Alyssa Rowan <akr@akr.io> Wed, 28 January 2015 09:19 UTC

Return-Path: <akr@akr.io>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 23FD91A01E7 for <cfrg@ietfa.amsl.com>; Wed, 28 Jan 2015 01:19:31 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.003
X-Spam-Level:
X-Spam-Status: No, score=-0.003 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id j3Y1jLv9PY8L for <cfrg@ietfa.amsl.com>; Wed, 28 Jan 2015 01:19:29 -0800 (PST)
Received: from entima.net (entima.net [78.129.143.175]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D84261A00CD for <cfrg@irtf.org>; Wed, 28 Jan 2015 01:19:28 -0800 (PST)
In-Reply-To: <CAHOTMVLZ3Hu2iAzAduu2A9kRgu36uVmMhYnEvAm786QyyUQigQ@mail.gmail.com>
References: <CAHOTMVLZ3Hu2iAzAduu2A9kRgu36uVmMhYnEvAm786QyyUQigQ@mail.gmail.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Content-Type: text/plain; charset="UTF-8"
From: Alyssa Rowan <akr@akr.io>
Date: Wed, 28 Jan 2015 09:19:26 +0000
To: cfrg@irtf.org
Message-ID: <45DA4E29-972A-4902-BFB4-4C23DC62ABEA@akr.io>
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/P7apxeLKBKvIVimamc8jtMMRMCs>
Subject: Re: [Cfrg] Signatures: curves, algorithms, etc
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 28 Jan 2015 09:19:31 -0000

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

On 27 January 2015 21:33:16 GMT+00:00, Tony Arcieri <bascule@gmail.com> 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-----