HMAC for round-trip validation

Question

I have a need to produce URLs to allow the downloading of a single file, without authentication. These links will be sent through email, and I understand and accept the risk of a given link being shared by its recipient (or intercepted in transit).

Each file is identified by a UUID, generated in SQL Server using NEWID(). I need to prevent an attacker who knows the link format from brute-force guessing other UUIDs and accessing other files shared this way. Note also that the links have an automatic expiration.

My current link scheme sends the UUID along with an HMAC. The HMAC is generated using:

1. a payload composed of system-level salt + a per-file nonce salt + the UUID
2. a 128-byte system-level key to compute a SHA2-512 HMAC

Is any part of this superfluous or excessive? Does using HMAC gain me any additional security over a simple strong hash in this scenario?

For discussion about T-SQL NEWID(), see SQL Server : does NEWID() always gives a unique ID? on StackOverflow.

Answer 1

If you look at RFC 4122 then you can see which bits are not random. I think that are 128 bits in the UUID and 6 of them are non-random to indicate the scheme used. That leaves 122 bits of UUID, which is probably enough to consider them relatively random. Only if you generate many millions of them is there a chance of collision. However, there is a reason why a hash commonly has an output size of double the wanted security level because of the birthday paradox. And 122 / 2 = 61 bits of security, which is on the low side. So it might be a good idea to extend at least the randomness of the value.

Of course you can always add random bits to them and a MAC using a secret key would that. It would allow you to reject tries with relative confidence. Furthermore, you could reject those before a database lookup. How much confidence depends on the security of the MAC, usually limited by the output size of the MAC. It does of course require the additional burden of key management though.

Alternatively you could simply add more random bits to the UUID or to generate a proprietary 256 bit UUID. However, I think the MAC scheme over the UUID is relatively elegant as the MAC can be over the UUID, while keeping the UUID scheme intact, and it can be extended by adding a salt. Of course the secret key must be kept secret otherwise an adversary can generate the same.

The disadvantage is that the UUID as send with MAC and possible salt is not standardized anymore, so you have to think about an alternative canonical encoding of UUID and MAC.

Answer 2

Your goal, if I have understood correctly, is to create an unforgeable bearer token which you will send to a user, and which the user can later present to you in order to gain access to a resource, say a file. An adversary should be unable to guess any tokens they weren't given outright, even if they are given many many tokens.

You appear to be constrained by using a UUID as part of your token in order to identify the file. There are two possibilities here:

1. You are simply required to use the UUID syntax.

   If you are simply required to use the UUID syntax and you have the latitude to decide afresh (once you implement your new bearer token design) for each file what UUID gets at it, you can simply choose a uniform random version 4 UUID with a cryptographically secure random number generator so that the UUIDs are unpredictable. Whether SQL Server's NEWUUID() does this I cannot tell you.

   There are $2^{122}$ version 4 UUIDs. Even if you issue a quintillion different UUIDs, about $2^{50}$, and even if the adversary tries querying a quintillion different UUIDs, the probability that the adversary is successful at forging even one UUID is less than $2^{100}\!/2^{122} = 1/2^{22}$—less than one in a million. You should adjust these numbers, of course, for the largest plausible online bandwidth your application will have.

   What about a collision? Well, set aside the security for a moment—what will your application do, for legitimate users, if there is a collision between UUIDs? Even if you have a quintillion different files, the probability of collision is still less than one in a million. In general, if there are $n$ files, the probability of a collision is less than $n^2\!/2^{122}$, by the birthday paradox. If this is a staggeringly enormous distributed system, maybe that's a concern—maybe you should use 256-bit tokens rather than ≈128-bit tokens as database keys.

2. You are actually required to use a particular UUID generator, and you are not guaranteed that the UUID generator is cryptographically unpredictable.

   In this case, you need a little more than just the UUID—you need to append an unforgeable authenticator, like an HMAC as you suggested.

---

There are other reasons why you might want an authenticator on a bearer token. For example, you might want additional access controls on the resource: you may want to limit access to a particular purpose specified by the user, or limit access to a particular time period—and for some reason you can't store these access controls alongside the resource itself. Maybe the dealer of bearer tokens, who decides which parties should have access to which resources when, is administratively separate from the keeper of the files.

The standard security notion for an authenticator, or message authentication code, is EUF-CMA, or existential unforgeability under (adaptive) chosen-message attack. The threat model is that an adversary can query your system as an oracle for the authenticator on any message of their choice, and then they win if they find the authenticator on any message they didn't query the oracle for. The legitimate user—the dealer of bearer tokens, the keeper of files—must maintain a secret key that the adversary cannot predict, of course, or all security is void.

When the keeper of the files receives a bearer token $(m, a)$ where $m$ is a message and $a$ is an authenticator, they can drop the message on the floor if $a$ is not the correct authenticator for the message $m$. Parts of the message may be implicit. For example, a logged-in user might have a username $u$, and might furnish a UUID $i$ alongside an authenticator $a$; the keeper of the files might consider the (uniquely encoded) concatenation $(u, i)$ to be the message on which $a$ is a putative authenticator.

HMAC-SHA512 is a safe choice of an authenticator function, although it's unnecessarily long—it is safe to truncate to 256 bits, or to use HMAC-SHA256 instead, and really, if truncated to 128 bits that's still plenty. (Collisions are not relevant for the authenticator.) You should use a 256-bit key in any case (even for HMAC-MD5). There is no advantage to a longer key, but very long keys could cause trouble owing to a quirk in the design of HMAC. You could also use the SHA-3 KMAC128, or keyed BLAKE2, or any other PRF-based MAC you like. (A caveat about MACs like Poly1305-AES: These are essentially one-time MACs that require a message sequence number to be safe. I do not recommend that here.)

That leaves the question of: What figures in as the message for the authenticator? In general, you should always ensure the authenticator covers all information that you will act on. Obviously that includes the UUID and anything else provided by the user.

You've also included a salt. What does a salt do? The main purpose of a salt is to mitigate multi-target attacks on the key by separating the input space. For example, if 1000 different sites install your application, and for some reason issue authenticators under their own secret keys on the same UUID (and access control time and so on), then an adversary can get a batch advantage with rainbow tables on a parallel machine to find one of the site's keys at 1/1000 the cost of an attack on only a single site at a time. So in that case it may be worthwhile to hash a per-site salt in with the UUID in every authenticator. But what about a per-file salt? Each file already has a unique identifier. So there's no need for a per-file salt.