[Cfrg] EdDSA private key restrictions & composability (Re: normative references)

Adam Back <adam@cypherspace.org> Wed, 15 January 2014 20:07 UTC

Return-Path: <adam@cypherspace.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id CB10E1AE1A6 for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 12:07:01 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.301
X-Spam-Status: No, score=-1.301 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, J_CHICKENPOX_12=0.6, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-0.001] autolearn=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id 7KHhQ4TLUtXO for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 12:07:00 -0800 (PST)
Received: from mout.perfora.net (mout.perfora.net []) by ietfa.amsl.com (Postfix) with ESMTP id DFFF11AE153 for <cfrg@irtf.org>; Wed, 15 Jan 2014 12:06:59 -0800 (PST)
Received: from netbook (c107-70.i07-27.onvol.net []) by mrelay.perfora.net (node=mrus0) with ESMTP (Nemesis) id 0M3z0U-1VByLC2G6U-00qtmU; Wed, 15 Jan 2014 15:06:37 -0500
Received: by netbook (Postfix, from userid 1000) id B3AE02E2836; Wed, 15 Jan 2014 21:06:29 +0100 (CET)
Received: by flare (hashcash-sendmail, from uid 1000); Wed, 15 Jan 2014 21:06:27 +0100
Date: Wed, 15 Jan 2014 21:06:26 +0100
From: Adam Back <adam@cypherspace.org>
To: Paul Lambert <paul@marvell.com>
Message-ID: <20140115200626.GA23829@netbook.cypherspace.org>
References: <mailman.4685.1389738617.2658.cfrg@irtf.org> <52D645EC.4000408@gmail.com> <52D684EE.9050304@cisco.com> <CEFBFBE5.2C52B%paul@marvell.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Disposition: inline
In-Reply-To: <CEFBFBE5.2C52B%paul@marvell.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Hashcash: 1:20:140115:paul@marvell.com::z2DaVaSzEV4g0OCU:02ztB
X-Hashcash: 1:20:140115:mcgrew@cisco.com::86gZB1M4fxx27E4P:02/Rb
X-Hashcash: 1:20:140115:yaronf.ietf@gmail.com::M4jVvVQ9q1zqcbXA:0000000000000000 0000000000000000000000006A5l
X-Hashcash: 1:20:140115:cfrg@irtf.org::CZXjsKPu7In/gBR7:00003K1J
X-Provags-ID: V02:K0:ytBCJl86Rec0A7H2TZ4rvGZXwZ5c2+vxehUDQ8FR9y0 x4CbE7UvV5Zr3N/2hfrHvBfPnG6NhfubZ8K0y7WgwTWFE9TqfZ Z3LtIC/X0MGFEFz0bCwzRK70DuKWrmOhdN0VuwnLdYyOxMEiLq o26/IJMo8TlPtg30CA5V9/NvhHJoJS46T9JXKRnF1O3S+VzwKT qMM4N6qpsP4ZnYWEOzS1qO5Z0rFZtY0TctOpuL87GPpmbLQnnm VIIvksOmni+RYHe/3zQMbzMAMsRVkyxdQPcxh8YLgt69sMNeV/ AsWWhx/+ZJhXPwH3nU5RRFGVt3z2ETxC/yB7OREOiu29z1viHM 7GeFfp4gUpMbh5/2GfI/8E/f2qTol3MzGlm5AFl2W
Cc: Yaron Sheffer <yaronf.ietf@gmail.com>, David McGrew <mcgrew@cisco.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Subject: [Cfrg] EdDSA private key restrictions & composability (Re: normative references)
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, 15 Jan 2014 20:07:02 -0000

On Wed, Jan 15, 2014 at 10:02:01AM -0800, Paul Lambert wrote:
> - unclear guidelines on important security topics
>    E.g.
>      ed25519 has restrictions on the secret key structure for ECDH
>      Does this extend to other curves?

Actually on this narrow topic re Ed25519 curve for EdDSA uses, I noticed
this also.  I think bit 254 being 1 could be optional so (Curve25519 has the
same private key restrictions for ECDH) so long as constant time montgomery
addition starts from bit 254 regardless.  And the remaining hard code is the
lowest 3 bits 000 but that which I presume is precomputed multiplication by
the cofactor, as seen in the verification relation 8sG=8R+8H(R,Q,m)Q. 
(Using ECDSA labelling G is base, Q=dG pub key).

The paper seems quite unclear and hard to pick apart and maybe the algorithm
just a little too much speed hacked.  The above seems to break
composability.  Ie derived public keys (Q_i = Q+M(c,i)G) where c is a
shared-secret, i is a counter; bitcoin uses this for backup and offline
security reasons.  Similar examples abound: threshold signatures, blind
signatures; one of the exciting thing to me about seeing EdDSA adopted is
that it is a Schnorr variant, and Schnorr has much simpler multiparty,
threshold and even blinding.  ECDSA has no blinding and DSA blinding is a
monstrosity involving Damgard-Jurik's generalized variant of Paillier as a
substep!  But some of these things are lost or complicated by the unusual
private key restrictions, which I think if I'm not mistaken are just related
to tiny optimizations or otherise redundant defenses against variable time
execution which can be otherwise restated.

These kind of questions might or might not be in scope for the draft,
depending on your point of view.  (But anyway if anyone feels like
expounding on the above, on list or offlist, I would quite practically
interested :)