The redis project patched a possible memory corruption vulnerability in the sdsResize method using commit 5f5f298a. The changes addressed an edge case whereby the method may not set the simple dynamic string (SDS) type field. SDS values use a variable-sized header based on their type. The types are defined as one of HI_SDS_TYPE_5, HI_SDS_TYPE_8, HI_SDS_TYPE_16, HI_SDS_TYPE_32, or HI_SDS_TYPE_64 where the number defines the bit width of the length and size fields. HI_SDS_TYPE_5 is a special case where the length is encoded in the 5 most significant bits of the flags field (whose 3 least significant bits are the type), and there is no dedicated length or size field.

These types are defined in deps/hiredis/sds.h and the format is:

hisdshdr5                  FBBBB...
hisdshdr8                LAFBBBB...
hisdshdr16             LLAAFBBBB...
hisdshdr32         LLLLAAAAFBBBB...
hisdshdr64 LLLLLLLLAAAAAAAAFBBBB...
           ^       ^       ^^
           |       |       |\ (char *)sds points here
           |       |       \ 1 - byte of flags where the 3 LSBs are the type and the 5 MSBs are the size in hisdshdr5 or unused
           |       \ N-bits of allocation size (number of bytes available for the buffer)
           \ N-bits of length (number of bytes used by the buffer)

The changes to sdsResize ensure that when realloc is not used to perform the resizing operation, that the type field is always set before the calls to sdssetlen and sdssetalloc. The unpatched implementation of sdsResize would simply set the SDS length and size with the allocations were already considered to be “optimal”. If the allocation was already optimal and did not require a reallocation to adjust the size, but the SDS type itself needed to be increased to store the new value, the size field may overflow in such a way that the SDS size is marked as smaller than it is.

This condition would require:

1. Redis be built with the USE_JEMALLOC macro, without this compile-time setting alloc_already_optimal will never be truish
   
2. That sdsResize be called to enlarge the SDS value
   
3. That the allocation size occupied by the SDS value be the same as the new size that it is being enlarged to
   
4. The original size be of a smaller SDS type than the new size (i.e. the new size requires more bits to store than are available within the original).
   

A quick spot check reveals that the redis package provided by Fedora 39 is built with the USE_JEMALLOC macro defined and meets the first condition. For the second condition, locations where sdsResize is invoked need to be identified. This search yields the following 4 locations:

• sdsRemoveFreeSpace — This location will only reduce the size of the allocation
  
• sdsTest — These locations are only used as part of testing. Also the sizes are static.
  
• clientsCronResizeQueryBuffer — This location will only reduce the size of the allocation. It’s intended to run periodically to reclaim unused memory that was once occupied by the query buffer. It can not be used to enlarge the SDS value. The resize value could be set to c->bulklen, which is attacker-controllable by using bulk loading, however, it will not be larger than the existing allocation.
  
• hllSparseSet
  

hllSparseSet

This function uses sdsResize to increase the size of the sds struct.

This will call sdsResize as the PFADD command is received. The size will increment by three each time it is called. sdsResize is only called when there are fewer than 3 bytes available in the sds structure. When enlarging the sds structure, o->ptr is increased to either double its current value or 300, whichever is smaller. The sds structure is resized in this way until it has reached server.hll_sparse_max_bytes which is 3,000 by default. This means that it can only be resized at most 13 times. Of those 13 times the value is enlarged, it only changes SDS type twice, once from 5 to 8 the first time it is resized and then from 8 to 16 the 4th time it is resized. In neither of these cases is the existing allocation the same size as the requested one, most likely because of how the buffer is doubling in size at this point. Because the existing allocation size is not the same as the requested one, the alloc_already_optimal value is false in sdsResize and the branch is taken which sets the type correctly.

The hllSparseSet code path can be triggered with the following Python code for debugging:

import redis
import time

r = redis.Redis(host='localhost', port=6379, decode_responses=True)

start = int(time.time())
for i in range(0x1000):
	r.pfadd('pf-' + str(start), str(i))

r.close()

Conclusion

Based on this analysis there is no demonstratable threat to the redis project posed by this bug. The necessary conditions to enlarge an SDS value in the way necessary to trigger the overflow are not reacable by any code path included in the most recent vulnerable version 7.2.3. Nevertheless, this bug should be and has been patched to prevent it’s use in the future. An ideal scenario where this bug could be leveraged would require the attacker to have a high degree of control over both the currently allocated size of the SDS and the new size. In that case, starting with an SDS of 0xff bytes and resizing it to 0x100 would use the affected code path and incorrectly set the length and size to 0.