Re: [COSE] draft-ietf-lwig-curve-representations-13

[Ilari Liusvaara <[e-mail]>]

On Fri, Nov 06, 2020 at 02:37:01PM -0500, Rene Struik wrote:
> Hi Goran:
> 
> Please find below some brief feedback on your note:
>
> - ECDSA has been around since 1999, has been widely standardized, and has
> seen lots of analysis, where ECDSA25519 is simply yet another instantiation.

Unfortunately, there are some issues:

- ECDSA signing involves inversion modulo order, which is nasty to
  implement and slow. Especially as it needs to be made resistant
  to side-channel attacks, as side channels against that can be used
  to recover the private key.

- ECDSA25519 is not well-defined in general case. The issue is that
  it depends on bit order of hash function output as it involves
  truncating hash to 253 bits (which is not divisible by 8), and not
  all hash functions define their output bit order.

  And even with hash functions that do define output bit order, not
  all define it the same way. For example, output bit order of SHA-256
  and SHA3-256 (and SHAKE*) seems to be different, and thus ECDSA25519
  of SHA-256 hash is calculated differently than ECDSA25519 of SHA3-256
  hash.

  Even if one restricts to NIST-approved hash functions, this breaks
  traditional signahash-style ECDSA interface, as hash function used
  is not passed in.

  None of P-256, P-384 nor brainpool curves ever trigger this special
  case. P-521 in theory could, but in practice that does not happen
  either, as it would require kind of hash function nobody uses. B-x
  curves could also in theory, but in practice those are either not
  used, or used with hashes that do not need truncation.

> Signature generation and verification times for ECDSA25519 should be similar
> to those of Ed25519 (since timing is dominated by scalar multiplication,
> where one could simply use Montgomery arithmetic [3]). In my personal view,
> ECDSA25519 may be more secure than Ed25519 (if only because it is
> non-deterministic, see Security section [6]); similar side-channel care has
> to be taken in either case.

I do not think that is correct, because ECDSA has that inversion mod
order:

- The time to perform that is not negligible. Even compared to scalar
  multiplication.
- In signing, it is one more operation to be side-channel resistant.
  (the outer hash computation in Ed25519 does not need to be side-
  channel resistant).

And that determinism versus non-determinism is not hard property of the
signature schemes. There is deterministic ECDSA, and that can be appiled
with any curve where ECDSA is well-defined. And while making Ed25519 noisy
or non-deterministic breaks the specificaition, it does not break
interoperability.

(I have actually written non-deterministic Ed25519 implementation as
part of really horrible special-purpose TLS 1.3 implmentation. Yes, it
does interoperate in real world.)



And some notes about making version of Ed25519 that uses SHA-256:

- The Ed25519 subkey derivation needs to be split into two hashes
  instead of running once and splitting the result. The input fits into
  one block anyway, so it will still be fast. For example,
  a=SHA256(0|k_priv) and seed=SHA256(1|k_priv).
- It is not trivially possible to replace the inner hash SHA512(seed|M)
  with SHA256(seed|M). However, it turns out that the order in fact
  does allow this replacement.
- If one wants noisy signatures, one way is to replace SHA256(seed|M)
  with SHA256(seed|M)^noise. The noise must be independent of the
  private key and seed, but otherwise bad noise (including completely
  broken one) will not cause immediate catastrophic failure.
- If one wants randomized signatures, due to the same reasons as why
  the inner hash may be replaced, it is recommended to generate more
  randomness than 256 bits, and then use SHA256 to squash it to 256
  bits. This hedges against not-quite-ideal random number generators
  that would otherwise cause catastrophic failure. However, it will
  not prevent broken random number generator from causing immediate
  catastrophic failure.
- The outer hash SHA512(R|A|M) can trivially be replaced by
  SHA256(R|A|M).

However, if one truly wants the lightest signatures in code size, AFAIK
there is no beating qDSA-type constructions. The notes above about
randomized, noisy and deterministic signatures apply here too (except
for the seed expansion, one could use seed=SHA256(2|k_priv)), as the
nontrivialities are tied to order, and Curve25519 and Edwards25519
being isomorphic/isogenous share the order.

The different seed expansion is to remove nasty interaction between
the two signatures. As otherwise signing the same message with both
using the same private key results in key compromise.

qDSA operates on x-only montgomery ladder, which means it does not
need point compression and can share most of the key agreement code.
One drawback of this is issues with fault attacks. 

And with regards to Edwards448/Curve448, analogous nontrivialities
would apply to hash function with at least 448-bit output, which means
one could use 512-bit hash with curve of that order.


-Ilari