Elliptic curve crypto on a micro controller

[Janne Oksanen]

I've been listening to Security Now long enough to know that with crypto you should always reach out to more knowledgeable people to make sure you're doing it right.

I need to implement a secure pairing of IoT devices. To do that I'm thinking I will need to use asymmetric crypto with the public key printed on the new device. Then that key will be entered into the user interface of the hub and the hub reaches out to the new device and does a Diffie-Hellman key exchange to establish a symmetric key for the network traffic. So far so good?

Because this code will be running on a micro controller there are some resource constraints (EEPROM, RAM, CPU cycles). That's why I'm thinking I should use elliptic curve crypto so the key size will be as small as possible while still maintaining security. I know better than rolling my own so I searched for a library implementation and found something called mirco-ecc (http://kmackay.ca/micro-ecc/).

Micro-ecc of course depends on a cryptographically secure random number generator. Because I'm working with a micro controller my options are a bit limited. The controller, however, does have a true random number generator that feeds from the radio receiver. According to the data sheet it's able to produce two bits of entropy every 1µs. So I do have a robust source of entropy. Next I searched for a cryptographically secure pseudo random number generator that I could use with the entropy generated by the radio receiver. I found a variation of Mersenne Twister called TinyMT (https://en.wikipedia.org/wiki/Mersenne_Twister#TinyMT). There is a library available on GitHub from the original authors and I'm thinking I could create a wrapper that initializes it from the TRNG and interfaces with micro-ecc library.

Am I on the right track here? What do you guys think?

 

[PHolder]

I would at least look for an implementation of SALT for your device (or one that will build for it and be efficient enough for your purposes.) There are even versions for 8-bit micro-controllers, such as: https://munacl.cryptojedi.org/ SALT should offer Curve25519, which may be more efficient than other choices for asymmetric crypto on limited devices.

In any case, you may be overkilling your design. I don't know if you're making many of these devices or just a one-off. The simplest approach provides an initial one time (pairing) password unique to each device that is either generated from something unique about the device, or pre-loaded by the machine that loads the firmware into the device. This way you can have a reset button on the device to reset it back to the initial state if it should ever go wrong. (And it WILL go wrong.) Apple's approach for this, for example, puts this info into a little QR code on the device to aid in the pairing.

Using this approach allows you to know (or build) an initial symmetric key to talk to the device while you provide it with something more durable from the controlling host. (Remembering that the controlling host probably also can supply an initial source of randomness.) You can also use this initial key to build a "cheap" form of signature of updated firmware if the device has an emergency recovery mode for its firmware when reset to known good. (Because as already stated, things WILL go wrong, especially during development/testing.)

 

[Janne Oksanen]

The simplest approach provides an initial one time (pairing) password unique to each device that is either generated from something unique about the device, or pre-loaded by the machine that loads the firmware into the device.

Right, this is what I was thinking. I was a little confused there. We don't need a Diffie-Hellman exchange because the network controller already has the public key of the new device and can just send the symmetric network key in encrypted form. And only the correct device will be able to decrypt it and join the network. But I don't think we want the pairing key to be symmetric or anyone who's seen the pairing code can make a man-in-the-middle.

I will look into SALT. Thank you for the suggestion. The performance of the library is not critical since it's only used once for pairing and after that the network communication will be using hardware accelerated AES. So whether the pairing takes 3 seconds or 10 seconds is not really an issue as long as it's secure and the code can fit on the chip.

 

[PHolder]

But I don't think we want the pairing key to be symmetric or anyone who's seen the pairing code can make a man-in-the-middle.

I understand your concern, but it will always boil down to building initial trust. Since, in the ideal situation, this is only ever done once, and it's unlikely any future attacker is present during setup, and since the information needed can require physical presence during setup, it seems many IoT devices use an approach that is the least complicated, and theoretically risks a person-in-the-middle attack. I'm not advocating for this approach, but I certainly understand how it develops, because in the end the system HAS to be understood by mere mortals, and because things WILL go wrong, you need to be able to have a reliable way to start fresh.

 

[Janne Oksanen]

How do you know that the key on those IoT devices is symmetric? I mean from the user's standpoint the procedure looks exactly the same unless there's some extra step to actually verify that you're connecting to the right device (blinking LEDs, pressing a button or something). With asymmetric keys that's not required.

 

[PHolder]

How do YOU know that the asymmetric key is from the device and not from a person-in-the-middle? ;-)

 

[Janne Oksanen]

Because only the actual device will have the private key needed to decode the messages sent by the network controller. The private key is not written on the box like the symmetric key would be.

 

[PHolder]

Fair point, but since you could just as easily write a symmetric key into the device that only you (the manufacturer) and it (the device) knows, what's the difference? You don't need to reveal the symmetric key, and you do need to guard it, just like the asymmetric key... so I don't really see much difference... ? I guess you might be implying you write the public key on the box to identify the device (or use the serial number to look up the public key) but again, I don't think that buys you much in a scenario of initial setup (or a full reset).

Also don't forget to plan for if the device needs to be forcefully reset, or the network password (WiFi) needs to be reset, or if it's given away or resold, or if the protocol you chose is found out to be weak (say for example, you chose RSA, and quantum crypto can break it) how do you start completely over? All you're going to have is the serial number (or an initial password, or something physically on the device, because you won't be able to rely on the new owner having the original box.)

 

[Janne Oksanen]

you could just as easily write a symmetric key into the device that only you (the manufacturer) and it (the device) knows, what's the difference?

Let's think about this. How would this work? Would all the devices have the same symmetric key? In that case you have a secret to keep and if that secret ever gets out (by disclosure or reverse engineering) all of your devices are compromised. Or would the network controller need to be updated with all they potential keys as they come out of the factory? In that case you would have many secrets to keep and reverse engineering a network controller could reveal all of them. The difference with an asymmetric key is that every client device holds a secret that is specific to that one device. There is no need to have a central repository of keys. And reverse engineering that one key only gives you access to that one device which you obviously already have access to.

Also don't forget to plan for if the device needs to be forcefully reset, or the network password (WiFi) needs to be reset, or if it's given away or resold, or if the protocol you chose is found out to be weak (say for example, you chose RSA, and quantum crypto can break it) how do you start completely over? All you're going to have is the serial number (or an initial password, or something physically on the device, because you won't be able to rely on the new owner having the original box.)

Maybe I'm missing something, but to me it seems like all these challenges are exactly the same regardless of the type of encryption type (symmetric/asymmetric) used for the initial pairing. What is the difference? Or is this just a side note?

 

[PHolder]

What is the difference?

That was my entire point. You don't need asymmetric encryption, though you may want it to be "cool." It costs more compute for not to much extra gain, and it comes with all the same problems of keeping secrets and initial trust establishment. The device still needs a unique secret key, the service host still needs to have a list of the corresponding keys, and you still need to have a way to reset the device from fresh.

My suggestion would be probably be something simpler. The device presumably needs a unique MAC address which can be its serial number. It will then be written physically onto the device (on a sticker presumably.) You will come up with some algorithm which will be proprietary to your service (but will be impossible to keep secret.) You can input the MAC and maybe the date and time or something from the server, and it will generate a temporary symmetric key. (This will still be possible to person-in-the-middle, but I think that is actually unavoidable if you think about it... and your risk is ONLY during initial install for the briefest moments while that initial key is in use.) The first steps are to set a new, permanent symmetric key from HQ, and then use that for all future communications. (Or you could set a shared secret, which is fed into your previously mentioned algorithm that gets mixed with the time from the server on every occasion where a new link is established.)

The idea being you can get away with just a secure cryptographic hash (SHA256 say) and a secure symmetric encryption (AES256 say) and do something like:

--- device in initial state ---
serviceUniqueVal=FooBar123
tempID = MAC
aRandVal = BestPossibleRandom()
initialID = HASH(tempID,serviceUniqueVal,aRandVal)
device->service: HELLO I'M NEW; initialID
device<-service: WELCOME; DATE=12345; ServiceID=98765
initialKey = HASH(initialID,DATE,ServiceID,serviceUniqueVal) (done on both ends)
verifyMsg = HASH(initialKey, serviceUniqueVal) (done on both ends)
device->service: verifyMsg
device<-service: SymEnc(initialKey, newSharedSecret)
saveLocally(savedServiceID=ServiceID, savedSharedSecret=newSharedSecret)


--- device in ongoing state ---
msgNumber=0
aRandVal = BestPossibleRandom()
device->service: HELLO I'M BACK; savedServiceID, aRandVal
device<-service: WELCOME BACK; DATE=12345; SessionID=091827
sessionKey = HASH(SessionID,savedSharedSecret,DATE,aRandVal)
...
msg_n = SymEnc(sessionKey, msgNumber++, "message contents")
device->service: msg_n
device<-service: rsp_n
...
device<-service: SessionExpiresPleaseRenegotiate

Another option to consider is the NOISE protocol, but it will have higher computational requirements as it definitely uses asymmetric keys. (It's what Signal uses, I believe, and definitely what WireGuard uses.) https://noiseprotocol.org/

 

[Janne Oksanen]

It costs more compute for not to much extra gain

In this application it does not matter whether the pairing takes 1 second or 10 seconds. What does matter is that the decision I make now is future proof for at least 15 years from now. So I don't see any reason to cut corners with security if there are no hard constraints force me to do so. I appreciate your input but I'm still going to default to the highest level of security that I can provide for the users. If it turns out that ECC is not practical then I will look into your suggestion.

 

[PHolder]

every client device holds a secret that is specific to that one device. There is no need to have a central repository of keys.

Um... I don't understand your point here. You need to know who should be using which private key, which means you need a list of which public key corresponds to which device. If you don't have this list, then someone can spoof a device with their own key, and you won't be able to tell legitimate devices from fake devices.

 

[Janne Oksanen]

Um... I don't understand your point here. You need to know who should be using which private key, which means you need a list of which public key corresponds to which device. If you don't have this list, then someone can spoof a device with their own key, and you won't be able to tell legitimate devices from fake devices.

Here's how I've figured it would work:

1. You have a network controller that has some kind of UI where you can enter a pairing key (public key) of the device you want to add to the network.
2. You buy a new device. The device has a key printed on the device. The device has a corresponding private key in memory.
3. The network controller sends out a broadcast that has the symmetric network key encrypted with the public key.
4. Only the device with the corresponding private key can decrypt the message and join the network.
5. Device joins the network and gets its own address from the network controller and can start receiving messages encrypted with the symmetric network key.
6. The asymmetric key is never used again. No list of keys required.

Makes sense?

 

[PHolder]

You're implying a customer has at least two devices then? As in at least one controller and one device under control? This is a more expensive proposition than normal IoT devices, because the controller is likely a small single purpose computer of some sort (a RPi or equivalent at minimum.) And it also presents two vectors of attack, rather than one. (You need to keep the firmware in the device secure as well as keeping the firmware/OS in the controller secure.)

Based on that use of two devices, a single asymmetric key exchange for pairing probably isn't too expensive. You still need the budget to carry that crypto code with the system for a single use of course. I get your desire for feeling like it's as secure as you can make it, but for 99.9% of customers, being in their broadcast domain is likely secure enough... most devices don't contain state secrets and it's highly unlikely an attacker is there during an initial paring event.

Also, you still have no way to authenticate the controller to the device nor the device to the controller. (If legitimacy of either is at stake.) A malicious controller will accept any device without requiring a user to enter anything. A malicious controller/device can get in the middle of the interchange at the stage "The network controller sends out a broadcast that has the symmetric network key encrypted with the public key."

If you don't care about corresponding a key to a device, you could skip putting one in the device in the first place. Just have the device contact the controller (insecurely) and have the controller publish its public key. Then the device can pick a random key and handshake the controller securely.

 

[AlanD]

Also, you still have no way to authenticate the controller to the device nor the device to the controller. (If legitimacy of either is at stake.) A malicious controller will accept any device without requiring a user to enter anything. A malicious controller/device can get in the middle of the interchange at the stage "The network controller sends out a broadcast that has the symmetric network key encrypted with the public key."

No, the suggestion was that each device has an identifier, which is also that device's public key, printed on it. On the first device, you enter the public key of the second ( and third...n) device(s). The first device then sends out the network key, encrypted with the second device's public key. Only the second device can decrypt the network key and authenticate to the first device.

 

[PHolder]

Only the second device can decrypt the network key and authenticate to the first device.

I think you're not thinking like an attacker. The "fake" controller doesn't need the user to enter anything. If the controlled device doesn't know who's in charge (because how would it?) then it will respond to any device that can use its freely available public key to construct a message to it. If you don't have two way authentication, or authentication of both parties, then you don't actually have authentication. Without a way to enforce that a controller is legitimate it could send the device a message as if it were invited to join the network, then supply it with bad firmware, and then the attacker is now there forever.

 

[ChrisK9EQ]

Highly constrained systems will likely want to use symmetric keys. The Microchip SAML11 does a bang-up job of protecting secrets and also has hardware AES. It's cheap (less than $2), very, very low power, with an M23 core. AES-CCM is probably the preferred mode since it only requires AES-encrypt to operate. You need to use the "master key" to generate session keys that are unique to each session. The session key, along with a TRND nonce is needed along with a message counter. (See NIST SP-800-38C). Two (or more) devices can create a unique session key by sharing a TRND they each generate and sharing it with the other device(s). These TRNDs are then encrypted with the "master key" to produce a session key thus resulting in the "master key" never encrypting the same thing twice - as required by good security practices.

If you need authentication of individual IoT devices, then use a server to provide crypto services. Naturally each IoT would require its own secret key tied to an ID which only that IoT device and the server know. Best to use an HSM on the server.

If you're doing Bluetooth, you may want to consider the nRF 52840. For the crypto library, I highly, highly recommend WolfSSL which includes WolfCrypto. This runs on almost any CPU and OS and is way better than OpenSSL. (Nobody should use OpenSSL with WolfSSL (and others) available.)

 

[Janne Oksanen]

I think you're not thinking like an attacker. The "fake" controller doesn't need the user to enter anything. If the controlled device doesn't know who's in charge (because how would it?) then it will respond to any device that can use its freely available public key to construct a message to it. If you don't have two way authentication, or authentication of both parties, then you don't actually have authentication. Without a way to enforce that a controller is legitimate it could send the device a message as if it were invited to join the network, then supply it with bad firmware, and then the attacker is now there forever.

This is something I had not thought of so let's walk through this attack model and see what happens.

1. Attacker has access to the public key of the new end device
2. Attacker constructs a fake man-in-the-middle device to look like the network controller to the end device and the end device to the network controller
3. User powers up the end device for pairing
4. Fake network controller sends a pairing request to the new device
5. New device pairs with the fake network controller
6. User adds the public key to the real network controller
7. The man-in-the-middle device cannot join the network because it doesn't have the private key of the end device
8. The man-in-the middle device can't relay the pairing message to the end device because the end device is not in pairing mode

So I think from that perspective my solution is secure. Let's play out another scenario:

1. Attacker has access to the public key of the new end device
2. Attacker constructs a fake man-in-the-middle device to look like the network controller to the end device and the end device to the network controller
3. User adds the public key to the real network controller
4. Man-in-the-middle device cannot respond to pairing message because it's encrypted with the end device's public key.
5. Man-in-the-middle device cannot temper with the message because it cannot decrypt it.
6. End device pairs with the real network controller.

Is there some other scenario that could happen that I have not thought of? Or am I just plain wrong somehow?

 

[PHolder]

New device pairs with the fake network controller

I suspect after the device pairs with any malicious controller then it is at this point the jeopardy starts for the end device... depending on what this pairing means the fake controller can now do to the end device? If it could, say, offer it "new" malicious firmware, which it would accept, then all bets are off at any point thereafter...

 

[Janne Oksanen]

"new" malicious firmware

Let's say firmware updates need to be signed. That should take care of that problem. Anything else you can think of?