Determining strength of truncated HMAC

Question

I have data stored on a device which I must guarantee integrity, for ease of explanation the data is like numerical field representing 'credit balance available'.

The device only ever interacts with a single computer; I therefore wish to verify integrity of the balance using a HMAC: the computer reads the balance and MAC, verifies it using its private key, updates the balance and computes a new HMAC, and writes this back to the device.

The limitations: I want the hash to only be 32bits, so I will truncate it. The key can be arbitrarily long and I can use SHA1 etc.

Am I safe to assume that an attacker cannot find the secret key even though the hash is 32 bits? What if the hash was 8 bits?

In this system, the computer will block a device if it provides an invalid MAC, thus an attacker has only one attempt to provide a valid message/MAC combination.

Note: I've read this security.SE question but I am confused by the answer and the 3rd comment on the answer (by @LateralFractal), otherwise it is a similar question.

Answer 1

Details matter.

As @Ricky points out, showing truncated HMAC values won't help the attacker finding the secret key, compared to a similar situation where the HMAC values would not be truncated. This makes sense: the truncation only removes information.

However, the attacker is not ultimately after the secret key. What the attacker really wants is to make forgeries, i.e. compute some HMAC values that the computer will accept as its own. Finding out the secret key allows making forgeries, but the ability to make forgeries does not necessarily entail knowledge of the private key.

Fortunately, HMAC tends to behave like a PRF, so there are two known methods to make a forgery:

1. Perform a brute force enumeration of possible keys until the right one is found (one that matches a few known value+HMAC pairs). This attack is defeated by choosing the key is in space large enough to make the enumeration unrealistic (i.e. you generate a 128-bit key with a cryptographically strong PRNG).

2. Luck. The attacker sends a random sequence of bits as HMAC value and hopes that it will work. This attack is defeated by not truncating HMAC values to too small a length, and/or applying other mitigations such as allowing only one try and irrevocably rejecting devices that once showed even a single bogus HMAC value (as you do).

The "luck" attack works with probability 2^-n, where n is the size (in bits) of your truncated HMAC output. I.e. with a 32-bit output, then a luck-based forgery has probability 1 in 4 billions or so to go undetected. This is the best that can be done with a 32-bit output, in all generality; that HMAC behaves as a PRF means that it is "optimal" in that respect. If you truncate to 8 bits, then the attack success probability is 1 in 256, which is probably too much for comfort. But this is your decision to make, based on your usage context.

Also (again as @Ricky points out), beware of replay attacks. A valid MAC, assuming that there was no forgery, only demonstrates to the computer that it saw and "approved" the message contents at some point -- but not that it was the last message that it saw. Old message-HMAC pairs can be sent again by a fake device. To defeat replay attacks, you must maintain some state on the computer (the computer must remember something about the device, e.g. a "message sequence number", that is part of the data over which the MAC is computed, and incremented for each message).

Answer 2

Yes. ​ Yes.

B interacts with A and the challenger as follows: B forwards all queries from A to the challenger,
and gives the same output as A. For each response from the challenger, B truncates the response
and sends the truncated response to A. A's view in that interaction is identical to A's view in
the interaction for your scenario with the same key, so if A finds the secret key then so does B.

B is a constructive reduction from finding the secret key for HMAC to finding the secret key
for truncated HMAC. ​ Therefore, if "an attacker cannot find the secret key" for HMAC
then "an attacker cannot find the secret key even though the hash is" truncated.

Note that you'll need something to defend against reuse of old balance-tag pairs.

"Truncating a well designed cryptographic" PRF "should not result any security weaknesses other than
a reduction in the" codomain's size. "As" PRFs, by definition, are pseudo-random across their domain.

"All other things equal, using a more modern hash algorithm"
(SHA-256) "is safer than using an older one" (SHA-1).


"Say you want 2^16 instead of 2^256. This is a phenomenal drop in" tag "space size. At 2^16 or 2^32"
a random tag will have a 1/(2^16) or 1/(2^32) respectively chance of being accepted. "Whilst QR codes
are less responsive at longer sizes," there is a tradeoff of tag length versus forgery probability.