Skip to content

Instantly share code, notes, and snippets.

@hellman

hellman/write.ipynb

Last active February 28, 2021 14:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hellman/a8c9a09b1ce6959226f9d75cf94b805f to your computer and use it in GitHub Desktop.
Save hellman/a8c9a09b1ce6959226f9d75cf94b805f to your computer and use it in GitHub Desktop.
Download ZIP
AeroCTF 2021 - Horcrux (Crypto)
Display the source blob
Display the rendered blob
Raw
write.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# AeroCTF 2021 - Horcrux\n",
"\n",
"I didn't participate in the [AeroCTF](https://ctftime.org/event/1224) but looked at the challenges afterwards. Please see nice and creative solutions by [rkm0959](https://rkm0959.tistory.com/211) and [Mystiz](https://mystiz.hk/posts/2021-02-28-aeroctf/). Here I will describe an alternativ solution to the Horcrux challenge.\n",
"The first part of my solution is simpler by using resultants.\n",
"\n",
"However, I realized that I overcomplicated the second part a lot. I keep this writeup to keep the techniques which might be useful in other scenarios."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here is the code:\n",
"\n",
"```py\n",
"#!/usr/bin/env python3.8\n",
" \n",
"from os import urandom\n",
"from gmpy2 import next_prime\n",
"from random import randrange, getrandbits\n",
"from Crypto.Cipher import AES\n",
"from fastecdsa.curve import Curve\n",
" \n",
" \n",
"def bytes_to_long(data):\n",
" return int.from_bytes(data, 'big')\n",
" \n",
" \n",
"def generate_random_point(p):\n",
" while True:\n",
" a, x, y = (randrange(0, p) for _ in range(3))\n",
" b = (pow(y, 2, p) - pow(x, 3, p) - a * x) % p\n",
" \n",
" if (4 * pow(a, 3, p) + 27 * pow(b, 2, p)) % p != 0:\n",
" break\n",
" \n",
" return Curve(None, p, a, b, None, x, y).G\n",
" \n",
" \n",
"class DarkWizard:\n",
" def __init__(self, age):\n",
" self.power = int(next_prime(getrandbits(age)))\n",
" self.magic = generate_random_point(self.power)\n",
" self.soul = randrange(0, self.power)\n",
" \n",
" def create_horcrux(self, location, weakness):\n",
" # committing a murder\n",
" murder = self.cast_spell(b'AVADA KEDAVRA')\n",
" \n",
" # splitting the soul in half\n",
" self.soul = self.soul * pow(2, -1, self.power) % self.power\n",
" \n",
" # making a horcrux\n",
" horcrux = (self.soul + murder) * self.magic\n",
" \n",
" # nobody should know location and weakness of the horcrux\n",
" horcrux.x ^= location\n",
" horcrux.y ^= weakness\n",
" \n",
" return horcrux\n",
" \n",
" def cast_spell(self, spell_name):\n",
" spell = bytes_to_long(spell_name)\n",
" \n",
" return spell %~ spell\n",
" \n",
" \n",
"def encrypt(key, plaintext):\n",
" cipher = AES.new(key=key, mode=AES.MODE_ECB)\n",
" padding = b'\\x00' * (AES.block_size - len(plaintext) % AES.block_size)\n",
" \n",
" return cipher.encrypt(plaintext + padding)\n",
" \n",
" \n",
"def main():\n",
" wizard_age = 3000\n",
" horcruxes_count = 2\n",
" \n",
" wizard = DarkWizard(wizard_age)\n",
" print(f'Wizard\\'s power:\\n{hex(wizard.power)}\\n')\n",
" print(f'Wizard\\'s magic:\\n{wizard.magic}\\n')\n",
" \n",
" key = urandom(AES.key_size[0])\n",
" horcrux_length = len(key) // horcruxes_count\n",
" \n",
" for i in range(horcruxes_count):\n",
" key_part = key[i * horcrux_length:(i + 1) * horcrux_length]\n",
" \n",
" horcrux_location = bytes_to_long(key_part[:horcrux_length // 2])\n",
" horcrux_weakness = bytes_to_long(key_part[horcrux_length // 2:])\n",
" \n",
" horcrux = wizard.create_horcrux(horcrux_location, horcrux_weakness)\n",
" print(f'Horcrux #{i + 1}:\\n{horcrux}\\n')\n",
" \n",
" with open('flag.txt', 'rb') as file:\n",
" flag = file.read().strip()\n",
" \n",
" ciphertext = encrypt(key, flag)\n",
" print(f'Ciphertext:\\n{ciphertext.hex()}')\n",
" \n",
" \n",
"if __name__ == '__main__':\n",
" main()\n",
"```\n",
"\n",
"Data:\n",
"```\n",
"Wizard's power:\n",
"0x27266a1284b761f793a529b9664693a6b1db36864a8664898d98d8010ec51afffaef2d1c79ab2078c1e0b289a1719d34b0a081ca325ba2b367017ee8e0824aaa9488409e76e923d0f0fc917ddfc1b0534e93a74246405dadfd1683f0dc31682eed0fa6b95fc235c845e16d2ef40463b7e746668dad82981fc4e05933aca410c65b36f89738f7d97502f6626c38f595338f3864638d8613fb74c16b63f3969a49ebd103ef354ed756c3cd5e67f1d2dbe5acdbc088bd6c1d503acef4ec59e4a09efac4729ca796ad25217fe74e7a0c7ef5a3e1fcd9eb9288fb89e842ef0b16642f7e84e27df4bcb623726e2c44ef46be07f9b5a5f92fe2c77d0de79fa6d46193b064207125d8935c2ff04f63e2f858e98d2518077dc58e13307f01d65ae953efd70980f3aeed320b7a6b66eb0c578dc3f05d426f412c4e3c7a9bcc68f27fe236fde41400371a39f53828824f5de3d5902cd3e7dcaee58b89c1a234188e391d412e7bc598d4f10b2bcb26aab7cd09194e80be046022ee8471\n",
"\n",
"Wizard's magic:\n",
"X: 0x4f69c16e493693a9342b7b9bb0ae42d0e7425996151c631a5620ad4d7ed372d285f04df82975a379080af08322fd927cf8ea9702f4533b5981351dd12358ca61c6e34af3f902b13d2981cae7cd2416e910bfe2c90f3b64c02bf933b1d11ff8ee384f5b507d9a0b1be38b15e7db3ba700ed32122a0163ec66530911fe142e098187771f5a248627a1709800069d402c1a61a17bd053ff6541f981898df6670420b0f3ea6ebd6d01d24f6fe9e3091a7c36df0c1ad7596e8ae090c54528385422911ff8e1dc201ab56844bc92acabc495c442104de5c34a5fe6661b7213500f4ccef6e76b94c34d60772fcf0c1250e66812d85efcda4b323250f740d0d57d40697fedae0bdbaceb0582cd7c82a27610e7f9fba5ac8f84e006d034dcf481f2dc9338acabd51c28afc1b4fc1d0cd7c1cd5ad21109e8708e9458e5301868c68920ab1aefb1e9184383002e6c893f1793443f8388f3f1b6e1f4ecaecb4cf000f57f677156efdacb20d60a35b8337ee416957aadffdc889dce487\n",
"Y: 0x2393c955e5f44ab3ac052dafd83554222728393b8fd20630f3c4f122d8c86d872a7b692b3782f12a6e57352c46328f85fad2d73eaccfcbf7beb47f97da2148c4f3fc7d6751bf66569c97a64f732e7cc71767ba11b1419732035c0285ff6973fba230a3d315fba7820855208e07e6fc5bc4b2cc3868aacde3b8e9b2075bfe861b2ebccd9b6c836d85dc319290263961344d348fe8faa0aa3ebca76fe514a7b7ba313a8200727b22a8714f8bba9e5ec2c549e5bfb5857c050d1ff0471d4b01426c2ee583a7d4b6c30df5ad2d9a6902f574416f8d55ed192b29d521e5d23a54e5062400b539468dca9aa3dc558feac63c88fc696d42434ad9a83551e6860aeb6a4d84ca80713387fa8c56a1e473a82af63ec03a71202aba0ae46fb9a97132f4c92d332327e2c11b79008586b22d92d60c3155e88b5e1f9c193b363ca28f0990400afb6e8148458708b89c6023c0d5ebb746bcd754fe37a84ee4dea6baa273b2ef31a864e9586f01bae855cc0d6f6055b2546b2a918664bdb6\n",
"(On curve <None>)\n",
"\n",
"Horcrux #1:\n",
"X: 0x2700ff7abe81679c770d3171c993c55da4a47cda3360e33d2b763e65517f307a39d401a256ee0634f3f1c6c244aad34422dccfe9ebd1803339972095eb2b0a57c82ee0db9ba94365cfb5270c4924c5c1ec00db2aff529aa923b113d2ca8ad6a6774fb7c655cd101ea63bc5a6ea0261f8da82d455219c7584d7de0757b2fda627c4684d3bac8f899c24178c7e0ecef6c226892b86043d3853cdb777889ce2901d8496bf0232dd000208eb2ce77e953c478551b1112ebf4b02f0086726210a50dc20ac08eb15d846084f9324b4f1f5ec73e3ef7e4a5207e04ebb866f731201e5f626084d1b61c158cfd0fdbaae8b8dd23ba599689c74a790933a3e77daa1c95fbde63b74381aff2b98f41cfebb7f1b220a4f2e8c3361734d7bd6648c720efc0a5f978917d8b84b4764e416762884f00104981e62d876d460bd8c1095cd755d8f31c5377e5ef935da77ff82e823b49d817a1f91bd4d155306173eb07efa4567d362e1cddbf0483873d5efc9286c36a58e5b3d995f3d01ca60\n",
"Y: 0x1bf9a696ef976644dd903fb148892044fe65dd16bf12966a6b6e43be4b3b52aaa348a76ed5a53bbb400a366c59c96cf88a9c6a713273a722c0c8cd6f42b7c6f5e1911d2d323780bce65be80eef4d375dd3425a9ff832e4166765c7687aaf3c6f3c1ae7c561c46c49f0075bb68d48b95be5fd2c94996a42ba255eb638ae5ce449064cc81831f2239dbb93f4944693ee42a507dc2878988928dc9ed5bb5cb3b3eba9ac414b4171e505d285edaf02d13c0748e47b17a498cb0c15883977a11cde98995a022999a555fb3f1a3b9226dc4122f3db6c86036b1b0e6ada10b23b8c89ddb590f2186191c0f1148a04a8e35c905d4053943554c58e8f0e2ccac42c2307532e2b8f55b74fccb8ab24a977c557d10bd7c8621bef3e7f326d00c3ff28a52ee85ec61bb8aef14f67ac80da5885a93f2840a5e44d9800b0352163667ba851bb15c4083955e1fba5cd9d6e7bf103a2bbb0fbc868136cf2871815762514c691e6352af18324d1ccdc21da3e1c4c6aa771aa9fccf343ad64b8\n",
"(On curve <None>)\n",
"\n",
"Horcrux #2:\n",
"X: 0xa439486ae1dbd96ca0796947609757b9dc068d8ed8287f98261c0c77e0940d29e25d27e16b97bc6983be505b8295886a5e880664ecb2d9161036f5beb1dbdac08da0cc2797d574e0feac67bbcb43275ab9e9d936aa17fd9a0a13a2f95e111b5e0893c4d4c3afae3bfa4a60fc5d0673215dd876b8bc960fc765401135dc708562cbeb572fcefaef1fef51782f6e0b495c0799cf89a9f47ffec11b0e780fb41e80d75681f7c9dd5fbf5e93e1dcda8091ca6a84de5b82b3abc9194913119e429781c12c11ebc6b6e80c01683344319879dec8fe59dd2f9c5b7b6e5e211153ae3b5fd161edae59777f3e76ecdeaef518495e512119451c6a97a8f471c4349ba7df8c3e9c1ba67f7a4fef57551d58b8c87607dc830c8074eec50841a1e365be90b528e4f39b8e19e7617191ac5118bb1abc44739d65384d915cb72e226122965ebae1581f55ecb12e523b0e904b3c0a1b26cf506ca030a68fe40d34c0912272277cd0d605ab057dbb5423cca28629661ad163232e766e80949\n",
"Y: 0x29cfc760529c48d68bc086a5b4403f1d4446db04abe243c99baf659b5e67cd6cdac9a658f273f4c682b9e13dda72aaa1ede42c69c98640f2fc58eabeef143a65334e4a236a6e72a157d92ab1a541c9bcf7d953b386a40d68880312ed1e900f6ba481bf134515f5a4c245a0d924db0e5105fc44fae71fc991df85219403ba5d48f68d5d91151f8411b4cbb6971bd63030b523989fa7ec94c14136ac712d4e91eca4c930d79caab7c328043c762917c4b3f868ce037cae9f19a579272c6b13ca8c19d349f5777bf6ac9c078d8472c92582daf96b30d4f7b8fdc004a36b792c133e2b6511956480892636ea91a3361afd8a3afbe3a5bf889feb5a5dc143f5a917347591634218066f2f71b36afd5257f6637152ac9a0965daa881ddc86ca8a8545b255cbb14e7738297a55c7428d9a0e79dee37f801fc1d49d205be809e0cd1b8a1b9d1d5b1b1a9ae98e7c564718cb17d10a3dd01c2914d7bb96c45a4fc942c2ed628354882464407c3208938282471aa2b8016e46c998e4\n",
"(On curve <None>)\n",
"\n",
"Ciphertext:\n",
"b6094505efd8e2824e8cc8698e5e68e3b2c306a2c8179fbefbfb7d2fc1a0cfb921a89f94dde88b04e655ad87d15efcc7466af652d6a330e92babceca94be63b126702153ad83d24baf7d8848bb71202771a2d80870fbd17462a715906dfc63bc\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"What we have reduces to equations of 3 points on an unknown elliptic curve:\n",
"$$\n",
"y_0^2 = x_0^3 + ax_0+ b,\n",
"$$\n",
"$$\n",
"(y_1\\oplus\\beta_1)^2 = (x_1\\oplus\\alpha_1)^3 + a(x_1\\oplus\\alpha_1)+ b,\n",
"$$\n",
"$$\n",
"(y_2\\oplus\\beta_2)^2 = (x_2\\oplus\\alpha_2)^3 + a(x_2\\oplus\\alpha_2)+ b,\n",
"$$\n",
"where $a,b \\in \\mathbb{F}_p$, $p$ is a 3000-bit known prime, $\\alpha_1,\\alpha_2,\\beta_1,\\beta_2$ are 32-bit random integers.\n",
"The idea here is that XORing is equivalent to adding or subtracting a 32-bit value in the field. So we will simply replace the XOR with addition in the field (recovering the original variables is trivial).\n",
"\n",
"Let's setup the data:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"execution": {
"iopub.execute_input": "2021-02-28T14:35:59.889432Z",
"iopub.status.busy": "2021-02-28T14:35:59.889050Z",
"iopub.status.idle": "2021-02-28T14:36:00.017729Z",
"shell.execute_reply": "2021-02-28T14:36:00.016669Z",
"shell.execute_reply.started": "2021-02-28T14:35:59.889387Z"
}
},
"outputs": [],
"source": [
"from sage.all import *\n",
"proof.arithmetic(False)\n",
"\n",
"p = 0x27266a1284b761f793a529b9664693a6b1db36864a8664898d98d8010ec51afffaef2d1c79ab2078c1e0b289a1719d34b0a081ca325ba2b367017ee8e0824aaa9488409e76e923d0f0fc917ddfc1b0534e93a74246405dadfd1683f0dc31682eed0fa6b95fc235c845e16d2ef40463b7e746668dad82981fc4e05933aca410c65b36f89738f7d97502f6626c38f595338f3864638d8613fb74c16b63f3969a49ebd103ef354ed756c3cd5e67f1d2dbe5acdbc088bd6c1d503acef4ec59e4a09efac4729ca796ad25217fe74e7a0c7ef5a3e1fcd9eb9288fb89e842ef0b16642f7e84e27df4bcb623726e2c44ef46be07f9b5a5f92fe2c77d0de79fa6d46193b064207125d8935c2ff04f63e2f858e98d2518077dc58e13307f01d65ae953efd70980f3aeed320b7a6b66eb0c578dc3f05d426f412c4e3c7a9bcc68f27fe236fde41400371a39f53828824f5de3d5902cd3e7dcaee58b89c1a234188e391d412e7bc598d4f10b2bcb26aab7cd09194e80be046022ee8471\n",
"F = GF(p)\n",
"\n",
"x0 = F(0x4f69c16e493693a9342b7b9bb0ae42d0e7425996151c631a5620ad4d7ed372d285f04df82975a379080af08322fd927cf8ea9702f4533b5981351dd12358ca61c6e34af3f902b13d2981cae7cd2416e910bfe2c90f3b64c02bf933b1d11ff8ee384f5b507d9a0b1be38b15e7db3ba700ed32122a0163ec66530911fe142e098187771f5a248627a1709800069d402c1a61a17bd053ff6541f981898df6670420b0f3ea6ebd6d01d24f6fe9e3091a7c36df0c1ad7596e8ae090c54528385422911ff8e1dc201ab56844bc92acabc495c442104de5c34a5fe6661b7213500f4ccef6e76b94c34d60772fcf0c1250e66812d85efcda4b323250f740d0d57d40697fedae0bdbaceb0582cd7c82a27610e7f9fba5ac8f84e006d034dcf481f2dc9338acabd51c28afc1b4fc1d0cd7c1cd5ad21109e8708e9458e5301868c68920ab1aefb1e9184383002e6c893f1793443f8388f3f1b6e1f4ecaecb4cf000f57f677156efdacb20d60a35b8337ee416957aadffdc889dce487)\n",
"y0 = F(0x2393c955e5f44ab3ac052dafd83554222728393b8fd20630f3c4f122d8c86d872a7b692b3782f12a6e57352c46328f85fad2d73eaccfcbf7beb47f97da2148c4f3fc7d6751bf66569c97a64f732e7cc71767ba11b1419732035c0285ff6973fba230a3d315fba7820855208e07e6fc5bc4b2cc3868aacde3b8e9b2075bfe861b2ebccd9b6c836d85dc319290263961344d348fe8faa0aa3ebca76fe514a7b7ba313a8200727b22a8714f8bba9e5ec2c549e5bfb5857c050d1ff0471d4b01426c2ee583a7d4b6c30df5ad2d9a6902f574416f8d55ed192b29d521e5d23a54e5062400b539468dca9aa3dc558feac63c88fc696d42434ad9a83551e6860aeb6a4d84ca80713387fa8c56a1e473a82af63ec03a71202aba0ae46fb9a97132f4c92d332327e2c11b79008586b22d92d60c3155e88b5e1f9c193b363ca28f0990400afb6e8148458708b89c6023c0d5ebb746bcd754fe37a84ee4dea6baa273b2ef31a864e9586f01bae855cc0d6f6055b2546b2a918664bdb6)\n",
"x1 = F(0x2700ff7abe81679c770d3171c993c55da4a47cda3360e33d2b763e65517f307a39d401a256ee0634f3f1c6c244aad34422dccfe9ebd1803339972095eb2b0a57c82ee0db9ba94365cfb5270c4924c5c1ec00db2aff529aa923b113d2ca8ad6a6774fb7c655cd101ea63bc5a6ea0261f8da82d455219c7584d7de0757b2fda627c4684d3bac8f899c24178c7e0ecef6c226892b86043d3853cdb777889ce2901d8496bf0232dd000208eb2ce77e953c478551b1112ebf4b02f0086726210a50dc20ac08eb15d846084f9324b4f1f5ec73e3ef7e4a5207e04ebb866f731201e5f626084d1b61c158cfd0fdbaae8b8dd23ba599689c74a790933a3e77daa1c95fbde63b74381aff2b98f41cfebb7f1b220a4f2e8c3361734d7bd6648c720efc0a5f978917d8b84b4764e416762884f00104981e62d876d460bd8c1095cd755d8f31c5377e5ef935da77ff82e823b49d817a1f91bd4d155306173eb07efa4567d362e1cddbf0483873d5efc9286c36a58e5b3d995f3d01ca60)\n",
"y1 = F(0x1bf9a696ef976644dd903fb148892044fe65dd16bf12966a6b6e43be4b3b52aaa348a76ed5a53bbb400a366c59c96cf88a9c6a713273a722c0c8cd6f42b7c6f5e1911d2d323780bce65be80eef4d375dd3425a9ff832e4166765c7687aaf3c6f3c1ae7c561c46c49f0075bb68d48b95be5fd2c94996a42ba255eb638ae5ce449064cc81831f2239dbb93f4944693ee42a507dc2878988928dc9ed5bb5cb3b3eba9ac414b4171e505d285edaf02d13c0748e47b17a498cb0c15883977a11cde98995a022999a555fb3f1a3b9226dc4122f3db6c86036b1b0e6ada10b23b8c89ddb590f2186191c0f1148a04a8e35c905d4053943554c58e8f0e2ccac42c2307532e2b8f55b74fccb8ab24a977c557d10bd7c8621bef3e7f326d00c3ff28a52ee85ec61bb8aef14f67ac80da5885a93f2840a5e44d9800b0352163667ba851bb15c4083955e1fba5cd9d6e7bf103a2bbb0fbc868136cf2871815762514c691e6352af18324d1ccdc21da3e1c4c6aa771aa9fccf343ad64b8)\n",
"x2 = F(0xa439486ae1dbd96ca0796947609757b9dc068d8ed8287f98261c0c77e0940d29e25d27e16b97bc6983be505b8295886a5e880664ecb2d9161036f5beb1dbdac08da0cc2797d574e0feac67bbcb43275ab9e9d936aa17fd9a0a13a2f95e111b5e0893c4d4c3afae3bfa4a60fc5d0673215dd876b8bc960fc765401135dc708562cbeb572fcefaef1fef51782f6e0b495c0799cf89a9f47ffec11b0e780fb41e80d75681f7c9dd5fbf5e93e1dcda8091ca6a84de5b82b3abc9194913119e429781c12c11ebc6b6e80c01683344319879dec8fe59dd2f9c5b7b6e5e211153ae3b5fd161edae59777f3e76ecdeaef518495e512119451c6a97a8f471c4349ba7df8c3e9c1ba67f7a4fef57551d58b8c87607dc830c8074eec50841a1e365be90b528e4f39b8e19e7617191ac5118bb1abc44739d65384d915cb72e226122965ebae1581f55ecb12e523b0e904b3c0a1b26cf506ca030a68fe40d34c0912272277cd0d605ab057dbb5423cca28629661ad163232e766e80949)\n",
"y2 = F(0x29cfc760529c48d68bc086a5b4403f1d4446db04abe243c99baf659b5e67cd6cdac9a658f273f4c682b9e13dda72aaa1ede42c69c98640f2fc58eabeef143a65334e4a236a6e72a157d92ab1a541c9bcf7d953b386a40d68880312ed1e900f6ba481bf134515f5a4c245a0d924db0e5105fc44fae71fc991df85219403ba5d48f68d5d91151f8411b4cbb6971bd63030b523989fa7ec94c14136ac712d4e91eca4c930d79caab7c328043c762917c4b3f868ce037cae9f19a579272c6b13ca8c19d349f5777bf6ac9c078d8472c92582daf96b30d4f7b8fdc004a36b792c133e2b6511956480892636ea91a3361afd8a3afbe3a5bf889feb5a5dc143f5a917347591634218066f2f71b36afd5257f6637152ac9a0965daa881ddc86ca8a8545b255cbb14e7738297a55c7428d9a0e79dee37f801fc1d49d205be809e0cd1b8a1b9d1d5b1b1a9ae98e7c564718cb17d10a3dd01c2914d7bb96c45a4fc942c2ed628354882464407c3208938282471aa2b8016e46c998e4)\n",
"\n",
"BITS = 32"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"execution": {
"iopub.execute_input": "2021-02-28T14:36:00.020566Z",
"iopub.status.busy": "2021-02-28T14:36:00.019823Z",
"iopub.status.idle": "2021-02-28T14:36:00.045672Z",
"shell.execute_reply": "2021-02-28T14:36:00.044274Z",
"shell.execute_reply.started": "2021-02-28T14:36:00.020509Z"
}
},
"outputs": [],
"source": [
"# SOLVING\n",
"R = PolynomialRing(F, names='aa1, aa2, bb1, bb2, a, b')\n",
"aa1, aa2, bb1, bb2, a, b = R.gens()\n",
"bounds = dict(aa1=2**BITS, aa2=2**BITS, bb1=2**BITS, bb2=2**BITS)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"execution": {
"iopub.execute_input": "2021-02-28T14:36:00.048978Z",
"iopub.status.busy": "2021-02-28T14:36:00.048300Z",
"iopub.status.idle": "2021-02-28T14:36:00.078147Z",
"shell.execute_reply": "2021-02-28T14:36:00.067755Z",
"shell.execute_reply.started": "2021-02-28T14:36:00.048921Z"
}
},
"outputs": [],
"source": [
"eq0 = x0**3 + a*x0 + b - y0**2\n",
"eq1 = (x1 + aa1)**3 + a*(x1 + aa1) + b - (y1 + bb1)**2\n",
"eq2 = (x2 + aa2)**3 + a*(x2 + aa2) + b - (y2 + bb2)**2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that the unknowns $a,b$ are large and so more annoying than the small $\\alpha_1,\\alpha_2,\\beta_1,\\beta_2$. Since we have 3 equations, we can get rid of $a, b$ and obtain a single equation:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"execution": {
"iopub.execute_input": "2021-02-28T14:36:00.082350Z",
"iopub.status.busy": "2021-02-28T14:36:00.081280Z",
"iopub.status.idle": "2021-02-28T14:36:00.124080Z",
"shell.execute_reply": "2021-02-28T14:36:00.122867Z",
"shell.execute_reply.started": "2021-02-28T14:36:00.082265Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[aa1^3*aa2, aa1*aa2^3, aa1^3, aa1^2*aa2, aa1*aa2^2, aa2^3, aa2*bb1^2, aa1*bb2^2, aa1^2, aa1*aa2, aa2^2, aa2*bb1, bb1^2, aa1*bb2, bb2^2, aa1, aa2, bb1, bb2, 1]\n"
]
},
{
"data": {
"text/plain": [
"20"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def resultant(p1, p2, var):\n",
" p1 = p1.change_ring(QQ)\n",
" p2 = p2.change_ring(QQ)\n",
" var = var.change_ring(QQ)\n",
" r = p1.resultant(p2, var)\n",
" return r.change_ring(F)\n",
"\n",
"poly = eq0\n",
"poly1 = resultant(poly, eq1, b)\n",
"poly2 = resultant(poly, eq2, b)\n",
"poly = resultant(poly1, poly2, a)\n",
"poly /= poly.coefficients()[0]\n",
"print(poly.monomials())\n",
"len(poly.monomials())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is a degree-4 equation over $\\mathbb{F}_p$ with 4 variables and very small solutions. Using full Coppersmith-like would be rather hard here.\n",
"For such extreme imbalance - max term example is $|\\alpha_1^3\\alpha_2| \\le 2^{32\\cdot 4}= 2^{128}$ versus $p \\approx 2^{3000}$ - we can try simpler techniques. Linearization is one of them. Indeed, we can consider this equation as linear equation with 19 variables of varying sizes. The total size of unknowns is:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"execution": {
"iopub.execute_input": "2021-02-28T14:36:00.126679Z",
"iopub.status.busy": "2021-02-28T14:36:00.125948Z",
"iopub.status.idle": "2021-02-28T14:36:00.173371Z",
"shell.execute_reply": "2021-02-28T14:36:00.171702Z",
"shell.execute_reply.started": "2021-02-28T14:36:00.126626Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"aa1^3*aa2 128.00\n",
"aa1*aa2^3 128.00\n",
"aa1^3 96.00\n",
"aa1^2*aa2 96.00\n",
"aa1*aa2^2 96.00\n",
"aa2^3 96.00\n",
"aa2*bb1^2 96.00\n",
"aa1*bb2^2 96.00\n",
"aa1^2 64.00\n",
"aa1*aa2 64.00\n",
"aa2^2 64.00\n",
"aa2*bb1 64.00\n",
"bb1^2 64.00\n",
"aa1*bb2 64.00\n",
"bb2^2 64.00\n",
"aa1 32.00\n",
"aa2 32.00\n",
"bb1 32.00\n",
"bb2 32.00\n",
"1 0.00\n"
]
},
{
"data": {
"text/plain": [
"(1408.00000000000, 'total')"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bits = 0\n",
"for mono in poly.monomials():\n",
" mono_bits = RR(log(mono.change_ring(ZZ).subs(**bounds), 2))\n",
" print(mono, \"%.2f\" % mono_bits )\n",
" bits += mono_bits\n",
"bits, \"total\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The rule of thumb for a modular linear equation is to compare the total bit-length of unknowns (1408) to the bit-length of the modulus (3000). We have a large margin!\n",
"Let's go LLL:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"execution": {
"iopub.execute_input": "2021-02-28T14:36:00.176149Z",
"iopub.status.busy": "2021-02-28T14:36:00.175353Z",
"iopub.status.idle": "2021-02-28T14:36:00.276285Z",
"shell.execute_reply": "2021-02-28T14:36:00.275305Z",
"shell.execute_reply.started": "2021-02-28T14:36:00.176088Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1 x x x x x x 1 x x x x x x x x x x x x\n",
"0 p 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
"0 0 p 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
"0 0 0 p 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
"0 0 0 0 p 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
"0 0 0 0 0 p 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
"0 0 0 0 0 0 p 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
"0 0 0 0 0 0 0 p 0 0 0 0 0 0 0 0 0 0 0 0\n",
"0 0 0 0 0 0 0 0 p 0 0 0 0 0 0 0 0 0 0 0\n",
"0 0 0 0 0 0 0 0 0 p 0 0 0 0 0 0 0 0 0 0\n",
"0 0 0 0 0 0 0 0 0 0 p 0 0 0 0 0 0 0 0 0\n",
"0 0 0 0 0 0 0 0 0 0 0 p 0 0 0 0 0 0 0 0\n",
"0 0 0 0 0 0 0 0 0 0 0 0 p 0 0 0 0 0 0 0\n",
"0 0 0 0 0 0 0 0 0 0 0 0 0 p 0 0 0 0 0 0\n",
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 p 0 0 0 0 0\n",
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 p 0 0 0 0\n",
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 p 0 0 0\n",
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 p 0 0\n",
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 p 0\n",
"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 p\n"
]
}
],
"source": [
"n = len(poly.monomials())\n",
"m = matrix(ZZ, n, n)\n",
"m[0] = vector(poly.coefficients())\n",
"m[1:,1:] = p * identity_matrix(n-1)\n",
"def prmat(m):\n",
" for row in m:\n",
" print(*[{0: \"0\", 1: \"1\", p: \"p\"}.get(v, \"x\") for v in row])\n",
"prmat(m)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"What we are doing is simply finding a multiple of our polynomial modulo $p$ (by a constant) such that its absolute value will be less than $p$ even with maximum values of the variables."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"execution": {
"iopub.execute_input": "2021-02-28T14:36:00.278118Z",
"iopub.status.busy": "2021-02-28T14:36:00.277716Z",
"iopub.status.idle": "2021-02-28T14:36:00.946203Z",
"shell.execute_reply": "2021-02-28T14:36:00.944997Z",
"shell.execute_reply.started": "2021-02-28T14:36:00.278070Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"20 x 20 dense matrix over Integer Ring"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# inspired by defund's code style https://github.com/defund/coppersmith\n",
"monos = vector(poly.change_ring(ZZ).monomials())\n",
"factors = [mono(**bounds) for mono in monos]\n",
"\n",
"[m.rescale_col(i, factor) for i, factor in enumerate(factors)]\n",
"m = m.LLL()\n",
"m = m.change_ring(QQ)\n",
"[m.rescale_col(i, QQ(1)/factor) for i, factor in enumerate(factors)]\n",
"m = m.change_ring(ZZ)\n",
"m"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"execution": {
"iopub.execute_input": "2021-02-28T14:36:00.948357Z",
"iopub.status.busy": "2021-02-28T14:36:00.947898Z",
"iopub.status.idle": "2021-02-28T14:36:01.115144Z",
"shell.execute_reply": "2021-02-28T14:36:01.113610Z",
"shell.execute_reply.started": "2021-02-28T14:36:00.948306Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"polynomial with max value 2835.33974382588 bits\n",
"polynomial with max value 2835.30655858310 bits\n",
"polynomial with max value 2835.39889680289 bits\n",
"polynomial with max value 2835.56026947599 bits\n",
"polynomial with max value 2835.27471060592 bits\n",
"polynomial with max value 2835.39148433409 bits\n",
"polynomial with max value 2835.40453160632 bits\n",
"polynomial with max value 2835.29853369271 bits\n",
"polynomial with max value 2835.67243387373 bits\n",
"polynomial with max value 2835.54980064626 bits\n",
"polynomial with max value 2835.39233844327 bits\n",
"polynomial with max value 2835.45721853969 bits\n",
"polynomial with max value 2835.60736646230 bits\n",
"polynomial with max value 2997.92022101675 bits\n",
"polynomial with max value 3061.29094246777 bits\n",
"polynomial with max value 3061.29094246777 bits\n",
"polynomial with max value 3091.96901437270 bits\n",
"polynomial with max value 3093.29094246767 bits\n",
"polynomial with max value 3093.29094246767 bits\n",
"polynomial with max value 3125.29094246767 bits\n",
"got 13 polynomials\n"
]
}
],
"source": [
"polys = []\n",
"for pol in m*monos:\n",
" maxval = sum(\n",
" (abs(int(coef)) * mono).change_ring(ZZ).subs(**bounds)\n",
" for coef, mono in pol\n",
" )\n",
" print(\"polynomial with max value\", RR(log(maxval, 2)), \"bits\")\n",
" if maxval < p:\n",
" polys.append(pol)\n",
"print(\"got\", len(polys), \"polynomials\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"13 good polynomials! That's more than enough. Note that we still have degree-4 equations, but over $\\mathbb{Z}$ instead of $\\mathbb{F}_p$. Out of a single equation! In fact, this trick can be also used if you start with an equation over integers: choose an appropriate-sized modulus and do the process to get more equations for free!\n",
"\n",
"It is left to solve the polynomial system over integers. One standard way is to use Gröbner basis/resultats, but it's performance is unpredictable and unreliable. A better way is to perform bitwise recovery (modulo 2, modulo 4, modulo 8, etc.). It is especially powerful when we have more polynomials then equations."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"execution": {
"iopub.execute_input": "2021-02-28T14:36:01.119754Z",
"iopub.status.busy": "2021-02-28T14:36:01.119275Z",
"iopub.status.idle": "2021-02-28T14:36:01.145378Z",
"shell.execute_reply": "2021-02-28T14:36:01.142946Z",
"shell.execute_reply.started": "2021-02-28T14:36:01.119712Z"
}
},
"outputs": [],
"source": [
"def recover(hs, vars, solbits, padbits=20): \n",
" nbits = solbits + padbits\n",
" from itertools import product\n",
" sols = {(0,) * len(vars)}\n",
" polys = [h.change_ring(Zmod(2**nbits)) for h in hs]\n",
" for i in range(nbits):\n",
" print(\"bit\", i, \"/\", nbits, \":\", len(sols), \"candidates\")\n",
" sols2 = set()\n",
" mod = 2**i\n",
" polys = [h.change_ring(Zmod(2*mod)) for h in hs]\n",
" for bits in product(range(2), repeat=len(vars)):\n",
" for sol in sols:\n",
" sol2 = tuple(ss + bit*mod for ss, bit in zip(sol, bits))\n",
" if any(poly(*sol2) for poly in polys):\n",
" continue\n",
" sols2.add(sol2)\n",
" sols = sols2\n",
" if not sols:\n",
" print(\"fail\", i)\n",
" return\n",
" print(\"sols?\", i, len(sols))\n",
" # TBD: automate adding pad bits to determine right sols by smallness\n",
" for sol in sols:\n",
" # fix signs\n",
" sol = [v if v < 2**(nbits-1) else (v-2**nbits) for v in sol]\n",
" # too large solution\n",
" if any(abs(v) >= 2**solbits for v in sol):\n",
" continue\n",
" # wrong solution\n",
" if any(poly(*sol) for poly in hs):\n",
" continue\n",
" yield sol"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In fact, we can see that 4 equations (against 4 variables) are sufficient here:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"execution": {
"iopub.execute_input": "2021-02-28T14:36:01.156071Z",
"iopub.status.busy": "2021-02-28T14:36:01.149696Z",
"iopub.status.idle": "2021-02-28T14:36:02.627219Z",
"shell.execute_reply": "2021-02-28T14:36:02.625492Z",
"shell.execute_reply.started": "2021-02-28T14:36:01.155897Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"bit 0 / 52 : 1 candidates\n",
"bit 1 / 52 : 2 candidates\n",
"bit 2 / 52 : 2 candidates\n",
"bit 3 / 52 : 2 candidates\n",
"bit 4 / 52 : 2 candidates\n",
"bit 5 / 52 : 2 candidates\n",
"bit 6 / 52 : 2 candidates\n",
"bit 7 / 52 : 2 candidates\n",
"bit 8 / 52 : 2 candidates\n",
"bit 9 / 52 : 2 candidates\n",
"bit 10 / 52 : 2 candidates\n",
"bit 11 / 52 : 2 candidates\n",
"bit 12 / 52 : 2 candidates\n",
"bit 13 / 52 : 2 candidates\n",
"bit 14 / 52 : 2 candidates\n",
"bit 15 / 52 : 2 candidates\n",
"bit 16 / 52 : 2 candidates\n",
"bit 17 / 52 : 2 candidates\n",
"bit 18 / 52 : 2 candidates\n",
"bit 19 / 52 : 2 candidates\n",
"bit 20 / 52 : 2 candidates\n",
"bit 21 / 52 : 2 candidates\n",
"bit 22 / 52 : 2 candidates\n",
"bit 23 / 52 : 2 candidates\n",
"bit 24 / 52 : 2 candidates\n",
"bit 25 / 52 : 2 candidates\n",
"bit 26 / 52 : 2 candidates\n",
"bit 27 / 52 : 2 candidates\n",
"bit 28 / 52 : 2 candidates\n",
"bit 29 / 52 : 2 candidates\n",
"bit 30 / 52 : 2 candidates\n",
"bit 31 / 52 : 2 candidates\n",
"bit 32 / 52 : 2 candidates\n",
"bit 33 / 52 : 2 candidates\n",
"bit 34 / 52 : 2 candidates\n",
"bit 35 / 52 : 2 candidates\n",
"bit 36 / 52 : 2 candidates\n",
"bit 37 / 52 : 2 candidates\n",
"bit 38 / 52 : 2 candidates\n",
"bit 39 / 52 : 2 candidates\n",
"bit 40 / 52 : 2 candidates\n",
"bit 41 / 52 : 2 candidates\n",
"bit 42 / 52 : 2 candidates\n",
"bit 43 / 52 : 2 candidates\n",
"bit 44 / 52 : 2 candidates\n",
"bit 45 / 52 : 2 candidates\n",
"bit 46 / 52 : 2 candidates\n",
"bit 47 / 52 : 2 candidates\n",
"bit 48 / 52 : 2 candidates\n",
"bit 49 / 52 : 2 candidates\n",
"bit 50 / 52 : 2 candidates\n",
"bit 51 / 52 : 2 candidates\n",
"sols? 51 2\n"
]
},
{
"data": {
"text/plain": [
"[1155305281, 1076744709, -62177711, -30259545]"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"R = PolynomialRing(ZZ, names='aa1, aa2, bb1, bb2')\n",
"polys = [R(pol) for pol in polys]\n",
"sols = list(recover(polys[:4], R.gens(), BITS))\n",
"sols[0]"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"execution": {
"iopub.execute_input": "2021-02-28T14:36:02.629402Z",
"iopub.status.busy": "2021-02-28T14:36:02.628964Z",
"iopub.status.idle": "2021-02-28T14:36:02.919791Z",
"shell.execute_reply": "2021-02-28T14:36:02.918688Z",
"shell.execute_reply.started": "2021-02-28T14:36:02.629348Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'Aero{\"Voldemort,\" said Riddle softly, \"is my past, present, and future, Harry Potter....\"}\\x00\\x00\\x00\\x00\\x00\\x00'"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from struct import pack\n",
"from Crypto.Cipher import AES\n",
"ct = bytes.fromhex(\"b6094505efd8e2824e8cc8698e5e68e3b2c306a2c8179fbefbfb7d2fc1a0cfb921a89f94dde88b04e655ad87d15efcc7466af652d6a330e92babceca94be63b126702153ad83d24baf7d8848bb71202771a2d80870fbd17462a715906dfc63bc\")\n",
"sol_aa1, sol_aa2, sol_bb1, sol_bb2 = sols[0]\n",
"parts = [\n",
" (int(x1)+int(sol_aa1))^int(x1),\n",
" (int(y1)+int(sol_bb1))^int(y1),\n",
" (int(x2)+int(sol_aa2))^int(x2),\n",
" (int(y2)+int(sol_bb2))^int(y2),\n",
"]\n",
"key = pack(\">4I\", *parts)\n",
"AES.new(key, mode=AES.MODE_ECB).decrypt(ct).decode()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Bonus:** this approach works for 64-bit secrets!"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"execution": {
"iopub.execute_input": "2021-02-28T14:36:02.921865Z",
"iopub.status.busy": "2021-02-28T14:36:02.921453Z"
}
},
"outputs": [],
"source": [
"sola = F(31337) / F(1000)\n",
"solb = F(31333337) / F(1000000)\n",
"\n",
"BITS = 64\n",
"solaa1 = randrange(2**BITS)\n",
"solbb1 = randrange(2**BITS)\n",
"solaa2 = randrange(2**BITS)\n",
"solbb2 = randrange(2**BITS)\n",
"\n",
"E = EllipticCurve(GF(p), [sola, solb])\n",
"x0, y0 = E.random_element().xy()\n",
"x1, y1 = E.random_element().xy()\n",
"x2, y2 = E.random_element().xy()\n",
"x1 -= solaa1\n",
"x2 -= solaa2\n",
"y1 -= solbb1\n",
"y2 -= solbb2\n",
"solaa1, solaa2, solbb1, solbb2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If you clone this notebook and run with SageMath kernel (python mode, todo so replace `sage.repl.ipython_kernel` with `ipykernel_launcher` in the kernel.json file), rerun everything from the `# SOLVING` cell up to recovery of aa1, aa2, bb1, bb2."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Bonus 2:** here is the simple Mystiz-style solution instead of the overcomplicated part."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"poly /= poly.constant_coefficient() # this is crucial\n",
"n = len(poly.monomials())\n",
"factors = [\n",
" int(mono.subs(**bounds))\n",
" for mono in poly.monomials() if mono != 1\n",
"]\n",
"fmat = diagonal_matrix(QQ, factors)\n",
"m = matrix(QQ, n, n)\n",
"m[0:n-1,:1] = matrix(ZZ, n-1, 1, poly.coefficients()[:-1])\n",
"m[n-1,0] = p\n",
"m[:n-1,1:] = ~fmat\n",
"prmat(m)\n",
"m = m.LLL()\n",
"m[:,1:] *= fmat\n",
"m = m.change_ring(ZZ)\n",
"\n",
"for row in m:\n",
" if row[0] == 1:\n",
" row = -row\n",
" if row[0] == -1:\n",
" sol = list(row[-4:])\n",
" if poly(*(sol + [0, 0])) == 0:\n",
" print(\"sol\", sol)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "SageMath python",
"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.8.5"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment