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

[Rene Struik <[e-mail]>]

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]).

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" <[e-mail] 
> <mailto:[e-mail]>> 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 <[e-mail] 
> <mailto:[e-mail]>> 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
> >>>> [e-mail] <mailto:[e-mail]>
> >>>> http://www.irtf.org/mailman/listinfo/cfrg
> >>>
> >>>
> >>>
> >>> --
> >>> email: [e-mail] <mailto:[e-mail]> | 
> Skype: rstruik
> >>> cell: [phone] | US: [phone]
> >>>
> >>> _______________________________________________
> >>> Cfrg mailing list
> >>> [e-mail] <mailto:[e-mail]>
> >>> http://www.irtf.org/mailman/listinfo/cfrg
> >>
> >>
> >>
> >
> >
> > --
> > email: [e-mail] <mailto:[e-mail]> | Skype: 
> rstruik
> > cell: [phone] | US: [phone]
> >
>


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]