How does Nginx look-up cached resource?

[Maxim Dounin]

Hello!

On Wed, Sep 09, 2015 at 12:07:36AM +0300, Gena Makhomed wrote:

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

Yes, that's the basic idea.  Though I still think that such an 
attack is unlikely to be practical now due to various limiting 
factors (like crc32 check and $request_uri being ASCII), but it 
certainly make sense to mitigate such potential attacks.

[...]

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

Yes, in my testing I wasn't able to detect any statistically 
significant difference in performance.  Patch:

# HG changeset patch
# User Maxim Dounin <mdounin at mdounin.ru>
# Date 1441818706 -10800
#      Wed Sep 09 20:11:46 2015 +0300
# Node ID 85034da89d12dfdf5e0d72f0a99251f98ec1764c
# Parent  412ccd679a4691725d5a5562494051a3cadd69ca
Cache: check the whole cache key in addition to hashes.

This prevents a potential attack that discloses cached data if an attacker
will be able to craft a hash collision between some cache key the attacker
is allowed to access and another cache key with protected data.

See http://mailman.nginx.org/pipermail/nginx-devel/2015-September/007288.html.

Thanks to Gena Makhomed and Sergey Brester.

diff --git a/src/http/ngx_http_file_cache.c b/src/http/ngx_http_file_cache.c
--- a/src/http/ngx_http_file_cache.c
+++ b/src/http/ngx_http_file_cache.c
@@ -521,9 +521,12 @@ wakeup:
 static ngx_int_t
 ngx_http_file_cache_read(ngx_http_request_t *r, ngx_http_cache_t *c)
 {
+    u_char                        *p;
     time_t                         now;
     ssize_t                        n;
+    ngx_str_t                     *key;
     ngx_int_t                      rc;
+    ngx_uint_t                     i;
     ngx_http_file_cache_t         *cache;
     ngx_http_file_cache_header_t  *h;
 
@@ -547,12 +550,27 @@ ngx_http_file_cache_read(ngx_http_reques
         return NGX_DECLINED;
     }
 
-    if (h->crc32 != c->crc32) {
+    if (h->crc32 != c->crc32 || h->header_start != c->header_start) {
         ngx_log_error(NGX_LOG_CRIT, r->connection->log, 0,
                       "cache file \"%s\" has md5 collision", c->file.name.data);
         return NGX_DECLINED;
     }
 
+    p = c->buf->pos + sizeof(ngx_http_file_cache_header_t)
+        + sizeof(ngx_http_file_cache_key);
+
+    key = c->keys.elts;
+    for (i = 0; i < c->keys.nelts; i++) {
+        if (ngx_memcmp(p, key[i].data, key[i].len) != 0) {
+            ngx_log_error(NGX_LOG_CRIT, r->connection->log, 0,
+                          "cache file \"%s\" has md5 collision",
+                          c->file.name.data);
+            return NGX_DECLINED;
+        }
+
+        p += key[i].len;
+    }
+
     if ((size_t) h->body_start > c->body_start) {
         ngx_log_error(NGX_LOG_CRIT, r->connection->log, 0,
                       "cache file \"%s\" has too long header",
@@ -583,7 +601,6 @@ ngx_http_file_cache_read(ngx_http_reques
     c->last_modified = h->last_modified;
     c->date = h->date;
     c->valid_msec = h->valid_msec;
-    c->header_start = h->header_start;
     c->body_start = h->body_start;
     c->etag.len = h->etag_len;
     c->etag.data = h->etag;

[...]

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

Yes, I think switching away from MD5 is a right way to go.  On the 
other hand, SHA1 is not that much better - while no collisions are 
currently known, it's cryptographically broken.  SHA256 is slower 
(but not sure we care, as it's unlikely to be statistically 
significant in overral testing).  SHAKE128 looks interesting, but 
it's not really available anywhere now.

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