1

I'm implementing an API key based authentication scheme and I'm caching valid API key entries (hash, scope etc.) in a memory cache. For the cache key, I had been using the first 8 characters of the base 64 representation of the key hash. I did this because there are 64^8 (281,474,976,710,656) possible keys, so I thought that would be more than enough.

Then when a key arrived, I hashed it, encoded it in base64, grabbed the first 8 characters then pulled the auth details from the cache and returned it to the API logic.

But considering it further, I significantly reduce collision resistance by doing this. It still has a large amount of collision resistance, but haven't I just reduced key entropy to 32 bit instead of 128 bit? So an attacker only has to match the first 32 bits of the key to pass.

I have a couple of options:

  1. Leave it as it is, but do an equality check between the full length keys before returning the matching auth entry. (If it doesn't match, log the attempt and fail the auth request)

  2. Use the full length hash for the cache key.

Approach 1 seems to be a bit awkward, if I'm doing an equality check straight after, the key might as well be better. Approach 2 seems better.

I expect 128bit hashing for the cache key is probably slightly slower than 32 bit hashing + an equality check. But I suspect it's neither here nor there.

Is there any other advantage to either approach (or a different approach I haven't considered)?

14
  • 2
    "But I suspect it's neither here nor there." This is the important thing. Unless you have shown via profiling or similar this check is actually significant, just do the simple thing and use 128 bit keys. Commented Jun 27 at 9:52
  • You'd have to be very hard up for memory these days until trading a small number of bytes in RAM for added code complexity makes any sense at all. Commented Jun 27 at 9:57
  • if you have no collision risk on the shorter key. why do you have a long api key at all? This seems like a recipe for security holes
    – Ewan
    Commented Jun 27 at 13:52
  • Remember that attacker does not have to match a paticular key. They just need to match any key from the large pool of your active users.
    – Basilevs
    Commented Jun 27 at 14:09
  • @KilianFoth I was coming to a similar conclusion myself when looking at the code. Commented Jun 27 at 22:28

1 Answer 1

3

Avoid Premature Optimization

This is premature optimization. You don't know if using 128 bits is slow or fast. You're complicating a simple operation and spending a lot of time thinking about a part of the code that might or might not be slow. Only optimize once you know it is a bottleneck of some kind and have measured it (YAGNI).

Also keep in mind, it's not just your attacker that has to match the first 32 bits. You'll fully overwrite a valid API key with another valid API key if they happen to have a collision, leading to some nasty bugs and unhappy customers if you get enough usage on this API. 32 bit hash values have a 1 in 100 Chance of collision at 9292 entries, and a 1 in 10 Chance at 30084, according to This site

3
  • Thanks for the answer, particularly the link at the end regarding collision probabilities. I hadn't realised how high a chance there would be of collision with 32 bit keys. Commented Jun 28 at 23:03
  • As a side point though, I don't think increasing the number of buckets will reduce a bottleneck caused by a long cache key. If hashing the cache key to look up the correct bucket takes too long, the way to fix it is to use a faster hashing algorithm (or shorter key) Commented Jun 28 at 23:21
  • You're right. I remembered that Loadfactor can increase the speed without considering it's just the actual lookup speed. I'll edit my answer to remove that. Commented Jun 28 at 23:38

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.