Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
HITCON CTF 2019 Quals - Lost Key Again (crypto)
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# HITCON CTF 2019 Quals - Lost Key Again (crypto)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The challenge has the following code:\n",
"\n",
"```py\n",
"def read_key():\n",
" key_file = open(\"key\")\n",
" n,e,d = map(int,key_file.readlines()[:3])\n",
" return n,e,d\n",
"\n",
"def calc(n,p,input):\n",
" data = \"X: \"+input\n",
" num = bytes_to_long(data)\n",
" res = pow(num,p,n)\n",
" return long_to_bytes(res).encode('hex')\n",
"\n",
"def read_flag():\n",
" flag = open('flag').read()\n",
" assert len(flag) >= 50\n",
" assert len(flag) <= 60\n",
" prefix = os.urandom(68)\n",
" return prefix+flag\n",
"\n",
"n,e,d = read_key()\n",
"flag = calc(n,e,read_flag())\n",
"print 'Here is the flag!', flag\n",
"for i in xrange(100):\n",
" m = raw_input('give me your X value: ')\n",
" try:\n",
" m = m.decode('hex')[:15]\n",
" print calc(n,e,m)\n",
" except:\n",
" print 'no'\n",
" exit(0)\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can encrypt messages of length up to 15 bytes, prepended by $T=$ \"X: \"=0x583a20.\n",
"The challenge only provides encryption oracle, therefore knowing $e$ and $n$ should allow to decrypt, i.e. they must be weak in some way. This already hints about some guessing, but first we need to recover $n$ and/or $e$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Typically, to recover the modulus, when $e$ is unknown, we use multiplicativity of RSA:\n",
"\n",
"$$ a^e \\times b^e \\equiv (a \\times b)^e \\pmod{n}.$$\n",
"\n",
"If we compute the values on the left and on the right, they will differ by a multiple of $n$. After collecting a few of them, we recover $n$ using the GCD.\n",
"\n",
"Here, due to restrictions (3-byte padding and small size), we can not find values $a,b$ such that $a,b,ab$ all have correct padding \"X: \".\n",
"\n",
"However, the key is to notice that we are not required to obtain **one** enc() on the righthand side: we can use any nontrivial relations. Let's find some!\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let $pad_t(x) := 256^tT + x$. We want to find relations of the form\n",
"\n",
"$$\n",
"pad_{t_1}(x_1)^{e_1} pad_{t_2}(x_2)^{e_2} \\ldots = pad_{t_1'}(x_1')^{e_1'} pad_{t_2'}(x_2')^{e_2'} \\ldots,\n",
"$$\n",
"\n",
"where all $t_i$ should be at most 15, all $x_i \\le 256^{t_i}$, and all $e_i$ must be small (since we will compute the expressions on both sides in integers). How can we find them? Let's map the problem to a linear one!\n",
"\n",
"One approach is to consider *logarithms*: taking logarithm of the equation leads to a linear equation. However, logarithms in real numbers have precision issues, which are hard to tackle with. Instead, we can make logarithms base each prime to produce a vector of integers. Equivalently, we obtain multiple linear equations. \n",
"\n",
"This approach is similar to the index calculus method and some sieving methods. First, we choose a factor base $B$ made of small primes up to a chosen limit and look for values that split completely in $B$ and have correct padding $pad_t$. Note that this is doable only because we can choose *small* numbers $pad_t(x)$, which have high chance to split in a small factor base."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"ExecuteTime": {
"end_time": "2019-10-12T13:43:30.558144Z",
"start_time": "2019-10-12T13:43:30.547188Z"
}
},
"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"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"ExecuteTime": {
"end_time": "2019-10-12T13:43:30.558144Z",
"start_time": "2019-10-12T13:43:30.547188Z"
}
},
"outputs": [],
"source": [
"T = 0x583a20 # \"X: \""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Experimentally, we can find that all 53 primes below 250 make a good factorbase. Our goal is to find $53 + \\epsilon$ messages that split in $B$, where $\\epsilon$ is the minimum kernel dimension that we would like. The larger the kernel is, the more relations will be there, and higher chance to find small ones."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"# factorbase\n",
"B = set(primes(250))\n",
"# number of required relations\n",
"# more extra -> larger kernel -> smaller relations!\n",
"N = len(B) + 50\n",
"\n",
"def facb(v):\n",
" res = []\n",
" for p in B:\n",
" e = 0\n",
" while v % p == 0:\n",
" e += 1\n",
" v //= p\n",
" res.append((p, e))\n",
" if v == 1: return res"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 1-th/103 B-smooth number: t= 1 x= 16 factors: 2^4 * 41 * 109 * 127 * 163\n",
" 2-th/103 B-smooth number: t= 1 x= 60 factors: 2^2 * 7^2 * 17 * 19 * 103 * 227\n",
" 3-th/103 B-smooth number: t= 1 x= 179 factors: 3^2 * 7 * 17 * 61 * 139 * 163\n",
" 4-th/103 B-smooth number: t= 2 x= 2128 factors: 2^4 * 11 * 31 * 41 * 67 * 131 * 193\n",
" 5-th/103 B-smooth number: t= 2 x= 3551 factors: 3^4 * 7^2 * 61 * 83 * 109 * 173\n",
" 6-th/103 B-smooth number: t= 2 x= 4096 factors: 2^12 * 41 * 109 * 127 * 163\n",
" 7-th/103 B-smooth number: t= 2 x= 5216 factors: 2^5 * 3^2 * 13^3 * 29 * 107 * 193\n",
" 8-th/103 B-smooth number: t= 2 x= 7738 factors: 2 * 11^2 * 13 * 47 * 103 * 139 * 179\n",
" 9-th/103 B-smooth number: t= 2 x= 8222 factors: 2 * 3^3 * 5^2 * 11^3 * 23 * 53 * 173\n",
" 10-th/103 B-smooth number: t= 2 x= 9522 factors: 2 * 5^3 * 7 * 71 * 113 * 137 * 197\n",
" 11-th/103 B-smooth number: t= 2 x= 14342 factors: 2 * 3^2 * 5 * 13^2 * 31 * 73 * 101 * 109\n",
" 12-th/103 B-smooth number: t= 2 x= 15059 factors: 3 * 7 * 53 * 67 * 113 * 193 * 233\n",
" 13-th/103 B-smooth number: t= 2 x= 15360 factors: 2^10 * 7^2 * 17 * 19 * 103 * 227\n",
" 14-th/103 B-smooth number: t= 2 x= 18496 factors: 2^6 * 7^2 * 11 * 31 * 37 * 61 * 157\n",
" 15-th/103 B-smooth number: t= 2 x= 19112 factors: 2^3 * 3^2 * 5 * 7 * 11^2 * 47 * 137 * 193\n",
" 16-th/103 B-smooth number: t= 2 x= 19882 factors: 2 * 5 * 7 * 11 * 17^2 * 19^2 * 53 * 89\n",
" 17-th/103 B-smooth number: t= 2 x= 23195 factors: 3 * 13 * 23^3 * 37 * 113 * 191\n",
" 18-th/103 B-smooth number: t= 2 x= 24212 factors: 2^2 * 3 * 5 * 43^2 * 113 * 167 * 181\n",
" 19-th/103 B-smooth number: t= 2 x= 26060 factors: 2^2 * 3^2 * 31 * 61 * 151 * 191 * 193\n",
" 20-th/103 B-smooth number: t= 2 x= 29687 factors: 3^3 * 5 * 31 * 47 * 53 * 163 * 223\n",
" 21-th/103 B-smooth number: t= 2 x= 29888 factors: 2^6 * 3 * 23 * 43 * 59 * 149 * 227\n",
" 22-th/103 B-smooth number: t= 2 x= 30256 factors: 2^4 * 7^2 * 19 * 23 * 73 * 109 * 139\n",
" 23-th/103 B-smooth number: t= 2 x= 31187 factors: 3 * 5 * 7^2 * 17 * 19 * 37 * 179 * 241\n",
" 24-th/103 B-smooth number: t= 2 x= 35766 factors: 2 * 11 * 13 * 19^2 * 97 * 157 * 241\n",
" 25-th/103 B-smooth number: t= 2 x= 36032 factors: 2^6 * 3^6 * 5 * 17 * 19 * 47 * 107\n",
" 26-th/103 B-smooth number: t= 2 x= 42800 factors: 2^4 * 3^2 * 7^2 * 29 * 31^2 * 41 * 47\n",
" 27-th/103 B-smooth number: t= 2 x= 44753 factors: 3^3 * 7 * 11 * 17 * 19 * 31 * 109 * 167\n",
" 28-th/103 B-smooth number: t= 2 x= 45824 factors: 2^8 * 3^2 * 7 * 17 * 61 * 139 * 163\n",
" 29-th/103 B-smooth number: t= 2 x= 46048 factors: 2^5 * 7 * 29^2 * 89 * 97 * 233\n",
" 30-th/103 B-smooth number: t= 2 x= 49637 factors: 3 * 5 * 11 * 13 * 71 * 97 * 113 * 227\n",
" 31-th/103 B-smooth number: t= 2 x= 50612 factors: 2^2 * 3^7 * 5 * 7 * 13 * 31 * 37 * 83\n",
" 32-th/103 B-smooth number: t= 2 x= 51536 factors: 2^4 * 3 * 7 * 17 * 19 * 79 * 193 * 229\n",
" 33-th/103 B-smooth number: t= 2 x= 51947 factors: 3 * 5^2 * 11 * 43^3 * 53 * 109\n",
" 34-th/103 B-smooth number: t= 2 x= 52106 factors: 2 * 3^2 * 19 * 23 * 47 * 53 * 83 * 233\n",
" 35-th/103 B-smooth number: t= 2 x= 55393 factors: 7^5 * 19 * 67 * 89 * 199\n",
" 36-th/103 B-smooth number: t= 2 x= 56039 factors: 3^4 * 11 * 19 * 23 * 79 * 97 * 127\n",
" 37-th/103 B-smooth number: t= 2 x= 60284 factors: 2^2 * 3 * 13 * 31 * 47 * 67 * 149 * 167\n",
" 38-th/103 B-smooth number: t= 2 x= 62519 factors: 3^5 * 7 * 101 * 113 * 131 * 149\n",
" 39-th/103 B-smooth number: t= 2 x= 62897 factors: 3^3 * 5^4 * 7 * 13 * 29 * 67 * 127\n",
" 40-th/103 B-smooth number: t= 2 x= 65144 factors: 2^3 * 3 * 7^2 * 53 * 137 * 199 * 223\n",
" 41-th/103 B-smooth number: t= 3 x= 3732 factors: 2^2 * 5^2 * 7^3 * 13 * 17 * 29 * 41 * 47 * 229\n",
" 42-th/103 B-smooth number: t= 3 x= 12062 factors: 2 * 3^5 * 5 * 7^2 * 17^2 * 23^2 * 73^2\n",
" 43-th/103 B-smooth number: t= 3 x= 47230 factors: 2 * 7 * 13 * 19 * 89 * 107 * 113 * 131 * 199\n",
" 44-th/103 B-smooth number: t= 3 x= 92327 factors: 3 * 5 * 11 * 13 * 29 * 37 * 47 * 61^2 * 241\n",
" 45-th/103 B-smooth number: t= 3 x= 118496 factors: 2^5 * 3^5 * 11^2 * 13^2 * 61 * 73 * 137\n",
" 46-th/103 B-smooth number: t= 3 x= 135227 factors: 3^2 * 5 * 7 * 11 * 13^2 * 17 * 23 * 31 * 79 * 173\n",
" 47-th/103 B-smooth number: t= 3 x= 148773 factors: 13 * 97 * 101 * 107 * 137 * 223 * 233\n",
" 48-th/103 B-smooth number: t= 3 x= 167357 factors: 3^2 * 5^2 * 7 * 17 * 61 * 67^2 * 101 * 131\n",
" 49-th/103 B-smooth number: t= 3 x= 226307 factors: 3^4 * 5^2 * 11^2 * 23^2 * 29 * 131 * 197\n",
" 50-th/103 B-smooth number: t= 3 x= 247850 factors: 2 * 3 * 7^2 * 31 * 47 * 71 * 103 * 173 * 179\n",
" 51-th/103 B-smooth number: t= 3 x= 253436 factors: 2^2 * 3 * 7^3 * 13 * 43 * 53 * 59 * 97 * 139\n",
" 52-th/103 B-smooth number: t= 3 x= 289264 factors: 2^4 * 13 * 17 * 53 * 101 * 107 * 211 * 227\n",
" 53-th/103 B-smooth number: t= 3 x= 296982 factors: 2 * 5^2 * 11 * 17 * 61^2 * 71 * 173 * 227\n",
" 54-th/103 B-smooth number: t= 3 x= 334844 factors: 2^2 * 3 * 11^2 * 23 * 53^3 * 109 * 179\n",
" 55-th/103 B-smooth number: t= 3 x= 348687 factors: 5 * 13 * 29 * 103^2 * 109 * 191 * 233\n",
" 56-th/103 B-smooth number: t= 3 x= 405532 factors: 2^2 * 5^2 * 7^2 * 19 * 37 * 41 * 73 * 97^2\n",
" 57-th/103 B-smooth number: t= 3 x= 500696 factors: 2^3 * 3 * 13 * 37^2 * 83 * 107^2 * 239\n",
" 58-th/103 B-smooth number: t= 3 x= 502308 factors: 2^2 * 11^3 * 13 * 17 * 47 * 61 * 149 * 193\n",
" 59-th/103 B-smooth number: t= 3 x= 529907 factors: 3 * 5^2 * 11 * 13 * 23 * 107 * 137 * 139 * 193\n",
" 60-th/103 B-smooth number: t= 3 x= 530856 factors: 2^3 * 13^2 * 19 * 61 * 71 * 89 * 97 * 101\n",
" 61-th/103 B-smooth number: t= 3 x= 544768 factors: 2^12 * 11 * 31 * 41 * 67 * 131 * 193\n",
" 62-th/103 B-smooth number: t= 3 x= 578000 factors: 2^4 * 3^2 * 23 * 31^2 * 43 * 67 * 71 * 149\n",
" 63-th/103 B-smooth number: t= 3 x= 630007 factors: 5^3 * 11 * 13 * 41 * 47 * 73 * 173 * 223\n",
" 64-th/103 B-smooth number: t= 3 x= 642184 factors: 2^3 * 11^2 * 17 * 37 * 41 * 71 * 229 * 239\n",
" 65-th/103 B-smooth number: t= 3 x= 662930 factors: 2 * 3 * 11 * 41 * 73 * 131 * 139 * 149 * 181\n",
" 66-th/103 B-smooth number: t= 3 x= 674328 factors: 2^3 * 29 * 41 * 47 * 61 * 139 * 157 * 163\n",
" 67-th/103 B-smooth number: t= 3 x= 674876 factors: 2^2 * 3^2 * 11 * 19 * 23 * 79 * 181 * 197 * 199\n",
" 68-th/103 B-smooth number: t= 3 x= 720337 factors: 5 * 89 * 137 * 139 * 211 * 227 * 239\n",
" 69-th/103 B-smooth number: t= 3 x= 736417 factors: 5 * 19 * 29 * 79 * 107 * 113 * 191 * 193\n",
" 70-th/103 B-smooth number: t= 3 x= 793144 factors: 2^3 * 13^2 * 17 * 37 * 47 * 97 * 131 * 191\n",
" 71-th/103 B-smooth number: t= 3 x= 841240 factors: 2^3 * 7^2 * 11 * 19 * 163 * 173 * 199 * 211\n",
" 72-th/103 B-smooth number: t= 3 x= 844166 factors: 2 * 3^2 * 7 * 11 * 19 * 31 * 97 * 107^3\n",
" 73-th/103 B-smooth number: t= 3 x= 909056 factors: 2^8 * 3^4 * 7^2 * 61 * 83 * 109 * 173\n",
" 74-th/103 B-smooth number: t= 3 x=1004870 factors: 2 * 3^2 * 29 * 31 * 41 * 53 * 89 * 139 * 223\n",
" 75-th/103 B-smooth number: t= 3 x=1033607 factors: 3^3 * 5^2 * 7 * 23 * 31 * 37 * 71 * 97 * 113\n",
" 76-th/103 B-smooth number: t= 3 x=1048576 factors: 2^20 * 41 * 109 * 127 * 163\n",
" 77-th/103 B-smooth number: t= 3 x=1081632 factors: 2^5 * 5^5 * 113 * 179 * 199 * 241\n",
" 78-th/103 B-smooth number: t= 3 x=1081991 factors: 3^6 * 7 * 13 * 17 * 41 * 61 * 163 * 211\n",
" 79-th/103 B-smooth number: t= 3 x=1108199 factors: 3^2 * 7 * 11 * 13 * 37 * 89 * 109 * 131 * 229\n",
" 80-th/103 B-smooth number: t= 3 x=1111880 factors: 2^3 * 3^8 * 29 * 41 * 73 * 107 * 199\n",
" 81-th/103 B-smooth number: t= 3 x=1190435 factors: 3 * 7 * 11^3 * 47^2 * 89 * 127 * 139\n",
" 82-th/103 B-smooth number: t= 3 x=1262921 factors: 3 * 157 * 163 * 167 * 193 * 197 * 199\n",
" 83-th/103 B-smooth number: t= 3 x=1280964 factors: 2^2 * 41 * 43 * 67 * 79 * 109 * 113 * 211\n",
" 84-th/103 B-smooth number: t= 3 x=1335296 factors: 2^13 * 3^2 * 13^3 * 29 * 107 * 193\n",
" 85-th/103 B-smooth number: t= 3 x=1341632 factors: 2^6 * 3^2 * 5^4 * 17 * 37 * 53 * 59 * 137\n",
" 86-th/103 B-smooth number: t= 3 x=1352359 factors: 7^2 * 17 * 19^2 * 83 * 109 * 181 * 197\n",
" 87-th/103 B-smooth number: t= 3 x=1366210 factors: 2 * 13 * 19 * 23 * 29 * 89 * 149^3\n",
" 88-th/103 B-smooth number: t= 3 x=1407564 factors: 2^2 * 11 * 23^2 * 29 * 53 * 71 * 181 * 211\n",
" 89-th/103 B-smooth number: t= 3 x=1412228 factors: 2^2 * 3^6 * 11^2 * 19 * 37 * 47 * 53 * 157\n",
" 90-th/103 B-smooth number: t= 3 x=1424320 factors: 2^6 * 13 * 17 * 71 * 73 * 83 * 107 * 149\n",
" 91-th/103 B-smooth number: t= 3 x=1431275 factors: 3 * 13 * 31 * 107 * 109 * 181 * 191 * 199\n",
" 92-th/103 B-smooth number: t= 3 x=1468832 factors: 2^5 * 3 * 5^2 * 7^2 * 13 * 53 * 67 * 107 * 167\n",
" 93-th/103 B-smooth number: t= 3 x=1518636 factors: 2^2 * 17 * 47 * 73 * 101 * 137 * 151 * 199\n",
" 94-th/103 B-smooth number: t= 3 x=1530920 factors: 2^3 * 3^3 * 13 * 79 * 113 * 157^3\n",
" 95-th/103 B-smooth number: t= 3 x=1629907 factors: 5^2 * 11^2 * 29 * 79 * 241^3\n",
" 96-th/103 B-smooth number: t= 3 x=1646382 factors: 2 * 5^3 * 47 * 53 * 67 * 89 * 151 * 173\n",
" 97-th/103 B-smooth number: t= 3 x=1684132 factors: 2^2 * 5^4 * 43 * 137 * 151 * 181 * 241\n",
" 98-th/103 B-smooth number: t= 3 x=1728280 factors: 2^3 * 7 * 11^2 * 17 * 127 * 149 * 191 * 233\n",
" 99-th/103 B-smooth number: t= 3 x=1771841 factors: 3^3 * 7 * 19^3 * 31 * 83 * 127 * 229\n",
"100-th/103 B-smooth number: t= 3 x=1817859 factors: 7^4 * 19 * 37 * 41^2 * 179 * 191\n",
"101-th/103 B-smooth number: t= 3 x=1837964 factors: 2^2 * 3^7 * 17^2 * 31 * 61 * 103 * 197\n",
"102-th/103 B-smooth number: t= 3 x=1897317 factors: 5 * 11^2 * 19 * 41 * 61 * 127 * 163^2\n",
"103-th/103 B-smooth number: t= 3 x=1942904 factors: 2^3 * 3^2 * 29 * 71 * 83 * 173 * 199 * 229\n",
"Done 103\n"
]
}
],
"source": [
"sources = []\n",
"vecs = []\n",
"for t in range(1, 100):\n",
" if len(sources) >= N: break\n",
" for x in range(0, 256**t-1):\n",
" if len(sources) >= N: break\n",
" v = 256**t * T + x\n",
" fac = facb(v)\n",
" if fac:\n",
" ps = {p for p, e in fac}\n",
" vecs.append([e for p, e in fac])\n",
" sources.append((t, x))\n",
" print(\"%3d-th/%d B-smooth number: t=%2d x=%7d factors: %r\" % (len(sources), N, t, x, factor(v)))\n",
"print(\"Done\", len(sources))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In a few seconds we have found 103 $B$-smooth messages! We are looking for *relations* between them, let's look at the kernel. Furthermore, we are interested in *small* relations, since we will compute the corresponding values in integers. Let's apply LLL to the kernel first:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ml = matrix(ZZ, vecs).left_kernel().matrix().LLL()\n",
"ml[0]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Wow, a very small relation indeed! What does it correspond to?"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"pad(t=2,x=2128)^-1 *\n",
"pad(t=2,x=3551)^1 *\n",
"pad(t=3,x=544768)^1 *\n",
"pad(t=3,x=909056)^-1 *\n",
"= 1\n"
]
}
],
"source": [
"p = 1\n",
"for i, c in enumerate(ml[0]):\n",
" if c:\n",
" t, x = sources[i]\n",
" p *= (256**t*T + x)**c\n",
" print(\"pad(t=%d,x=%d)^%d *\" % (t, x, c))\n",
"print(\"= %d\" % p) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ouch, fractions? We can not invert since we don't know $n$... But we don't need to! We simply move the negative power to the righthand side and get the relation that we want:\n",
"\n",
"$$\n",
"pad_2(3551)pad_3(544768) = pad_2(2128)pad_3(909056).\n",
"$$\n",
"\n",
"Let's now collect a few smallest relations:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"pad(t=2,x=3551)^1 * pad(t=3,x=544768)^1 = pad(t=2,x=2128)^1 * pad(t=3,x=909056)^1\n",
"'X: \\r\\xdf'^1 * 'X: \\x08P\\x00'^1 = 'X: \\x08P'^1 * 'X: \\r\\xdf\\x00'^1\n",
"\n",
"pad(t=2,x=4096)^1 * pad(t=3,x=544768)^1 = pad(t=2,x=2128)^1 * pad(t=3,x=1048576)^1\n",
"'X: \\x10\\x00'^1 * 'X: \\x08P\\x00'^1 = 'X: \\x08P'^1 * 'X: \\x10\\x00\\x00'^1\n",
"\n",
"pad(t=2,x=5216)^1 * pad(t=3,x=544768)^1 = pad(t=2,x=2128)^1 * pad(t=3,x=1335296)^1\n",
"'X: \\x14`'^1 * 'X: \\x08P\\x00'^1 = 'X: \\x08P'^1 * 'X: \\x14`\\x00'^1\n",
"\n",
"pad(t=2,x=2128)^1 * pad(t=2,x=15360)^1 = pad(t=1,x=60)^1 * pad(t=3,x=544768)^1\n",
"'X: \\x08P'^1 * 'X: <\\x00'^1 = 'X: <'^1 * 'X: \\x08P\\x00'^1\n",
"\n",
"pad(t=2,x=3551)^1 * pad(t=2,x=4096)^1 = pad(t=1,x=16)^1 * pad(t=3,x=909056)^1\n",
"'X: \\r\\xdf'^1 * 'X: \\x10\\x00'^1 = 'X: \\x10'^1 * 'X: \\r\\xdf\\x00'^1\n",
"\n",
"pad(t=2,x=3551)^1 * pad(t=2,x=45824)^1 = pad(t=1,x=179)^1 * pad(t=3,x=909056)^1\n",
"'X: \\r\\xdf'^1 * 'X: \\xb3\\x00'^1 = 'X: \\xb3'^1 * 'X: \\r\\xdf\\x00'^1\n",
"\n",
"pad(t=2,x=14342)^1 * pad(t=2,x=15360)^1 * pad(t=2,x=19112)^1 * pad(t=2,x=19882)^1 * pad(t=2,x=49637)^1 * pad(t=2,x=60284)^1 * pad(t=3,x=334844)^1 * pad(t=3,x=500696)^1 * pad(t=3,x=544768)^1 * pad(t=3,x=674328)^1 * pad(t=3,x=841240)^1 * pad(t=3,x=1081991)^1 * pad(t=3,x=1190435)^1 * pad(t=3,x=1728280)^1 = pad(t=2,x=7738)^1 * pad(t=2,x=8222)^1 * pad(t=2,x=15059)^1 * pad(t=2,x=42800)^1 * pad(t=2,x=44753)^1 * pad(t=2,x=55393)^1 * pad(t=3,x=289264)^1 * pad(t=3,x=502308)^1 * pad(t=3,x=720337)^1 * pad(t=3,x=793144)^1 * pad(t=3,x=1048576)^1 * pad(t=3,x=1412228)^1 * pad(t=3,x=1424320)^1 * pad(t=3,x=1897317)^1\n",
"'X: 8\\x06'^1 * 'X: <\\x00'^1 * 'X: J\\xa8'^1 * 'X: M\\xaa'^1 * 'X: \\xc1\\xe5'^1 * 'X: \\xeb|'^1 * 'X: \\x05\\x1b\\xfc'^1 * 'X: \\x07\\xa3\\xd8'^1 * 'X: \\x08P\\x00'^1 * 'X: \\nJ\\x18'^1 * 'X: \\x0c\\xd6\\x18'^1 * 'X: \\x10\\x82\\x87'^1 * 'X: \\x12*#'^1 * 'X: \\x1a_\\x18'^1 = 'X: \\x1e:'^1 * 'X: \\x1e'^1 * 'X: :\\xd3'^1 * 'X: \\xa70'^1 * 'X: \\xae\\xd1'^1 * 'X: \\xd8a'^1 * 'X: \\x04i\\xf0'^1 * 'X: \\x07\\xaa$'^1 * 'X: \\n\\xfd\\xd1'^1 * 'X: \\x0c\\x1a8'^1 * 'X: \\x10\\x00\\x00'^1 * 'X: \\x15\\x8c\\x84'^1 * 'X: \\x15\\xbb\\xc0'^1 * 'X: \\x1c\\xf3e'^1\n",
"\n"
]
}
],
"source": [
"rels = []\n",
"for row in ml[:7]:\n",
" rel = []\n",
" for i, c in enumerate(row):\n",
" t, x = sources[i]\n",
" v = 256**t*T + x\n",
" v = v**abs(c)\n",
" if c:\n",
" rel.append((c, t, x))\n",
" print(\n",
" \" * \".join(\"pad(t=%d,x=%d)^%d\" % (r[1], r[2], r[0]) for r in rel if r[0] > 0),\n",
" \"=\",\n",
" \" * \".join(\"pad(t=%d,x=%d)^%d\" % (r[1], r[2], -r[0]) for r in rel if r[0] < 0),\n",
" )\n",
" print(\n",
" \" * \".join(repr(long_to_bytes(256**r[1]*T+r[2])) + \"^%d\" % r[0] for r in rel if r[0] > 0),\n",
" \"=\",\n",
" \" * \".join(repr(long_to_bytes(256**r[1]*T+r[2])) + \"^%d\" % (-r[0]) for r in rel if r[0] < 0),\n",
" )\n",
" print()\n",
" rels.append(rel)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The first 6 relations are very short and should be enough to recover $n$! The others are of course still usable if needed: they have a reasonable amount of terms and small powers."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"cache = {}\n",
"def query(x, t):\n",
" if (x, t) not in cache:\n",
" f.read_until(b\"X value:\")\n",
" assert x < 256**t\n",
" assert x < 256**15\n",
" bx = long_to_bytes(x) if x else \"\"\n",
" bx = \"\\x00\" * (t - len(bx)) + bx\n",
" f.send_line(bx.encode(\"hex\"))\n",
" cache[x, t] = int(f.read_line().strip(), 16)\n",
" return cache[x, t]"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"rel [(-1, 2, 2128), (1, 2, 3551), (1, 3, 544768), (-1, 3, 909056)]\n",
"rel [(-1, 2, 2128), (1, 2, 4096), (1, 3, 544768), (-1, 3, 1048576)]\n",
"rel [(-1, 2, 2128), (1, 2, 5216), (1, 3, 544768), (-1, 3, 1335296)]\n",
"rel [(-1, 1, 60), (1, 2, 2128), (1, 2, 15360), (-1, 3, 544768)]\n",
"rel [(-1, 1, 16), (1, 2, 3551), (1, 2, 4096), (-1, 3, 909056)]\n",
"rel [(-1, 1, 179), (1, 2, 3551), (1, 2, 45824), (-1, 3, 909056)]\n",
"\n",
"n = 28152737628466294873353447700677616804377761540447615032304834412268931104665382061141878570495440888771518997616518312198719994551237036466480942443879131169765243306374805214525362072592889691405243268672638788064054189918713974963485194898322382615752287071631796323864338560758158133372985410715951157\n"
]
}
],
"source": [
"f = Sock(\"3.115.26.78 31337\")\n",
"f.read_until(\"flag! \")\n",
"encflag = bytes_to_long(f.read_line().strip().decode(\"hex\"))\n",
"n = 0\n",
"for rel in rels[:6]:\n",
" print(\"rel\", rel)\n",
" vl = vr = 1\n",
" for c, t, x in rel:\n",
" v = query(x, t)\n",
" if c < 0:\n",
" vr *= v**(-c)\n",
" else:\n",
" vl *= v**c\n",
" n = gcd(n, vl - vr)\n",
"f.close()\n",
"print()\n",
"print(\"n =\", n)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now comes the guessing part: we recovered $n$, so what? Even if we recover $e$ (may be it's small?) we only have the encryption oracle...\n",
"\n",
"After trying basic factorization attacks on $n$, we can find that Pollard's $p-1$ works: $p-1$ is smooth for at some prime factor of $n$:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2 * 269 * 1013 * 1997 * 2293 * 5477 * 6521 * 8521 * 9029 * 13729 * 15511 * 16333 * 18119 * 19963 * 24329 * 25589 * 26561 * 37889 * 38231 * 38557 * 38851 * 47881 * 49477 * 49547 * 49549 * 59009 * 63149 * 64067 * 66733 * 67807 * 70139 * 76543 * 78277 * 85621 * 85991 * 88289\n"
]
}
],
"source": [
"p = 531268630871904928125236420930762796930566248599562838123179520115291463168597060453850582450268863522872788705521479922595212649079603574353380342938159\n",
"q = 52991530070696473563320564293242344753975698734819856541454993888990555556689500359127445576561403828332510518908254263289997022658687697289264351266523\n",
"assert n == p * q\n",
"print(factor(p-1))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This allows us to recover the public exponent too, since we can apply Pohlig-Hellman's discrete logarithm method. Sage can do it for us transparently:"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"375469807216214245"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"f = Sock(\"3.115.26.78 31337\")\n",
"msg0 = T\n",
"enc0 = query(0, 0)\n",
"f.close()\n",
"F = GF(p)\n",
"e = F(enc0).log(F(msg0))\n",
"assert pow(msg0, e, n) == enc0\n",
"e"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'X: \\xb2J\\xb4\\x82\\xb6\\x042!\\x15\\xce$\\xf83\\xd6\\xd6nF?\\x1an\\xd6\\xd0\\xbc\\xed<O>\\xee\\x97*\"g\\x14\\xa6\\xf0k%\\xd6\\xfa\\xf4`\\x8a{\\x05\\x12\\x86\\xfe\\x1f!\\xb2\\xb3\\x16\\xbfa\\x04:^~\\x1bjc4\\xb2\\x04\\xeb\\xfe\\x9ayhitcon{@@@_5m00thneSS_CAN_give_y0u_everything_@@@}\\n'"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"d = inverse_mod(e, n - p - q + 1)\n",
"long_to_bytes(pow(encflag, d, n))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Aftermath\n",
"\n",
"After the CTF my colleague told me a very simple way to find $n$. In fact, it is basically the same as the 6 relations that I used, but I didn't realize their trivial structure, for example:\n",
"\n",
"```py\n",
"'X: \\r\\xdf'^1 * 'X: \\x08P\\x00'^1 = 'X: \\x08P'^1 * 'X: \\r\\xdf\\x00'^1\n",
"```\n",
"\n",
"Clearly, there are arbitrary two messages and their copies padded by a null bytes!\n",
"\n",
"Since we can append a null byte to any message, we obtain encryptions of $m$ and $256m$, and if we repeat for another message $m'$, we get:\n",
"\n",
"$$m^e \\times (256m')^e = (m')^e \\times (256m)^e.\n",
"$$\n",
"\n",
"Since we obtain reduced modulo $n$ encryptions, the products are likely to be separated by a nonzero multiple of $n$, and $n$ can thus be recovered using a couple of $gcd$.\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"
},
"latex_envs": {
"LaTeX_envs_menu_present": true,
"autoclose": false,
"autocomplete": true,
"bibliofile": "biblio.bib",
"cite_by": "apalike",
"current_citInitial": 1,
"eqLabelWithNumbers": true,
"eqNumInitial": 1,
"hotkeys": {
"equation": "Ctrl-E",
"itemize": "Ctrl-I"
},
"labels_anchors": false,
"latex_user_defs": false,
"report_style_numbering": false,
"user_envs_cfg": false
},
"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
}
@hellman

This comment has been minimized.

Copy link
Owner Author

@hellman hellman commented Oct 14, 2019

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