By DoctorEvil on Nextcoin.org
Sponsored by MSIN on BitcoinTalk.org
NXT's Crypto.java and Curve25519.java look kosher aside from a signing bug that is currently being worked around.
- Reviewed the primary/secondary literature on Curve25519 and EC-KCDSA to evaluate them vis-a-vis the NXT use-case.
- Re-implemented these primitives from scratch in Python (differently than the Java version).
- Scoured every line of the Crypto.java/Curve25519.java.
- Ran tests to uncover output discrepancies between my implementation and the Java version.
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).
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:
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.
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.
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.
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).
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.
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.
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).