Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
HITCON CTF 2019 Quals - Very Simple Haskell (crypto)
{
"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
}
@hellman

This comment has been minimized.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment