Code signing on Arduino (aka locked bootloaders)

I’ve searched around, but haven’t really found anything on this topic. I want to implement some kind of code signing or bootloader locking to prevent unapproved code from running, so I can publish firmware updates but prevent someone from publishing a “hacked” version. Code security can’t be a concern here since the binaries have to be sent out anyways for an update and could easily be reverse engineered. However, the only way to run unsigned code would be to hack in an ISP header on the board and flash a different bootloader. That’s fine because it doesn’t compromise the security of any stock hardware.

So it looks like I’ll have to write something myself, but I’m curious what more experienced programmers have to say. If you have any thoughts on any of this please let me know!

Requirements

  • Speed - total boot should not take more than ~2s
  • Size - needs to be as small as possible - 2k to fit in 328p BL section which might not be possible
  • Secure - the signing must be cryptographically secure so that no one else can sign code
  • Compatible - ideally, the implementation wouldn’t break the use of avrdude (or possibly even the Arduino IDE) to make updating easy

My plan so far is as follows:
Code base:
The base will probably start from optiboot, since it has the 1s WDT boot and is only 512bytes. However, EEPROM support is probably necessary (more on that later) which eats into the size considerably. It might be acceptable to remove EEPROM support and just leave EEPROM write.

Signature verification:
The signature/verification needs to be fast, secure, and not take a lot of space. The best option seems to do a Full Domain Hash with RSA. It’s an older signature standard, but should still be very secure, especially since there will be so few published signatures (crypto people correct me if I’m wrong). Before the application starts, I’ll hash the program memory, decrypt an RSA signature, and compare it to the hash.

Hashing:
For hashing, according to this arduino crypto library, it seems that blake2s is by far the fastest. Initial tests show I can hash the entire 32k program memory in about 650ms by loading 1k into SRAM at a time, with no optimizations on the blake2s code. It might be faster with a bigger buffer and some code tweaking. Unfortunately, it requires ~192 bytes of init vectors. That may need to go into EEPROM. The next fastest is SHA-256, but it requires a massive state table that eats up too much space…

Signature decryption:
I think 1024 bits should be large enough that it would cost considerable computing power (and $$) to crack. 512 is definitely too easy, and 2048 is probably unnecessary given that the private key should be completely inaccessible. I think with the full SRAM available, it should be feasible to do 1024 bit decryption in a reasonable amount of time. The public key exponent will probably be fixed at 65537 to avoid having to store it. The modulus, however, will be a full 128 bytes, and needs to be stored in the BL section of flash memory (can’t put it in the EEPROM or it could get changed).

Signature location and Firmware Updating:
Storing the 128 byte signature with the program is a little tricky. If it’s just defined in the source code, it could end up anywhere in memory, and would have to be found and ignored before doing the hash (since the hash is of the program binary without the signature). That would cost a lot of time. The other problem is that avrdude only erases flash pages that get programmed. So if there’s left over program data at some memory address that isn’t used in an update, it will cause the hash to be different than expected.

There are a few possibilities, none seem that great:
Location-

  1. Store the signature in EEPROM, which requires an additional programming step (although it may already be necessary to fit program size)
  2. Manually tweak the hex output during signing to place the signature at some known address in flash, and hard code that in the bootloader.

Updating-

  1. Either modify the hex to overwrite the entire flash contents with known data, or modify the bootloader to do that during every update
  2. Include a program length parameter somewhere, probably in the encrypted signature, but I’m worried that could compromise security (not sure how exactly…)

Program Size:
I’m pretty sure I won’t get this to fit in a 2k bootloader space. That’s not entirely a problem, but I’m not sure how to tell the linker to (or if I even can) start the bootloader code at the right address, but put any code longer than the bootloader section (like the hashing/decryption functions) in a specific place…

I could compile some of the functions separately and place them at the end of application memory, then add a jump instruction at the last address that always goes to the start of the signature verification, wherever that may be. The bootloader would then jump to that jump instruction. This is a bit beyond my expertise; surely there’s a more elegant way of doing this…

If you’ve read this far… thank you!

Keeping people from uploading whatever code they want to devices that they own seems to fly in the face of one of Arduino’s core values, open-source hardware. What specific threat are you even trying to defend against?

Seems rather pointless when anyone with a High Voltage programmer can come in, erase anything you've programmed in, bootloader or otherwise, and then load up whatever they want anyway.

High Voltage programmer http://www.gammon.com.au/forum/?id=12898

Standalone programmer from SD card, no PC required: http://www.crossroadsfencing.com/BobuinoRev17/Programmer.html |500x488

I want to implement some kind of code signing or bootloader locking to prevent unapproved code from running, so I can publish firmware updates but prevent someone from publishing a "hacked" version.

the only way to run unsigned code would be to hack in an ISP header on the board and flash a different bootloader. That's fine because it doesn't compromise the security of any stock hardware.

I don't think I understand your "threat model." "I want to implement two complex cryptographic algorithms in my bootloader, but it's fine if a trivial hardware hack undoes it all..." And "key management"?

What kind of device do you plan to do this for? Who are you trying to stop from uploading their own code, the device's owner or someone else? If it's the device's owner, as I mentioned, this goes against everything the open-source hardware community stands for. If it's someone else, then you're trying to solve the wrong problem. You should try to solve "how do I only let the owner install new firmware", rather than "how do I only let signed firmware be installed".

It's partly academic in interest, but also just a question of making things idiot proof. This is for taking an arduino prototype to production. The idea is to make it easy to load an update via usb, but not easy to put any random code on it that could cause problems. If someone wants to program it with icsp/hv, I have nothing against it because they probably have enough an idea of what they're doing that they realize they may experience unexpected behavior. What I'm trying to avoid is people breaking a product because some guy posted a shoddy arduino sketch. It's also just a really interesting technical challenge.

Have you looked into Atmel's existing app-notes on "secure bootloaders"? It sounds like most of what you want to do could be accomplished simply by using ANY other bootloader than the ones that Arduino uses; no encryption required at all - just "can't load random sketches."

I hadn't, but thanks for the tip. It looks like they generally use symmetric key encryption, either to authenticate the firmware before running it, or to protect its contents during the transfer to the end user/upload to the micro. I wanted to avoid symmetric key because it has to be stored in the bootloader, and if anyone manages to get it, all security is thrown out the window. That being said, people seem pretty confident in the fuses from preventing an easy read, but there's still always the risk of a side channel attack. Their AES bootloader is only 2k, though, so maybe I can get a public key encryption bootloader down to that size...

I wanted to avoid symmetric key because it has to be stored in the bootloader, and if anyone manages to get it, all security is thrown out the window.

So ... your "threat model" includes "someone will pull the bootloader out of the chip, extract the key, use it to build his own counterfeit signed images that he then distributes to your unsuspecting customers"? I guess that's a valid concern, and I've been bitten before by assuming "bad guys" had less access than they actually did (ie "known-plaintext attack".) But it's a pretty big jump form what you said in Reply #5: "I'm trying to avoid is [naive users] breaking a product because some guy posted a shoddy arduino sketch"

I think it's doubtful that you can fit the hash code plus the RSA code in a bootloader (~4kbytes, 2kwords); I spent a bit of time searching for a "reference" RSA application for AVR to get a size estimate, and couldn't find any, which is not a good sign.

westfw: I think it's doubtful that you can fit the hash code plus the RSA code in a bootloader (~4kbytes, 2kwords)

https://www.google.com/search?q=minimum+rsa+key+size

RSA claims that 1024-bit keys are likely to become crackable some time between 2006 and 2010 and that 2048-bit keys are sufficient until 2030.[14] An RSA key length of 3072 bits should be used if security is required beyond 2030.

A 2048 bit key is 256 bytes of boot area Flash. A rather large chunk.


The recovery path has not been mentioned. What is supposed to happen if the signature is invalid?

With such a tiny memory space, what's the point of calling it an 'update' as if you are not doing a fresh install? Are you intending these updates to only work on chips that already have a particular code?

westfw: So ... your "threat model" includes "someone will pull the bootloader out of the chip, extract the key, use it to build his own counterfeit signed images that he then distributes to your unsuspecting customers"? I guess that's a valid concern, and I've been bitten before by assuming "bad guys" had less access than they actually did (ie "known-plaintext attack".) But it's a pretty big jump form what you said in Reply #5: "I'm trying to avoid is [naive users] breaking a product because some guy posted a shoddy arduino sketch"

I think it's doubtful that you can fit the hash code plus the RSA code in a bootloader (~4kbytes, 2kwords); I spent a bit of time searching for a "reference" RSA application for AVR to get a size estimate, and couldn't find any, which is not a good sign.

It's the same concern. If someone extracts the key, then anyone can sign images, which would enable naive users to break a product via usb flash (the standard update method), which is much easier than using icsp/hv.

Is there any reason the bootloader can't run the hashing/RSA function from non bootloader section of memory? If you tell the linker to put it in a specific place and prevent the bootloader from writing those addresses...

[quote author=Coding Badly link=msg=3332789 date=1499630430] https://www.google.com/search?q=minimum+rsa+key+size

A 2048 bit key is 256 bytes of boot area Flash. A rather large chunk.


The recovery path has not been mentioned. What is supposed to happen if the signature is invalid?

[/quote]

My thought was to put the signature in EEPROM instead. Or possibly a different section of program memory. Then load into the RAM no problem.

If the signature is invalid, you can still load another image; it wouldn't prevent the bootloader from running, just the app from starting.

INTP: With such a tiny memory space, what's the point of calling it an 'update' as if you are not doing a fresh install? Are you intending these updates to only work on chips that already have a particular code?

The updates are for the application memory, not the bootloader. And yes its basically a fresh install, but I think almost all micro firmware updates would do a completely fresh memory write instead of just patching certain addresses. The updates would work on any chip since they wouldn't be encrypted. But on the particular chips that have the locked bootloader, only signed updates would run.

kayson: If someone extracts the key, then anyone can sign images...

That is not how pubic key encryption works. I will give you a hint: the name is relevant.

...which would enable naive users to break a product via usb flash...

The problem is that you are equating malicious third party with annoying end user. Those are significantly different threat models. An annoying end user can be stopped with a CRC. A malicious third party can only be thwarted with public key encryption.

Is there any reason the bootloader can't run the hashing/RSA function from non bootloader section of memory?

It has yet to be determined that would be necessary so there is no point discussing it.

My thought was to put the signature in EEPROM instead.

I'm beginning to suspect you have latched onto a solution you believe is cool and are now hunting for a problem.

If the signature is invalid, you can still load another image; it wouldn't prevent the bootloader from running, just the app from starting.

So signature check at startup. Every time. You probably should first determine just how much time is needed for RSA on an eight bit processor before deciding that is a good idea. Especially given the fact that a simple two-phase commit eliminates the need for checking every time.

Is there any reason the bootloader can't run the hashing/RSA function from non bootloader section of memory? If you tell the linker to put it in a specific place and prevent the bootloader from writing those addresses...

The bootloader could exceed 4k as long as it has a start address at the proper place, and does all of it's SPM instructions (for writing flash) from the (4k) bootloader area.

If someone extracts the key, then anyone can sign images...

That is not how pubic key encryption works.

I'm pretty sure the first comment was in response to my suggestion that he use a simpler "secure bootloader" (with PKC)...

westfw: I'm pretty sure the first comment was in response to my suggestion that he use a simpler "secure bootloader" (with PKC)...

Ah yes. Failed to include "symmetric key" in the quote. My apologies.

However, given the possibility of protecting a symmetric key with fuse bits extracting such a key strikes me as especially difficult for an end user.

given the possibility of protecting a symmetric key with fuse bits extracting such a key strikes me as especially difficult for an end user.

In this version of the "threat model", it's not the end user who extracts the key, it's the Evil Competing Firmware Maker (highly competent about ISP and cryptographically aware and with a lot of spare time) who extracts the key and starts distributing bogus firmware for the device, turning your home sprinkler system into one of a multitude of "water wasting bots" that can be used to attack the public utilities. Or something.

I made a similar mistake once; typed in a random key for a binary, assuming that it would be relatively hard for a bad guy to backtrack and figure out the key, given the resulting encrypted passwords. I entirely forgot to consider that someone could have access to both plaintext AND cryptotext (all you needed was your own box), at which point it was pretty trivial to figure out the key. And people did. :-( (at which point, people smarter than me looked at the problem, decided that it was somewhere between "really hard" and "impossible" to actually fix, given the constraints imposed, so we renamed the feature from "encryption" to "obfuscation" and went on with our lives. (If "obfuscation" hadn't been the original goal anyway, I would've been more careful.) Sigh. We told the blackmailer to go jump in a lake, or something (above my pay grade!)

[quote author=Coding Badly link=msg=3334389 date=1499733501] That is not how pubic key encryption works. I will give you a hint: the name is relevant.

The problem is that you are equating malicious third party with annoying end user. Those are significantly different threat models. An annoying end user can be stopped with a CRC. A malicious third party can only be thwarted with public key encryption.

It has yet to be determined that would be necessary so there is no point discussing it.

I'm beginning to suspect you have latched onto a solution you believe is cool and are now hunting for a problem.

So signature check at startup. Every time. You probably should first determine just how much time is needed for RSA on an eight bit processor before deciding that is a good idea. Especially given the fact that a simple two-phase commit eliminates the need for checking every time.

[/quote]

Yeah I was talking about the AES decryption on upload that seems to be the paradigm for the atmel secure bootloader in their app note.

I haven't decided on anything. I'm not really sure what the best way is to do what I want, hence this post. To be honest, I wasn't aware of the extreme confidence in the security of the fuse bits. But it still doesn't address the concern of a side channel attack if you're using symmetric key, and people can do crazy things by sniffing the power supply. Not that I think anyone would go to that extreme in my particular case, but if its possible to do something with public key, then I don't have to worry about side channel at all.

The time and program size are my biggest concerns. So far I don't think I can get below say 600ms for the progmem hashing, which leaves around 1s max for the RSA, assuming I drop the WDT for an upload to 500ms (to hit a 2s boot). And the hashing algorithm in the stock library compiles to 8k (though there's a bunch of junk in there too).

westfw: In this version of the "threat model", it's not the end user who extracts the key, it's the Evil Competing Firmware Maker (highly competent about ISP and cryptographically aware and with a lot of spare time) who extracts the key and starts distributing bogus firmware for the device, turning your home sprinkler system into one of a multitude of "water wasting bots" that can be used to attack the public utilities. Or something.

Yeah that's mostly it; admittedly it does sound a little far fetched. I was more thinking along the lines of slightly malicious hacker who is competent and has a lot of spare time. In that case, though AES would probably suffice since side channel attacks require some serious expertise and resources.

But still, if there's a possibility for something that boots in a reasonable amount of time, takes a reasonable amount of space, and is both immune to side channel attacks and any manipulation of fuses, then why not do that...