Tiny Firmware Authentication I am developing a product based on the NXP LPC11C24 microcontroller. It will communicate with PC software to perform its work. 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, decrypting, verifying, and writing the image to its flash memory.
I want this mechanism to be secure against PC software analysis 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:

Enter firmware update mode
Receive IV, initialize AES
Receive encrypted 272-byte block
Decrypt block with AES-128 CBC
CRC-32 checksum first 256 bytes, verify checksum matches last 16 bytes
If verification fails, stop the process. If successful, write 256 bytes to flash.
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?
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. RSASSA-PSS would be nice, at a slight expense in code complexity.

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 &lt;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:


It is inconsistently described: CRC-32 is 4-byte, leaving how that "matches last 16 bytes" a mystery.
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.
Have the bootloader download the code in Flash.
When download is done, check the signature of the whole firmware just downloaded and written, and if OK re-enable the firmware to run at reset.
Optionally, the signature can be part of what's written in Flash, and the check performed again at each reset.


The bootloader can use the whole device's RAM, thus the technique works down to 1kB RAM total (rather than 8kB here).