The embedded device is a low-power 8-bit microcontroller (memory usage is constrained to about 10kb code, 1kb ram). As the device is battery-powered and manual service should be minimal, more powerful processors are not an option.
Throughput is very limited, so performance is not too much of an issue.
The system we came up with is AES-ctr mode encryption with hmac-sha authentication:
// encryption_key, mac_key, device_id are all independent, secure random,
// unique per device pre-programmed values
// aes-ctr encryption (pseudocode)
first_nonce = nonce = device_id || counter++
for block in plaintext
ciphertext.append(aes_ctr_encrypt_block(encryption_key, block, nonce))
nonce = device_id || counter++ // counter is saved in non-volatile storage (e.g. flash or eeprom) to avoid re-using after power down
// authenticate nonce + ciphertext (pseudocode)
data = first_nonce || ciphertext
mac_tag = hmac_sha2(data, mac_key)
// send or store mac_tag, nonce and ciphertext
send(mag_tag || data)
The receiving side should then use the deviceID to look up the mac_tag and verify it matches. By checking if the counter is larger than the one previously received we want to eliminate replay attacks.
If the validation checks out, the data is decrypted.
Is this a secure system? Also, what would be the effect of truncating the output of hmac_sha2 to 128 bits?