{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Game of Life" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Introduction\n", "\n", "__Solved by__: [avl](https://twitter.com/avlsec)\n", "\n", "__Event__: DEFCON CTF Quals 2020: [https://ctftime.org/event/994](https://ctftime.org/event/994)\n", "\n", "__Challenge name__: Fountain OOO REliving (115 pts)\n", "\n", "__Description__: We have found the fountain OOO RElive. By discovering its secrets, you will restart the game of life with a chance to do it all over again. This challenge is in memory of John Conway (26 December 1937 – 11 April 2020).\n", "\n", "__File__: `fountain-ooo-relive`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## First analysis" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We quickly realise `fountain-ooo-relive` is a MacroCell file representing a pattern that can be imported into the Golly software. Which corroborates the fact this challenge is a tribute to John Conway, a British mathematician famous for its cellular automation called \"Game of Life\".\n", "\n", "Wikipedia is your friend: [https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life)\n", "\n", "Link to software: [http://golly.sourceforge.net/](http://golly.sourceforge.net/)" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "with open('fountain-ooo-relive', 'r') as f:\n", " data = f.read()" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['[M2]', '# GOOOlly its the Fountain OOO REliving']" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "data.splitlines()[:2]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "After importing the file as a pattern into Golly, we obtain this:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![](../_images/golly.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "... which very much looks like a computer architecture!\n", "\n", "It turns out to be a minimalistic RISC architecture designed by a bunch of people who were challenged to make Tetris run on top of Golly. Here is a link to this epic thread: [https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-life](https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-life)\n", "\n", "They basically built:\n", "- a basic RISC architecture\n", "- an assembly language\n", "- an interpreter\n", "- a higher-level language called Cogol" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Find the flag" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Having read the above thread, it becomes obvious that the flag will be derived from instructions the organisers concealed into the memory of that custom computer.\n", "\n", "But where are the instructions stored in memory? In the ROM! The instructions fetched from the ROM then update values of memory locations located in the RAM, after execution. \n", "\n", "The goal here is therefore to find instructions from the ROM.\n", "\n", "The below figure shows where the ROM and the RAM are." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![](../_images/golly2.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If we zoom in on the ROM, we get..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![](../_images/ROM.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "...a grid of automates that represents bits in memory. So we've got two different automates corresponding to 0s and 1s.\n", "\n", "For example, if we zoom in even more, the automate representing \"1\" is ![](../_images/1.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Let the fun begin" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "My approach here was:\n", "- Use computer vision to detect patterns corresponding to 1s\n", "- Create a corresponding matrix with the fetched 0s and 1s\n", "- Parse the binary code to get assembly code\n", "- Find the flag from the assembly" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Detect bits with OpenCV\n", "\n", "The below code detects 1s and upload them in the `coords` array." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import cv2\n", "import numpy as np\n", "from matplotlib import pyplot as plt\n", "\n", "img_rgb = cv2.imread('../_images/ROM.png') # Screenshot of the ROM\n", "img_gray = cv2.cvtColor(img_rgb, cv2.COLOR_BGR2GRAY)\n", "\n", "template = cv2.imread('../_images/1.png',0) # Screenshot of a pattern coresponding to \"1\"\n", "\n", "w, h = template.shape[::-1]\n", "\n", "res = cv2.matchTemplate(img_gray,template,cv2.TM_CCOEFF_NORMED)\n", "threshold = 0.8\n", "loc = np.where( res >= threshold)\n", "\n", "coords = []\n", "\n", "for pt in zip(*loc[::-1]):\n", " cv2.rectangle(img_rgb, pt, (pt[0] + w, pt[1] + h), (0,0,255), 2)\n", " coords.append(pt)\n", "\n", "cv2.imwrite('../_images/res.png',img_rgb)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And it gives:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![](../_images/res.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Coordinates to matrix\n", "\n", "We then convert the results stored in the `coords` array to a matrix." ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [], "source": [ "n_cols = 116\n", "n_lines = 59 # with the first one \n", "delta = 22\n", "start_y = 6\n", "start_x = 4\n", "\n", "mat = np.zeros((59,116),int)\n", "\n", "new_coords = []\n", "for c in coords:\n", " x,y = c\n", " x = int((x - start_x)/delta)\n", " y = int((y - start_y)/delta)\n", " new_coords.append((x,y))\n", " mat[y][x] = 1" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAABE4AAAI/CAYAAABpkpzSAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3dbYxt11kf8P/qHSfhpbfhhtS6Y6d1KlyQVZUJGsVBoIrmQie8COcDSkGUWiiVv1A1tFQ08AVVaiWQKl6qIiQrSXElSoguL7H4wDQ2QWmlNsWXjCDEVHFTAvY4cYAEaJGcGFY/zEl7c3Mfz/adNfvsc/z7SdGds2d77Wev8+x1zvyz50zrvQcAAACAz/eX1l0AAAAAwFIJTgAAAAAKghMAAACAguAEAAAAoCA4AQAAACgITgAAAAAKO3Me7EsvXeh3veq2OQ8JAAAAcKprv/nsH/TeX3nj9jMFJ621NyT5iSQXkryt9/7Dz7f/Xa+6Lf/98FVnOSQAAADAcBcuP/HRm22/5V/Vaa1dSPKTSb4xyT1JvqO1ds+tjgcAAACwNGf5jJPXJnmi9/6R3vunk7wzyX1jygIAAABYv7MEJ3ck+f3rHj+52gYAAACwFc79r+q01h5orT3WWnvsE3/45+d9OAAAAIBhzhKcPJXk+k96vXO17XP03h/sve/33vdf+YoLZzgcAAAAwLzOEpz8epK7W2uvbq29JMm3J3l4TFkAAAAA63fLf4649/5ca+0fJznMyZ8jfkfv/beHVQYAAACwZq33PtvBLrZL/d52ZbbjAQAAAEzxSL96rfe+f+P2c/9wWAAAAIBNJTgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqnBiettXe01p5prX3wum2XWmvvaa19ePXvl5xvmQAAAADzm3LHyU8necMN296a5NHe+91JHl09BgAAANgqpwYnvff3JfmjGzbfl+Sh1dcPJXnj4LoAAAAA1u5WP+Pk9t7706uvP5bk9kH1AAAAACzGmT8ctvfek/Tq+621B1prj7XWHvtMnj3r4QAAAABmc6vBycdba5eTZPXvM9WOvfcHe+/7vff92/LSWzwcAAAAwPxuNTh5OMn9q6/vT/LuMeUAAAAALMeUP0f8s0n+a5Ivb6092Vp7c5IfTvINrbUPJ/n61WMAAACArbJz2g699+8ovnVlcC0AAAAAi3LmD4cFAAAA2FaCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAIDCzroLuBWHx0frLoE1O9jdm7TflF6ZMtac46hp3Dhq0gNq0gNq0gNz18Q0U587gFGmrOEXLt98uztOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKLTe+2wHu9gu9XvbldmOx/Y6PD6atN/B7t6QseYcR03jxlGTHpi7JgCmmbqGwxReoxnlkX71Wu99/8bt7jgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgsLPuAgDW7WB3b1HjjBxrm2ta4rkdHh8NO96UseYcZ4k1bep8Tx0LwFoxzdS198VML03rkwuXb77dHScAAAAABcEJAAAAQEFwAgAAAFAQnAAAAAAUBCcAAAAABcEJAAAAQEFwAgAAAFAQnAAAAAAUBCcAAAAAhdZ7n+1gF9ulfm+7cuZxDo+PBlSzXAe7e6fuM2UORo2z1Jo43Tb3wJRxpo7FNNvcA9ameW1zD1ib5rXEHliiqfM0pyXOpXmaxjydzhxNs8R5eqRfvdZ7379xuztOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKOysu4B1O9jdO3Wfw+Oj2cZ5IfvNNQ7TjOyBUWON7AH9NC9rE6Ns89qkl+a3tLVp21/npszTFCPPbVRNIy1tnrZ5jhLzNIVrbpolrrsXLt98uztOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKOysu4BbcbC7N2m/w+OjIftsqinzNPX8zdOLu5cS8zSFtWkavTSNeTqda24a7wemGTlPcx5v6nUwahw1jeuTpdU0qp6pY6lpeTVt6jU31VnWcHecAAAAABQEJwAAAAAFwQkAAABAQXACAAAAUBCcAAAAABQEJwAAAAAFwQkAAABAQXACAAAAUGi999kOdrFd6ve2K7MdDwAAAGCKR/rVa733/Ru3u+MEAAAAoCA4AQAAACgITgAAAAAKghMAAACAguAEAAAAoCA4AQAAACgITgAAAAAKghMAAACAws66C7gVh8dHk/Y72N0bMtac46hp3DhLrGlT53uJNW1qDyyxJj2gJj2gJj0wdp4A2C6n3nHSWntVa+29rbUPtdZ+u7X2ltX2S62197TWPrz690vOv1wAAACA+Uz5VZ3nknxf7/2eJK9L8j2ttXuSvDXJo733u5M8unoMAAAAsDVODU5670/33n9j9fWfJnk8yR1J7kvy0Gq3h5K88byKBAAAAFiHF/ThsK21u5K8Jsn7k9zee3969a2PJbl9aGUAAAAAazY5OGmtfXGSn0/yvb33P7n+e733nqQX/90DrbXHWmuPfSbPnqlYAAAAgDlNCk5aa7flJDT5md77L6w2f7y1dnn1/ctJnrnZf9t7f7D3vt97378tLx1RMwAAAMAspvxVnZbk7Uke773/6HXfejjJ/auv70/y7vHlAQAAAKzPzoR9vibJdyX5rdbaZ//A/Q8m+eEk72qtvTnJR5O86XxKBAAAAFiPU4OT3vt/SdKKb18ZWw4AAADAcky542RWh8dHp+5zsLs361hzjqMmPaCm7e6BJdakB9SkB9SkB+avCYDN8YL+HDEAAADAi4ngBAAAAKAgOAEAAAAoCE4AAAAACoITAAAAgILgBAAAAKAgOAEAAAAoCE4AAAAACjvrLuA8HezurbuEzzGynqWd20hLnKdtnu+RtnmeltiXo2zzuY20zec2knlim197R9Z0eHw05HhTxpli7nMbac5eGfW8jTzeFHP20tTjTTG1pm3ugSVaYl+e95y74wQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAIDCzroLOE+Hx0en7nOwuzdknymm1DP1eEs7t5FGndtIS6xplE2te6o5r9+px1paP2372rTEHliakXUvcZ6W+LyMqmmJ5zbKyF5a4jzNuaZOMfK1YGnnNtXUOZjzeHPOwdyvBVMssQeW+Jq5xPmes+45uOMEAAAAoCA4AQAAACgITgAAAAAKghMAAACAguAEAAAAoCA4AQAAACgITgAAAAAKghMAAACAQuu9z3awi+1Sv7dded59Do+PTh3nYHdvVEks0MgeWFo/Takn2dweX9p8M42+3NxzW6Jtnm+vT9NqWtq5jTR3D2yqUc/v3H25tGPNbe7e3dS5nLvuOa+nkWvznH0y0iP96rXe+/6N291xAgAAAFAQnAAAAAAUBCcAAAAABcEJAAAAQEFwAgAAAFAQnAAAAAAUBCcAAAAABcEJAAAAQGFn3QWcp8Pjo1P3Odjdm6GSE1PqSabVNOrcRtY0yshjjRpr1HyPPLdt7oGlXbujzfncbWpfjrS0dWD0WCOMXAeWeG0ubb633RLnconr5RQjX8dHWeLzO6eR8z3n69PcRp3b3K+ro+ZyZN1z1jT3+4El9m7FHScAAAAABcEJAAAAQEFwAgAAAFAQnAAAAAAUBCcAAAAABcEJAAAAQEFwAgAAAFAQnAAAAAAUBCcAAAAAhZ11F3CeDnb3hoxzeHw027E22TbP05y9NPV4S5zLJdY0ysj+3uZ5cm6baeS5jbpWlviassQeWOI8jbLEdXfumqa+b5jTnD03dZylrTsjn7clXuNzHm/ua2CJ1+Womuaue+7r6bz70h0nAAAAAAXBCQAAAEBBcAIAAABQEJwAAAAAFAQnAAAAAAXBCQAAAEBBcAIAAABQEJwAAAAAFHbWXcB5Ojw+OnWfg929GSoZf6xRYy2xppGW1gNL9GI//03muWPUGjdlnKljbbMlvqYs8TlZ4jyNMrLuqdfdaTZ1Lpdom+dym6/LqZY4B0v7WXTqujRq/ZpiKX3pjhMAAACAguAEAAAAoCA4AQAAACgITgAAAAAKghMAAACAguAEAAAAoCA4AQAAACgITgAAAAAKO+su4Dwd7O6tu4TPcXh8NGm/KXVPGWvUOFPHWqJRdY+a75GWWNMSLXGelljTKEs8tyXWtLTnd2Q9Szu3ZFxNSzw3ppnzfdPUPhn5Pm3EONu+Ni9xDkYZ1SebbGnv+ac+J0t77qbO45x1L+XnVXecAAAAABQEJwAAAAAFwQkAAABAQXACAAAAUBCcAAAAABQEJwAAAAAFwQkAAABAQXACAAAAUNhZdwHn6fD46NR9Dnb3huwzxahxRhpZ06j5HjXOSNvcA1PmO5m39pHHWuKcL62mkT0w6txGrgNLm+9kea9PIy1xDV+ipV0r2/6cbOr5zfm+aYnvB5ZY0xRT65lzvZw6l3OPNac56x7ZAyOPd5qR19yUsTbpPYM7TgAAAAAKghMAAACAguAEAAAAoCA4AQAAACgITgAAAAAKghMAAACAguAEAAAAoCA4AQAAACgITgAAAAAKO6ft0Fp7WZL3JXnpav+rvfcfaq29Osk7k7wiybUk39V7//R5Frsuh8dHp+5zsLs3QyXjjzfl3KYeb1RNc8/lnJY43yONula2+ZpLtnuemGZpz8vItWmUpc1RMvaaGzXWEudpiTUt0Tb3wBRz1z11nTvNps73FKPmKJn/Z5U531tt6vuvJb6GjZrvqcc7iyl3nDyb5PW9969MspfkDa211yX5kSQ/1nv/siSfTPLm8ysTAAAAYH6nBif9xP9ePbxt9b+e5PVJrq62P5TkjedSIQAAAMCaTPqMk9bahdbaUZJnkrwnyf9M8qne+3OrXZ5Mcsf5lAgAAACwHpOCk977n/fe95LcmeS1Sb5i6gFaaw+01h5rrT32mTx7i2UCAAAAzO8F/VWd3vunkrw3yVcneXlr7bMfLntnkqeK/+bB3vt+733/trz0TMUCAAAAzOnU4KS19srW2stXX39Bkm9I8nhOApRvW+12f5J3n1eRAAAAAOtw6p8jTnI5yUOttQs5CVre1Xv/5dbah5K8s7X2r5J8IMnbz7FOAAAAgNmdGpz03n8zyWtusv0jOfm8EwAAAICtNOWOk8U5PD6atN/B7t6wseYaZ25T5iiZdn5zzvcS655a0yhLrGmJtnmeRtU98vy3eb5HntvS5mnksZb4/C5tvkda4rltc01LvFaW+B507ppGPXdLrHvO3h35M9YUS1wrpph7Luf++WnUWEv7+XHqWBcu33z7C/pwWAAAAIAXE8EJAAAAQEFwAgAAAFAQnAAAAAAUBCcAAAAABcEJAAAAQEFwAgAAAFAQnAAAAAAUWu99toNdbJf6ve3K8+5zeHx06jgHu3ujStpYo+ZpyjgjxxpZ04uduZxmib27tJqmrqmbeo3PPU9z0rvzPidLrGmUkT2wREvsy6WtqSPrntuovnSNjzP3+4Ftfn2a8xqf+7Vg7h6Y4pF+9Vrvff/G7e44AQAAACgITgAAAAAKghMAAACAguAEAAAAoCA4AQAAACgITgAAAAAKghMAAACAguAEAAAAoLCz7gKA7XGwu3fqPofHR7ONM9WcdY8ea65xRo41sqYp5pzvqX25tGtlZO8ucZw515RNXptGWWLvjrLENXWUkb07yhJfV5do1HO3ydfTpvbAnNfd3Nf4EvtySk0XLt98uztOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKOysu4BbcXh8NOvxDnb3Tt1nZE1TjrfN5p7vOU19bked38i5HNWXSxsnGTffI/tyylhLXJvmrHuT18ol9twoo56XuXtg7n6acn5LXAde7Nf43HVv6jwt0RJ7d9RY2/zeeao552Dua27O19W5bdL65Y4TAAAAgILgBAAAAKAgOAEAAAAoCE4AAAAACoITAAAAgILgBAAAAKAgOAEAAAAoCE4AAAAACoITAAAAgELrvc92sIvtUr+3XXnefQ6Pj2aq5sTB7t6p+0ypadQ4Uy3xeHOaem5zPr9TzF33qGPNfbw5n5Opx5ubeTrdyN51jY+ztLVi6lhLtLRrLpl3Lrf9/Jd2fks8t7nfo4wy91zO/Ro2p7lf61/s761G2tSfVx/pV6/13vdv3O6OEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqt9z7bwS62S/3edmW24x0eH812rIPdvWFjjap7Sk0j52jkHJxm7rrnfE5GWuLzO6WmTZ2nqXUvrZ+W2CdTbOo6MPV4o2zyPJ1mU19713G808z5vCWbe82NfA2b8/XQ87u8ay5Z3no5tZ4lXk+jjrdES3vtHWmJfflIv3qt975/43Z3nAAAAAAUBCcAAAAABcEJAAAAQEFwAgAAAFAQnAAAAAAUBCcAAAAABcEJAAAAQEFwAgAAAFBovffZDnaxXer3tiuzHQ8AAABgikf61Wu99/0bt7vjBAAAAKAgOAEAAAAoCE4AAAAACoITAAAAgILgBAAAAKAgOAEAAAAoCE4AAAAACoITAAAAgMLOugu4FYfHR+suAQAAPs/B7t66SwBgMHecAAAAABQEJwAAAAAFwQkAAABAQXACAAAAUBCcAAAAABQEJwAAAAAFwQkAAABAQXACAAAAUBCcAAAAABR21l3AjQ6Pj07d52B3b4ZKAADghZnyXhaAsaZkBFPW5wuXb77dHScAAAAABcEJAAAAQEFwAgAAAFAQnAAAAAAUBCcAAAAABcEJAAAAQEFwAgAAAFAQnAAAAAAUJgcnrbULrbUPtNZ+efX41a2197fWnmit/Vxr7SXnVyYAAADA/F7IHSdvSfL4dY9/JMmP9d6/LMknk7x5ZGEAAAAA6zYpOGmt3Znkm5O8bfW4JXl9kqurXR5K8sbzKBAAAABgXabecfLjSb4/yV+sHr8iyad678+tHj+Z5I7BtQEAAACs1anBSWvtW5I803u/disHaK090Fp7rLX22Gfy7K0MAQAAALAWOxP2+Zok39pa+6YkL0tyMclPJHl5a21nddfJnUmeutl/3Ht/MMmDSXKxXepDqgYAAACYwal3nPTef6D3fmfv/a4k357kV3vv35nkvUm+bbXb/UnefW5VAgAAAKzBC/mrOjf6F0n+WWvtiZx85snbx5QEAAAAsAxTflXn/+m9/1qSX1t9/ZEkrx1fEgAAAMAynOWOEwAAAICtJjgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKAhOAAAAAAqCEwAAAICC4AQAAACgIDgBAAAAKOysu4BbcXh8NGm/g929IWPNOY6axo2zxJo2db6XWNOm9sASa9IDatIDatIDY+cJgO3ijhMAAACAguAEAAAAoCA4AQAAACgITgAAAAAKghMAAACAguAEAAAAoCA4AQAAACgITgAAAAAKrfd++k6t/W6SP03y50me673vt9YuJfm5JHcl+d0kb+q9f/L5xrnYLvV725XnPdbh8dGp9Rzs7p26DwAAzG3Ke1kAxpqSEUxZny9cfuJa733/xu0v5I6Tv9t737tukLcmebT3fneSR1ePAQAAALbGWX5V574kD62+fijJG89eDgAAAMByTA1OepL/1Fq71lp7YLXt9t7706uvP5bk9uHVAQAAAKzRzsT9vrb3/lRr7a8meU9r7Xeu/2bvvbfWbvphKaug5YEkeVm+8EzFAgAAAMxp0h0nvfenVv8+k+QXk7w2ycdba5eTZPXvM8V/+2Dvfb/3vn9bXjqmagAAAIAZnBqctNa+qLX2lz/7dZK/l+SDSR5Ocv9qt/uTvPu8igQAAABYhym/qnN7kl9srX12///Ye/+V1tqvJ3lXa+3NST6a5E3nVyYAAADA/E4NTnrvH0nylTfZ/odJrpxHUQAAAABLcJY/RwwAAACw1QQnAAAAAAXBCQAAAEBBcAIAAABQEJwAAAAAFAQnAAAAAAXBCQAAAEBBcAIAAABQEJwAAAAAFHbWXcCtODw+mrTfwe7ekLHmHEdN48ZZYk2bOt9LrGlTe2CJNekBNekBNemBsfMEwHZxxwkAAABAQXACAAAAUBCcAAAAABQEJwAAAAAFwQkAAABAQXACAAAAUBCcAAAAABQEJwAAAAAFwQkAAABAQXACAAAAUBCcAAAAABQEJwAAAAAFwQkAAABAQXACAAAAUBCcAAAAABQEJwAAAAAFwQkAAABAQXACAAAAUGi999kOdrFd6ve2K8+7z+Hx0UzVAAAAAJvuYHfv1H2mZA0XLj9xrfe+f+N2d5wAAAAAFAQnAAAAAAXBCQAAAEBBcAIAAABQEJwAAAAAFAQnAAAAAAXBCQAAAEBBcAIAAABQ2Fl3ATc62N1bdwkAAADAFpmWNTxx063uOAEAAAAoCE4AAAAACoITAAAAgILgBAAAAKAgOAEAAAAoCE4AAAAACoITAAAAgILgBAAAAKCws+4CztPh8dGp+xzs7i1qHDWNG2eJNW3qfC+xpk3tgSXWpAfUpAfUpAfmrwmAcc57fXbHCQAAAEBBcAIAAABQEJwAAAAAFAQnAAAAAAXBCQAAAEBBcAIAAABQEJwAAAAAFAQnAAAAAAXBCQAAAECh9d5nO9jFdqnf266ceZzD46MB1QAAwFgHu3vrLgHgRWdKRjBlfX6kX73We9+/cbs7TgAAAAAKghMAAACAguAEAAAAoCA4AQAAACgITgAAAAAKghMAAACAguAEAAAAoCA4AQAAACjszHmwv/m3/yyHh0ezHe9gd+/UfQ6PT69nznHUNG6cJda0qfO9xJo2tQeWWJMeUJMeUJMemL8mAMYZtT5fuHzz7e44AQAAACgITgAAAAAKghMAAACAguAEAAAAoCA4AQAAACgITgAAAAAKghMAAACAguAEAAAAoNB67/MdrLVPJPnodZu+NMkfzFYAzE+Ps830N9tMf7Pt9DjbTH9zq/567/2VN26cNTj5vIO39ljvfX9tBcA50+NsM/3NNtPfbDs9zjbT34zmV3UAAAAACoITAAAAgMK6g5MH13x8OG96nG2mv9lm+pttp8fZZvqbodb6GScAAAAAS7buO04AAAAAFmttwUlr7Q2ttf/RWnuitfbWddUBI7TWXtVae29r7UOttd9urb1ltf1Sa+09rbUPr/79knXXCreqtXahtfaB1tovrx6/urX2/tU6/nOttZesu0a4Va21l7fWrrbWfqe19nhr7aut4WyL1to/Xb0/+WBr7Wdbay+zhrOpWmvvaK0901r74HXbbrpetxP/dtXnv9la+6r1Vc4mW0tw0lq7kOQnk3xjknuSfEdr7Z511AKDPJfk+3rv9yR5XZLvWfX0W5M82nu/O8mjq8ewqd6S5PHrHv9Ikh/rvX9Zkk8mefNaqoIxfiLJr/TevyLJV+ak163hbLzW2h1J/kmS/d7730pyIcm3xxrO5vrpJG+4YVu1Xn9jkrtX/3sgyU/NVCNbZl13nLw2yRO994/03tro2pYAAAMgSURBVD+d5J1J7ltTLXBmvfene++/sfr6T3PyhvuOnPT1Q6vdHkryxvVUCGfTWrszyTcnedvqcUvy+iRXV7vobzZWa+2vJPk7Sd6eJL33T/fePxVrONtjJ8kXtNZ2knxhkqdjDWdD9d7fl+SPbthcrdf3JfkP/cR/S/Ly1trleSplm6wrOLkjye9f9/jJ1TbYeK21u5K8Jsn7k9zee3969a2PJbl9TWXBWf14ku9P8herx69I8qne+3Orx9ZxNtmrk3wiyb9f/Tra21prXxRrOFug9/5Ukn+T5PdyEpj8cZJrsYazXar12s+dDOHDYWGg1toXJ/n5JN/be/+T67/XT/6ElT9jxcZprX1Lkmd679fWXQuck50kX5Xkp3rvr0nyf3LDr+VYw9lUq896uC8nAeFuki/K5/+aA2wN6zXnYV3ByVNJXnXd4ztX22BjtdZuy0lo8jO9919Ybf74Z28HXP37zLrqgzP4miTf2lr73Zz8auXrc/J5EC9f3fadWMfZbE8mebL3/v7V46s5CVKs4WyDr0/yv3rvn+i9fybJL+RkXbeGs02q9drPnQyxruDk15Pcvfo075fk5AOqHl5TLXBmq897eHuSx3vvP3rdtx5Ocv/q6/uTvHvu2uCseu8/0Hu/s/d+V07W61/tvX9nkvcm+bbVbvqbjdV7/1iS32+tfflq05UkH4o1nO3we0le11r7wtX7lc/2tzWcbVKt1w8n+Yerv67zuiR/fN2v9MBk7eROpjUcuLVvysnvzF9I8o7e+79eSyEwQGvta5P85yS/lf//GRA/mJPPOXlXkr+W5KNJ3tR7v/HDrGBjtNa+Lsk/771/S2vtb+TkDpRLST6Q5B/03p9dZ31wq1prezn58OOXJPlIku/Oyf/BZA1n47XW/mWSv5+TvwL4gST/KCef82ANZ+O01n42ydcl+dIkH0/yQ0l+KTdZr1dh4b/Lya+n/VmS7+69P7aOutlsawtOAAAAAJbOh8MCAAAAFAQnAAAAAAXBCQAAAEBBcAIAAABQEJwAAAAAFAQnAAAAAAXBCQAAAEBBcAIAAABQ+L/yi27sNOUimAAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "plt.figure(figsize=(20,10))\n", "plt.imshow(mat)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Matrix to binary code instructions\n", "\n", "Following the Stack Overflow thread, we can turn the matrix into instruction lines, which we store in the `code` variable. " ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [], "source": [ "code = \"\"\n", "for j in range(n_cols):\n", " for i in range(n_lines - 1):\n", " if mat[i+1][j] == 1:\n", " code += '1'\n", " else:\n", " code += '0'\n", " code += '\\n'" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['0000000000000000000000000000000000000000000000000000000001',\n", " '0000000000000000000011111111111111100011111111111111110001',\n", " '0000000000001001100100000000001001100100000000001001110011',\n", " '0000000000001001110010101010110001110100000000000000010110',\n", " '0000000000001001010100000000001001010100000000001001110011',\n", " '0000000000001001110011000111011000110100000000000000010110',\n", " '0000000000001001000100000000001001000100000000001001110011',\n", " '0000000000001001110010101101001001100100000000000000010110',\n", " '0000000000001000110100000000001000110100000000001001110011',\n", " '0000000000001001110010101101101111010100000000000000010110']" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "code.splitlines()[:10]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Binary code to assembly instructions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\"Assembly to binary code\" has been implemented in the Python script: [https://github.com/QuestForTetris/QFT/blob/master/CreateROM.py](https://github.com/QuestForTetris/QFT/blob/master/CreateROM.py)\n", "\n", "We reversed that script to get a \"binary code to assembly\" function. \n", "\n", "Assembly instructions are now stored in the `asm` variable." ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [], "source": [ "from bitstring import BitArray\n", "\n", "opcodes = {'0000': 'MNZ',\n", " '0001': 'MLZ',\n", " '0010': 'ADD',\n", " '0011': 'SUB',\n", " '0100': 'AND',\n", " '0101': 'OR',\n", " '0110': 'XOR',\n", " '0111': 'ANT',\n", " '1000': 'SL',\n", " '1001': 'SRL',\n", " '1010': 'SRA'}\n", "\n", "modes = {'00': '',\n", " '01': 'A',\n", " '10': 'B',\n", " '11': 'C'}\n", "\n", "def parse(code):\n", " out = \"\"\n", " count = 0 \n", " for l in code.splitlines()[::-1]:\n", " opcode = opcodes[l[-4:]]\n", " arg1 = l[18*2:-4]\n", " arg2 = l[18:18*2]\n", " arg3 = l[:18]\n", " mode1 = modes[arg1[:2]]\n", " arg1 = str(BitArray(bin=arg1[2:]).int)\n", " mode2 = modes[arg2[:2]]\n", " arg2 = str(BitArray(bin=arg2[2:]).int)\n", " mode3 = modes[arg3[:2]]\n", " arg3 = str(BitArray(bin=arg3[2:]).int)\n", " out += str(count) + '. ' + opcode + ' ' + mode1 + arg1 + ' ' + mode2 + arg2 + ' ' + mode3 + arg3 +'\\n'\n", " count+=1\n", " return out" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [], "source": [ "asm = parse(code)" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0. MLZ -1 44 43\n", "1. XOR 0 0 2\n", "2. MLZ -1 25971 2\n", "3. MLZ -1 14554 3\n", "4. MLZ -1 22445 4\n", "5. MLZ -1 25411 5\n", "6. MLZ -1 3743 6\n", "7. MLZ -1 13391 7\n", "8. MLZ -1 12059 8\n", "9. MLZ -1 2554 9\n", "10. MLZ -1 15823 10\n", "11. MLZ -1 5921 11\n", "12. MLZ -1 18009 12\n", "13. MLZ -1 14823 13\n", "14. MLZ -1 4757 14\n", "15. MLZ -1 7754 15\n", "16. MLZ -1 22480 16\n", "17. MLZ -1 8371 17\n", "18. MLZ -1 12418 18\n", "19. MLZ -1 22738 19\n", "20. MLZ -1 16499 20\n", "21. MLZ -1 7132 21\n", "22. MLZ -1 22793 22\n", "23. MLZ -1 22307 23\n", "24. MLZ -1 12485 24\n", "25. MLZ -1 7936 25\n", "26. MLZ -1 26630 26\n", "27. MLZ -1 15483 27\n", "28. MLZ -1 6471 28\n", "29. MLZ -1 1806 29\n", "30. MLZ -1 22705 30\n", "31. MLZ -1 25019 31\n", "32. MLZ -1 16442 32\n", "33. MLZ -1 5145 33\n", "34. MLZ -1 15593 34\n", "35. MLZ -1 23867 35\n", "36. MLZ -1 23738 36\n", "37. MLZ -1 14086 37\n", "38. MLZ -1 23123 38\n", "39. MLZ -1 0 39\n", "40. XOR A1 -27179 39\n", "41. SUB A39 A2 2\n", "42. XOR A1 -14018 39\n", "43. SUB A39 A3 3\n", "44. XOR A1 -22549 39\n", "45. SUB A39 A4 4\n", "46. XOR A1 -27735 39\n", "47. SUB A39 A5 5\n", "48. XOR A1 -225 39\n", "49. SUB A39 A6 6\n", "50. XOR A1 -15190 39\n", "51. SUB A39 A7 7\n", "52. XOR A1 -8339 39\n", "53. SUB A39 A8 8\n", "54. XOR A1 -1415 39\n", "55. SUB A39 A9 9\n", "56. XOR A1 -12768 39\n", "57. SUB A39 A10 10\n", "58. XOR A1 -6243 39\n", "59. SUB A39 A11 11\n", "60. XOR A1 -18725 39\n", "61. SUB A39 A12 12\n", "62. XOR A1 -13743 39\n", "63. SUB A39 A13 13\n", "64. XOR A1 -7402 39\n", "65. SUB A39 A14 14\n", "66. XOR A1 -4444 39\n", "67. SUB A39 A15 15\n", "68. XOR A1 -22495 39\n", "69. SUB A39 A16 16\n", "70. XOR A1 -12017 39\n", "71. SUB A39 A17 17\n", "72. XOR A1 -16138 39\n", "73. SUB A39 A18 18\n", "74. XOR A1 -22234 39\n", "75. SUB A39 A19 19\n", "76. XOR A1 -20283 39\n", "77. SUB A39 A20 20\n", "78. XOR A1 -5054 39\n", "79. SUB A39 A21 21\n", "80. XOR A1 -22161 39\n", "81. SUB A39 A22 22\n", "82. XOR A1 -22641 39\n", "83. SUB A39 A23 23\n", "84. XOR A1 -16096 39\n", "85. SUB A39 A24 24\n", "86. XOR A1 -4238 39\n", "87. SUB A39 A25 25\n", "88. XOR A1 -26510 39\n", "89. SUB A39 A26 26\n", "90. XOR A1 -13059 39\n", "91. SUB A39 A27 27\n", "92. XOR A1 -5726 39\n", "93. SUB A39 A28 28\n", "94. XOR A1 -2182 39\n", "95. SUB A39 A29 29\n", "96. XOR A1 -22211 39\n", "97. SUB A39 A30 30\n", "98. XOR A1 -28099 39\n", "99. SUB A39 A31 31\n", "100. XOR A1 -20296 39\n", "101. SUB A39 A32 32\n", "102. XOR A1 -7012 39\n", "103. SUB A39 A33 33\n", "104. XOR A1 -12961 39\n", "105. SUB A39 A34 34\n", "106. XOR A1 -21059 39\n", "107. SUB A39 A35 35\n", "108. XOR A1 -21210 39\n", "109. SUB A39 A36 36\n", "110. XOR A1 -14493 39\n", "111. SUB A39 A37 37\n", "112. XOR A1 -21817 39\n", "113. SUB A39 A38 38\n", "114. MLZ -1 -2 0\n", "115. MLZ 0 0 0\n", "\n" ] } ], "source": [ "print(asm)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Interpreter" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "An interpreter exists: [http://play.starmaninnovations.com/qftasm/](http://play.starmaninnovations.com/qftasm/)\n", "\n", "But the code is easy enough to be analysed quickly:\n", "* The `MLZ -1 [n] [addr]` instructions set the `addr` value to the number `n`.\n", "* Addresses 2 to 38 contain values that then get updated using `XOR` and `SUB` methods.\n", "* Two other variables located respectively in addresses 1 and 39 are being used to perform the updates.\n", "* Value at address 39 is known but not at address 1." ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [], "source": [ "def interpreter(asm, addr1):\n", " init = []\n", " xored = []\n", " for l in asm.splitlines()[2:39]:\n", " init.append(int(l.split()[3]))\n", " for l in asm.splitlines()[40:-2:2]:\n", " xored.append(int(l.split()[3]))\n", " return [(addr1^v)-u+32768 for u,v in zip(init,xored)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solving the challenge\n", "\n", "* We know that the flag starts with `OOO`.\n", "* As address 1 is unknown, the last step here is to try out different possibilities for that address (bruteforce) until we find the ASCII decimal code to the `O` character in the 3 first addresses containing the flag (2, 3 and 4)." ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [], "source": [ "def solve(asm):\n", " for i in range(37000):\n", " l = interpreter(asm, i)\n", " if l[:3] == [79,79,79]:\n", " return \"\".join([chr(u) for u in l])\n", " return 'Not found'" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'OOO{in_this_life___youre_on_your_own}'" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solve(asm)" ] } ], "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.7.4" } }, "nbformat": 4, "nbformat_minor": 4 }