What is the shortest viable hmac for non-critical applications?

Question

I'd like to generate a QR code (or some other 2D barcode) that would include a HMAC of its contents. Since it's a printed QR code, and since it will already contain a fair amount of data, I'd like the HMAC overhead to be as small as possible, while still making it reasonably difficult to crack.

By "reasonably difficult" I mean "for an average guy with a gaming PC". In addition, the content is not super sensitive - it's a ticket with a value of 20€ or less. Mostly less. Plus the HMAC key can be regularly rotated (say, once per day), and the tickets will not be valid for more than 30 days at most. Therefore I'm not worried about people who have access to mainframes and months of cracking time.

With such low security requirements, I think that a fairly short HMAC should do the trick - if it's done right - but I don't know which one to use. The typical ones you see everywhere are based on something no less than SHA1 (preferably SHA256), but that's already 160 bits, which will make a QR code substantially bigger. Are there any shorter options available?

Added:

People have raised many valid questions and I think that I have been too vague. My apologies. I'll clarify:

The tickets in question are for public transportation, so they can potentially include quite a bit of info - ID, routes, weekdays, validity period, stop combinations, fare reductions, ride counts - just to name a few. As such the QR code can easily become pretty big, and therefore the rate of scanning problems will rise too. Hence I'm interested in shaving off as many bits as possible.

I'm also aware that it's all too easy to copy a printed barcode. The main validation method will always be an online one. But as the transport moves, especially through remote areas of the country, mobile networks might not always be available. Or you know, noting is perfect, and the backend validation servers can suffer downtime too. The HMAC then is a fallback method for validation in cases when online validation is unavailable. This is actually another barrier for the potential adversary, because their attacks will only work when the validation device is offline. Plus, even when offline, the validation devices can retain a local history of recently validated tickets, so two people using the same ticket in the same ride would not work.

All in all, I believe that while such a scheme isn't completely watertight, the risks are low enough to be acceptable. The barrier for a successful attack is high enough that it will not be a common occurrence; and even if someone does somehow manage to pull it off, the lost fares are not that large.

Answer 1

You could use a truncated HMAC as specified in section 5 of RFC 2104.

Quoting from this:

We recommend that the output length t be not less than half the length of the hash output (to match the birthday attack bound) and not less than 80 bits (a suitable lower bound on the number of bits that need to be predicted by an attacker).

Thus if you wishes to truncate a SHA1 HMAC to 80-bits, this would fall within the specification. Personally, I'd prefer people to minimise the use of SHA1 in all applications so that the libraries can be retired. In this case SHA224 with 112-bit truncation is still within the specification.

Note that truncations (or short HMACs in general) permit feasible attacks on non-repudiation. With $\approx 40$ bits of work, you can produce two tokens with the same 80-bit HMAC. This would allow you to issue/sell one token, but then claim it was not the original. Of course the adversary in this set-up is you and the victim is the token purchaser, so you may not care.

ETA 20240911: NIST SP800-107 section 5.3.3 reads

When applications truncate the HMAC outputs to generate MacTags to a desired length, λ, the λ left-most bits of the HMAC outputs shall be used as the MacTags. However, the output length, λ, shall be no less than 8 bits. For example, a low bandwidth channel or a desired high efficiency computation application such as audio or video casting application might use 8-bit MacTags.

which seems to say that 8-bit tags are permissible by NIST if we interpret a QR-code as a low bandwidth channel. These would give an opportunistic forger, who is able to submit $s$ tickets, a $s/256$ chance of success.

Answer 2

Let me summarize your security model as I understand it:

• Alice declares certain messages to be valid, and can declare more valid messages over time.
• Only Alice needs to be able to determine whether messages are valid.
• Adversaries may want to forge messages, i.e. may want to get a message accepted as valid even though Alice has never declared it to be valid.
• Presumably, you don't want Alice to have to memorize all valid messages.

Since only Alice needs to be able to validate messages, you can use a MAC with a secret key that only Alice knows. (If you needed Bob to be able to validate messages but not craft valid messages, you would need an asymmetric scheme.)

Since only Alice is able to validate messages, the only way someone can forge a message is through an active attack. Therefore the minimum strength does not come from computing power, but from how much bandwidth the attacker can get through Alice. There's no universal figure for that: it depends how your validation system works. Let $B$ be the maximum number of messages that you estimate that an attacker can submit.

The probability that a random message has a valid $k$-bit MAC is $2^{-k}$. The probability of a successful attack is less than $B \cdot 2^{-k}$. Take $k$ that is large enough for this number to be comfortably small.

You can truncate a MAC as you want. All the bits are equally meaningful.

Verifying truncated MACs makes forgeries easier because it lowers the chance that a random message has a valid truncated-MAC. It does not make it easier for an adversary to figure out the key. (Using a shorter key would do that, but there's no reason to use a key that's less than the standard length.)

Do note that there is no way to prevent duplicated messages. Given that you call messages “tickets”, this may be a concern. If two customers present the same ticket, you'd better have some way to determine which one is legitimate.

On a final note, using a MAC fundamentally means that you can't separate the authority that creates valid messages from the authority that verifies whether a message is valid. In other words, the ticket checker can also create valid tickets. If you want to avoid this, you need to replace the MAC by an asymmetric scheme. And with an ordinary asymmetric scheme, anyone can obtain the public key so anyone can check the validity of a ticket offline, and therefore you can't truncate signatures.

Answer 3

Frame challenge.

The enemy of a printed QR Code is not a very fast computer. It's the photocopier.

It's even worse than a magnetic stripe, and there's a good reason we switched from magnetic stripes to chips in payment cards.

If your ticket contains all the information about validity and can be verified offline, nothing prevents anyone from simply copying your QR Code. And adding an HMAC will not change anything: you copy the HMAC along with the rest. So you sell one ticket, and 5000 people can use it. Or the same person can use it 30 times.

If you keep a printed ticket, then you need your QR Code to include a unique code, and check if that unique code has already been used or not (so you need to be online). Make sure your codes are assigned randomly and are long enough, and you don't need anything else. No other data is required (it will be returned by the database), and no HMAC required.

Of course, this only works for single use tickets (you would mark the code as used in your database on validation), though it could be used for a sequence of segments and associated validations (you have a flag for each segment associated with the unique code, and you check them off as they are used), or possible for a limited number of uses (count how many times the code has been used).

If you want to have pure offline validation, then if you want any form of security you need dynamic QR Codes (i.e. shown by a phone, not on paper). The QR Code should then include something like a timestamp, and the validation method (your HMAC) should include this timestamp in addition to the rest of the data.

Your validation would then check both the HMAC and that the timestamp is close to the current time (your should allow for a bit of a delta due to possible time sync issues) before using any of the data.

Now it depends on how quickly one can present a QR Code for validation. After an unsuccessful read, you should have a delay, say one second, before a new QR Code can be presented. Then find out how many times/how long one is willing to rotate though HMACs. This should yield a pretty small number, probably in the dozens or hundreds.

That should give you an idea of how short your HMAC can be. A few dozen bits should be more than enough (provided you rotate your key regularly, otherwise your problem is people finding that key).

Answer 4

Thanks to @Gilles 'SO- stop being evil' for summarizing the security model. I see it slightly differently:

• Vendor Alice declares certain messages to be valid from time to time.
• Only Bob, the doorman, needs to be able to determine whether messages are valid.
• Adversaries appearing at the door may want to forge "apparently valid" messages to fool Bob.
• Alice does not make a DB of all valid messages available to Bob.

The advice remains the same:

Truncate the HMAC down to some small $k$-bit prefix that you view as an acceptable risk, in view of the low ticket price and limited calendar extent of vulnerability.

Monitor transactions at the door, and increase $k$ if you see more failed forgery attempts than your risk model had anticipated. That is, Bob will eventually send logs to Alice for post-mortem audit. Even when online connectivity is available, Bob should always first perform an offline check and note the result, as part of the audit log.

Notice that your customer / adversary won't be able to attempt offline verifications, as you can never send the HMAC's keying material to their browser or mobile app. Only Bob may obtain such keys. Remember to occasionally do regularly scheduled key rotations.

a printed QR code, and since it will already contain a fair amount of [offline] data

You really only need a single bit of data: Should Bob admit this customer, or not?

Consider allocating at most 32 bits for a database Primary Key ID, and push most of the offline-available data fields you mentioned into the DB record. The QR code will mention that ID plus some things Bob will find helpful like name, gender and age, but there's no need for an exhaustive dossier of things that offline decision making won't need anyway. Think of it as similar to the bit.ly (online) URL-shortening service.

Sometimes name and address can be long. But even a truncated form can assist the doorman in making a decision on whether to admit someone. To support exceptional admission procedures, a few bits of hash of the full field would allow for a customer to supply the full data at the door so Bob could verify it.