What is a simple information authentication protocol for constrained devices? Background: I have an application where devices will poll information from some source on the network. 

These devices are very basic and have modest processing and memory capabilities. Hashing (and by extension, HMACs) is doable, but more might be too much.

The information is public, and the devices do not need to authenticate themselves to the source. However, the information must be authentic and fresh.

The protocol I have in mind is that (edited for clarity)


a device would generate an appropriately large nonce, and send it unencrypted to the source. The nonce is never seen before and can not be predicted.
the source would accept the nonce, concatenate it with the information,  generate the HMAC for the result, and then send the result back to the device. Note that the source does not authenticate devices and accepts any nonce sent to it.
the device would check that the HMAC is valid, and proceed to act on the information.


I believe this would provide the required security (Hopefully). However, I would very much rather use a well-known protocol if such protocol can meet both security and hardware constraints.

This leads me to my two questions:


What are the well-known and studied protocols that can meet these constraints?
In the unlikely case that no such protocol exists, what do you think of the protocol proposed in this post?


Any input on this matter would be appreciated.
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.