HITCON CTF 2019 Quals - Randomly Select a Cat

randomly_select_cat.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# HITCON CTF 2019 Quals - Randomly Select a Cat\n",
    "\n",
    "This challenge was written in Ruby. It is relatively complicated and required several steps to solve.\n",
    "\n",
    "```ruby\n",
    "SIZE = 1024\n",
    "L = SIZE / 4 - 1\n",
    "CAFE = \"\\xCA\\xFE\\x12\\x04\"\n",
    "\n",
    "class String\n",
    "    def enhex\n",
    "        self.unpack('H*')[0]\n",
    "    end\n",
    "end\n",
    "\n",
    "def die(msg)\n",
    "    puts \"\\e[1;31mMEOW! #{msg}\\e[0m\"\n",
    "    exit 1\n",
    "end\n",
    "\n",
    "def gen_key\n",
    "    e = 3.to_bn\n",
    "    p = OpenSSL::BN::generate_prime(SIZE, false)\n",
    "    q = OpenSSL::BN::generate_prime(SIZE, false)\n",
    "    n = p * q\n",
    "    phi = (p - 1) * (q - 1)\n",
    "    d = e.mod_inverse(phi)\n",
    "    [e, d, n]\n",
    "end\n",
    "\n",
    "def H(m)\n",
    "    Digest::SHA256.hexdigest(m).to_i(16).to_bn\n",
    "end\n",
    "\n",
    "def unpad(s)\n",
    "    die 'meow zzz' unless s.size == L && s[0, 4] == CAFE\n",
    "    s[4..-1].gsub(/^\\x00*/, '')\n",
    "end\n",
    "\n",
    "def pad(s)\n",
    "    zero = L - 4 - s.size\n",
    "    die 'meooooooooooooooooow' unless zero >= 0\n",
    "    CAFE + \"\\x00\" * zero + s\n",
    "end\n",
    "\n",
    "def sign(m, d, n)\n",
    "    h = H(m)\n",
    "    nonce = SecureRandom.base64(6)\n",
    "    obj = {hash: h.to_i, nonce: nonce}\n",
    "    num = pad(Zlib.deflate(obj.to_json)).enhex.to_i(16).to_bn\n",
    "    die 'meow??' if num >= n\n",
    "    num.mod_exp(d, n)\n",
    "rescue\n",
    "    die 'meeeeeow'\n",
    "end\n",
    "\n",
    "def verify(m, sig, e, n)\n",
    "    num = sig.mod_exp(e, n)\n",
    "    obj = JSON[Zlib.inflate(unpad(num.to_s(2)))]\n",
    "    die 'meow T_T' if obj['hash'] != H(m)\n",
    "    die 'meowwww' unless obj['nonce'] && Base64::decode64(obj['nonce']).size == 6\n",
    "    true\n",
    "rescue\n",
    "    false\n",
    "end\n",
    "\n",
    "def decrypt(m, d, n)\n",
    "    die 'meow :(' unless m >= 0 && m < n\n",
    "    c = m.mod_exp(d, n).to_s(2)\n",
    "    unpad(c)\n",
    "rescue\n",
    "    nil\n",
    "end\n",
    "\n",
    "FLAG = IO.read('flag')\n",
    "\n",
    "# CATS ARE TRUE COLOR!!!\n",
    "CATS = Dir.glob('cat/cat*')\n",
    "\n",
    "e, d, n = gen_key\n",
    "loop do\n",
    "    puts 'meow?'\n",
    "    cmd = gets.strip\n",
    "    case cmd\n",
    "    when 'meow~'\n",
    "        puts 'meow~'\n",
    "        msg = gets.strip\n",
    "        die 'meow :O' if msg.size > 128\n",
    "        die 'meow?!' if msg.include?('meow')\n",
    "        puts sign(msg, d, n)\n",
    "    when 'meow!'\n",
    "        puts 'meow meow~'\n",
    "        admin_cmd = decrypt(gets.strip.to_i(16).to_bn, d, n)\n",
    "        die 'meow?' if admin_cmd.nil?\n",
    "        case admin_cmd\n",
    "        when /^meow(.)$/\n",
    "            # meow? meow!\n",
    "            meow = $1\n",
    "            puts 'meow meow meow?'\n",
    "            sig = gets.strip.to_i(16).to_bn\n",
    "            if verify(admin_cmd, sig, e, n)\n",
    "                system(meow)\n",
    "            else\n",
    "                die 'meow!?'\n",
    "            end\n",
    "        when 'meow'\n",
    "            puts IO.read(CATS.sample)\n",
    "        else\n",
    "            puts 'meow...!'\n",
    "        end\n",
    "    when 'meow.'\n",
    "        break\n",
    "    else\n",
    "        puts 'meow...?'\n",
    "    end\n",
    "end\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The RSA key is generated per each connection, with the public exponent $e=3$. We are given an access to the signing oracle and we can execute signed encrypted commands.\n",
    "The operations use the following padding: \n",
    "\n",
    "`\n",
    "CAFE1204 <00 bytes> <message/hash>\n",
    "`\n",
    "\n",
    "The number of null bytes is such that the whole blob is exactly 255 bytes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recovering $n$\n",
    "\n",
    "The first step is of course to recover $n$.\n",
    "The decryption oracle could be used as a padding oracle, but the header is 4 bytes which is too much for the challenge scale. Otherwise, we could try the Bleichenbacher attack.\n",
    "Therefore, we will only use the signing oracle.\n",
    "\n",
    "The signing oracle generates a JSON object with the hash of the given message and a random nonce. This JSON string is compressed using *zlib*, padded using the scheme described above, and signed by the RSA key. As a result, an output signature $s$ is such that\n",
    "\n",
    "$$\n",
    "s^3 \\equiv \\text{[\"0xCAFE1204\" <00 bytes pad> <compressed object>]} \\pmod{n}.\n",
    "$$\n",
    "\n",
    "Experimentally, we can observe the compressed object size: it is equal to 96 bytes. Denote the numeric value of the compressed object by $r$, and the value of \"CAFE1204\" padded to full size by $T$. We obtain\n",
    "\n",
    "$$\n",
    "s^3 - T = r + kn.\n",
    "$$\n",
    "\n",
    "We can consider $r$ as \"noise\". The lefthand side is known, therefore we obtain a \"noisy\" multiple of $n$. We can collect several such multiples and run approximate GCD algorithms, for example [\"Algorithms for Approximate Common Divisor Problem\" by Galbraith et al.](https://eprint.iacr.org/2016/215.pdf), basic attack from Section 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-13T11:48:03.369190Z",
     "start_time": "2019-10-13T11:48:02.591264Z"
    }
   },
   "outputs": [],
   "source": [
    "from __future__ import print_function, division\n",
    "from sage.all import *\n",
    "from Crypto.Util.number import *\n",
    "from sock import Sock\n",
    "class Stop(Exception): _render_traceback_ = lambda self: None\n",
    "import zlib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-13T11:48:03.369190Z",
     "start_time": "2019-10-13T11:48:02.591264Z"
    }
   },
   "outputs": [],
   "source": [
    "CAFE = \"\\xCA\\xFE\\x12\\x04\"\n",
    "PRIME_SIZE = 1024\n",
    "L = 255\n",
    "TOP = bytes_to_long(CAFE + \"\\x00\" * 155 + \"\\x00\" * 96)\n",
    "e = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-13T13:14:18.176163Z",
     "start_time": "2019-10-13T13:14:08.410485Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "asking sigs\n",
      "asking sigs ok\n",
      "trying n 24096146733400732651636474984784164777796836410462549627405269440664921231582529310564052304860586556128448503815412803737413884921291438744961546167491676298788701952035269601946027132702266737765516947678488330853372754438104678119690809258806217086885523922034974395247904679299152926582974578021074649377354885070168846946878010495272863759352780503535897698362521591109366795239213790933485428775707047382851758163559440708552039015861048263560941745055440966172925921322134733832017646132523837729318007839018707675842290474456835562520933079945971361735900119221219222808286494884401412297126465891494428086483\n",
      "n = 24096146733400732651636474984784164777796836410462549627405269440664921231582529310564052304860586556128448503815412803737413884921291438744961546167491676298788701952035269601946027132702266737765516947678488330853372754438104678119690809258806217086885523922034974395247904679299152926582974578021074649377354885070168846946878010495272863759352780503535897698362521591109366795239213790933485428775707047382851758163559440708552039015861048263560941745055440966172925921322134733832017646132523837729318007839018707675842290474456835562520933079945971361735900119221219222808286494884401412297126465891494428086483\n"
     ]
    }
   ],
   "source": [
    "f = Sock(\"127.1 3239\")\n",
    "def getsig(msg):\n",
    "    assert msg.strip() == msg\n",
    "    f.read_until(\"meow?\\n\")\n",
    "    f.send_line(\"meow~\")\n",
    "    f.read_until(\"meow~\\n\")\n",
    "    f.send_line(msg)\n",
    "    sig = int(f.read_line().strip())\n",
    "    return sig\n",
    "\n",
    "print(\"asking sigs\")\n",
    "sigs = [getsig(\"x\") for _ in range(10)]\n",
    "print(\"asking sigs ok\")\n",
    "\n",
    "while True:\n",
    "    # randomize by shuffling - enough\n",
    "    vs = [sig**3 - TOP for sig in sigs]\n",
    "    shuffle(vs)\n",
    "    t = len(sigs)-1\n",
    "    m = matrix(ZZ, len(sigs), len(sigs))\n",
    "    m[0,0] = scale = 256**96\n",
    "    for i in range(t):\n",
    "        m[0,1+i] = vs[1+i]\n",
    "        m[1+i,1+i] = vs[0]\n",
    "    ml = m.LLL()\n",
    "    n = vs[0] // (ml[0][0] // scale)\n",
    "    n = abs(n)\n",
    "\n",
    "    print(\"trying n\", n)\n",
    "    # sanity check for false positives\n",
    "    if all(n % p for p in primes(1000)):\n",
    "       break \n",
    "print(\"n =\", n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Forging a Malicious ~~Cat~~ Command\n",
    "After recovering $n$, we have to forge the signature of a malicious command. Puzzling at a first glance, we can only sign one-byte command. How useful it is?!\n",
    "\n",
    "Luckily, the author has left a hint:\n",
    "\n",
    "```ruby\n",
    "FLAG = IO.read('flag')\n",
    "CATS = Dir.glob('cat/cat*')\n",
    "```\n",
    "\n",
    "The folder contains a folder named `cat`! If we run the command `*`, and `cat` is the first file in the folder, then the shell will treat the `cat` as the command and all the other files as arguments! That is exactly what we need, since the file `flag` will be also displayed.\n",
    "\n",
    "As a result, we need to sign the string `\"meow*\"`. Note however that Ruby's regular expressions treat `$` as the end of line, not the end of string. Therefore, we can actually sign string of the form `\"meow*\\n anything\"`. This is useful as we would want to randomize the hash of the string."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Forging the signature is possible due to the classic cube root attack: the public exponent is 3, therefore we can sign numbers that are perfect cubes.\n",
    "We can choose arbitrarily the most 1/3 of the bits of the message and round the number to the nearest perfect cube. As a result, the 2/3 least significant bits will be \"randomized\".\n",
    "The rest of the solution consists in squeezing the compressed JSON object into the controlled area."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Newer versions of zlib in Python 3 have more options. The JSON object to be compressed contains only two keys: the integer value of the hash of the message, and the 8-byte nonce which must have the base64 alphabet. In order to improve compressibility, we randomize the hash value using the newline trick mentioned above, and we set the nonce to 8 times the most repeated digit of the hash. The `Z_RLE` strategy seems to fit well and produces the required short length rather quicky:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Small compression: seed 1465123123123 iteration 271694 message b'meow*\\n1465123394817'\n",
      "b'{\"nonce\":\"00000000\",\"hash\":8158553658004955363051773480484500330185828383964533608200155000381841430460}'\n",
      "\n",
      "msg = 'meow*\\n1465123394817'\n",
      "json = '{\"nonce\":\"00000000\",\"hash\":8158553658004955363051773480484500330185828383964533608200155000381841430460}'\n",
      "test = 'x\\x01-\\xc11\\x0e@\\x00\\x10\\x04\\xc0\\xbf\\\\\\xad\\xd8\\xb3\\xb7g\\xf9\\x8d\\x88DE\\xa1\\x14\\x7f\\xd7\\x98y\\xe2\\xbc\\xcem\\x8f%\\xf0\\x8b!\\x8e\\xf5>bq\\xca\\x12[\\x06j\\x96\\xd8\\x84r\\x9aXF\\xb9\\x04\\x90H\\xcb\\xa3i\\xce]\"\\x1b\\x1e\\x81\\x94\\x00\\xd0\\xe9\\xca\"\\xaa\\xf1~\\xf2\\xb3\\x17\\x04'\n",
      "\n",
      "78012dc1310e40001004c0bf5cadd8b3b767f98d884445a1147fd79879e2bcce6d8f25f08b218ef53e6271ca125b066a96d884729a5846b9049048cba369ce5d221b1e819400d0e9ca22aaf17ef2b31704\n",
      "78012dc1310e40001004c0bf5cadd8b3b767f98d884445a1147fd79879e2bcce6d8f25f08b218ef53e6271ca125b066a96d884729a5846b9049048cba369ce5d221b1e819400d0e9ca22aaf17ef2b31704\n",
      "Root ok!\n"
     ]
    }
   ],
   "source": [
    "#!/usr/bin/env python3\n",
    "import zlib, hashlib, sys\n",
    "if sys.version[0] != \"3\": raise Stop\n",
    "from collections import Counter\n",
    "from libnum import nroot\n",
    "from random import randint\n",
    "from Crypto.Util.number import *\n",
    "\n",
    "seed = 1465123123123\n",
    "for itr in range(10**9):\n",
    "    msg = \"meow*\\n%d\" % (seed + itr)\n",
    "    msg = msg.encode(\"ascii\")\n",
    "    d = int(hashlib.sha256(msg).hexdigest(), 16)\n",
    "    dig = Counter(str(d)).most_common()[0][0]\n",
    "    json = '{\"nonce\":\"%s\",\"hash\":%d}' % (str(dig)*8, d)\n",
    "    obj = zlib.compressobj(level=9, memLevel=9, strategy=zlib.Z_RLE)\n",
    "    test = obj.compress(json.encode(\"ascii\")) + obj.flush()\n",
    "    if len(test) <= 81:\n",
    "        print(\"Small compression: seed %d iteration %d message %r\" % (seed, itr, msg))\n",
    "        print(zlib.decompress(test))\n",
    "        print()\n",
    "        print(\"msg =\", repr(msg).lstrip(\"b\"))\n",
    "        print(\"json =\", repr(json).lstrip(\"b\"))\n",
    "        print(\"test =\", repr(test).lstrip(\"b\"))    \n",
    "        print()\n",
    "        header = b\"\\xCA\\xFE\\x12\\x04\" + test\n",
    "        hi = bytes_to_long(header.ljust(255, b\"\\xff\"))\n",
    "        rt = nroot(hi, 3)\n",
    "        print(test.hex())\n",
    "        s = long_to_bytes(rt**3)\n",
    "        print(s[4:4+len(test)].hex())\n",
    "        if s[4:4+len(test)] == test:\n",
    "            print(\"Root ok!\")\n",
    "            break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We get the required data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "msg = 'meow*\\n1465123394817'\n",
    "json = '{\"nonce\":\"00000000\",\"hash\":8158553658004955363051773480484500330185828383964533608200155000381841430460}'\n",
    "test = 'x\\x01-\\xc11\\x0e@\\x00\\x10\\x04\\xc0\\xbf\\\\\\xad\\xd8\\xb3\\xb7g\\xf9\\x8d\\x88DE\\xa1\\x14\\x7f\\xd7\\x98y\\xe2\\xbc\\xcem\\x8f%\\xf0\\x8b!\\x8e\\xf5>bq\\xca\\x12[\\x06j\\x96\\xd8\\x84r\\x9aXF\\xb9\\x04\\x90H\\xcb\\xa3i\\xce]\"\\x1b\\x1e\\x81\\x94\\x00\\xd0\\xe9\\xca\"\\xaa\\xf1~\\xf2\\xb3\\x17\\x04'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can send and execute the malicious `cat` command!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-13T13:14:49.588512Z",
     "start_time": "2019-10-13T13:14:18.180717Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pt: cafe1204000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006d656f772a0a31343635313233333934383137\n",
      "ct: 580849953a39ce65d83329b8924f8e3d75ceaca574fabe78f127836e37dec3088e801c70ff1bb14ee2b86e3e30a76faa53a6cf11e4ac0eedd460e150d8c9e02153aff48ae9b8e046b19eb60495e839d3d4ba84f3df2f49a3f733224b6dcfac520aea92a19070550219ba98e669589a6391086d2efbe9e1dfee102e211e9fe591b33754b0b89e212c2fcdd367cb630e15e1de36bb8dcffd323d8feeb1a9f6107c1f0370d404640285f58f287620f5361a2d35c374f8831d383edaa2eed033af6686edc56e21d5cd353230a4becf470b0e4f573516c40ae513c3917c27a2fd389a4038fde5ae0903627e5198173fec1486b6394d8afeec0fa4a0e83de7c38cab45\n",
      "signature: ecf2b87a407f0d103828e9f1c80a112aac7aeda34f3286fe7b4d5574a3a6ca84d648b482f2707643f9f8ac7d87edd681eaef4d5d90c5745888a6c486747f8ef1a46595c87184dc5769120e440fc18965ef63be74f8\n",
      "Output:\n",
      "#!/usr/bin/env ruby\n",
      "# encoding: ASCII-8BIT\n",
      "\n",
      "require 'base64'\n",
      "require 'digest'\n",
      "require 'json'\n",
      "require 'openssl'\n",
      "require 'securerandom'\n",
      "require 'zlib'\n",
      "\n",
      "Dir.chdir(File.dirname(__FILE__))\n",
      "\n",
      "SIZE = 1024\n",
      "L = SIZE / 4 - 1\n",
      "CAFE = \"\\xCA\\xFE\\x12\\x04\"\n",
      "\n",
      "class String\n",
      "  def enhex\n",
      "    self.unpack('H*')[0]\n",
      "  end\n",
      "end\n",
      "\n",
      "def gg(msg)\n",
      "  puts \"\\e[1;31mMEOW! #{msg}\\e[0m\"\n",
      "  exit 1\n",
      "end\n",
      "\n",
      "def gen_key\n",
      "  e = 3.to_bn\n",
      "  p = OpenSSL::BN::generate_prime(SIZE, false)\n",
      "  q = OpenSSL::BN::generate_prime(SIZE, false)\n",
      "  n = p * q\n",
      "  phi = (p - 1) * (q - 1)\n",
      "  d = e.mod_inverse(phi)\n",
      "  [e, d, n]\n",
      "end\n",
      "\n",
      "def H(m)\n",
      "  Digest::SHA256.hexdigest(m).to_i(16).to_bn\n",
      "end\n",
      "\n",
      "def unpad(s)\n",
      "  gg 'meow zzz' unless s.size == L && s[0, 4] == CAFE\n",
      "  s[4..-1].gsub(/^\\x00*/, '')\n",
      "end\n",
      "\n",
      "def pad(s)\n",
      "  zero = L - 4 - s.size\n",
      "  gg 'meooooooooooooooooow' unless zero >= 0\n",
      "  CAFE + \"\\x00\" * zero + s\n",
      "end\n",
      "\n",
      "def sign(m, d, n)\n",
      "  h = H(m)\n",
      "  nonce = SecureRandom.base64(6)\n",
      "  obj = {hash: h.to_i, nonce: nonce}\n",
      "  num = pad(Zlib.deflate(obj.to_json)).enhex.to_i(16).to_bn\n",
      "  gg 'meow??' if num >= n\n",
      "  num.mod_exp(d, n)\n",
      "rescue\n",
      "  gg 'meeeeeow'\n",
      "end\n",
      "\n",
      "def verify(m, sig, e, n)\n",
      "  num = sig.mod_exp(e, n)\n",
      "  obj = JSON[Zlib.inflate(unpad(num.to_s(2)))]\n",
      "  gg 'meow T_T' if obj['hash'] != H(m)\n",
      "  gg 'meowwww' unless obj['nonce'] && Base64::decode64(obj['nonce']).size == 6\n",
      "  true\n",
      "rescue\n",
      "  false\n",
      "end\n",
      "\n",
      "def decrypt(m, d, n)\n",
      "  gg 'meow :(' unless m >= 0 && m < n\n",
      "  c = m.mod_exp(d, n).to_s(2)\n",
      "  unpad(c)\n",
      "rescue\n",
      "  nil\n",
      "end\n",
      "\n",
      "FLAG = IO.read('flag')\n",
      "\n",
      "# CATS ARE TRUE COLOR!!!\n",
      "CATS = Dir.glob('cat/cat*')\n",
      "\n",
      "$stdout.sync = true\n",
      "\n",
      "def main\n",
      "  e, d, n = gen_key\n",
      "  loop do\n",
      "    puts 'meow?'\n",
      "    cmd = gets.strip\n",
      "    case cmd\n",
      "    when 'meow~'\n",
      "      puts 'meow~'\n",
      "      msg = gets.strip\n",
      "      gg 'meow :O' if msg.size > 128\n",
      "      gg 'meow?!' if msg.include?('meow')\n",
      "      puts sign(msg, d, n)\n",
      "    when 'meow!'\n",
      "      puts 'meow meow~'\n",
      "      admin_cmd = decrypt(gets.strip.to_i(16).to_bn, d, n)\n",
      "      gg 'meow?' if admin_cmd.nil?\n",
      "      case admin_cmd\n",
      "      when /^meow(.)$/\n",
      "        # meow? meow!\n",
      "        meow = $1\n",
      "        puts 'meow meow meow?'\n",
      "        sig = gets.strip.to_i(16).to_bn\n",
      "        if verify(admin_cmd, sig, e, n)\n",
      "          system(meow)\n",
      "        else\n",
      "          gg 'meow!?'\n",
      "        end\n",
      "      when 'meow'\n",
      "        puts IO.read(CATS.sample)\n",
      "      else\n",
      "        puts 'meow...!'\n",
      "      end\n",
      "    when 'meow.'\n",
      "      break\n",
      "    else\n",
      "      puts 'meow...?'\n",
      "    end\n",
      "  end\n",
      "end\n",
      "\n",
      "main\n",
      "hitcon{nya-nya-nyan-nyan-nya-nya-nyan-QH2-TGUlwu4}\n",
      "meow?\n",
      "\n"
     ]
    }
   ],
   "source": [
    "pt = CAFE + \"\\x00\" * (255 - 4 - len(msg)) + msg\n",
    "pt = bytes_to_long(pt)\n",
    "print(\"pt: %x\" % pt)\n",
    "# encrypt command\n",
    "ct = int(pow(int(pt), 3, int(n)))\n",
    "print(\"ct: %x\" % ct)\n",
    "\n",
    "# signature: cube root\n",
    "header = CAFE + test\n",
    "hi = bytes_to_long(header.ljust(255, \"\\xff\"))\n",
    "rt = int(hi**(QQ(1)/3))\n",
    "print(\"signature: %x\" % rt)\n",
    "\n",
    "f.read_until(\"meow?\\n\")\n",
    "f.send_line(\"meow!\")\n",
    "f.read_until(\"meow meow~\\n\")\n",
    "f.send_line(\"%x\" % ct)\n",
    "f.read_until(\"meow meow meow?\\n\")\n",
    "f.send_line(\"%x\" % rt)\n",
    "f.send_line(\"meow.\")\n",
    "print(\"Output:\")\n",
    "print(f.read_all())\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 8.8",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}