I'll start off by saying I'm a noob with respect to software security but I've been reading about security models for a while. Also, I'm afraid some people would just say "go and hire a security expert" which is probably the most correct way to do it but we're a tiny start up and I'm going to have to implement the security model for our embedded mesh network to the best of my abilities.
So, here's what the hardware/firmware looks like:
2 different ARM MCUs, with about 1KB of RAM remaining after the current stack, that support 128-bit AES CBC (and ECB, but I know that should never be used) and SHA-256.
Both MCUs have libraries that support 802.15.4 security but we'd need more RAM than available for supporting the number of devices that we want to allow in a single network. Also, devices with either MCU should be able to talk to devices with the other one and both of them have implemented different versions of the 802.15.4 security model. The PHY/MAC has already been tested for compatibility.
128 bit AES key is stored in secured flash (Can only be erased using JTAG but not read from). 64 bit key for SHA 256, also in secured flash. Both keys are pre-shared among all devices.
Each packet contains a header with length, version, type fields and a variable sized payload.
Each device has a 32 bit frame counter that is initialized on first boot to a 16 bit random number (allowing enough room before the overflow happens) and is incremented after sending a packet. For incoming packets, the frame counter has to be greater than the last frame counter for the sender. If it isn't, the packet is considered a replay and is dropped. The frame counter need not necessarily be prev_counter + 1 because of the possibly dropped packets and the way our mesh works.
Finally, the question:
So, given that we can only use 128-bit AES CBC and SHA256, what'd be the most secure way of implementing authenticated encryption?
Note that since this is a low bandwidth network, we'd like to keep the per packet overhead to a minimum. And that'd be 16 byte IV + AES padding, if necessary + 4 bytes of hash, imo.