How does Nginx look-up cached resource?

[Gena Makhomed]

On 07.09.2015 19:58, Maxim Dounin wrote:

>>> Also, it's important to understand that, while collision attacks
>>> now exists, it doesn't really make MD5 bad for various
>>> non-security uses.
>>
>> nginx cache is security use too.
>>
>> If user configure common shared cache for all virtual servers,
>> and config have two servers: first, protected by access,
>> auth_basic or auth_request modules from unauthorized use,
>> and second server with publicly available content.
>>
>> If attacker know proxy_cache_key, for example $scheme$host$request_uri
>> and know $request_uri from protected site - he can create MD5/crc32
>> collision by building specific $request_uri for second server,
>> and he will got unauthorized access to protected content
>> from the first, protected web site.
>>
>> This is looks like vulnerability.
>
> Yes, this looks like a valid example of a potentially affected
> configuration.  Though as far as I know, it is not currently
> possible to construct a value (which choosen prefix) that maps to
> a given md5 value.

It is possible and already was used to create forged certificates.

In 2007, a chosen-prefix collision attack was found against MD5,
requiring roughly 2**50 evaluations of the MD5 function. The paper
also demonstrates two X.509 certificates for different domain names,
with colliding hash values. This means that a certificate authority
could be asked to sign a certificate for one domain, and then that
certificate could be used to impersonate another domain.
- 
https://en.wikipedia.org/wiki/Collision_attack#Chosen-prefix_collision_attack

Details: http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/

Current nVidia GPU hardware can process hundreds of thousands
of MD5 hashes per second, and multiple GPU can be used
in cluster with linear scalability, as I understand.

>> And this vulnerability can be fixed as Sergey Brester propose:
>>
>> We should always compare the keys,
>> after cache entry with hash value was found.
>>
>> Or vulnerability can be minimized by using secure hash
>> function instead of current cryptographically broken MD5.
>
> I think moving away from MD5 is a right way to go.

160-bit SHA1 ?

...we present an identical-prefix collision attack
and a chosen-prefix collision attack on SHA-1 with
complexities equivalent to approximately 2**61
and 2**77.1 SHA-1 compressions, respectively.
- https://marc-stevens.nl/research/papers/EC13-S.pdf

SHA1 also was considered as insecure for SSL certificates,
and now all forced to migrate from SHA1 to at least SHA-256:
http://googleonlinesecurity.blogspot.co.uk/2014/09/gradually-sunsetting-sha-1.html

Collision attacks against SHA-1 are too affordable:
https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html

Content cached in nginx caches also can be very valuable,
even more valuable than SSL certificates for other sites.

====================================================

Using SHA-256 or SHA-512 or SHA3-256 or SHA3-512 is secure
right now, but it requires more CPU power and more memory.

More secure and robust way is to store proxy_cache_key
value into cache file on disk and check this value
before sending cached response to client. In such way
we can be ensured, what cache misuse is not possible,
and may be even fast 128-bit secure hash functions
can be used, to minimize memory usage and CPU requirements.
SHA1 truncated to 128 bits or something better than SHA1,
or even leave current MD5 as is - for retaining backward
compatibility with existing installations around the world.

If retaining backward compatibility is not mandatory,
may be SHAKE128(M, 128) can be used as 128-bit hash
for saving server memory, but checking proxy_cache_key value
is still required for preventing information disclosure attacks,
- because this is only 128 bit hash and it can be brute forced
in near future, as it described at Bruce Schneier site for SHA1.

P.S.

Using MurmurHash is not good idea, because attacker
can easy make collisions and invalidate popular entries
from cache, and this technology can be used for DDoS attacks.
(even in case if only one site exists on server with nginx cache)

Using secure hash function for nginx cache is strong requirement,
even in case then full proxy_cache_key value check will be added.

-- 
Best regards,
  Gena