# 4 bytes authentication problem

I have a classic security problem where Alice needs to prove its identity to Bob but with quite unusual requirements and constraints due to a M2M context.

EDITs in bold

The communication channel used between Alice and Bob has the following characteristics :

• only Alice can send messages to Bob (Bob cannot talk to Alice)
• messages from Alice are 4 bytes long
• Bob stops listening during 10 minutes after receiving 10 messages
• Alice must prove its identity using only one message if possible

Other specific requirements are :

• Alice has low CPU & memory resources, Bob has high CPU & memory resources
• The message must include Alice identity, but without the need to hide it
• There is an unlimited number of Bob entities
• There is < 4000 entities like Alice which can authenticate to any Bob
• Replay attacks must be reasonably prevented (a replay can be possible during a few minutes after emission but not more)
• It is ok for Bob to be fooled by brute force as long as it takes time to the adversary to do so (i.e. several days of computation or message retry)

Here is what I came up with for Alice 4 bytes message :

``````bits 1-20 = truncate(HMAC(date.format(dd/MM/yy hh:mm)),20)
bits 21-32 = Alice ID (12bits = 4096 IDs)
``````

When Bob receive the message, if we allow for X minutes deviation between Alice's and Bob's clock, Bob computes

``````truncate(HMAC(date.format(dd/MM/yy hh:mm)),20)
``````

for X/2 minutes after and before the reception. So for e.g. X=10 minutes, Bob computes 10 values. If one of these values match Alice emission, Alice is authenticated.

The adversary has X / 2^20 chances to randomly generate the good message. Since Bob only listen 10 messages every 10 minutes, this would take ~73 days on average if my maths are correct (for X = 10 minutes), which is fine.

Replay attack is possible during X/2 minutes.

The higher chance of collision introduced by truncating the HMAC to 20 bits do not compromise the private key nor reduce the level of security of the process AFAIK.

I am a developer, not a security guy, is my solution reasonable and my analysis correct? Do you see a better one ?

• just wondering, is this a real world situation or your home work? :)
– aviv
Commented Jul 29, 2014 at 12:24
• this is a very serious and concret M2M real world situation, but I can't be more precise on the context ;) Commented Jul 29, 2014 at 12:46

What matters is the respective abilities of Alice and Bob with regards to storage. In your case, you assume that neither Alice or Bob has any memory; they share a secret value (for HMAC), but they have not read-write slot to update. On the other hand, you also assume that Alice and Bob have clocks which are reasonably accurate (within a few minutes of each other).

If Alice and Bob have clocks but no memory, then your solution is reasonable. Your math is a bit off:

• If Bob allows for a deviation of X minutes, then he will compute 2X+1 values, not just X.
• Replay attacks are possible for up to 2X minutes or so, if Alice's clock is too early by X minutes.

If Bob has some transient memory (RAM...) then he can furthermore protect himself against replay attacks by remembering the messages received in the last 2X minutes: that way, Bob can detect replay of messages which are not too old (and old messages would be rejected because of their age).

If Alice and Bob have permanent read-write memory, then they can use a counter instead of a clock. This can make hardware implementation much easier (clocks need a constant energy supply, counters do not).

Your main mistake, though, is that you are trying to define your own protocol. This is, generally speaking, not a good idea. Instead, you should rely on existing, peer-reviewed protocols. Therefore, you want to use HOTP (for the counter-based solution) or TOTP (which internally reuses the HOTP mechanics). You are warmly encouraged to read through their respective RFC (RFC 4226 and 6238, respectively), which are nicely written.

(You were not far, though. Your proposal is quite close to TOTP. But cryptography is subtle, so using existing standards is always better.)

• Thank you for this complete answer, I updated my question regarding memory. Alice has constrained memory (a few Mo) and Bob has lots of RAM and storage. I forgot to mention that there is a lot of Bob out there, so storing message against replay and using counter instead of clock won't work I think. Commented Jul 29, 2014 at 15:10