Re: [CFRG] Psychic Signatures

[Neil Madden <[e-mail]>]

> On 21 Apr 2022, at 07:56, Eric Lagergren <[e-mail]> wrote:
> 
> Project Wycheproof has a very good set of test vectors like this. They should be table stakes at this point. Alas, (most) test vectors can only demonstrate that the code isn’t _obviously_ broken, which is a low bar. 
> 

After I found this bug I ran the Wycheproof test suite against the JVM - it has a mode specifically to test Java cryptography implementations. Unfortunately, it appears to have been broken by changes made in Java 9 that introduced modules to the Java language. After I hacked around that in a local copy it found the bug immediately. So, a low bar, but one that Java failed to reach anyway.

Ironically, the work that introduced this bug into Java [1] appears to have been partially motivated by a desire to remove older curves [2]:

“Removal of obsolete elliptic curves support, including underlying library libsunec.
[…]
Weaknesses in the implementation of the native library EC code make it necessary to remove support for future releases. The most common EC curves have already been re-implemented in Java in the SunEC JCE provider.”

I’m not sure what “weaknesses” were in the C++ implementation, but it did at least check for this all-zero condition, and with a very clear comment referencing the spec to justify it [3]. So how did this get missed in the rewrite?

Well, lack of tests is one cause - and I note that no unit test was included in the fix (that took 5 months for them to release) [4].

The ECDSA rewrite in Java uses a new constant-time (branch-free) modular big integer framework in the JDK that was developed specifically “for crypto algorithms like Poly1305 and X25519” according to the commit message [5]. The previous C++ implementation uses a generic big integer library instead, so perhaps timing side-channels are the weakness that the above quoted message refers to. 

It’s tempting to conclude that a rush to protect against the "new shiny" side-channel vulns has led to a neglect of much more basic and devastating security checks, but I’ll note that Java’s EdDSA implementation does make the similar (much simpler) check on the range of the s value [6]. As I understand it, forgetting this check in EdDSA would anyway “merely” lead to malleable signatures [7], and not to a total loss of security as in ECDSA. 

The sooner ECDSA goes away the better, but as I learnt when writing up this bug, ECDSA over NIST P-256 is basically the only game in town for current WebAuthn/FIDO authenticator devices, with only a tiny handful supporting Ed25519 (*in addition to* ECDSA) and the one outsider of Windows Hello still using RSA PKCS#1 v1.5 signatures. Sigh.

[1]: https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-8237218 <https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-8237218> 
[2]: https://bugs.java.com/bugdatabase/view_bug.do?bug_id=8251547 <https://bugs.java.com/bugdatabase/view_bug.do?bug_id=8251547> 
[3]: https://github.com/openjdk/jdk/blob/jdk-15-ga/src/jdk.crypto.ec/share/native/libsunec/impl/ec.c#L956 <https://github.com/openjdk/jdk/blob/jdk-15-ga/src/jdk.crypto.ec/share/native/libsunec/impl/ec.c#L956> 
[4]: https://github.com/openjdk/jdk/commit/e2f8ce9c3ff4518e070960bafa70ba780746aa5c <https://github.com/openjdk/jdk/commit/e2f8ce9c3ff4518e070960bafa70ba780746aa5c> 
[5]: https://github.com/openjdk/jdk/commit/f15ab37909c2621bef10332c9b031668bb489de9 <https://github.com/openjdk/jdk/commit/f15ab37909c2621bef10332c9b031668bb489de9> 
[6]: https://github.com/openjdk/jdk/blob/master/src/jdk.crypto.ec/share/classes/sun/security/ec/ed/EdDSAOperations.java#L144 <https://github.com/openjdk/jdk/blob/master/src/jdk.crypto.ec/share/classes/sun/security/ec/ed/EdDSAOperations.java#L144> 
[7]: https://www.rfc-editor.org/rfc/rfc8032.html#section-8.4 <https://www.rfc-editor.org/rfc/rfc8032.html#section-8.4> 

— Neil