Phase 3 x86_64.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# x86_64: Phase 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Imports\n",
    "\n",
    "import angr\n",
    "import claripy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We push the input values to the stack and then pop them right before the function exits. Since no value is pushed onto the stack during the execution of the function, we can safely manipulate the stack in the way we planned."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Load the binary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "project = angr.Project('bomb64')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define the address for the start of the execution path."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The address where the symbolic execution shall begin. It is right after parsing of two numbers taken as input.\n",
    "addr_start = 0x400F60\n",
    "\n",
    "# The address of the return of phase_3.\n",
    "# We end it there so as to dump the stack and retrieve values before the stack frame is discarded.\n",
    "addr_target = 0x400FC9\n",
    "\n",
    "# The address of the first instruction of the explode_bomb function, which is to be avoided.\n",
    "addr_bomb = 0x40143A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define a blank state for the simulation, a state with most of it's data uninitialized. Pass the address where the state is initialized, along with the user input to be given via standard input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "state = project.factory.blank_state(addr=addr_start)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Setup the stack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Push the null value,\n",
    "# so as to setup the stack as depicted in the pictures. \n",
    "state.stack_push(0x0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Push the symbolic values to be input on the stack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# We push two symbolic values required as the pair-set values.\n",
    "for i in range(2):\n",
    "    state.stack_push(claripy.BVS(\"num_{}\".format(i), 32))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create a simulation manager with this blank state that would help us manage the symbolic execution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "simgr = project.factory.simulation_manager(state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We call the explore method of the simulation manager, tasked with finding an execution path that reaches the target address and avoids the address which explodes the bomb."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING | 2020-06-16 00:21:30,064 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mThe program is accessing memory or registers with an unspecified value. This could indicate unwanted behavior.\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:30,066 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mangr will cope with this by generating an unconstrained symbolic variable and continuing. You can resolve this by:\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:30,066 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32m1) setting a value to the initial state\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:30,067 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32m2) adding the state option ZERO_FILL_UNCONSTRAINED_{MEMORY,REGISTERS}, to make unknown regions hold null\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:30,070 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32m3) adding the state option SYMBOL_FILL_UNCONSTRAINED_{MEMORY_REGISTERS}, to suppress these messages.\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:30,076 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling register rax with 8 unconstrained bytes referenced from 0x400f60 (phase_3+0x1d in bomb64 (0x400f60))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:30,504 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:31,025 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:31,114 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:31,194 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:31,277 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:31,375 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:31,464 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:31,551 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<SimulationManager with 15 active, 1 found, 2 avoid>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "simgr.explore(find=addr_target, avoid=addr_bomb, enable_veritesting=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We dereference the execution path \"found\" by the simulation manager and dump the stack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "found = simgr.found[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remove the stack setup first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING | 2020-06-16 00:21:31,673 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffe4 with 4 unconstrained bytes referenced from 0x400fc9 (phase_3+0x86 in bomb64 (0x400fc9))\u001b[0m\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<BV64 Reverse(Reverse(num_1_40_32) .. mem_7fffffffffeffe4_50_32{UNINITIALIZED})>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Pop the null value we pushed to stack first,\n",
    "# as part of stack setup.\n",
    "found.stack_pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Popped value: 0x13700000001\n",
      "Decimal number on the lower end: 1\n",
      "Decimal number on the higher end: 311\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'1 311'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer = []\n",
    "\n",
    "curr = found.solver.eval(found.stack_pop())\n",
    "print(\"Popped value: {0}\".format(hex(curr)))\n",
    "\n",
    "# Masking is done using bit-wise operators to split the values merged in the block.\n",
    "lower_end = curr & 0xffffffff\n",
    "print(\"Decimal number on the lower end: {0}\".format(lower_end))\n",
    "answer.append(str(lower_end))\n",
    "higher_end = curr>>32 & 0xffffffff\n",
    "answer.append(' ')\n",
    "print(\"Decimal number on the higher end: {0}\\n\".format(higher_end))\n",
    "answer.append(str(higher_end))\n",
    "answer.append(' ')\n",
    "\n",
    "# Removes the space in the end.\n",
    "''.join(answer[:-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's the two number combination we need to input to pass the third phase."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's add a constraint to specifically reach an end with values that satisfy each case in the jump table. Add the constraint on the first value since that is used to match a case in the table."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the form:\n",
    "```state.solver.add(num_1 == x)```, where x is the integer value of a case out of the jump table."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's put it in a loop to get the all the values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING | 2020-06-16 00:21:33,850 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling register rax with 8 unconstrained bytes referenced from 0x400f60 (phase_3+0x1d in bomb64 (0x400f60))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:34,082 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:34,177 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffe4 with 4 unconstrained bytes referenced from 0x400fc9 (phase_3+0x86 in bomb64 (0x400fc9))\u001b[0m\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 207\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING | 2020-06-16 00:21:36,298 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling register rax with 8 unconstrained bytes referenced from 0x400f60 (phase_3+0x1d in bomb64 (0x400f60))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:36,525 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:36,608 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffe4 with 4 unconstrained bytes referenced from 0x400fc9 (phase_3+0x86 in bomb64 (0x400fc9))\u001b[0m\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 311\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING | 2020-06-16 00:21:39,952 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling register rax with 8 unconstrained bytes referenced from 0x400f60 (phase_3+0x1d in bomb64 (0x400f60))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:40,400 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:40,518 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffe4 with 4 unconstrained bytes referenced from 0x400fc9 (phase_3+0x86 in bomb64 (0x400fc9))\u001b[0m\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 707\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING | 2020-06-16 00:21:43,575 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling register rax with 8 unconstrained bytes referenced from 0x400f60 (phase_3+0x1d in bomb64 (0x400f60))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:43,807 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:43,881 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffe4 with 4 unconstrained bytes referenced from 0x400fc9 (phase_3+0x86 in bomb64 (0x400fc9))\u001b[0m\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 256\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING | 2020-06-16 00:21:46,728 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling register rax with 8 unconstrained bytes referenced from 0x400f60 (phase_3+0x1d in bomb64 (0x400f60))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:46,997 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:47,088 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffe4 with 4 unconstrained bytes referenced from 0x400fc9 (phase_3+0x86 in bomb64 (0x400fc9))\u001b[0m\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 389\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING | 2020-06-16 00:21:50,308 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling register rax with 8 unconstrained bytes referenced from 0x400f60 (phase_3+0x1d in bomb64 (0x400f60))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:50,638 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:50,735 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffe4 with 4 unconstrained bytes referenced from 0x400fc9 (phase_3+0x86 in bomb64 (0x400fc9))\u001b[0m\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 206\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING | 2020-06-16 00:21:53,950 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling register rax with 8 unconstrained bytes referenced from 0x400f60 (phase_3+0x1d in bomb64 (0x400f60))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:54,201 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:54,289 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffe4 with 4 unconstrained bytes referenced from 0x400fc9 (phase_3+0x86 in bomb64 (0x400fc9))\u001b[0m\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6 682\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING | 2020-06-16 00:21:56,242 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling register rax with 8 unconstrained bytes referenced from 0x400f60 (phase_3+0x1d in bomb64 (0x400f60))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:56,619 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffec with 4 unconstrained bytes referenced from 0x400fbe (phase_3+0x7b in bomb64 (0x400fbe))\u001b[0m\n",
      "WARNING | 2020-06-16 00:21:56,755 | \u001b[32mangr.state_plugins.symbolic_memory\u001b[0m | \u001b[32mFilling memory at 0x7fffffffffeffe4 with 4 unconstrained bytes referenced from 0x400fc9 (phase_3+0x86 in bomb64 (0x400fc9))\u001b[0m\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 327\n"
     ]
    }
   ],
   "source": [
    "for x in range(0, 8):\n",
    "    # Load the binary.\n",
    "    project = angr.Project('bomb64')\n",
    "\n",
    "    # Init the addresses.\n",
    "    addr_start = 0x400F60\n",
    "    addr_target = 0x400FC9\n",
    "    addr_bomb = 0x40143A\n",
    "\n",
    "    # Init a blank state.\n",
    "    state = project.factory.blank_state(addr=addr_start)\n",
    "\n",
    "    # Setup the stack.\n",
    "    state.stack_push(0x0)\n",
    "\n",
    "    # Define the symbolic values.\n",
    "    num_1 = claripy.BVS(\"num_1\", 32)\n",
    "    num_2 = claripy.BVS(\"num_2\", 32)\n",
    "\n",
    "    # Add the constraint.\n",
    "    state.solver.add(num_1 == x)\n",
    "\n",
    "    # Push the input to the stack.\n",
    "    state.stack_push(num_1)\n",
    "    state.stack_push(num_2)\n",
    "\n",
    "    # Init the simulation manager.\n",
    "    simgr = project.factory.simulation_manager(state)\n",
    "\n",
    "    # Let Angr explore.\n",
    "    simgr.explore(find=addr_target, avoid=addr_bomb, enable_veritesting=True)\n",
    "\n",
    "    # Get the answer from the found state.\n",
    "    found = simgr.found[0]\n",
    "    found.stack_pop()\n",
    "\n",
    "    answer = []\n",
    "\n",
    "    curr = found.solver.eval(found.stack_pop())\n",
    "\n",
    "    lower_end = curr & 0xffffffff\n",
    "    answer.append(str(lower_end))\n",
    "    higher_end = curr>>32 & 0xffffffff\n",
    "    answer.append(' ')\n",
    "    answer.append(str(higher_end))\n",
    "    answer.append(' ')\n",
    "\n",
    "    # Removes the space in the end.\n",
    "    print(''.join(answer[:-1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And there we go. Values to satisfy all the cases in the jumptable."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}