No proper way to perform EC DiffieHellman

[davidiw]

In ECDH, we're supposed to take the x value in the point. However, it is unclear to me how we would do so using this library. Perhaps we should extend the notion of point to return the first value in a series (tuple) of values?

See: http://en.wikipedia.org/wiki/Elliptic_curve_Diffie%E2%80%93Hellman

[bford]

Can you clarify what you mean by "take the x value in the point"?

I see, the ECDH spec apparently uses just the x-coordinate as the shared secret, since the only requirement is that the two endpoints can compute the same thing and it won't be further used as input to any other computation (except a hash or seed). Makes sense - but that particular choice might be somewhat to specific to particular curve representations (e.g., Weierstrauss); I would want to make sure that's still reasonable say for Edwards curve representation as well.

If you're not trying to do an implementation of ECDH that's binary-bit-level compatible with the official ECDH spec - i.e., if you're just trying to do "diffie-hellman" with the library - then just use the Encode() method to produce the shared secret. That'll do something reasonable and secure regardless of the specific curve or representation; its only downside is that it might not produce precisely the same bits as the ECDH spec would.

If you do want bit-for-bit ECDH compatibility, it might indeed be reasonable to add API methods to get the X and Y coordinates specifically - but they probably shouldn't be in the abstract.Point interface since their interpretation are curve-specific and wouldn't apply at all for integer groups for example.

[davidiw]

In EC, a point consists of an (x, y) pair. As you also read in the spec, the x of the (x, y) is used as the DH value.

While binary compatibility is a concern, I'm willing to defer that for functionality and usability. My bigger concern is the security of using "Encode" as well as the (x, y) combined value. Perhaps the Encode call embeds semi-static values for certain bit positions (such as the length in bytes of x or y) that might compromise the security of the DH.

[bford]

Certainly not every bit produced by Encode is going to be unbiased or unpredictable, but that's also the case if you just use the x-coordinate: e.g., when using P-256, the probability of the topmost bit being a 1 will be significantly smaller than the probability of the topmost bit being a 0, because the field modulus is less than 2^256 (but greater than 2^255). In Curve25519, the topmost bit of the x-coordinate will always be 0 because the modulus is only 255 bits. This is all totally standard and normal. And it's not just the high bits: e.g., many curves have cofactors (including Curve25519), which means that the result of any normal DH will be a multiple of 4 or 8 or something like that relative to the base point; hence the least-significant bits will be far from "unbiased" either.

The upshot is that no one should ever be using the "immediate" output of any DH computation to pick an unbiased random number (e.g., to pick a lottery winner) or something like that. The output of a DH must always be run through a hash, or used as a seed for a symmetric cipher, or otherwise used in some cryptographic context that doesn't care if every single bit is unpredictable or unbiased as long as "enough" bits contain good entropy. Given that, either using the x-coordinate or the result of Encode() should be just as good.

[bford]

Hi David, does my answer above address the issue? If so please close this Issue. Thanks.

[davidiw]

In some ways yes, others ways no. Perhaps more generally speaking, we should open an issue or keep a doc of things that are being done in a non-standard way. I am concerned that it may be very difficult to have other libraries (and platforms) talk to an application using this crypto library.

I do agree that using Encode vs x as a byte array is likely to offer similar security, but it is also not compatible with other libraries. I'll leave it to you to decide how to go forward.

[bford]

Perhaps it would be better to call this a crypto "framework" rather than a crypto "library", because its primary goal is not to be just a collection of random pieces of crypto functionality (though that may be how it seems at times), but a small but powerful set of "hourglass API" type abstractions and corresponding implementations mainly for building new decentralized systems, like Dissent. Backwards compatibility with existing formats and such is sometimes relevant but is not a primary goal for the framework as a whole: maintaining complete format-compatibility with all the existing random crypto protocols and formats would tie our hands more than I want to in terms of design. Not to say backwards compatibility isn't important at all - I want to be able to incorporate backward compatibility with selected, particularly important formats (e.g., I'm thinking some compatibility code for reading OpenSSH, GPG, and PKCS key-pairs and such might be useful) - but I don't see these as the most "central" pieces of the framework.

[davidiw]

I think you hit the nail on the head when you stated "maintaining complete format-compatibility with all the existing random crypto protocols and formats would tie our hands more than I want to in terms of design". That's where we got lost in code design in the C++ case. At any rate, could we include an issues file and mention some of these general concerns? or even add some summary of this to the readme?

[bford]

Absolutely! Sure, perhaps just put it in the README for now, and we can move it elsewhere if it ever gets too lengthy to be there.

[bford]

David, could you add what you think should be in the README about this and then close this issue? Thanks.