Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
SECCON 2019 CTF Quals - Crazy Repetition of Codes (crypto)
{
"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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment