Tiny Firmware Authentication

I am developing a product based on the NXP LPC11C24 microcontroller. It will communicate with PC software to perform its function. I am attempting to build a secure firmware update functionality. The PC program will download firmware images from us and send them to the device, which will then decrypt, verify, and write the image to its flash memory. I want this mechanism to be secure against the analysis of the PC software and trivial attacks on the encryption. Assuming the attacker has full knowledge of the device and PC protocol, uploading an unauthorized firmware image should be more difficult than e.g. defeating the chip's code protection, clock glitching, side-channel attacks, or similar.

The difficulty is space limitations. I have a hard limit of 4KB of ROM (ARM Cortex-M0 code, for size reference) and a firm limit of 1KB of RAM, of which I can budget perhaps 2.5KB and 600 bytes, respectively, to the decryption and authentication process. In light of this, I chose AES-128 CBC encryption with CRC-32 authentication. My method is to create a random IV, split up the firmware image into 256-byte blocks, and add a CRC-32 checksum after each block, repeated four times to pad to the AES block size, then encrypt the 272-byte block. The checksum is to catch data corruption during the transfer from PC to device (the PC can use SHA-256 to verify integrity from the web) and to authenticate the block. The PC cannot do the authentication, because the PC to device protocol would be trivial to intercept.

The firmware update process would be as follows:

1. Enter firmware update mode
4. Decrypt block with AES-128 CBC
5. CRC-32 checksum first 256 bytes, verify checksum matches last 16 bytes
6. If failure, stop the process. If success, write 256 bytes to flash.
7. Repeat from 3 while blocks remain

I have done some research and it seems this CRC then AES method is trivially vulnerable (detailed in this other answer), but the attacks rely on known or chosen plaintext, which will not be the case here. Only us, the manufacturer, will be releasing updates, and they will always be encrypted. Is this then sufficient protection for my scenario, or at least harder to break than decapping the chip or exploiting the chip manufacturer's code protection system? Is there a better way that will fit the extremely tight memory requirements?

• Can you just use EAX or CCM as your mode instead of CBC? – SEJPM Jan 6 '17 at 17:10
• This has many issues, among which: as described, it is trivial to load a segment of the software (removing beginning or/and end, by 256-byte increment); just remove the end, and to remove the beginning use as IV the end of the end of the last block removed from the beginning. And, the AES key is bound to be in the verification code; for the integrity function, you really want a signature verification; this might be feasible with the code constraints stated, but won't be easy. – fgrieu Jan 6 '17 at 18:25
• @SEJPM AES-128-EAX actually sounds like pretty much what I want. I found a nice library here which is a bit over budget but I should be able to stomp it down to size (e.g. by storing the key schedule in ROM) without compromising the side channel resistance. Thanks for the suggestion. – tpw_rules Jan 6 '17 at 18:59
• CCM (packet based AEAD cipher) might be a slightly better match, could be made a tiny bit smaller and is NIST standardized. It's also an absolute bugger to implement correctly IMHO. Nevertheless, if you become stuck when trying EAX.... – Maarten Bodewes Jan 7 '17 at 12:55

The title says authentication, that is we want only the real firmware to load and run, unmodified. There are fast, practical code signature techniques for that. Most importantly they require no secret in the target device.

The baseline would be that the target contains an RSA 2048-bit public key with $$e=3$$, and uses that to verify an RSASSA-PKCS1-v1_5 signature with SHA-256 of the firmware.

Given that the firmware won't fit in RAM, signature verification must be after writing the firmware in Flash but before running it. That check could be at each startup, if we can afford to save the 256-byte signature in Flash, and some milliseconds of startup delay.

This can be done with 2kB byte of Flash, including public key (256 bytes, can get down to <100 with special generation techniques), and within the stated RAM budget. Using Rabin signature (similar to RSA but with $$e=2$$) can save some time, RAM, and even code.

This is quite secure against all except attacks that modify what the hardware does (e.g. with a JTAG probe, or power supply glitch). For proper implementation, and if the whole firmware is secure (free from buffer overflows and similar), there is excellent insurance general users can't reproduce the attack on their device.

For secrecy of the code, as in the body of the question, there must be a secret in the target. Serious adversaries will manage to extract that secret, and will be able to decipher the code. My advice: use encryption, but know it's breakable.

I see no reason to use AES, unless it is required in the application AND the loader's AES code is reused by the application. ChaCha seems a better choice.

I won't comment on the proposed solution beyond stating that:

1. It is inconsistently described: CRC-32 is 4-byte, leaving how that "matches last 16 bytes" a mystery.
2. It writes the firmware by small 256-byte chunks, therefore it gives no insurance that it leaves the firmware as a whole in a consistent state in case on interrupted download. This is a tried and tested avenue to disaster.

The correct solution to issue 2 is:

• Invalidate the current firmware when firmware download is initiated, leaving only the bootloader running at next reset; this insures that download can be started over in case of power loss.