secure embedded/microcontroller crypto using AES-ctr with hmac-sha2 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?
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".)