Hi Ilari:
I do think ECDSA25519 is unambiguously specified and is not allowed to
be abused by cutting corners, sincee the security consideration section
explicitly writes/
/
/
/
/ "T//o prevent intra-protocol cross-instantiation attacks, ephemeral
private keys MUST NOT be reused between instantiations of ECDSA25519 or
ECDSA448."/.
A method for inversion of non-zero elements of GF(q) is provided in
Appendix E.1 of draft NIST SP 800-186, which writes
/If one is concerned about side-channel leakage, one should compute
u^{−1} indirectly by first computing the inverse of the blinded
element λu, where λ is a random nonzero element of GF(q), 1984 and
subsequently computing λ(λu)^{−1} = u^{−1}. This yields an inversion
routine where the inversion operation itself does not require
side-channel protection and which may have relatively low
computational complexity./
Specifying ECDSA25519 and ECDSA448 simply allows its use, but does not
mandate this.
Other arguments that one could change EdDSA to make this more secure
against trivial fault attacks and about other cool things (like qDSA) do
not seem to be relevant to the lwig curve draft or the COSE WG and seem
more appropriate for, e.g., the CFRG mailing list.
Best regards, Rene
On 2020-11-09 11:19 a.m., Ilari Liusvaara wrote:
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
_______________________________________________
COSE mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/cose
--
email: [email protected] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867
_______________________________________________
COSE mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/cose
