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

[Watson Ladd <[e-mail]>]

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.

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



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin