Safe linking

glibc 최신 버전에선 취약한 singly linked list를 위한 mitigation이 추가되었다.
기존 tcache, fastbin 들의 성능을 거의 감소시키지 않고 pointer hijacking을 보호한다.

• Partial pointer override: Modifying the lower bytes of the pointer (Little Endian).
• Full pointer override: Hijacking the pointer to a chosen arbitrary location.
• Unaligned chunks: Pointing the list to an unaligned address.

위와 같은 3개의 일반적인 공격에 대해 방어할 수 있다.
safe linking을 우회하고 공격하기 위해서는 이제 heap leak과 pointer leak이 둘 다 필요하게 된다.

Protection

리눅스에선 heap base가 ASLR에 의해서 mmap_base와 함께 초기화된다.

random_base = ((1 << rndbits) - 1) << PAGE_SHIFT)

이때 PAGE_SHIFT 만큼 shift 된다.
리눅스는 virtual address를 physical address로 변환을 쉽게하기 위해서 page로 나눈다.
그래서 일반적으로 4kb 단위로 나누어지게 된다.

#define PAGE_SHIFT              12        //    1<< 12 = 4096 = 4KB

PAGE_SHIFT는 위와 같다.

Mask := (L >> PAGE_SHIFT)

singly linked list의 pointer가 위치한 주소를 L이라고 가정하면, Mask를 다음과 같이 정의할 수 있다.
singly linked list pointer가 P라고 가정하고 보면 아래와 같다.

PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
*L = PROTECT(P)

이제 위 방법을 통해서 ASLR의 무작위성을 이용한 암호화가 가능하다.

위와 같이 동작하게 된다.

위와 같은 protection layer는 공격자가 빨간색 랜덤 비트들을 알지 못하면, pointer를 변조하지 못한다는 것을 의미한다.

Analysis

tcache만 간단하게 분석해보면 좀 더 정확히 알 수 있다.

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.  If a collision does happen
   consistently enough, it could cause a degradation in performance since the
   entire list is checked to check if the block indeed has been freed the
   second time.  The odds of this happening are exceedingly low though, about 1
   in 2^wordsize.  There is probably a higher chance of the performance
   degradation being due to a double free where the first free happened in a
   different thread; that's a case this check does not cover.  */
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
    }
}

/* Caller must ensure that we know tc_idx is valid and there's room
   for more chunks.  */
static __always_inline void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
  tcache_entry *e = (tcache_entry *) chunk2mem (chunk);

  /* Mark this chunk as "in the tcache" so the test in _int_free will
     detect a double free.  */
  e->key = tcache_key;

  e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]);
  tcache->entries[tc_idx] = e;
  ++(tcache->counts[tc_idx]);
}

/* Caller must ensure that we know tc_idx is valid and there's
   available chunks to remove.  */
static __always_inline void *
tcache_get (size_t tc_idx)
{
  tcache_entry *e = tcache->entries[tc_idx];
  if (__glibc_unlikely (!aligned_OK (e)))
    malloc_printerr ("malloc(): unaligned tcache chunk detected");
  tcache->entries[tc_idx] = REVEAL_PTR (e->next);
  --(tcache->counts[tc_idx]);
  e->key = 0;
  return (void *) e;
}

glibc 2.34 malloc.c의 일부다.

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

tcache_key를 초기화 해주는 함수다.

tcache_put (mchunkptr chunk, size_t tc_idx)
{
  tcache_entry *e = (tcache_entry *) chunk2mem (chunk);

  /* Mark this chunk as "in the tcache" so the test in _int_free will
     detect a double free.  */
  e->key = tcache;

  e->next = tcache->entries[tc_idx];
  tcache->entries[tc_idx] = e;
  ++(tcache->counts[tc_idx]);
}

위 코드는 glibc 2.31 malloc.c 코드의 일부다.

/* Caller must ensure that we know tc_idx is valid and there's room
   for more chunks.  */
static __always_inline void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
  tcache_entry *e = (tcache_entry *) chunk2mem (chunk);
  /* Mark this chunk as "in the tcache" so the test in _int_free will
     detect a double free.  */
  e->key = tcache_key;
  
  e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]);
  tcache->entries[tc_idx] = e;
  ++(tcache->counts[tc_idx]);
}

glibc 2.31 때는 그냥 key에다 tcache 넣고 검증했었는데, 약간 바뀌었다.

static __always_inline void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
  tcache_entry *e = (tcache_entry *) chunk2mem (chunk);

  /* Mark this chunk as "in the tcache" so the test in _int_free will
     detect a double free.  */
  e->key = tcache_key;

  e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]);
  tcache->entries[tc_idx] = e;
  ++(tcache->counts[tc_idx]);
}

tcache_put을 보면, PROTECT_PTR (&e->next, tcache->entries[tc_idx])을 e->next에 집어넣는 것을 알 수 있다.

#define PROTECT_PTR(pos, ptr) \
  ((__typeof (ptr)) ((((size_t) pos) >> 12) ^ ((size_t) ptr)))

PROTECT_PTR 매크로는 위와 같다.
pos에 대해서 1.5바이트를 밀어서 Mask를 구해서 xor 하는 것을 볼 수 있다.

static __always_inline void *
tcache_get (size_t tc_idx)
{
  tcache_entry *e = tcache->entries[tc_idx];
  if (__glibc_unlikely (!aligned_OK (e)))
    malloc_printerr ("malloc(): unaligned tcache chunk detected");
  tcache->entries[tc_idx] = REVEAL_PTR (e->next);
  --(tcache->counts[tc_idx]);
  e->key = 0;
  return (void *) e;
}

tcache_get 함수의 모습이다.

#define REVEAL_PTR(ptr)  PROTECT_PTR (&ptr, ptr)

이때 REVEAL_PTR 매크로는 위와 같다.

PROTECT_PTR 매크로가 호출되면 (&e->next) >> 12 ^ tcache->entries[tc_idx] -> e->next 가 되고, REVEAL_PTR 매크로가 호출되면, (&e->next) >> 12 ^ e->next -> tcache->entries[tc_idx]가 되면서 복호화가 된다.

또한 이제 REVEAL_PTR 해주고 나서 aligned_OK를 호출한다.
그래서 tcache duplication에서 size를 0x7f로 주면 이제 여기서 터진다.

Bypass

pointer와 pointer의 주소가 같은 page 내에 있다면, 복호화를 할 수 있다.
떨어져 있어도, pointer와 pointer의 주소의 page-offset을 구해서 복호화가 가능하다.

아래 깃허브에서 복호화 코드를 확인할 수 있다.
https://github.com/n132/Dec-Safe-Linking

같은 page 내에 있다고 가정하면, 상위 1.5 바이트는 0x00과 xor 되기 때문에, plaintext일 수 밖에 없다는 점을 이용하면, 쉽게 복호화가 가능하다. 상위 1.5 바이트와 다시 xor 해서 1.5 바이트를 구하고, 그러면 또 1.5 바이트를 아니까 다음 1.5 바이트를 구할 수 있다.

long decrypt(long cipher)
{
	puts("The decryption uses the fact that the first 12bit of the plaintext (the fwd pointer) is known,");
	puts("because of the 12bit sliding.");
	puts("And the key, the ASLR value, is the same with the leading bits of the plaintext (the fwd pointer)");
	long key = 0;
	long plain;

	for(int i=1; i<6; i++) {
		int bits = 64-12*i;
		if(bits < 0) bits = 0;
		plain = ((cipher ^ key) >> bits) << bits;
		key = plain >> 12;
		printf("round %d:\n", i);
		printf("key:    %#016lx\n", key);
		printf("plain:  %#016lx\n", plain);
		printf("cipher: %#016lx\n\n", cipher);
	}
	return plain;
}

위와 같은 함수로 decrypt가 가능하다.

page-offset을 알면, z3로 돌려서 확률적으로 복호화가 가능한것 같다.
PROTECT_PTR 해서 leaked와 같고, pointer와 pointer의 주소 사이의 페이지 오프셋이 off와 같고, 0x0... ~ 0x7f... 범위로 제한해서 방정식을 풀면 나온다.

from z3 import *
def XxX(leaked, off):
    leaked = BitVecVal(leaked, 48)
    off  = BitVecVal(off,48)

    res  = BitVec('res', 48)
    sss  = BitVec('sss', 48)

    s = Solver()

    s.add((sss>>12)^res==leaked)
    s.add((sss>>12)-(res>>12)==off)
    s.add((res>>40)<=0x7f)
    s.add((res>>40)>=0)

    if str(s.check()) == 'sat':
        m = s.model()
        return  m.evaluate(res).as_long() & 0xfffffffff000
    else:
        print(s.check())
        exit(1)