really_sick_aesthetic.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Securityfest CTF 2022"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## really_sick_æsthetic\n",
    "\n",
    "This is a mix between Franklin-Reiter and Håstad's attack. We are given\n",
    "\n",
    "$$\n",
    "\\left\\{\n",
    "\\begin{array}{rcl}\n",
    "x^3 &\\equiv& c_1 \\pmod{n_1}\\\\\n",
    "(ax + b)^3 &\\equiv& c_2 \\pmod{n_2}\\\\\n",
    "(cx + d)^3 &\\equiv& c_3 \\pmod{n_3}\n",
    "\\end{array}\n",
    "\\right.\n",
    "$$\n",
    "\n",
    "In Håstad's attack, the chinese-remainder theorem (CRT) is utilized to make $x^3$ smaller than the combined moduli, afterwhich a regular cube root (or more generally, $n$th root can be applied) as it is not subject to _wrapping around_.\n",
    "\n",
    "To solve this, one can define\n",
    "$$\n",
    "\\left.\n",
    "\\begin{array}{rcrcl}\n",
    "p_1(x) &=& x^3 - c_1 &\\equiv& 0 \\pmod{n_1}\\\\\n",
    "p_2(x) &=& (ax + b)^3 - c_2 &\\equiv& 0 \\pmod{n_2}\\\\\n",
    "p_3(x) &=& (cx + d)^3 - c_3 &\\equiv& 0 \\pmod{n_3}\n",
    "\\end{array}\n",
    "\\right.\n",
    "$$\n",
    "\n",
    "which can be combined into a polynomial $P(x)$ via CRT. Then a root-finding algorithm can be applied to find $x$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "n1, n2, n3 = 1401319611347356773887154859254297488587748916167528411781955161070771235056492239930915055430725842906735678800721088435590827145380843922331596331217195998289782451691023636938672246577057750538399961569425132775422780215874173061239620286809361247476788799084351705535705191719741473638161177830819062913, 93929270671640676038272300621577590050388546365573376058848268755586443513273392470288465422034947305882115935273812814090585070611845743805708732148965001758685938419891262987151989750411904643337379571106949332912476594370786031126592832074202606178259666176275819642895388993805423801590346121886463154493, 16942255048162971761210283484837728649885892177575028340105590631533021846865838703837850496337964481215216748513001294835312645433010478899804925326573174869703026494395537885248285153728354458825455324651596388723156984568435202926704664556435326575519823264262426064534649720827701655074670423046369428487\n",
    "a, b, c, d = 816707757334025955873551300291115957244929178359163189898836703794096446035376642681339350269646402403623381300867313940921411937931855866555460115147443198624007849492344102900953388236705014598317668063410070421658320251867938311242756954445599777691127340178194758168120083391846957297043258538971682656, 745711826496100756612627309746963018286384869064570930929420181315701128858481411996420808944706255787336734726114648250308181091719587312246849339268467320198235168275114019618372903191004050047010404038580467357659473336645389978388162270444112395481987515683470136265832310695565656316066649488457251542, 457113559991336310217047954994454259015470269139045253465880453115425882867168371751366860291496286988706829825972982124718895516194348207894013000632929345548822790821065845244320278540909961203024618547366059145546677151699090715138478903903713059476077714630963005563020709732576278095273999695170245879, 509199941399276795750649828994710794297214191656907620132065560140027602600782775401578085170024829709169889862887726457343903644876293675737086407127920668618215833854745693576935098817794913606783358855099827179163328860990718950946614721022541431359002875691363746468433769282630310194268851308235950929\n",
    "c1, c2, c3 = 1268196573919981524276949967801999986488529166073152640081117541596594438854836034605091034310174116029963325447867011142758840266458010604314712206281207486042576686131112279236592688360682514879866358817285786950878940051455988959409256539680442525853200118747541970284236278058810272505720905257745240883, 64208823083728071837064999419452205104115247850043866522128501646834783777966548620165452087334309723488367313973950057214802570403789761738914272552005923211386317615619928040804318066050436314100228196466534901781541660761105159754722013559344265999734902281442779083683166805632208178603445218079969320285, 8509227949500504626057408247321015695521219754070289890807066036172664538036554468734653260395519871677018843271256389298835987869898579912928540836245194980365843079281083074016559389213798536654944263567871852040147199080662496995097561192482940890984303786845410433468150776276754709196911737317257395314"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The CRT can be performed as follows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "from operator import mul\n",
    "load(\"https://raw.githubusercontent.com/defund/coppersmith/master/coppersmith.sage\")\n",
    "\n",
    "N = [n1, n2, n3]\n",
    "C = [c1, c2, c3]\n",
    "Q = [[1, 0], [a, b], [c, d]]\n",
    "\n",
    "n = reduce(mul, N)\n",
    "R = Integers(n)\n",
    "S.<x> = PolynomialRing(R, 1) ## requires this stupid fucking `1` or else it will be wrong datatype\n",
    "\n",
    "# guessed bits\n",
    "bits = 119*8\n",
    "delta = int.from_bytes(b'SECFEST{', byteorder='big') * 2^bits\n",
    "\n",
    "P = S(0)\n",
    "for m, q, c in zip(N, Q, C):\n",
    "    u = n // m\n",
    "    p = u\n",
    "    f = p * ((q[0]*(x + delta) + q[1])^3 - c)\n",
    "    P += f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now have $P(x)$. The message will be a small root in the new bigger modulus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 3\n"
     ]
    }
   ],
   "source": [
    "m, d = 10, 3\n",
    "print(m, d)\n",
    "\n",
    "roots = small_roots(P, (2^bits,), m=m, d=d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b\"SECFEST{0xlol}\\x8d\\xad/\\x8a\\x1eV/<\\x86\\x07\\xeeL\\xf1'\\xa1\\xe6\\x11#\\x84\\xda5p1z\\xc4\\xab\\xe9\\xfb\\xf9\\xc5\\xc3\\x03_\\x0c\\x86\\xef\\x16\\x17KP\\xa6\\x94[qZ\\x86\\x81{5\\x84CT\\xd5\\x81\\xc5\\xfd\\xe6\\x1c\\xb7\\xe8\\x8b\\x12\\xd8i\\xef\\xe4Z\\x19`.\\xc0\\xb6\\x83(\\xf1\\x85\\xc1[\\x9d\\x1e*\\xc6\\xfb\\xef\\xf6\\xf1\\xdd\\x10&G\\xae\\x19\\xc6\\xc8\\x9f\\x00\\xc8\\x05\\xc1\\xd0SJ9\\xach\\x02G9F\\xc5\\xce\\xf8W\"\n"
     ]
    }
   ],
   "source": [
    "print(b\"SECFEST{\" + int(roots[0][0]).to_bytes(119, byteorder='big'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "..and we have the flag."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.0",
   "language": "sage",
   "name": "sagemath"
  },
  "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}