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

[Watson Ladd <[e-mail]>]

On Mar 13, 2015 10:34 AM, "Rene Struik" <[e-mail]> 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" <[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]>
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]
>> >>>> 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]
>> >
>
>
>
> --
> email: [e-mail] | Skype: rstruik
> cell: [phone] | US: [phone]