Security requirements for EC Diffie Hellman implementation

I'm working on a crypto library to be used in a firmware product. Beside other things we need key agreement based on Diffie Hellman.

Since resources are very limited we use a crypto accelerator on the MCU for which a low level library exists, allowing beside other things to make elementary calculations on elliptic curves over $GF(p)$ and $GF(2^p)$.

Now I tried Diffie Hellman and tested the results against various test vectors. It works fine.

But, of course, I know that this self-made approach can be dangerous, when the detailed implementation is open for attacks, whatsoever kind of.

So the question: What requirements must be considered additionally to plain algorithms in order to make the outcome a "secure" solution?

To make a statement to the answers below:

1) We must use P-256 (it's not a choice)

2) What do you mean with large private multiplier? In my implemantation the private key is taken randomly between $1 \ldots 2^{256}$ (32 Bytes) and then reduced to modulo group order. Is this acceptable?

3) I use a hardware RNG (TRNG).

4) We must use KDF specified within NIST 800-56A Rev2

5) The other side is authenticated by ECDSA based on a certifcate

6)

side channel resistance is a hairy issue

I have to larn about what this is

7)

If you only have the really basic operations: make sure your scalar multiplication is constant-time.

Why is this required?

• What field are you using? 2^p or p? – mikeazo Sep 27 '16 at 18:34
• I use p. ECC P-256 in detail. – michael Sep 28 '16 at 6:59
• What sort of ECC operations do you have? Only the really basic ones like ad and double or full scalar-multiplication? – SEJPM Sep 28 '16 at 14:11
• It would improve the answers if you state what your threat model is. Is the attacker attacking over the internet? Is he on the same LAN? Is the attacker allowed to attach an oscilloscope to your power-supply? Can they stick your device in an electron microscope? – Patrick M Nov 23 '16 at 13:56

Here's the obvious advice (other than "don't roll your own protocol/solution; reuse one that has already been vetted"):

• Make sure that you use a secure curve. Obvious alternatives are P256 (with possible P224 or P192 if you need better performance, and don't mind cutting into the security somewhat), or (if you don't trust the US Government) a NUMS curve or a Brainpool curve. Normally, I'd suggest Curve25519; however if you have a crypto accelerator that's targeted towards arbitrary curves in Weierstrass form, well, it could do Curve25519, but it's more hassle, and you lose the advantages you normally gain from Curve25519.

• Make sure that you use a large sized private multiplier; for P256 (or any other curve based on a 256 bit prime), that means a 256 bit multiplier (and note: this doesn't mean that the 255th bit must be set; it means that all values between 1 and $2^{256}$ are possible). You can make things go a bit faster if you use a smaller range, however that also cuts into the security.

• Both sides need good entropy; if the attacker can guess the private multiplier of either side (or even reduce it to a not-huge subspace), he can recover the shared secret.

• Validate the point that you receive from the other side, that it is a point on the curve; for example, if the other side sends both $x$ and $y$ coordinates, make sure that when you plug them into the Elliptic Curve equation, both sides evaluate to the same value. There are cases where you can skip this (for example, if you use "point compression", or if you always generate a fresh random private multiplier for each exchange), however it's so cheap that it just makes sense.

• Use a good KDF to convert the ECDH shared secret into the keys that you'll actually use.

• Remember that ECDH does not authenticate who you're actually talking to. Unless no one other than the person you're talking to can possible send (or modify) a message to you, you need a way to authenticate the other side.

• Additional point: If you only have the really basic operations: make sure your scalar multiplication is constant-time. – SEJPM Sep 27 '16 at 21:15
• @SEJPM: side channel resistance is a hairy issue; depending on what side channels are available to the attacker, he might not need constant time..., or he might need to stand up to a full DPA/EMI attack. – poncho Sep 27 '16 at 21:20
• see my edits above. – michael Sep 28 '16 at 7:25

Depending on your use-case and threat model, you may well need to consider side-channel attacks. Given your edit suggesting that you've never heard of this, consider the following situation. You have a 4-digit PIN, and you have the following algorithm for checking said PIN when it's entered

// Probably not valid C, but the language is irrelevant here.
bool check_pin(char[] guess, char[] actual_pin){
for(int i=0; i<4; i++){
sleep(1);
if(guess[i] != actual_pin[i]){
return False;
}
}
return True;
}


I would like to attack that PIN using this algorithm. Though my search space is 10,000 possible PINs, it's fairly clear that I can guess any value of actual_pin within only 40 attempts by using a stopwatch. I guess 0000, 1000, 2000, ..., 9000 until I find that one of my guesses takes slightly longer to return than the others. Clearly, that guess has the first digit correct because it hits the sleep twice. I then attack the second digit by a similar method, then the third, then the fourth.

If the sleep were to be removed, it's still possible to use large numbers of guesses and nanosecond timing mechanisms to attack this implementation.

So, OK, you refactor the above algorithm into:

// Probably not valid C, but the language is irrelevant here.
bool check_pin(char[] guess, char[] actual_pin){
ret = True
for(int i=0; i<4; i++){
if(guess[i] != actual_pin[i]){
ret = False;
} else {
// Do something that takes just as long as assigning ret to False
}
}
return ret;
}


And maybe this algorithm now always takes the same amount of time, meaning the previous attack is completely invalid. Great. Now suppose I were to get an electromagnetic probe and point it at some resistor long the power line to your chip. As the power consumed by your device during this algorithm fluctuates, the amount of electromagnetic radiation emitted by this resistor will also fluctuate. If the true branch of that if statement goes out into the main memory and fiddles a value over there, whilst the false branch just sits and does nothing for a bit, those consumptions will differ, and I'll be able to tell which branch of this algorithm you're dropping down on every iteration.

This all sounds rather far-fetched, but I'm afraid that I've actually done this, against a home-brewed ECC implementation.

As it turns out, ECC is usually based off group exponentiation, which does the bulk of its work in something like this:

// Definitely not valid C, but the language is irrelevant here.
bool scalar_multiply(curve_point base, int[] exponent /*as an array of bits, highest-order bit first*/){
ret = point_at_infinity
for(bit in exponent){
if(bit == 1){
ret = mult(ret, base)
}
base = square(base)
}
return ret;
}


Unfortunately, in ECC, the square and multiply operations are drastically different and will produce completely different power signatures, making it really obvious which of the branches you've just hopped down, leaking your secret exponent without much difficulty. Timing attacks are also possible against these loops, but they usually involve loads of statistical tests, making them a bit harder to explain. Feel free to ask a follow up on how to use timing information to SCA a naive square-and-multiply loop.

Attacks like this are seriously hard, and usually involve a lab with an expensive oscilloscope in them (the one at my university cost tens-of-thousands of pounds), but they work. Timing attacks are much cheaper, but still possible.

This, of course, all depends on your threat model and where your chips are going to get used. If you're planning to distribute these across a large number of people and you're using them to protect millions of pounds in people's bank accounts, then you should probably take threats like this seriously. If you're securing a TV remote or something, it may not be worth bothering.

The take-home point is that, if you work naively, a skilled and well-funded attacker could conceivably leak all the private exponents used by a device that they have physical access to.

• Thanks. I beliefe that this is possible and I also heard about. If a system executes cryptographic functions only for a small percentage of run-time, how can an attacker know, for which times he has to pay attention? When I take an oscilloscope and measure the momentaneus power demand, the picture I get is quite "random". How can I focuss on an intersting time interval? Do I rely on certain patterns, which signal to me: "keep care, a group exponentiation is executed right now!"? – michael Sep 28 '16 at 10:06
• When I did my attacks, I had the target device raise a pin before something worth paying attention to happened, and then lower it again afterwards, which signalled the oscilloscope to turn itself on and off. Yes, this is sort of cheating. That said, the signature from a square and multiply loop is fairly clear. Each iteration tends to start with some low intensity, where all you're doing is jumping back to the start and incrementing the loop variable, followed by the actually hard work of squaring and multiplying. – ymbirtt Sep 28 '16 at 10:12
• This causes a fixed number of "bursts", of exactly two different lengths, each separated by a thin strip of very little activity. It's not inconceivable to spot this, especially if there's something that actually triggers it to start doing its DH negotiation that I can easily press repeatedly. – ymbirtt Sep 28 '16 at 10:14
• (Also worth noting is that the first time I did this I also got some pretty random looking signals from the scope and it turned out I'd forgotten to plug the amplifier in so all I got was literal random noise. Another worthy consideration...) – ymbirtt Sep 28 '16 at 10:18
• BTW: this wasn't your point, but your code to test passwords in 'constant' time really isn't constant time (because taken/not taken branches vary the time). Instead, you should do something like: ret = ret | (guess[i] - pin[i]) (where | is bitwise or); you initially set ret to 0, and at the bottom, you succeed if ret is still 0. That way, you have no data dependent branches. – poncho Oct 27 '16 at 16:46