I'm writing a bootloader that has to update the chip's application code over Bluetooth. The firmware should be sent authenticated encrypted to the device. I'm not worried about an attacker gaining access to the hex file (as I've read on here with a 500 dollar device you can clear the lock bit and read the firmware off the device anyway). What I want to do is prevent an attacker from uploading his own (potentially malicious) code to the device over Bluetooth. Therefore I need data authentication so that the device can detect that the code is coming from a malicious sender. Note that the attacker does not have physical access to the device so uploading his own code is only possible over Bluetooth.
The problem is that my code doesn't fit on the Atmega328p's 4kB bootloader. My Bluetooth bootloader is about 3kB without encryption, and with encryption gets up to 10kB (I'm using the avrnacl library). Looking around this forum I found that it is quite unusual to have such a large bootloader so I was wondering whether I was doing something wrong.
I considered switching to an XMEGA but they have a maximum bootloader size of 8kB so that wouldn't work either. An ARM chip or something similar would be another solution but this would require me to rewrite all of the code. And it seems a bit overkill since the performance of the Atmega is fine, it's just the bootloader that's too small for my purposes. Another solution would be to get an external memory chip for the bootloader (is this possible?) or even another avr chip just for encryption. Or an authenticated encryption library that's a lot smaller than the one I'm using right now. I'm not sure what the best way to go is here, I would appreciate any help!