HITCON CTF 2019 Quals - Very Simple Haskell (crypto)

very_simple_haskell.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# HITCON CTF 2019 Quals - Very Simple Haskell (crypto)\n",
    "\n",
    "The challenge is based on the following clean Haskell code:\n",
    "\n",
    "```haskell\n",
    "import Data.Char\n",
    "import System.IO\n",
    "\n",
    "n :: Integer\n",
    "n = 134896036104102133446208954973118530800743044711419303630456535295204304771800100892609593430702833309387082353959992161865438523195671760946142657809228938824313865760630832980160727407084204864544706387890655083179518455155520501821681606874346463698215916627632418223019328444607858743434475109717014763667\n",
    "\n",
    "k :: Int\n",
    "k = 131\n",
    "\n",
    "primes :: [Integer]\n",
    "primes = take k $ sieve (2 : [3, 5..])\n",
    "  where\n",
    "    sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]\n",
    "\n",
    "stringToInteger :: String -> Integer\n",
    "stringToInteger str = foldl (\\x y -> (toInteger $ ord y) + x*256) 0 str\n",
    "\n",
    "integerToString :: Integer -> String\n",
    "integerToString num = f num \"\"\n",
    "    where\n",
    "        f 0 str = str\n",
    "        f num str = f (div num 256) $ (:) (chr $ fromIntegral $ num `mod` 256) str\n",
    "\n",
    "numToBits :: Integer -> [Int]\n",
    "numToBits num = f num []\n",
    "    where \n",
    "        f 0 arr = arr\n",
    "        f x arr = f (div x 2) ((fromInteger $ x `mod` 2) : arr)\n",
    "\n",
    "extendBits :: Int -> [Int] -> [Int]\n",
    "extendBits blockLen arr\n",
    "    | len == 0 = arr\n",
    "    | len > 0 = (replicate (blockLen-len) 0) ++ arr\n",
    "    where len = (length arr) `mod` blockLen\n",
    "\n",
    "calc :: Integer -> [Int] -> Integer\n",
    "calc num [] = num\n",
    "calc num arr = calc result restArr\n",
    "    where\n",
    "        num2 = num*num `mod` n\n",
    "        (block, restArr) = splitAt k arr\n",
    "        zipped = zipWith (\\x y -> ((fromIntegral x)*y) `mod` n) block primes  \n",
    "        mul = product $ filter (/=0) zipped\n",
    "        result = num2*mul `mod` n\n",
    "\n",
    "magic :: String -> String\n",
    "magic input = result\n",
    "    where \n",
    "        num = stringToInteger input\n",
    "        bits = numToBits num\n",
    "        extended = reverse $ extendBits 8 bits\n",
    "        oriLen = length extended\n",
    "        extendedBits = extendBits k extended\n",
    "        oriLenBits = numToBits $ fromIntegral oriLen\n",
    "        extendedOriLenBits = extendBits k oriLenBits\n",
    "        finalBits = extendedOriLenBits ++ extendedBits\n",
    "        result = show $ calc 1 (reverse finalBits)\n",
    "\n",
    "main = do\n",
    "    flag <- readFile \"flag\"\n",
    "    putStrLn.show $ length flag\n",
    "    putStrLn $ magic (\"the flag is hitcon{\" ++ flag ++ \"}\") \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The challenge is rather straightforward. First, the flag is converted to a string of bits, padded to 8 and 131 bits, reversed, appended with length of padded string, etc.\n",
    "\n",
    "The final step is the $calc(num, arr)$ function. It splits the input string into 131-bit chunks, computes\n",
    "\n",
    "$$\n",
    "mul = p_1^{b_1} p_2^{b_2} \\cdots p_{131}^{b_{131}} \\mod{n},\n",
    "$$\n",
    "\n",
    "where $p_i$ is the $i$-th prime, $b_i$ is the $i$-th bit of the string. It updates $num$ with $num^2 \\times mul \\mod{n}$ and proceeds with the next blocks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a result, the final output is a product of primes raised to particular powers depending on bits of the input string and reduced modulo $n$. More precisely,\n",
    "the prime $p_i$ has power $4b_i + 2b_{i+131} + 3b_{i+262}$. After a close look, we can see that the only unknown part of the $calc$ input is formed by 6 bytes of the flag and is placed fully in the second block."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "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",
    "\n",
    "def s2b(s):\n",
    "    ret = []\n",
    "    for c in s:\n",
    "        ret.append(bin(ord(c))[2:].zfill(8))\n",
    "    return \"\".join(ret)\n",
    "\n",
    "def b2s(b):\n",
    "    ret = []\n",
    "    for pos in range(0, len(b), 8):\n",
    "        ret.append(chr(int(b[pos:pos + 8], 2)))\n",
    "    return \"\".join(ret)\n",
    "\n",
    "n = 134896036104102133446208954973118530800743044711419303630456535295204304771800100892609593430702833309387082353959992161865438523195671760946142657809228938824313865760630832980160727407084204864544706387890655083179518455155520501821681606874346463698215916627632418223019328444607858743434475109717014763667\n",
    "s = \"the flag is hitcon{abcdef}\"\n",
    "# simple bit transformations\n",
    "extended = map(int, s2b(s))\n",
    "extended[-7*8:-1*8] = [None] * 48\n",
    "extended = extended[::-1]\n",
    "extendedBits = [0] * (262 - len(extended)) + extended\n",
    "oriLen = 26 * 8\n",
    "oriLenBits = Integer(oriLen).bits()[::-1]\n",
    "extendedOriLenBits = [0] * (131 - len(oriLenBits)) + oriLenBits\n",
    "out = extendedOriLenBits + extendedBits\n",
    "\n",
    "s = out[::-1]\n",
    "v = 1\n",
    "prs = []\n",
    "prprod = 1\n",
    "for i in xrange(0, len(s), 131): \n",
    "    mul = 1\n",
    "    for bit, pr in zip(s[i:i+131], primes(1000)):\n",
    "        if bit is None:\n",
    "            prprod *= pr\n",
    "            prs.append(pr)\n",
    "        if bit == 1:\n",
    "            mul *= pr\n",
    "    v = v * v * mul % n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can easily cancel the other values and leave only the unknown prime powers. Note that we have squares of primes, and computing a square root modulo a composite is a hard problem. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "flagprod 3406218222930966554172275269328526576001581947668541896752967656582693660956578801\n",
      "factor 83^2 * 89^2 * 97^2 * 103^2 * 107^2 * 127^2 * 173^2 * 197^2 * 223^2 * 227^2 * 229^2 * 233^2 * 239^2 * 257^2 * 283^2 * 311^2 * 337^2 * 347^2\n"
     ]
    }
   ],
   "source": [
    "chal = 84329776255618646348016649734028295037597157542985867506958273359305624184282146866144159754298613694885173220275408231387000884549683819822991588176788392625802461171856762214917805903544785532328453620624644896107723229373581460638987146506975123149045044762903664396325969329482406959546962473688947985096\n",
    "diff = int(chal * inverse_mod(v, n)) % n\n",
    "print(\"flagprod\", diff)\n",
    "print(\"factor\", factor(diff))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Luckily, we don't have to solve it: the actual full product is not reduced, because it is small enough. It is easy to recover the flag now:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hitcon{v@!>A#}\n"
     ]
    }
   ],
   "source": [
    "bs = []\n",
    "for p in prs:\n",
    "    if diff % p**2:\n",
    "        bs.append(0)\n",
    "    else:\n",
    "        bs.append(1)\n",
    "bs = \"\".join(map(str, bs))\n",
    "print(\"hitcon{%s}\" % b2s(bs))"
   ]
  }
 ],
 "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}

https://nbviewer.jupyter.org/gist/hellman/ed290cb4a814cb884dcaa34d02950170