[curves] Unifying public key formats

[Trevor Perrin]

On Mon, Jan 19, 2015 at 2:16 PM, Paul Lambert <paul at marvell.com> wrote:
>
> DH is used commonly and often ephemeral - no need to uncompress.
> 2)b is appealing so as to match current DH usage and support compression.
> However, are we leaking one bit of info in the compressed bit if is there
> or not there?


If some implementations produce DH-only keys for a field and some
produce "full-format" keys (with a sign bit), this might indeed leak
some information in an anonymity context (like Tor).  Robert Ransom
has called this issue "implementation fingerprinting".

So assuming we're OK with Montgomery x for signature public keys,
there's some options for the relationship between DH and signature
keys:

A) Separate formats
Protocol fields are specified as "DH-only" or "full-format".  Use of a
full-format key in a DH-only field requires masking the sign bit.

B) Compatible formats
Protocol fields are specified as "DH-only or full-format", or
"full-format".  This makes it easer to use full-format keys for DH,
but creates the "implementation fingerprinting" risk.

C) Full-format keys everywhere
All public keys include the sign bit, so this is a true "unified
format".  The cost of computing this sign bit is low but not
negligible: efficient key generation will use Edwards format, so gets
it for free.  But a Montgomery-ladder-only implementation will require
an extra inversion, so key generation would be slowed by ~10%.

D) DH-type keys everywhere
All public keys omit the sign bit (Montgomery x public keys are used
for everything).  For signatures, the sign bit is included as part of
the signature (Robert Ransom suggested this, and TextSecure is using
it).  This means a very slight reduction in security, as each party
essentially has two signature keys, rather than one, so an attacker
could try to forge a signature against either of these keys.


All of these options seem reasonable to me, what do people think?


Trevor