How does Nginx look-up cached resource?

[Maxim Dounin]

Hello!

On Mon, Sep 07, 2015 at 10:29:42PM +0300, Gena Makhomed wrote:

> 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

For the attack you described chosen prefix collision attack is not 
enough, as it is about finding two colliding values with chosen 
prefixes.  But to mount the attack described one needs to find a 
value that maps to a given md5 hash - essentially, this is a 
preimage attack with additional requirements.

On the other hand, it might be possible to simplify requirements 
of the attack by forcing some authenticated user to load data 
under a given key and then retrieve this key contents using a 
choosen prefix collision previously calculated.

[...]

> 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.

May be you are right and checking full key value would be the most 
secure and efficient solution after all, especially keeping in 
mind backward compatibility.

[...]

> 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.

Agree, using intentionally non-secure hashes isn't a good idea.

-- 
Maxim Dounin
http://nginx.org/