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

David McGrew <mcgrew@cisco.com> Wed, 15 January 2014 21:01 UTC

Return-Path: <mcgrew@cisco.com>
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 748F51AE248 for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 13:01:40 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -14.439
X-Spam-Level:
X-Spam-Status: No, score=-14.439 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, J_CHICKENPOX_12=0.6, RCVD_IN_DNSWL_HI=-5, RP_MATCHES_RCVD=-0.538, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] 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 s71f7dcgahaw for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 13:01:39 -0800 (PST)
Received: from rcdn-iport-7.cisco.com (rcdn-iport-7.cisco.com [173.37.86.78]) by ietfa.amsl.com (Postfix) with ESMTP id 353DA1AE0D5 for <cfrg@irtf.org>; Wed, 15 Jan 2014 13:01:39 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=2519; q=dns/txt; s=iport; t=1389819687; x=1391029287; h=message-id:date:from:mime-version:to:cc:subject: references:in-reply-to:content-transfer-encoding; bh=Co0TsasuiWT9z/MEyKCfH6o0TgwwoG6H9t6FjaF99ag=; b=mm3ONzcFTr2nc6yEx4F14kBB1stXCvXW7IFhg3bsLLA76D71aUqVKm75 Kid7XpIrwZ/wVWRheLGZuIX0Sr+eeqwtP+tKkD0S8BsM3VqZmWgH9EA7G vN2vQ9c72zUDL/xcPWWJ8kOc/GraXEYQKemIfAjScDr4Vgj/j3pUJ2WPD c=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AgQFAJ/21lKtJV2Z/2dsb2JhbABTBoMLuQqDDoEWFnSCJQEBAQMBODoHBQsLGAklDwJGBg0BBwKHeAjDNReOFChDB4Q3AQOJR45ZhkWLUIFvgVwe
X-IronPort-AV: E=Sophos;i="4.95,665,1384300800"; d="scan'208";a="297558031"
Received: from rcdn-core-2.cisco.com ([173.37.93.153]) by rcdn-iport-7.cisco.com with ESMTP; 15 Jan 2014 21:01:27 +0000
Received: from [10.0.2.15] (rtp-mcgrew-8914.cisco.com [10.117.10.229]) by rcdn-core-2.cisco.com (8.14.5/8.14.5) with ESMTP id s0FL1QuY024585; Wed, 15 Jan 2014 21:01:26 GMT
Message-ID: <52D6F726.90203@cisco.com>
Date: Wed, 15 Jan 2014 16:01:26 -0500
From: David McGrew <mcgrew@cisco.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130922 Icedove/17.0.9
MIME-Version: 1.0
To: Adam Back <adam@cypherspace.org>
References: <mailman.4685.1389738617.2658.cfrg@irtf.org> <52D645EC.4000408@gmail.com> <52D684EE.9050304@cisco.com> <CEFBFBE5.2C52B%paul@marvell.com> <20140115200626.GA23829@netbook.cypherspace.org>
In-Reply-To: <20140115200626.GA23829@netbook.cypherspace.org>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Cc: Yaron Sheffer <yaronf.ietf@gmail.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [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 21:01:40 -0000

On 01/15/2014 03:06 PM, Adam Back wrote:
> 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. 

That's my impression too.

I think that one of the goals of this work is to follow US patent 
4,995,082 (Schnorr's signature scheme, which includes elliptic curve 
groups in its claims and which is expired).   In that case, it would 
make a lot of sense for a standard based on this work to cite that 
patent explicitly, and follow it closely.   Hopefully the good "speed 
hacks" are consistent with this approach, but I am not yet sure.

David

> 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 :)
>
> Adam
> .
>