Re: [Cfrg] Mishandling twist attacks

Michael Hamburg <mike@shiftleft.org> Fri, 28 November 2014 06:26 UTC

Return-Path: <mike@shiftleft.org>
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 19F861A1A3A for <cfrg@ietfa.amsl.com>; Thu, 27 Nov 2014 22:26:05 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 4.255
X-Spam-Level: ****
X-Spam-Status: No, score=4.255 tagged_above=-999 required=5 tests=[BAYES_50=0.8, 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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id kZpBJOSp9J4a for <cfrg@ietfa.amsl.com>; Thu, 27 Nov 2014 22:26:04 -0800 (PST)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 31AEF1A1A38 for <cfrg@irtf.org>; Thu, 27 Nov 2014 22:26:03 -0800 (PST)
Received: from [192.168.1.117] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 6D4AC3AC24; Thu, 27 Nov 2014 22:24:19 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1417155859; bh=gCiqocL4a7j15tiW6Ws/FW72RsaJ1SAVwSmVfNqndwE=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=DMUsw9sUZ1iqBy7wQr5VmM1yiliAexdLZ3RdKREXpWYjV6B+u5BDJ45M/uh9azZ7G 2SwD2q5KGHAYMOfQPsbB2pG5O15rSXMxp+0X04+NOsRoyBxlbpXBuN7wfUUqLHU3o7 MEc3BwggN3BkBhg5sTKukqSzp7r9+0OZaFhbzN58=
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 8.1 \(1993\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <20141128014059.26622.qmail@cr.yp.to>
Date: Thu, 27 Nov 2014 22:26:02 -0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <61DC51CF-8952-4259-810E-822ED98CCB1A@shiftleft.org>
References: <20141128014059.26622.qmail@cr.yp.to>
To: "D. J. Bernstein" <djb@cr.yp.to>
X-Mailer: Apple Mail (2.1993)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/0krSgzyICzdQjHP-XEM-nP2FGIg
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Mishandling twist attacks
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: Fri, 28 Nov 2014 06:26:05 -0000

> On Nov 27, 2014, at 5:40 PM, D. J. Bernstein <djb@cr.yp.to>; wrote:
> 
> 
> P.P.S. Apparently there's also a claim that ECDSA-PinkBikeShed would be
> simpler than ECDSA-Curve25519. This claim starts from the Curve25519
> paper's observation that _one_ of the primes for PinkBikeShed is
> slightly below 2^252; concludes that the _curve order_ is slightly below
> 2^255; and tries to argue that a curve order slightly below 2^255 has
> advantages outweighing the advantages of a curve order slightly above
> 2^255.
> 
> However, the curve order for PinkBikeShed is in fact _above_ 2^255, just
> like the curve order for Curve25519; so the intermediate conclusion is
> wrong, the subsequent argument is irrelevant, and the claim crumples.
> The _twist_ order is below 2^255 (divide by the twist cofactor 8 to
> obtain a prime slightly below 2^252, the prime that the paper is
> describing) but the twist isn't the curve that's being proposed. I'll
> find it richly entertaining if Microsoft now proposes the twist.


D’oh.  That’ll teach me to read.

It wasn’t really a claim against Curve25519, but a reason why someone might choose differently, and in fact a requirement for the NUMS curves, but I guess not for PinkBikeShed.

— Mike