Re: [Cfrg] Elliptic Curves - curve form and coordinate systems (ends on March 12th)

[Jakob Breier <[e-mail]>]

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