Sometimes you just want to verify that the user has a secret. A secret comes in many forms - a key, a random value, a secret function. Usually you share some aspect of this secret with another party. This comes in the form of a 'pre-shared secret,' though this could also be a public key.
A customer was recently facing a problem. They needed to prove a user was exactly who they said they are. Think of this as a stronger form of 2-factor authentication (2FA), beyond HMAC one-time pads (HOTP) or time-based OTP. A kind of YubiKey on steroids. The user would use a fingerprint reader on their token. If their prints match what is on file, the token would need to send an affirmation of the user's identity. But, as is well known, microcontrollers don't have great cryptographic capabilities. They even don't have access to much entropy. What can we do?
Challenges of Challenge-Response
There were two things working in this customer's favor. First, they control the manufacturing process. Any tokens they manufacture could be 'born' with one or more keys. These are generated at manufacturing time, in a secure manufacturing cell. Each key is then recorded, along with the device's serial number. When they send the token to the customer, all they have to do is record the serial number of the device. When it comes time for the user to log in, the back-end service knows immediately which key to use.
Unfortunately, I can't provide specifics on the hardware the customer used to build this token. Suffice to say, it was a Cortex M3-based design, with minimal hardware crypto support. These devices are disposable - the user will use it for a period of time, then discard it. The device can't be re-keyed in the field. CPU-intensive operations like RSA private key ops or even ECDH were out of the question. They are power-hungry and would decrease the life of the device. There was the possibility of using AES-GCM, but that came with its own battery life baggage. Either way, this would result in drastic reduction of the token's lifetime.
But, we have a shared secret - the device key. Enter HMAC. Both endpoints know the HMAC key, so both sides could generate an 'authorized' challenge. SHA-256 is efficient enough, for small enough messages. This enables a simple challenge-response protocol.
HMAC to the Rescue!
Hash-based Message Authentication Codes, or HMACs, mix a key with input data. This HMAC technique avoids weaknesses in Merkle-Damgård construction hashes (i.e. MD5, SHA-1, SHA-2), preventing extension attacks. HMAC does rely on a symmetric key - both parties need to agree on the key beforehand. Otherwise, one party will not be able to authenticate the message from the other.
The back end could fire an HMAC-SHA-256 authenticated challenge up to the token. This challenge could come in the form of a nonce plus a sequence number. The token then will verify the authentication code using its key. This just involves calculating its own HMAC of the challenge. Once the token has verified the authenticity of the challenge (and the fingerprint of the holder), the token can return its status. This is in the form of a second HMAC, of the status concatenated with the original challenge HMAC value. So long as those HMAC keys remain secure, the response is difficult to forge. By including a serial number in the challenge, you raise the bar for replay attacks, too.
You Don't Need the Whole Digest?!
An HMAC is mixing of several hash function outputs. If you're using SHA-256, this means the complete HMAC digest is 32 bytes long.
HMAC is interesting because it relies on each party calculating a result based on a secret. This means that both sides have to 'match' to verify the secret value. Where this becomes powerful is that the security of HMAC is proportional to the number of bits in the key. Life becomes even easier: you don't need to transport the whole HMAC.
This does mean you need control over your acceptance policy though. If you allow many guesses at the correct HMAC value, you will want more bits of the HMAC available on either end. But, if your communications channel is reliable, you can limit yourself to one try. This means that a failure requires a new challenge and response calculation. But this also eliminates the possibility of a brute-force attack.
Why Your Threat Model Matters
If your threat model includes a sophisticated attacker, say a nation-state with deep pockets, stop right here. You need to go all-out for your cryptographic solution, and I don't envy you. But, for this customer's case, they weren't worried about someone stealing the keys for a device. The nature of their service makes it easy to detect if a user's keys are compromised. As well, protecting against symmetric key theft is expensive and hard. But, by focusing on authenticating communications with the token, they could avoid easy attacks. This let them focus on what they needed to do: ensure the user is who they say they are.