secure embedded/microcontroller crypto using AES-ctr with hmac-sha2

Question

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?

Answer 1

Fgrieu has already posted a good answer, which I won't try to repeat. However, here are a few additional observations:

• For an embedded system, you may want to consider using CMAC-AES instead of HMAC, since you can reuse your AES implementation, and don't need a separate hash function.

• Further consider using SIV mode (RFC 5297). It's very similar to CTR+CMAC, but provides additional protection against accidental nonce reuse, and also removes the need for separate cipher and MAC keys.

• Do be careful about nonce reuse, especially if you don't use SIV. (But please use SIV, if possible!) Saving the nonce to flash after every message is generally not a good idea, so the usual approach is to write, say, nonce + 1024 to flash before each block of 1024 messages. On reboot, just resume from the last nonce value in flash, which should be greater than the last nonce actually used. (Also, make sure that nothing breaks even if power is lost during a write; there are standard techniques for handling this, but they're not really specific to crypto.)

• Consider including a timestamp and/or a sequence number in your messages to protect against replay attacks. If you're potentially using the same keys in both directions, or over multiple channels, also tag your messages with sender and receiver IDs. (These may be in plaintext, but they do need to be included in the MAC. For SIV, you can include these as "associated data".)

Answer 2

I understand the system as follows:

• data blocks are enciphered per AES-CTR, using key encryption_key, with an IV made by concatenating device_id and a counter held in Flash or EEPROM, incremented at each use;
• that enciphered data is integrity-protected by a 256-bit mac_tag computed using HMAC-SHA256 and mac_key.

That's theoretically sound if

1. device_id is unique.
2. encryption_key and mac_key are maintained secret, and preferably device-unique (e.g. factory-diversified by some sound key derivation function from device_id and a master key that does not leak; of course that works only if communication is between devices and a master holding the master key; for device-to-device communication, we are back to global shared key, or public-key cryptography).
3. counter does not overlap or otherwise return to an earlier state.

Truncating mac_tag to 128 bits is fine, except if a regulatory requirement prescribes otherwise.

Beware however that it is very hard to keep anything secret in an embedded system not designed from the grounds up for that goal; there's JTAG port, probing, buffer overflows, other side channels, induced faults..

And then there are implementation goofs, including but not limited to: deciphering something on the receiving side even though it did not pass the integrity check; failing to check on the receiving side that the counter increases; effectively incrementing counter on the transmitting side only after transmission has started (including because of some RAM cache); otherwise missing goal 3 above because power loss during Flash or EEPROM update is hard to deal with reliably, especially facing an adversary that cuts power at the worse moment (including old Murphy causing a reset because the Flash charge pump induces a power glitch), and an interrupted erase or program results in bits that do not read reliably at the same value, depending on power supply voltage, temperature, aging, or Schrödinger's cat health.

Answer 3

Considering the OP specifically mentions replay attacks, which I believe requires a unique CTR for replay protection even with SIV mode, then I believe SIV may only create a potential false sense of security and more complicated and maybe less flexible code than, say, something like EAX mode or based on EAX mode (EAX mode makes more sense to me than GCM for multiple reasons even on embedded systems with both GCM crypto and AES hardware accelerators; The slightly faster on powerful servers argument means next to nothing to me when faced with it's drawbacks such as complexity and memory use). EAX simplicity means it's less likely to be implemented incorrectly and developers can feel confident to use it's potential flexibility to improve security or efficiency in protocols.

Indeed replay protection isn't even mentioned in RFC 5297, a serious omission IMO. Especially considering lack of replay protection is the most likely implementation mistake by users of CMAC.

There is also AERO but it is less flexible and potentially encumbered according to one standards body, though a BSD license has been mentioned on the RFC I believe.