What is a simple information authentication protocol for constrained devices?
Your initial idea is good. What is needed here is a challenge response protocol but rather than key agreement we need to authenticate a piece of data.


device issues challenge:(device id , nonce)
server signs and replies with MAC and data:(data,mac(device_key,nonce||data))
device verifies mac


As long as nonces don't repeat the data must be re-MACed by a party knowing the devices secret key and the device can be sure it has fresh, valid, data.

all that's left is picking a MAC function. You want a low cost keyed MAC. SHA256 and other well known hash functions are expensive because they need to resist collisions when the adversary can see their internal state and using them for MACing a message is wasteful. Less expensive MAC functions exist.

Here are a few mac algorithms that would work well:


CBC-MAC_AES (use this if you have AES hardware)
CBC-MAC_SPECK64/128 (designed by NSA (do you trust them?), likely &lt;200 bytes code size on 8bit platform but similar on 32bit platforms)
Siphash (on Atmel AVR requires 1500 bytes code 42 bytes memory)


note on CBC_MAC: The wikipedia page mentions an IV which prevents replay attacks. IVs must be both unique and secret. If you have a secret IV used elsewhere, it can be reused with some caveats. The IV can also be generated from a nonce by encrypting the nonce. In your application though you can just prepend the nonce to the data before MACing.