How does Nginx look-up cached resource?

[Sergey Brester]

On 08.09.2015 01:17, Gena Makhomed wrote:

> There is no obscurity here. Value of proxy_cache_key is known,
> hash function is known, nginx sources is open and available.

If value of proxy_cache_key is known and attackers can generate it, what 
do you want to protect with some hash value?
If attacker can use any key - it's no matter which hash algorithm you 
have used (attacker can get entry).
If attacker can't use any key (it's protected with some internal nginx 
variable) - it's no matter also which hash will be used (attacker cannot 
get entry, because the keys will be compared also).

>> Hash value should be used only for fast searching of hash key. Not to 
>> identify the cached resources!
> You remember proposed solution from your message?
> http://mailman.nginx.org/pipermail/nginx-devel/2015-September/007286.html 
> [1]
> Attacker easily can provide DDoS attack against nginx in this case:
> http://www.securityweek.com/hash-table-collision-attacks-could-trigger-ddos-massive-scale 
> [2]
> Hash Table Vulnerability Enables Wide-Scale DDoS Attacks

And what's stopping him to do the same with much safe hash function? On 
the contrary, don't forget the generating of such hash values is cpu 
greedy also.

>> If your entry should be secure, the key (not it hash) should contain 
>> part of security token, authentication, salt etc.
> This is "security through obscurity",
> and you say, what this is bad thing.

Wrong! Because if this secure parts in key are an internal nginx 
values/variables (authenticated user name, salt etc.), that the attacker 
never can use!
He can theoretical use a variable part of key, to generate or brute some 
expected hash, equal with searched one, but the keys comparison makes 
all his attempts void.
If it is not so, the key contains nothing internals and attacker can use 
any key (example uri part) - see above - it's no matter which hash 
algorithm you have used (attacker can get entry because he can use key). 
The cache is then insecure.

>> So again: hash bears no security function, and if the whole key would 
>> be always compared - it would be at all not important which hash 
>> function will be used, and how secure it is. And to "crack" resp. 
>> return the cache entry you should always "crack" it completely key, 
>> not it hash.

> If site is under high load, and, for example contains many pages,
> which are very popular (for example, 100 req/sec of each) and backend
> need many time for generating such page, for example, 2-3 seconds -
> attacker can using MurmurHash create requestst to non-existend
> pages, with same MurmurHash hash value. And 404 responces
> from backend will replace very popular pages with different uri
> but with same MurmurHash hash value. And backend will be DDoS`ed
> by many requests for different popular pages. So, attacker easily
> can disable nginx cache for any known uri. And if backend can't
> process all client requests without cache - it will be overloaded
> and access to site will be denied for all new users.

1) big error - non-existend pages can be not placed in cache (no cache 
for 404);
2) attacker does not uses MurmurHash - it does nginx over a valid cache 
key generated nginx side, just to find the entry faster (for nothing 
else)!
3) the attacker almost always cannot control the key used for caching 
(except only if it a part of uri - insecure cache);
4) what do you want to do against it? If I understood it correct, 
instead of intensive load by page generation, you want shift the load 
into hash generation? Well, very clever. :)
5) DDOS prevention is in any event not the role of caching and can be 
made with other instruments (also using nginx);

> So, many thousands of nginx configurations will be in vulnerable state.

Wrong. Not a single one, and if only, then not vulnerable - because it 
would be then exactly so "vulnerable" with any other hash function - the 
configuration for key or something else is blame, not the hashing self.
Either the cache is insecure (any key can be used) - no matter which 
hash function,
Or the cache is secure (protected with any internal nginx variable as 
part of cache key, that attacker can't use) - fail by keys compare - no 
matter which hash function also.

> Hash table implementations vulnerable to algorithmic complexity attacks

That means the pure hashing, without keys comparison - that is safe if 
keys would be compared.
What I was already said and wrote 100 times.