How does Nginx look-up cached resource?

[Gena Makhomed]

On 08.09.2015 4:41, Maxim Dounin wrote:

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

Yes, $request_uri - full original request URI (with arguments)
Most backends ignore unknown request arguments without errors.

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

Check full key is not my idea,
author of this idea is Sergey Brester.

Overhead for such additional full key value check should be minimal.
But this protect nginx users from any future bugs in hash functions.

Using 256-bit or 512-bit secure hash function requires more memory,
requires more CPU power and therefore it is not very good solution.

But I am still not sure which 128-bit secure hash functions
will be the best choice for nginx cache keys hash function.

For legacy CPUs MD5 faster, but for new CPUs SHA1 is faster
(this can be checked with "openssl speed md5 sha1" command)

Chosen-prefix collision attack on MD5 has compexity 2**50,
but 128-bit SHA-1 is more secure than MD5 for such attack.

128-bit SHA-1 is always better than MD5 for new CPUs,
and may be this hash should be used for nginx cache?

But may be SHAKE128 from SHA-3 is even more faster and more secure?
Currently is no known any collision/preimage attacks against SHAKE128.

https://godoc.org/golang.org/x/crypto/sha3

The SHAKE functions are recommended for most new uses. They can produce 
output of arbitrary length. SHAKE256, with an output length of at least 
64 bytes, provides 256-bit security against all attacks. The Keccak team 
recommends it for most applications upgrading from SHA2-512. (NIST chose 
a much stronger, but much slower, sponge instance for SHA3-512.)

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

Replacing MD5 with other hash function will invalidate all old caches,
but this will be only one time performance degrade after nginx upgrade.

Choice between always using weak "secure" hash function and one time
cache invalidation IMHO should be resolved by replacing hash function.

IMHO, MD5 is worst, SHA1 is better and SHAKE128 is the best candidate.

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

Do not use the MD5 algorithm

Software developers, Certification Authorities, website owners, and 
users should avoid using the MD5 algorithm in any capacity. As previous 
research has demonstrated, it should be considered cryptographically 
broken and unsuitable for further use.

- http://www.kb.cert.org/vuls/id/836068

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

-- 
Best regards,
  Gena