2
$\begingroup$

Background

I'm building a URL shortener, and the URL to shorten may contain a SessionId.

For the URL shortener to not compromise the security of the SessionId, I must use a shortening strategy that fulfills the same requirements as the SessionId.

OWASP states that:

  • The session ID length must be at least 128 bits (16 bytes) here
  • The session ID value must provide at least 64 bits of entropy here

What I think about doing

  • Have a key-value store, where the value is the long (unshortened) URL, and the key is the shortened URL component.
  • When the user navigates to a shortened URL, the long URL is looked up in the key-value store, and returned to the user, who is then redirected.

So the key needs to be at least 128 bits (16 bytes) long, and provide at least 64 bits of entropy, to not compromise the SessionId.

If the key is a hash of the value, I can guarantee the key length, and know the entropy (based on the hashing algorithm used).

But which hashing algorithm should I use?

For example, MD5 digest length is exactly 128 bits. But I don't know what's it's minimum entropy.

The question

Which hashing algorithm produces a digest of at least 128 bits, with at least 64 bits of entropy?

(x-post from StackOverflow: https://stackoverflow.com/q/71224441/6517320)

$\endgroup$
2

1 Answer 1

5
$\begingroup$

The short answer to your hashing question is "use SHA-256." That's the answer for almost every secure-hashing problem, unless the answer is "use SHA-512." If you want a 128 bit hash, then you can truncate SHA-256 (take the first or last 128 bites). All bits in SHA-256 are independent, so you can extract any 128 of them as a hash.

That said, IMO you're thinking about this problem incorrectly. The point isn't about protecting SessionId specifically. The issue is that URLs may contain sensitive information, of which SessionId is just one example (if it's stored in the URL). If someone already knows the shortened URL, they can just ask your system for the full URL, so this is all about stopping attackers finding keys by guessing. You need to make your keyspace sparse, which is it say "much, much larger than the number of keys actually stored."

You're maintaining a key/value database, so there's no need to use a hash at all. You can just generate a random key for each URL. This is better than a hash because there's absolutely no connection between the key and the value.

Given your design, attackers cannot search offline. They have to contact your server. Say you can serve 1,000 requests/second, and you scale your total keyspace to be a trillion times larger than your planned number of URLs. That would take an attacker roughly 15,000 years (~1/2 the space searched) to find a single URL if they could consume all of your available bandwidth (which I expect you might notice....). With just a little bit of rate limiting per IP address, you could dramatically complicate this attack.

Given the above, if you wanted to store a billion URLs in your system, you'd need a keyspace of:

log2(1 billion URLs * 1 trillion multiplier) = 80 bits

In Base58 (which I like for this kind of problem because it's human-friendly), it would take around 14 characters. Tweaking the above values for rate limiting, period of attack you want to protect against, and number of stored URLs, you can choose how long your keys are.

You generally can compute random values on this scale without worrying about collisions (which is good for performance). For the same reason that it's extremely hard for an attacker to find a collision, it's extremely unlikely that you'll have one by accident. But if you want to double-check just how unlikely, look at the Birthday Attack. The calculations for "what's the likelihood that any values collide" are a different than "how long will it take an attacker to find a collision," and in some cases will force you to use longer keys.

IMO there's no need for hashes. But if you do need one, use SHA-256, truncated to whatever number of bits you want.

$\endgroup$
11
  • 2
    $\begingroup$ That depends on your PRNG. On Linux systems, if you use /dev/random, I believe it will block if the system drops below 160 bits of available entropy, so you should always be ok on that kind of system. I would expect any system you use a cryptographic PRNG is going to greatly exceed 64 bits for every value, but you'll have to check your documentation to be certain. For example, on some (but not all) systems /dev/urandom will return low-entropy values. $\endgroup$
    – Rob Napier
    Feb 22, 2022 at 17:34
  • 1
    $\begingroup$ But no hashing function can increase entropy, and if they are collision-resistant over the space in question, they will not (effectively) reduce entropy. The entropy from the original SessionId is going to be preserved by any cryptographic hash. If it had less than 64 bits originally, then so will the hash, and if it had more than 64 bits, so will the hash (minus a little). To increase entropy, you have to add a random salt, which means you're tied to the entropy of your PRNG (just like using a random key). crypto.stackexchange.com/questions/12505/… $\endgroup$
    – Rob Napier
    Feb 22, 2022 at 17:43
  • 1
    $\begingroup$ Pardon the confusing notation. If A <= B and A >= B then it's impossible for A > B. Because hashing can't increase entropy, but can decrease entropy, we don't stand to gain from hashing, but only lose $\endgroup$ Feb 22, 2022 at 18:45
  • 4
    $\begingroup$ "On Linux systems, if you use /dev/random, I believe it will block if the system drops below 160 bits of available entropy" That hasn't been true for a while now. Not that it matters, but it only blocks in early boot and then never again. Entropy isn't "used up", so blocking after seeding never helped anything. $\endgroup$ Feb 22, 2022 at 19:21
  • 2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.