Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have only about 2 weeks of cryptography experience mostly in the form of questions on bitcoin.se.

Is Curve25519-java up to date with current Curve25519 standards?

Is Curve25519 itself secure?

In other words, is it safe to use as it a cryptocurrency key-generation and transaction signing & verification algorithm?

share|improve this question
2  
As far as we know, Curve25519 itself is secure. But Curve25519 as specified by Bernstein only supports key-exchange, not signing. For signing I recommend using the related Ed25519 instead. –  CodesInChaos Jan 6 at 15:01
2  
Curve25519-java supports signing, but that wasn't in the original code and thus hasn't seen much review. It's also missing the other Ed25519 goodies, such as deterministic signatures, batch verification, or the faster fixed base multiplication. –  CodesInChaos Jan 6 at 15:18
3  
That Ed25519 implementation is glacially slow. Both the Curve25519-java implementation and the ed25519-java you linked aren't constant time, and thus potentially open to timing attacks (probably not a practical issue in this context). –  CodesInChaos Jan 6 at 15:31
2  
I just checked: It simply pushes the responsibility onto the caller. Since it's pretty hard to generate a good enough nonce, any caller who isn't a crypto expert will almost certainly get it wrong. –  CodesInChaos Mar 27 at 18:21
2  
@Gracchus The API of Curve25519-java is so awkward that few people will be able to use it correctly. It doesn't matter if your crypto works in theory if nobody is able to use it. –  CodesInChaos Mar 27 at 18:36

1 Answer 1

up vote 1 down vote accepted

Related to Curve25519

Curve25519 seems to be secure so far. Yet, you have to remind yourself that Dr. Bernstein specified Curve25519 for key-exchange. Meaning: key-generation, transaction signing, and verification are somewhat different beasts – you might want to cross-check on that before jumping toward Curve25519. Sure, Curve25519-java supports signing… but I’m not aware of a thorough, well-vetted cryptanalysis of the signing side of things. There might be issues with it, which have yet to be checked for to be found.

Related to Curve25519-java

NxtCoins.NL reports that BCT user named Jesse James, also known as DoctorEvil, reviewed the Java implementation and he seems to think it is safe. Quoting his publication: “Crypto Review of Curve25519.java & Crypto.java”, last modified on 2014-03-14:

Crypto Review of Curve25519.java & Crypto.java

By DoctorEvil on Nextcoin.org
Sponsored by MSIN on BitcoinTalk.org

TL;DR

NXT's Crypto.java and Curve25519.java look kosher aside from a signing bug that is currently being worked around.

General Methodology

  1. Reviewed the primary/secondary literature on Curve25519 and EC-KCDSA to evaluate them vis-a-vis the NXT use-case.
  2. Re-implemented these primitives from scratch in Python (differently than the Java version).
  3. Scoured every line of the Crypto.java/Curve25519.java.
  4. Ran tests to uncover output discrepancies between my implementation and the Java version.

Choice of Algorithm

Curve25519+EC-KCDSA are theoretically defensible choices for NXT's use-case. However, since cryptocurrency applications are dominated by signature verification, Ed25519 would have arguably been a slightly better pick (although no high quality Java implementations of it exist so NXT's choice is understandable).

Signing Bug

As I (and others) have noted before, the Curve25519.sign function has a legitimate flaw that causes it to occasionally produce invalid signatures. This flaw may have arisen because the original C code the Java was ported from used unsigned primitive integral types underlying its representation of big numbers whereas the Java port is restricted to signed types.

BloodyRookie's proposed patch is essentially sound, although it can be simplified and made constant-time. Here is a fixed sign function inspired by his changes:

(Java sourcecode)

public static final boolean sign(byte[] v, byte[] h, byte[] x, byte[] s) {
    // v = (x - h) s  mod q
    int w, i;
    byte[] h1 = new byte[32], x1 = new byte[32];
    byte[] tmp1 = new byte[64];
    byte[] tmp2 = new byte[64];     
    // Don't clobber the arguments, be nice!
    cpy32(h1, h);
    cpy32(x1, x);       
    // Reduce modulo group order
    byte[] tmp3=new byte[32];
    divmod(tmp3, h1, 32, ORDER, 32);
    divmod(tmp3, x1, 32, ORDER, 32);        
    // v = x1 - h1
    // If v is negative, add the group order to it to become positive.
    // If v was already positive we don't have to worry about overflow
    // when adding the order because v < ORDER and 2*ORDER < 2^256
    mula_small(v, x1, 0, h1, 32, -1);
    mula_small(v, v , 0, ORDER, 32, 1);     
    // tmp1 = (x-h)*s mod q
    mula32(tmp1, v, s, 32, 1);
    divmod(tmp2, tmp1, 64, ORDER, 32);
    for (w = 0, i = 0; i < 32; i++)
        w |= v[i] = tmp1[i];
    return w != 0;
 }

I have tested this patch with over 100,000 random keys/messages.

Non-standard Algorithm Tweaks

EC-KCDSA as implemented by Crypto/Curve25519.java does not exactly match the specification per IEEE P1363a. In particular:

It modifies EC-KCDSA to be deterministic. IMHO, this is good change. However, the implementation uses a non-standard deterministic signature nonce generation scheme; RFC6979's or Ed25519's scheme would arguably have been better choices on the basis of having been more looked at. That said, I couldn't find anything obviously wrong with the scheme used.

The implementation also deviates from the standard with regard to the computation of w, instead computing it as H(H(m) + x1) (using the terminology of Guide to Elliptic Curve Cryptography ). That said, I couldn't find anything obviously wrong with this deviation; it appears sound.

The implementation's EC-KCDSA key generation is also non-standard due to complications of Curve25519 using x-coordinate only representation. While this ambiguous representation is not problematic in the context of Diffie-Hellman key agreement (for which Curve25519 was specifically designed), it is inconvienent for naïve EC-KCDSA. The implementation uses a workaround during key generation to address this issue. While I couldn't find any reference to anyone else using the specific workaround, it appears to me to be sound.

Curve25519.verify uses a variant of a Montgomery ladder differential addition chain to calculate the curve point (vP + hG). I can't find any reference to this variant in the literature and this is easily the most optimization-obfuscated part of the implementation. That being said, nothing about it stands out as wrong and I can understand the performance motivation of using the variant.

Signature Malleability and Signature Canonicalization

It's worth noting that Daniel Bernstein, the primary designer of Curve25519, explicitly states in his paper on the related Ed25519 signature scheme that he does not consider signature malleability a part of the threat model when designing signature schemes. This should give pause to those who think they will be able to define canonicalization conventions to eliminate all sources of malleability. It may be possible to achieve using such conventions but it is not safe to assume without formal, peer-reviewed proof.

As far as I can tell, NXT's fix in response to the attack I reported earlier, makes it immune to signature malleability.

One malleability-related observation: public keys are EC x-coordinates over a field of order 2^255-19. This means every public key has two 32-byte representations. While an interesting sidenote, I don't see how this opens up any avenues for attack in the context of NXT.

I'd also like to make one correction to my earlier vulnerability report. The GROUP_ORDER constant in Curve25519 I reported as 2^252+2^124 (from misreading of a code comment) but is actually defined as 7237005577332262213973186563042994240857116359379907606001950938285454250989. My exploit code worked anyway simply because it used the constant as defined.

Side Channel Attacks

The implementation leaks a small amount (up to 2 bits?) of private key information via timing during signing in Crypto.sign because this function recomputes the signing key from the passphrase each invocation (Curve25519.keygen is not timing attack resistant when used to generate EC-KCDSA keys). I don't see any way to exploit this in the context of NXT. However, precomputing the signing key once at user login and passing it into the sign function would be appropriate if NXT were to ever have a code path where an external observer could cause a target to sign anything on-demand and observe it's timing (e.g. like some interactive authentication protocol).

Alternative Implementation

As part of my analysis I developed an alternative Python implementation of the crypto primitives. As noted, my code is pedagogical (slow and not timing-attack resistant). However, since it uses fundamentally different EC arithmetic (affine XY coordinates vs projective XZ coordinates), it serves as a useful sanity check of the Java version's math (as well as makes for a more understandable exposition of the underlying algorithms).

In a test with 1024 signers, it produced the same signature outputs and had the same verification results as the (patched) Java implementation.

Other Checks

The Curve25519 committed into NXT's repository (as of the publication of this report) exactly matches the port distributed by Dmitry Skiba. Not hugely notable, but thought this was worth checking for the sake of the tin-foil-hat crowd.

EC-KCDSA with ECDH

A formal proof of security that they are compatible was out of scope of this review. However, my preliminary investigations lead me to believe it is OK for NXT to re-use EC-KCDSA keys for ECDH key agreement (something which NXT currently does not do but which is implied by road mapped features).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.