Re: [Cfrg] Elliptic Curves - curve form and coordinate systems

Rene Struik <rstruik.ext@gmail.com> Fri, 13 March 2015 18:10 UTC

Return-Path: <rstruik.ext@gmail.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 19B331A19F8 for <cfrg@ietfa.amsl.com>; Fri, 13 Mar 2015 11:10:36 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_PASS=-0.001] 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 zQZ413Gv1BeD for <cfrg@ietfa.amsl.com>; Fri, 13 Mar 2015 11:10:31 -0700 (PDT)
Received: from mail-ie0-x233.google.com (mail-ie0-x233.google.com [IPv6:2607:f8b0:4001:c03::233]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id F03421A9089 for <cfrg@irtf.org>; Fri, 13 Mar 2015 11:10:30 -0700 (PDT)
Received: by iecvj10 with SMTP id vj10so114651572iec.0 for <cfrg@irtf.org>; Fri, 13 Mar 2015 11:10:30 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type; bh=PJxzGPUTXpc89ZKQjaK9jp6Tifbfoy63owvRCRBiMtw=; b=ngNVHxS/Bhye8Uh0nuKgq75jU4e/3RYxiThYKhtj34PButvqpEXwwQwuSJqsOzJkQv Slutxy4Esc8RQeQipZmUUyoWQuj68X8ysVBOEpeg51DOsJcO/9ww3HAK0cVOnlh3pNVM /wPwuxo+fEa8tq9eRPDyQZxrgEy8lpwcNwUEC56FI3TSbcwjzbBsStCVS9BhD6Lw26Rq yU8xpUZglcJyG3Tt2M3vKLeXW2i3FhKIQMgrcFJZii017eQn+MxfzaxjRLadKOHHwY28 eCfHo9HbDmxBB81ee0m6WXAhj0oXHEDsZjbjphegU58c/gAEMQOY0gbIn1r7Ru6+aMtI /12Q==
X-Received: by 10.50.7.1 with SMTP id f1mr86099079iga.8.1426270216213; Fri, 13 Mar 2015 11:10:16 -0700 (PDT)
Received: from [192.168.0.10] (CPE7cb21b2cb904-CM7cb21b2cb901.cpe.net.cable.rogers.com. [99.231.49.38]) by mx.google.com with ESMTPSA id s10sm1723825igr.2.2015.03.13.11.10.15 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 13 Mar 2015 11:10:15 -0700 (PDT)
Message-ID: <550327FE.9010303@gmail.com>
Date: Fri, 13 Mar 2015 14:10:06 -0400
From: Rene Struik <rstruik.ext@gmail.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.5.0
MIME-Version: 1.0
To: Watson Ladd <watsonbladd@gmail.com>
References: <54F8E735.2010202@isode.com> <5501E6A5.5040608@brainhub.org> <5502D58F.3030806@rwth-aachen.de> <5502F920.5050505@gmail.com> <CACsn0ckERomjBvQvs1T89VLYdOuj-WPDmzg_67mrQnaUe+0crA@mail.gmail.com> <55030B4F.5020108@gmail.com> <CACsn0ck19Ur2K0bDyeFMcNR7NprbcwxPKAdNVLK2NhuUcWBQYg@mail.gmail.com> <55031F93.2000204@gmail.com> <CACsn0cn0dgGT3B5v7pacCcB_AQ6iOJwCBaGpT8SoSH2-x0wnEg@mail.gmail.com>
In-Reply-To: <CACsn0cn0dgGT3B5v7pacCcB_AQ6iOJwCBaGpT8SoSH2-x0wnEg@mail.gmail.com>
Content-Type: multipart/alternative; boundary="------------000906090609010802000903"
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/SkAw_x7x8lAfY1559GKNlUWdcjc>
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Elliptic Curves - curve form and coordinate systems
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, 13 Mar 2015 18:10:36 -0000

As already said, one can have another series of emails on the impact of 
entirely speculative levels of sloppy behavior one attributes to 
implementations in one case but magically not in the other, as you seem 
to do, but - frankly - the CFRG email archive is already bursting out of 
its seams with emails repeating the same refrain (which I mentioned in 
my note below as "leading nowhere").

Moreover, it is entirely orthogonal to the succinct points I made.

{Apologies to others on the CFRG mailing list for having to state the 
first sentence above.}

==
 >> > Note: I know that you might bring up that people can "forget" to 
implement this known check that is known for over 15 years, but then 
people can also "forget" to check whether Curve25519 DH keys are equal 
to zero, so that discussion leads nowhere, since only speculates on 
levels of sloppy behavior one attributes to implementers in one case, 
but magically not in another.
 >> > <<RS

On 3/13/2015 1:43 PM, Watson Ladd wrote:
>
>
> On Mar 13, 2015 10:34 AM, "Rene Struik" <rstruik.ext@gmail.com 
> <mailto:rstruik.ext@gmail.com>> wrote:
> >
> > Hi Watson:
> >
> > I do not want this exchange to take ad infinitum, since I think I 
> made my point.
> >
> > One note, though:  the scenario where the DH key is the identity 
> corresponds to a point of order one (the smallest order theoretically 
> possible), which, if not checked for, immediately results in an 
> unsecured channel (or, more aptly, a channel secured with a fixed key 
> [akin to using as key an all-zero string or empty string password]).
>
> Any attack requiring cooperation of one side doesn't count. A protocol 
> that properly hashes transcripts doesn't have the problem with zero 
> keys that TLS does. But there is no similar protection for missing 
> validation.
> >
> > Rene
> > ==
> >
> > The consequences of getting the identity are minor. The consequences 
> of accepting points of small order are loss of the private key.
> >
> > On 3/13/2015 1:12 PM, Watson Ladd wrote:
> >>
> >>
> >> On Mar 13, 2015 9:08 AM, "Rene Struik" <rstruik.ext@gmail.com 
> <mailto:rstruik.ext@gmail.com>> wrote:
> >> >
> >> > Hi Watson:
> >> >
> >> > I think your assessment is technically incorrect. Please see 
> details below.
> >> >
> >> > Rene
> >> >
> >> >
> >> > On 3/13/2015 11:20 AM, Watson Ladd wrote:
> >> >>
> >> >> On Fri, Mar 13, 2015 at 7:50 AM, Rene Struik 
> <rstruik.ext@gmail.com <mailto:rstruik.ext@gmail.com>> wrote:
> >> >>>
> >> >>> Hi Jakob:
> >> >>>
> >> >>> This confuses different discussions:
> >> >>>
> >> >>> a) use of public key in computations.
> >> >>> Here, Andrey Jivsov's point was that receipt of a full point 
> (x,y) on a
> >> >>> curve, rather than a compressed point or simply the 
> x-coordinate, does not
> >> >>> artificially impose a performance penalty on all 
> implementations except
> >> >>> x-coordinate-only ones (Montgomery).
> >> >>
> >> >> This isn't artificial: use of compressed and x only coordinate
> >> >> representations has security benefits, because it makes the simplest
> >> >> implementation very simple.
> >> >
> >> > RS>>
> >> > As Andrey Jivsov already pointed out in an email long time ago, 
> using affine coordinates (x,y) allows
> >> > i) those implementers that wish to perform x-coordinate only 
> arithmetic to do so: they simply discard the y-coordinate of a 
> received affine point;
> >> > ii) those implementers that do wish to use a different method can 
> do so, without the need to perform point decompression. They could 
> also carry out point validation, at cost of roughly 2S+M for 
> Montgomery curves with small 'A' value (S=field squaring; M= field 
> multiply), which is << 1% of total cost and completely trivial.
> >>
> >> Y recovery complicates the Montgomery ladder significantly.
> >>
> >> >
> >> > Note: I know that you might bring up that people can "forget" to 
> implement this known check that is known for over 15 years, but then 
> people can also "forget" to check whether Curve25519 DH keys are equal 
> to zero, so that discussion leads nowhere, since only speculates on 
> levels of sloppy behavior one attributes to implementers in one case, 
> but magically not in another.
> >> > <<RS
> >>
> >> The consequences of getting the identity are minor. The 
> consequences of accepting points of small order are loss of the 
> private key.
> >>
> >> >
> >> >>> b) representation of public key in white list.
> >> >>> Here, one can use many methods to map a public key Q to a condensed
> >> >>> (perhaps, even human-recognizable) format f(Q).
> >> >>> This condensed format could take the form affine format curve 
> point,
> >> >>> compressed format, hash, leftmost n-octets, hash value, etc.
> >> >>>
> >> >>> My own take:
> >> >>>
> >> >>> Ad a):
> >> >>> I fully agree with Andrey Jivsov's point and think using 
> x-coordinate only
> >> >>> representations imposes a "moat" around ECC implementations, by 
> imposing a
> >> >>> levy on all implementations that, for whatever reason, may want 
> to use
> >> >>> something else than Montgomery arithmetic. {Please note that 
> this levy is
> >> >>> incurred (in the context of ECDH) during *online* 
> computations.} Such fully
> >> >>> specified points are particularly useful in settings, including
> >> >>> multiple-point multiplication, combined key computations and 
> signature
> >> >>> verifications, batch computations, since may allow significant 
> performance
> >> >>> advantages in those settings.
> >> >>
> >> >> But we're discussing ECDH, which isn't any of these cases.
> >> >
> >> > RS>> For a counter-example, please see my SAC 2010 paper on 
> combined key computations and signature verification. That paper 
> illustrated that the incremental cost of ECDSA signature verification 
> would shrink considerably when combined with ECDH key computation, 
> rather than when executed separately. See, e.g., 
> http://link.springer.com/chapter/10.1007%2F978-3-642-19574-7_9. The 
> paper suggests that essentially one gets ECDSA verifies for roughly 
> half the computational cost compared to when not using these tricks, 
> with a footnote at the end suggesting that improvements may be even 
> more pronounced with twisted Edwards curves (since depending on 
> relative Double/Add cost). {Of course, actual improvements depend on 
> implementation platform and scalar multiplication details, but can be 
> shown to hold accross the board, when one applies one's favorite picks 
> there.}
> >>
> >> Combs still work for fixed based mults.
> >>
> >> >
> >> > The point of my note was that enforcing x-coordinate only 
> representations would block approaches, such as, e.g., those in that 
> SAC 2010 paper, whereas using affine coordinates does not. Shouldn't 
> implementers be able to have some design freedom, if that would suit 
> them? (Esp. since speed has been touted as one of the triggers to 
> consider new curve forms?)
> >> > <<RS
> >> >
> >> >> Of course,
> >> >> there is no performance penalty: the Montgomery ladder is the 
> fastest
> >> >> variable scalar multiplication. Users who don't care about 
> performance
> >> >> can incur the square root cost: they don't care. Users who do care
> >> >> about performance are already going to use the Montgomery ladder.
> >> >>>
> >> >>> Ad b):
> >> >>> This is a non-issue in representation discussions with CFRG 
> with ECC, since
> >> >>> dealing with protocol issues, not user interfaces.
> >> >>> Nevertheless, here is a comparison that illustrates some condensed
> >> >>> representations that are possibly in a completely standardized 
> way, resp.
> >> >>> "cooked up" for user interfaces:
> >> >>>
> >> >>> Comparison example:
> >> >>> example P-256 public key, with affine coordinates (x,y),
> >> >>> x-coord = 6b 17 d1 f2 e1 2c 42 47 f8 bc e6 e5 63 a4 40 f2 77 03 
> 7d 81 2d eb
> >> >>> 33 a0 f4 a1 39 45 d8 98 c2 96
> >> >>> y-coord = 4f e3 42 e2 fe 1a 7f 9b 8e e7 eb 4a 7c 0f 9e 16 2b ce 
> 33 57 6b 31
> >> >>> 5e ce cb b6 40 68 37 bf 51 f5
> >> >>> a) standardized affine format: (0x04 || x-coord || y-coord) {65 
> octets}
> >> >>> b) standardized compressed format: (0x03 || x-coordinate) {33 
> octets}
> >> >>> c) non-standard, x-coordinate-only: x-coordinate {32 octets}
> >> >>> d) non-standard, truncated x-coordinate (x-coordinate mod 
> 2^128): 77 03 7d
> >> >>> 81 2d eb 33 a0 f4 a1 39 45 d8 98 c2 96 {16 octets}
> >> >>>
> >> >>> example Curve25519, Alice's public key (source:
> >> >>> draft-irtf-agl-cfrgcurve-00):
> >> >>> x-coord = 85 20 f0 09 89 30 a7 54 74 8b 7d dc b4 3e f7 5a 0d bf 
> 3a 0d 26 38
> >> >>> 1a f4 eb a4 a9 8e aa 9b 4e 6a
> >> >>> c) non-standard, x-coordinate-only: x-coordinate {32 octets}
> >> >>>
> >> >>> On 3/13/2015 8:18 AM, Jakob Breier wrote:
> >> >>>>
> >> >>>> On 12.03.2015 20:19, Andrey Jivsov wrote:
> >> >>>>>
> >> >>>>> * This proposal incurs 32 additional bytes of storage 
> overhead for the
> >> >>>>> public key, for the total of 64 bytes (compare this with 260+ 
> bytes for RSA
> >> >>>>> 2048).
> >> >>>>
> >> >>>>
> >> >>>> The storage costs and transmission costs might be 
> insignificant for
> >> >>>> machines, but I'd like to point out the human storage and 
> transmission
> >> >>>> costs. Take a look at SSH keys for example. Compare how well 
> you can
> >> >>>> visually parse several lines of keys in an authorized_keys 
> file in these
> >> >>>> three formats:
> >> >>>>
> >> >>>> ssh-rsa
> >> >>>> 
> AAAAB3NzaC1yc2EAAAADAQABAAABAQDRTSfbRohGanse3u4gnu8wOId85f5KKyEzo/l
> >> >>>>
> >> >>>> 
> MabVM4J92n6r4NPgN46pQ3bTc8XzLO5zHXY/mPSwQru3Ks+6Mcut7bDo0ohPcLcdIYGTbqXkfz3
> >> >>>>
> >> >>>> 
> KNDbdXwPMcaPamLmugNnj9UK2cPe8Q7F9DGSLaQc1eiC0JS/Qm0gG3ULqX3DEDFQbLBzH326Lov
> >> >>>>
> >> >>>> 
> 9gplu/U7D0bBiM7q7VQs32sz11L4KWY3RzUhuy6bQ7GGrkGvp78l7f+56AvQNeIV8fDOWKNE73s
> >> >>>>
> >> >>>> 
> Q3NybxWxQ771c5c+AZGYzkERlHWjxaxGA6V8ZUiE2VftHZMY4k6z4DC9hiadxwmr85qWriC7RrT
> >> >>>> OjmN9 Alice-HomePc
> >> >>>>
> >> >>>> ecdsa-sha2-nistp256
> >> >>>> AAAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAyNTYAAABBBLB
> >> >>>>
> >> >>>> 
> RUKndAEfMluniDolf8eJIdhh1l9C2iXKtnbvbM9vFbBMQ+l47i7wusn4G2RMYsFPbwlV4XQt4TT
> >> >>>> sEwkrcLss= Alice-HomePc
> >> >>>>
> >> >>>> ssh-ed25519
> >> >>>> AAAAC3NzaC1lZDI1NTE5AAAAICxtv8s7nwLqhkhryoY+w/u9ZrY7dr0ZPZhYuOS
> >> >>>> bxTIb Alice-HomePc
> >> >>>>
> >> >>>> They are in turn: RSA (2048 bit), 65 byte long nistp256 key 
> and 32 byte
> >> >>>> long ed25519 key (apparently, openssh already uses point 
> compression for
> >> >>>> this format). The difference would be even more pronounced, if 
> the SSH key
> >> >>>> storage format was more efficient, but the result of factor 
> two decrease
> >> >>>> from 64 byte to 32 byte keys is still significant. And these 
> are keys that
> >> >>>> you often copy and paste as plain text instead of sending 
> pubkey files, e.g.
> >> >>>> when you add one to GitHub or instant message it to a friend.
> >> >>>>
> >> >>>> Another example is TextSecure, the end-to-end encrypted 
> messenger app,
> >> >>>> that allows you to verify the 33 byte "identity" (32 byte 
> Curve25519 key +
> >> >>>> 0x05 prefix) by comparing them manually as 66 hex characters 
> (or scanning a
> >> >>>> QR-code). Threema, another encrypted messenger app, also 
> directly compares
> >> >>>> the public key (32 byte Curve25519) in the QR-code. (Threema 
> does also
> >> >>>> feature a 128bit fingerprint, though, that can be compared by 
> reading it
> >> >>>> aloud.)
> >> >>>>
> >> >>>> As all three examples feature interactive protocols anyway, 
> they could use
> >> >>>> fingerprints instead, but for various reasons don't and thus 
> profit from
> >> >>>> short key sizes.
> >> >>>>
> >> >>>> An example that does not have the alternative of using 
> fingerprints are
> >> >>>> key revocation certificates. I have a few of these printed out 
> for RSA keys
> >> >>>> and I fear the day I actually have to type them in.
> >> >>>> Also, if we'll ever have a chance to bring strong end-to-end 
> cryptography
> >> >>>> to the masses, then we need inexperienced users to backup 
> their private key.
> >> >>>> And I trust my parents far more to securely store, and later 
> on use, a slip
> >> >>>> of paper - which means writing down and later typing back in 
> the key - than
> >> >>>> a USB stick / a memory card / a CD / …, all which have to be 
> periodically
> >> >>>> checked whether they are still readable. And while this would 
> be totally
> >> >>>> impractical with RSA keys, with EC keys this becomes 
> borderline usable. And
> >> >>>> here the difference between 64 and 32 bytes is enormous.
> >> >>>>
> >> >>>> Best regards,
> >> >>>> Jakob Breier
> >> >>>>
> >> >>>> _______________________________________________
> >> >>>> Cfrg mailing list
> >> >>>> Cfrg@irtf.org <mailto:Cfrg@irtf.org>
> >> >>>> http://www.irtf.org/mailman/listinfo/cfrg
> >> >>>
> >> >>>
> >> >>>
> >> >>> --
> >> >>> email: rstruik.ext@gmail.com <mailto:rstruik.ext@gmail.com> | 
> Skype: rstruik
> >> >>> cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
> >> >>>
> >> >>> _______________________________________________
> >> >>> Cfrg mailing list
> >> >>> Cfrg@irtf.org <mailto:Cfrg@irtf.org>
> >> >>> http://www.irtf.org/mailman/listinfo/cfrg
> >> >>
> >> >>
> >> >>
> >> >
> >> >
> >> > --
> >> > email: rstruik.ext@gmail.com <mailto:rstruik.ext@gmail.com> | 
> Skype: rstruik
> >> > cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
> >> >
> >
> >
> >
> > --
> > email: rstruik.ext@gmail.com <mailto:rstruik.ext@gmail.com> | Skype: 
> rstruik
> > cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
>


-- 
email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363