SECCON 2019 CTF Quals - Crazy Repetition of Codes (crypto)

crazy_repetition_of_code.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SECCON 2019 CTF Quals - Crazy Repetition of Codes (crypto)\n",
    "\n",
    "The challenge abbreviation is CRC, so we can guess what this challenge is about:\n",
    "\n",
    "```py\n",
    "import os\n",
    "from Crypto.Cipher import AES\n",
    "\n",
    "def crc32(crc, data):\n",
    "  crc = 0xFFFFFFFF ^ crc\n",
    "  for c in data:\n",
    "    crc = crc ^ ord(c)\n",
    "    for i in range(8):\n",
    "      crc = (crc >> 1) ^ (0xEDB88320 * (crc & 1))\n",
    "  return 0xFFFFFFFF ^ crc\n",
    "\n",
    "key = b\"\"\n",
    "\n",
    "crc = 0\n",
    "for i in range(int(\"1\" * 10000)):\n",
    "  crc = crc32(crc, \"TSG\")\n",
    "assert(crc == 0xb09bc54f)\n",
    "key += crc.to_bytes(4, byteorder='big')\n",
    "\n",
    "crc = 0\n",
    "for i in range(int(\"1\" * 10000)):\n",
    "  crc = crc32(crc, \"is\")\n",
    "key += crc.to_bytes(4, byteorder='big')\n",
    "\n",
    "crc = 0\n",
    "for i in range(int(\"1\" * 10000)):\n",
    "  crc = crc32(crc, \"here\")\n",
    "key += crc.to_bytes(4, byteorder='big')\n",
    "\n",
    "crc = 0\n",
    "for i in range(int(\"1\" * 10000)):\n",
    "  crc = crc32(crc, \"at\")\n",
    "key += crc.to_bytes(4, byteorder='big')\n",
    "\n",
    "crc = 0\n",
    "for i in range(int(\"1\" * 10000)):\n",
    "  crc = crc32(crc, \"SECCON\")\n",
    "key += crc.to_bytes(4, byteorder='big')\n",
    "\n",
    "crc = 0\n",
    "for i in range(int(\"1\" * 10000)):\n",
    "  crc = crc32(crc, \"CTF!\")\n",
    "key += crc.to_bytes(4, byteorder='big')\n",
    "\n",
    "flag = os.environ['FLAG']\n",
    "assert(len(flag) == 32)\n",
    "\n",
    "aes = AES.new(key, AES.MODE_ECB)\n",
    "encoded = aes.encrypt(flag)\n",
    "assert(encoded.hex() == '79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e')\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to decrypt the flag, we need to compute the standard $CRC32$ function on strings build by repeating a short chunk $11\\ldots11$ times, where the number has 10000 **digits**! There is no hope to perform this number of operations (*at least* during the CTF). However, if we recall that $CRC32$ is an *affine* function, we can speed this up by using fast matrix exponentiation.\n",
    "\n",
    "*In fact, the simplest solution is to recall that the order of $CRC32$ is $2^{32}-1$, and for any fixed chunk the order will divide this number. Therefore, we can simply reduce `int(\"1\" x 10000)` modulo $2^{32}-1$, and run the code directly. After replacing the `crc32` implementation with `zlib.crc32`, it takes just a couple of minutes to compute the answer!*\n",
    "\n",
    "<details>\n",
    "\n",
    "```py\n",
    "import os\n",
    "from Crypto.Cipher import AES\n",
    "from zlib import crc32\n",
    "\n",
    "key = b\"\"\n",
    "\n",
    "crc = 0\n",
    "for i in range(int(\"1\" * 10000) % (2**32-1)):\n",
    "  crc = crc32(b\"TSG\", crc)\n",
    "assert(crc == 0xb09bc54f)\n",
    "key += crc.to_bytes(4, byteorder='big')\n",
    "\n",
    "crc = 0\n",
    "for i in range(int(\"1\" * 10000) % (2**32-1)):\n",
    "  crc = crc32(b\"is\", crc)\n",
    "key += crc.to_bytes(4, byteorder='big')\n",
    "\n",
    "crc = 0\n",
    "for i in range(int(\"1\" * 10000) % (2**32-1)):\n",
    "  crc = crc32(b\"here\", crc)\n",
    "key += crc.to_bytes(4, byteorder='big')\n",
    "\n",
    "crc = 0\n",
    "for i in range(int(\"1\" * 10000) % (2**32-1)):\n",
    "  crc = crc32(b\"at\", crc)\n",
    "key += crc.to_bytes(4, byteorder='big')\n",
    "\n",
    "crc = 0\n",
    "for i in range(int(\"1\" * 10000) % (2**32-1)):\n",
    "  crc = crc32(b\"SECCON\", crc)\n",
    "key += crc.to_bytes(4, byteorder='big')\n",
    "\n",
    "crc = 0\n",
    "for i in range(int(\"1\" * 10000) % (2**32-1)):\n",
    "  crc = crc32(b\"CTF!\", crc)\n",
    "key += crc.to_bytes(4, byteorder='big')\n",
    "\n",
    "flag = bytes.fromhex(\"79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e\")\n",
    "aes = AES.new(key, AES.MODE_ECB)\n",
    "encoded = aes.decrypt(flag)\n",
    "print(repr(encoded))\n",
    "```\n",
    "\n",
    "</details>\n",
    "\n",
    "<br/>\n",
    "\n",
    "The idea is to construct the $32\\times 32$ matrix $M$ and the 32-bit vector $c$ such that $CRC32_s(x, s) = M\\times x \\oplus c$ (where $s$ is the short string chunk used to build the string). This can be done in 33 black-box calls to $CRC32$: evaluating it at the zero vector and at all unit vectors. \n",
    "\n",
    "Finally, observe that the $e$-time repetition of $CRC32$ is expressed as\n",
    "$$\n",
    "CRC32^e(x, s) = M\\times (\\ldots M\\times(M\\times x \\oplus c) \\oplus c \\ldots )\\oplus c = M^e\\times x \\oplus (M^{e-1} \\oplus M^{e-2} \\oplus \\ldots M \\oplus I) \\times c,\n",
    "$$\n",
    "where $I$ is the $32\\times32$ identity matrix.\n",
    "\n",
    "In our case $x=0$ so we only need to evaluate the sum $M^{e-1} \\oplus M^{e-2} \\oplus \\ldots M \\oplus I$. This can be done using standard geometric series formula (luckily, $M\\oplus I$ is invertible):\n",
    "\n",
    "$$\n",
    "(M^{e-1} \\oplus M^{e-2} \\oplus \\ldots M \\oplus I) = \\frac{M^e\\oplus  I}{M\\oplus I}.\n",
    "$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Computing for 'TSG'\n",
      "Computing for 'is'\n",
      "Computing for 'here'\n",
      "Computing for 'at'\n",
      "Computing for 'SECCON'\n",
      "Computing for 'CTF!'\n",
      "b'SECCON{Ur_Th3_L0rd_0f_the_R1NGs}'\n"
     ]
    }
   ],
   "source": [
    "from sage.all import *\n",
    "from Crypto.Cipher import AES\n",
    "\n",
    "def crc32(crc, data):\n",
    "    crc = 0xFFFFFFFF ^^ crc\n",
    "    for c in data:\n",
    "        crc = crc ^^ ord(c)\n",
    "        for i in range(8):\n",
    "            crc = (crc >> 1) ^^ (0xEDB88320 * (crc & 1))\n",
    "    return 0xFFFFFFFF ^^ crc\n",
    "\n",
    "def frombin(v):\n",
    "    return ZZ(tuple(map(int, v))[::-1], base=2)\n",
    "\n",
    "def tobin(v, n):\n",
    "    return tuple(ZZ(v).digits(2, padto=n))[::-1]\n",
    "\n",
    "E = int(\"1\" * 10000) % (2**32-1)\n",
    "ID = identity_matrix(GF(2), 32, 32)\n",
    "\n",
    "def rep(s):\n",
    "    print(\"Computing for\", repr(s))\n",
    "    # build the vector\n",
    "    c = crc32(0, s)\n",
    "\n",
    "    # build the matrix\n",
    "    m = matrix(GF(2), 32, 32)\n",
    "    for i in range(32):\n",
    "        v = [0] * 32\n",
    "        v[i] = 1\n",
    "        v = frombin(tuple(v))\n",
    "        v = crc32(v, s) ^^ c\n",
    "        v = tobin(v, 32)\n",
    "        m.set_column(i, v)\n",
    "    c = vector(GF(2), tobin(c, 32))\n",
    "\n",
    "    matsum = (m**E + ID) * ~(m + ID)\n",
    "    res = matsum * c\n",
    "    return int(frombin(res)).to_bytes(4, byteorder=\"big\")\n",
    "\n",
    "key = b\"\"\n",
    "key += rep(\"TSG\")\n",
    "key += rep(\"is\")\n",
    "key += rep(\"here\")\n",
    "key += rep(\"at\")\n",
    "key += rep(\"SECCON\")\n",
    "key += rep(\"CTF!\")\n",
    "\n",
    "flag = bytes.fromhex(\"79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e\")\n",
    "aes = AES.new(key, AES.MODE_ECB)\n",
    "encoded = aes.decrypt(flag)\n",
    "print(encoded)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath-3",
   "language": "sage",
   "name": "sagemath3"
  },
  "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}

https://nbviewer.jupyter.org/gist/hellman/1f2040e3ef275ff11f6209b5a6a4fd72/crazy_repetition_of_code.ipynb