Elliptic Curve Cryptography: ECDH and ECDSA

http://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/

by onestone • 11 years ago

41 3 11 years ago

andrea.corbellini.name

tptacek• 11 years ago

Some things to be aware of if this article is inspiring to you:

1. You have to be especially careful with ECDH that the points you receive from your counterparty are valid for the specific domain parameters you're using, or else you can open yourself up to attacks. For this reason among others, cryptographers are converging on modern curves specifically designed to make it easier and safer to communicate points; Curve25519 is an "early" example of such a modern curve.

2. There's an emerging consensus that ECDSA is unsafe, due to its dependency on a random nonce. That nonce is surprisingly hard to get right: it needs to be a full-width number, with that width defined by the curve parameters, for which all the bits are unpredictable. This is an even stricter requirement than a CBC IV or a CTR nonce. Single-digit bit biases in ECDSA nonces have been exploited to recover keys!

Very few people write their own elliptic curve core code; most modern systems either use Nacl, or pilfer Curve25519 from it.

iCHAIT• 11 years ago

Last semester I was assigned ECC as a project for my Computer Networks Lab, me and my friends wrote these codes in python.

https://github.com/iCHAIT/Elliptical-Curve-Cryptography

You maybe interested in having a look at them. It would be great to hear your feedback. ( Pardon us if our implementation of any algorithm was incorrect, we are still in our learning stages as far as cryptographic algorithms are concerned. )

AlyssaRowan• 11 years ago

I should perhaps point out that this series is based on somewhat outdated elliptic curve techniques. It's a little easier to explain these operations over, say, Edwards curves, and I believe djb's done a couple of talks at hacker conferences explaining exactly that.

In particular, djb et al has eviscerated the argument that curves generated through seeds (for example via the X9.62 method) are in some way provably safe. Anyone can perform a partial second-preimage attack on even a perfect hash, and if they know an attack that affects one-in-a-million curves, they can easily bake a seed to match it: http://safecurves.cr.yp.to/bada55.html - I suppose this will be covered in the next post?

More interestingly, especially in light of if you know that, the most commonly-used elliptic curve for ECDSA/ECDH right now, secp256r1 (otherwise known as NIST P-256 or prime256v1), claims to be verifiably random but deliberately doesn't say where the seed came from. Public questions about this haven't met with particularly enlightening answers.

What I was able to find out wasn't as enlightening as I hoped: the seed for P-256 was computed by Certicom's engineers, working with the NSA. To what end? I don't know exactly, but I gather the precomputation actually had to do with picking parameters amenable to efficient implementation via (at-the-time) optimal, but Certicom-patented, techniques. The NSA use it (and P-384) themselves extensively and seem to trust it - and they haven't backdoored every crypto scheme they've ever had a hand in (their hash algorithms still seem to be fine) - but of course, there's always going to be that modicum of doubt, and unfortunately, whether it was cooked for anything else is beyond my knowledge.

(That's apparently part of why Satoshi Nakamoto chose secp256k1 for Bitcoin instead.)

This is also part of why CFRG were asked to recommend non-NIST curves, and have been focusing on recommending "rigid" curves, based on parameters which are obvious choices which are justifiable by themselves (and have settled on djb's Curve25519 at a ~256-bit strength and Hamburg's Ed448-Goldilocks at a >384-bit strength). They're simpler and faster to implement, too. The ECDH using Montgomery form is incredibly easy by comparison; and currently we're discussing specifics of the signature scheme, which I hope is probably going to look somewhat like EdDSA if it isn't EdDSA exactly.

Elliptic Curve Cryptography: ECDH and ECDSA

Related Stories