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

Mike Hamburg <> Wed, 28 January 2015 17:54 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id B73971A0381 for <>; Wed, 28 Jan 2015 09:54:34 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 1.555
X-Spam-Level: *
X-Spam-Status: No, score=1.555 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 3lH1XLOqd8nb for <>; Wed, 28 Jan 2015 09:54:33 -0800 (PST)
Received: from ( []) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 653A01A1AC2 for <>; Wed, 28 Jan 2015 09:54:30 -0800 (PST)
Received: from [] (unknown []) by (Postfix) with ESMTPSA id 90D19F2208; Wed, 28 Jan 2015 09:54:27 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple;; s=sldo; t=1422467667; bh=H7M4ZbVdmMIs9Xa4coU7ZZhZ8/n1mG9QsztGeOgRU3A=; h=Date:From:To:CC:Subject:References:In-Reply-To:From; b=CgwJAOisU/TkIOEcQ3qs8Gva+BEkXUAA829aRixiNKPoSkWE9gpBpOg4noKJcz5jJ 3F/AZrkPJwjfPXWtdiEiWqjhhaNgc/uKlugj6V/7NyW3y+WmpmHzAbgoZpkllt9+i/ Q0+7oO863gw4+jgTXOI+ZyVAx9Ozh8Zjbx8pXmxQ=
Message-ID: <>
Date: Wed, 28 Jan 2015 09:54:28 -0800
From: Mike Hamburg <>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0
MIME-Version: 1.0
To: Ilari Liusvaara <>, Alyssa Rowan <>
References: <> <> <20150128104831.GA2272@LK-Perkele-VII>
In-Reply-To: <20150128104831.GA2272@LK-Perkele-VII>
Content-Type: text/plain; charset="utf-8"; format="flowed"
Content-Transfer-Encoding: 8bit
Archived-At: <>
Subject: Re: [Cfrg] Signatures: curves, algorithms, etc
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 28 Jan 2015 17:54:34 -0000

On 01/28/2015 02:48 AM, Ilari Liusvaara wrote:
> On Wed, Jan 28, 2015 at 09:19:26AM +0000, Alyssa Rowan wrote:
>> Hash: SHA512
>> On 27 January 2015 21:33:16 GMT+00:00, Tony Arcieri <> 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