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
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 ?