Harden tcache double-free check

The tcache allocator layer uses the tcache pointer as a key to
identify a block that may be freed twice.  Since this is in the
application data area, an attacker exploiting a use-after-free could
potentially get access to the entire tcache structure through this
key.  A detailed write-up was provided by Awarau here:

https://awaraucom.wordpress.com/2020/07/19/house-of-io-remastered/

Replace this static pointer use for key checking with one that is
generated at malloc initialization.  The first attempt is through
getrandom with a fallback to random_bits(), which is a simple
pseudo-random number generator based on the clock.  The fallback ought
to be sufficient since the goal of the randomness is only to make the
key arbitrary enough that it is very unlikely to collide with user
data.

Co-authored-by: Eyal Itkin <eyalit@checkpoint.com>
---
 malloc/arena.c  |  8 ++++++++
 malloc/malloc.c | 32 ++++++++++++++++++++++++++++----
 2 files changed, 36 insertions(+), 4 deletions(-)

* Siddhesh Poyarekar:

> +/* Process-wide key to try and catch a double-free in the same thread.  */
> +static uintptr_t tcache_key;
> +
> +/* The value of tcache_key does not really have to be a cryptographically
> +   secure random number.  It only needs to be arbitrary enough so that it does
> +   not collide with values present in applications, which would be quite rare,
> +   about 1 in 2^wordsize.  */

The comment should say that a collision could result in performance
problems.

Apart from that, the patch looks okay to me.

Thanks,
Florian

On 06/07/2021 22:29, Siddhesh Poyarekar via Libc-alpha wrote:

> +/* Process-wide key to try and catch a double-free in the same thread.  */
> +static uintptr_t tcache_key;
> +
> +/* The value of tcache_key does not really have to be a cryptographically
> +   secure random number.  It only needs to be arbitrary enough so that it does
> +   not collide with values present in applications, which would be quite rare,
> +   about 1 in 2^wordsize.  */
> +static void
> +tcache_key_initialize (void)
> +{
> +  if (__getrandom (&tcache_key, sizeof(tcache_key), GRND_NONBLOCK)
> +      != sizeof (tcache_key))
> +    {
> +      tcache_key = random_bits ();
> +#if __WORDSIZE == 64
> +      tcache_key = (tcache_key << 32) | random_bits ();
> +#endif

The other usage for ramdom_bits at sysdeps/posix/tempname.c already uses
a uint_fast64_t, so I think it would be better to make it random_bits()
return 64-bit instead.

Also, calling random_bits() in a sequence will result in quite low
entropy, since it uses __clock_gettime64().  Maybe you could add
XOR the pid for the higher bits:

  static inline uint64_t
  random_bits (void)
  {
    struct __timespec64 tv;
    __clock_gettime64 (CLOCK_MONOTONIC, &tv);
    /* Shuffle the lower bits to minimize the clock bias.  */
    uint32_t ret_low = tv.tv_nsec ^ tv.tv_sec;
    ret_low ^= (ret_low << 24) | (ret_low >> 8);
    /* And add a lit more entropy for higher bits.  */
    uint32_t ret_high = ret_low ^ (uint32_t) __getpid ();
    return ((uint64_t) ret_high << 32) | ret_low;
  }

On 7/7/21 11:05 PM, Adhemerval Zanella via Libc-alpha wrote:
> 
> 
> On 06/07/2021 22:29, Siddhesh Poyarekar via Libc-alpha wrote:
> 
>> +/* Process-wide key to try and catch a double-free in the same thread.  */
>> +static uintptr_t tcache_key;
>> +
>> +/* The value of tcache_key does not really have to be a cryptographically
>> +   secure random number.  It only needs to be arbitrary enough so that it does
>> +   not collide with values present in applications, which would be quite rare,
>> +   about 1 in 2^wordsize.  */
>> +static void
>> +tcache_key_initialize (void)
>> +{
>> +  if (__getrandom (&tcache_key, sizeof(tcache_key), GRND_NONBLOCK)
>> +      != sizeof (tcache_key))
>> +    {
>> +      tcache_key = random_bits ();
>> +#if __WORDSIZE == 64
>> +      tcache_key = (tcache_key << 32) | random_bits ();
>> +#endif
> 
> The other usage for ramdom_bits at sysdeps/posix/tempname.c already uses

tempname.c seems to have its own random_bits function (i.e. it just 
happens to have the same name); it doesn't use the one in random_bits.h 
AFAICT.  All other users of random_bits() use 32-bit.  Entropy isn't 
really a concern in the above use case, it's just a key to avoid collisions.

Siddhesh

On 07/07/2021 14:58, Siddhesh Poyarekar wrote:
> On 7/7/21 11:05 PM, Adhemerval Zanella via Libc-alpha wrote:
>>
>>
>> On 06/07/2021 22:29, Siddhesh Poyarekar via Libc-alpha wrote:
>>
>>> +/* Process-wide key to try and catch a double-free in the same thread.  */
>>> +static uintptr_t tcache_key;
>>> +
>>> +/* The value of tcache_key does not really have to be a cryptographically
>>> +   secure random number.  It only needs to be arbitrary enough so that it does
>>> +   not collide with values present in applications, which would be quite rare,
>>> +   about 1 in 2^wordsize.  */
>>> +static void
>>> +tcache_key_initialize (void)
>>> +{
>>> +  if (__getrandom (&tcache_key, sizeof(tcache_key), GRND_NONBLOCK)
>>> +      != sizeof (tcache_key))
>>> +    {
>>> +      tcache_key = random_bits ();
>>> +#if __WORDSIZE == 64
>>> +      tcache_key = (tcache_key << 32) | random_bits ();
>>> +#endif
>>
>> The other usage for ramdom_bits at sysdeps/posix/tempname.c already uses
> 
> tempname.c seems to have its own random_bits function (i.e. it just happens to have the same name); it doesn't use the one in random_bits.h AFAICT.  All other users of random_bits() use 32-bit.  Entropy isn't really a concern in the above use case, it's just a key to avoid collisions.
Yes, but it is essentially what you are doing here: query getrandom
with GRND_NONBLOCK a falling back to clock_gettime.  And we also
have the random_bits from include/random-bits.h.

I think we would better to consolidate it with only one implementation.

On 7/7/21 11:39 PM, Adhemerval Zanella via Libc-alpha wrote:
> Yes, but it is essentially what you are doing here: query getrandom
> with GRND_NONBLOCK a falling back to clock_gettime.  And we also
> have the random_bits from include/random-bits.h.
> 
> I think we would better to consolidate it with only one implementation.

The randomness needs are quite different, but I see your point.  We 
could make a separate random_bits64 to cater to these two use cases. 
Can it be a separate patch though?  I'll put it on top of this one.

Thanks,
Siddhesh

On 07/07/2021 15:12, Siddhesh Poyarekar wrote:
> On 7/7/21 11:39 PM, Adhemerval Zanella via Libc-alpha wrote:
>> Yes, but it is essentially what you are doing here: query getrandom
>> with GRND_NONBLOCK a falling back to clock_gettime.  And we also
>> have the random_bits from include/random-bits.h.
>>
>> I think we would better to consolidate it with only one implementation.
> 
> The randomness needs are quite different, but I see your point.  We could make a separate random_bits64 to cater to these two use cases. Can it be a separate patch though?  I'll put it on top of this one.

I think it can be separate consolidation, what I am trying to avoid is
multiple random_bits implementation which different semantics within
glibc.

On 7/7/21 11:57 PM, Adhemerval Zanella wrote:
> I think it can be separate consolidation, what I am trying to avoid is
> multiple random_bits implementation which different semantics within
> glibc.
> 

Thanks, I'll push this if there are no further objections.

Siddhesh