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

[Rene Struik <[e-mail]>]

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

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
>> 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.}

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


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