# 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:

1. What are the well-known and studied protocols that can meet these constraints?
2. 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.

• Of paramount importance: can yo assume that the devices can hold a secret information (key) secret? If not, you need public-key cryptography. That might be doable since you need to verify authenticity of the signature of incoming data, and that's a job RSA or Rabin can do well and at moderate computational cost (contrary to signing outgoing data, which is much more costly).
– fgrieu
Jun 8 '16 at 6:40
• Yes, devices can store secret information. As you've correctly hinted at, HMAC verification requires that both parties share a secret key.
– Doe
Jun 8 '16 at 7:26
• Just generating a nonce on the sending side may not be enough; the receiver must have some protection against replay attacks. In other words, the receiver must check that the nonce is - indeed - a nonce. Jun 8 '16 at 8:26
• @MaartenBodewes The source (the nonce-receiving end) does not need to authenticate devices; It's providing a public service with public information to any interested party. That's why I believe that only devices need a nonce to guard against replays. Do correct me if I'm wrong.
– Doe
Jun 8 '16 at 8:49
• For a construction with MACs, you need to either share one key across all devices, or each device has its own key shared with the source. The first is a bad idea if devices can be compromised, and the second could cause a lot of overhead, if there are a lot of devices asking for the same information - the source would have to handle each request individually. With a digital signature, the information could be signed and published once for every possible receiver.
– tylo
Sep 7 '16 at 12:26

## 2 Answers

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:

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.

[I would rather put this as a comment but my 'reputation' is not high enough to allow comments].

the information must be authentic and fresh

Not sure what is meant by 'fresh' in this context.

Anyway, given that both the 'device' and the 'source' are capable of storing a secret key, first thing that springs to mind is a protocol based on a symmetric crypto (DES, 3DES, AES, etc.) with a key being updated on each data exchange by both parties according to a certain (simple) algorithm.

An example of such an approach can be found in "STANDARD 70 - BOOK 5 CARD ACCEPTOR TO ACQUIRER INTERFACE STANDARDS Security and Key Management". [I have the PDF in case you have troubles googling for it].

As you can guess from the title this approach widely used in POS device to Acquirer communications.

PS: Can you give us a hint of how exactly constrained your devices are? Are they capable of doing DES at least?

• Some additional reading can be found here: security.stackexchange.com/questions/20129/… The Standard70 I mentioned above uses MAC technique, but not HMAC, i.e. no hashing is involved.
– tum_
Jun 8 '16 at 8:09
• Thank you for your input, I hadn't considered symmetric encryption because it's not usually used for authentication. I will try to look into it.
– Doe
Jun 8 '16 at 8:58
• As for the devices, the exact specifications haven't been determined yet. (I don't even know if they'll be homogeneous) That's why I'm trying to keep my options open and keep everything as simple as possible.
– Doe
Jun 8 '16 at 9:00
• >hadn't considered symmetric encryption because it's not usually used for authentication -> that's a brave statement. Numerous flavours of MACing techniques based on symmetric crypto are widely used for authentication. I do recommend you to give this a thought as, normally, a symmetric cipher is less computationally demanding, than, say, a SHA-1 hash.
– tum_
Jun 8 '16 at 9:57