Re: [Cfrg] ECC mod 8^91+5

Ilari Liusvaara <ilariliusvaara@welho.com> Wed, 02 August 2017 08:12 UTC

Return-Path: <ilariliusvaara@welho.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E62FC12711E for <cfrg@ietfa.amsl.com>; Wed, 2 Aug 2017 01:12:43 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.001] autolearn=ham autolearn_force=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 BFjFt7BlHTIg for <cfrg@ietfa.amsl.com>; Wed, 2 Aug 2017 01:12:42 -0700 (PDT)
Received: from welho-filter3.welho.com (welho-filter3.welho.com [83.102.41.25]) by ietfa.amsl.com (Postfix) with ESMTP id CEB3C126BF3 for <cfrg@irtf.org>; Wed, 2 Aug 2017 01:12:41 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by welho-filter3.welho.com (Postfix) with ESMTP id E94332942A; Wed, 2 Aug 2017 11:12:39 +0300 (EEST)
X-Virus-Scanned: Debian amavisd-new at pp.htv.fi
Received: from welho-smtp3.welho.com ([IPv6:::ffff:83.102.41.86]) by localhost (welho-filter3.welho.com [::ffff:83.102.41.25]) (amavisd-new, port 10024) with ESMTP id aF1Y2zjQOIeR; Wed, 2 Aug 2017 11:12:39 +0300 (EEST)
Received: from LK-Perkele-VII (87-92-19-27.bb.dnainternet.fi [87.92.19.27]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by welho-smtp3.welho.com (Postfix) with ESMTPSA id 924D62313; Wed, 2 Aug 2017 11:12:37 +0300 (EEST)
Date: Wed, 02 Aug 2017 11:12:37 +0300
From: Ilari Liusvaara <ilariliusvaara@welho.com>
To: Dan Brown <danibrown@blackberry.com>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Message-ID: <20170802081237.k6pcmldfso4dkgeq@LK-Perkele-VII>
References: <810C31990B57ED40B2062BA10D43FBF501B181DA@XMB116CNC.rim.net> <810C31990B57ED40B2062BA10D43FBF501B7969D@XMB116CNC.rim.net>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF501B7969D@XMB116CNC.rim.net>
User-Agent: NeoMutt/20170609 (1.8.3)
Sender: ilariliusvaara@welho.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/IUZOqA3Hu3FBTIkWCpQdr06OAE4>
Subject: Re: [Cfrg] ECC mod 8^91+5
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 02 Aug 2017 08:12:44 -0000

On Tue, Aug 01, 2017 at 09:22:10PM +0000, Dan Brown wrote:
> Hi CFRG,
> 
> A minor addition to this topic.
> 
> In my first email on this topic, and in my recent IETF 99
> presentation, I mentioned that the proposed special curve
> 2y^2=x^3+x was similar to curves proposed in Miller's 1985 paper
> introducing of ECC. 
> 
> I believe (50% sure) that Miller made this non-square a 
> recommendation merely to help keep the group cofactor down (by
> ensuring a unique point of order 2, namely (0,0)).  

Unfortunately there is another related problem: The theorem that says
that folded Montgomery ladder always works assumes that there is
unique point of order 2.

So if using curve with multiple points of order 2, there may be
exceptional cases. And getting those cases wrong might be exploitable.

And handling those cases without timing sidechannels might be very
nasty to implement.
 
And sets of complete Montgomery and complete Edwards curves are very
closely related, so this is probably not complete either as Edwards
curve.

> By contrast 2y^2=x^3+x, has a subgroup of order 8.  (With points
> O, (0,0), (i,0), (-i,0), (1,1), (1,-1), (-1,i), (-1,-i).)  A subgroup
>  of order 4 (or 8) is nowadays considered (arguably) an advantage,
> because of various Edwards curves (but I am only 10% sure, since I
> haven't looked at this in a while, please correct me this is wrong).

It also seemingly has subgroup of order 9, which is considerably more
problematic than subgroup of order 8.

There are some more exotic ECC algorithms that just can't deal with
cofactor bigger than 1, but I think the worst problems that are 
attributed to cofactor >1 are actually caused by having a notation for
low-order points. And any complete curve has at least one such point.

And then, not having notations for low-order points is annoying in
implementing algorithms...


-Ilari