Skip to content

Instantly share code, notes, and snippets.

@hellman

hellman/1_chall.py Secret

Last active Jun 29, 2020
Embed
What would you like to do?
TCTF/0CTF 2020 Quals - emmm (crypto)
#!/usr/bin/python2
import random
from struct import pack,unpack
from flag import flag
P = 247359019496198933
C = 223805275076627807
M = 2**60
K0 = random.randint(1, P-1)
K1 = random.randint(1, P-1)
# not a bijection? can be adjusted but I'm lazy
def encrypt_block(x):
tmp = x * K0 % P
tmp = tmp * C % M
tmp = tmp * K1 % P
return tmp
for i in range(2**24):
pt = random.randint(1, P-1)
ct = encrypt_block(pt)
print pt, ct
pt = flag[5:-1]
assert flag.startswith('flag{') and flag.endswith('}') and len(pt)%8==0
fmt = '%dQ' % (len(pt)/8)
ct = pack(fmt, *map(encrypt_block, unpack(fmt, pt)))
print ct.encode('hex')
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 0CTF/TCTF 2020 Quals - emmm (crypto)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this challenge, we are given a simple block cipher (though not fully invertible), based on 3 modular multiplications."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"execution": {
"iopub.execute_input": "2020-06-29T13:34:47.753110Z",
"iopub.status.busy": "2020-06-29T13:34:47.751152Z",
"iopub.status.idle": "2020-06-29T13:34:47.779799Z",
"shell.execute_reply": "2020-06-29T13:34:47.776453Z",
"shell.execute_reply.started": "2020-06-29T13:34:47.752968Z"
}
},
"outputs": [],
"source": [
"# Sage mode\n",
"P = 247359019496198933 # 2**57.78\n",
"C = 223805275076627807 # 2**57.64\n",
"M = 2**60\n",
"K0 = random.randint(1, P-1)\n",
"K1 = random.randint(1, P-1)\n",
"\n",
"# not a bijection? can be adjusted but I'm lazy\n",
"def encrypt_block(x):\n",
" tmp = x * K0 % P\n",
" tmp = tmp * C % M\n",
" tmp = tmp * K1 % P\n",
" return tmp"
]
},
{
"cell_type": "markdown",
"metadata": {
"execution": {
"iopub.execute_input": "2020-06-29T12:21:50.379449Z",
"iopub.status.busy": "2020-06-29T12:21:50.378297Z",
"iopub.status.idle": "2020-06-29T12:21:50.391850Z",
"shell.execute_reply": "2020-06-29T12:21:50.389108Z",
"shell.execute_reply.started": "2020-06-29T12:21:50.379278Z"
}
},
"source": [
"We are also given $2^{24}$ random plaintext-ciphertext pairs and encrypted flag.\n",
"\n",
"Let's build linearized relation between a plaintext and the ciphertext, by introducing variables for modular reductions."
]
},
{
"cell_type": "markdown",
"metadata": {
"execution": {
"iopub.execute_input": "2020-06-29T12:21:50.379449Z",
"iopub.status.busy": "2020-06-29T12:21:50.378297Z",
"iopub.status.idle": "2020-06-29T12:21:50.391850Z",
"shell.execute_reply": "2020-06-29T12:21:50.389108Z",
"shell.execute_reply.started": "2020-06-29T12:21:50.379278Z"
}
},
"source": [
"Consider an encryption $(x, y)$.\n",
"Let \n",
"$$\n",
"\\begin{align}\n",
"t_1 &= \\lfloor K_0x / P \\rfloor < x, \\\\\n",
"t_2 &= \\lfloor (K_0x\\mod{P}) / M \\rfloor < PC/M, \\\\\n",
"t_3 &= \\lfloor K_1^{-1}y / P \\rfloor + \\epsilon < y + \\epsilon, \\\\\n",
"\\end{align}\n",
"$$\n",
"where $0 \\le \\epsilon \\le \\lfloor M / P \\rfloor = 4$ is such that $yK_1^{-1} -t_3P$ matches the plaintext side second step encryption (`tmp = tmp * C % M`). This little difference happens since the value after the second step can be large up to $M=2^{60}$ and then it is reduced modulo $P\\approx 2^{57.64}$, so a couple bits of information are lost."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Then, following two steps of encryption of $x$ and one step of decryption of $y$ we get:\n",
"$$\n",
"\\begin{align}\n",
"& (K_0x - t_1P)C - t_2M = K_1^{-1}y - t_3P, \\\\\n",
"\\Rightarrow &\n",
" xC\\cdot K_0 - y\\cdot K_1^{-1} - PC\\cdot t_1 - M\\cdot t_2 + P\\cdot t_3 = 0,\n",
"\\end{align}\n",
"$$\n",
"where we have unknowns\n",
"$$\n",
"\\begin{align}\n",
"0 \\le~ & K_0 < P,\\\\\n",
"0 \\le~ & K_1^{-1} < P,\\\\\n",
"0 \\le~ & t_1 < x,\\\\\n",
"0 \\le~ & t_2 < PC/M,\\\\\n",
"0 \\le~ & t_3 < y+\\epsilon.\n",
"\\end{align}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"execution": {
"iopub.execute_input": "2020-06-29T12:41:35.934568Z",
"iopub.status.busy": "2020-06-29T12:41:35.934010Z",
"iopub.status.idle": "2020-06-29T12:41:35.939785Z",
"shell.execute_reply": "2020-06-29T12:41:35.938713Z",
"shell.execute_reply.started": "2020-06-29T12:41:35.934501Z"
}
},
"source": [
"Note that $x,y,t_1,t_2,t_3$ are different for each known data pair."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can now use LLL to solve this constraint system. As an example, consider the following lattice for $n=3$ data pairs (rows as vectors):\n",
"$$\n",
"\\begin{matrix}\n",
"&~~~~ eq_0 ~~~~~~ eq_1 ~~~~~~ eq_2 ~~~ K_0 ~~~ K_1 ~~~ . ~~~~ t_{1,i} ~~~ . ~~~~ . ~~~~ t_{2,i} ~~~ . ~~~~ . ~~~~ t_{3,i} ~~~ . \\hfill \\\\\n",
"\\begin{matrix}\n",
"K_0 \\\\ K_1 \\\\ . \\\\ t_{1,i} \\\\ . \\\\ . \\\\ t_{2,i} \\\\ . \\\\ . \\\\ t_{3,i} \\\\ .\n",
"\\end{matrix} \\hspace{-1em}&\n",
"\\begin{pmatrix}\n",
"x_0C & x_1C & x_2C & 1 & & & & & & & & & & \\\\\n",
"y_0 & y_1 & y_2 & & 1 & & & & & & & & & \\\\\n",
"CP & & & & & 1 & & & & & & & & \\\\\n",
" & CP & & & & & 1 & & & & & & & \\\\\n",
" & & CP & & & & & 1 & & & & & & \\\\\n",
"M & & & & & & & & 1 & & & & & \\\\\n",
" & M & & & & & & & & 1 & & & & \\\\\n",
" & & M & & & & & & & & 1 & & & \\\\\n",
"P & & & & & & & & & & & 1 & & \\\\\n",
" & P & & & & & & & & & & & 1 & \\\\\n",
" & & P & & & & & & & & & & & 1 \\\\\n",
"\\end{pmatrix}\n",
"\\end{matrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We are looking for a linear combination of rows that makes the first $n$ entries zero, and the others to respect our bounds. We can achieve this by scaling the coordinates (columns): first $n$ columns should be multiplied by a very large number (forcing LLL to make it zero), the other columns should be multiplied inversely to their bounds. After applying the LLL, we need to scale back."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"execution": {
"iopub.execute_input": "2020-06-29T13:34:47.783252Z",
"iopub.status.busy": "2020-06-29T13:34:47.782103Z",
"iopub.status.idle": "2020-06-29T13:35:16.183268Z",
"shell.execute_reply": "2020-06-29T13:35:16.182586Z",
"shell.execute_reply.started": "2020-06-29T13:34:47.783130Z"
}
},
"outputs": [],
"source": [
"f = open(\"res\")\n",
"data = []\n",
"for line in f:\n",
" try:\n",
" pt, ct = map(int, line.split())\n",
" except:\n",
" break\n",
" data.append((pt, ct))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that the *bounds* of $t_{1,i},t_{2,i}$ depend on the actual plaintexts. We are thus interested in smallest plaintexts and ciphertexts. As we shall see, 20 smallest pairs are enough!"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"execution": {
"iopub.execute_input": "2020-06-29T13:35:16.184553Z",
"iopub.status.busy": "2020-06-29T13:35:16.184146Z",
"iopub.status.idle": "2020-06-29T13:36:02.050930Z",
"shell.execute_reply": "2020-06-29T13:36:02.050459Z",
"shell.execute_reply.started": "2020-06-29T13:35:16.184500Z"
}
},
"outputs": [],
"source": [
"data.sort(key=lambda a: a[0]**2 + a[1]**2)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"execution": {
"iopub.execute_input": "2020-06-29T13:36:02.051933Z",
"iopub.status.busy": "2020-06-29T13:36:02.051607Z",
"iopub.status.idle": "2020-06-29T13:36:02.055496Z",
"shell.execute_reply": "2020-06-29T13:36:02.054720Z",
"shell.execute_reply.started": "2020-06-29T13:36:02.051880Z"
}
},
"outputs": [],
"source": [
"n = 20\n",
"pairs = data[:20]"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"execution": {
"iopub.execute_input": "2020-06-29T13:36:02.057363Z",
"iopub.status.busy": "2020-06-29T13:36:02.056610Z",
"iopub.status.idle": "2020-06-29T13:36:02.230072Z",
"shell.execute_reply": "2020-06-29T13:36:02.227888Z",
"shell.execute_reply.started": "2020-06-29T13:36:02.057272Z"
}
},
"outputs": [],
"source": [
"m = matrix(QQ, 2 + 3*n, 2 + 4*n)\n",
"m[:,n:] = identity_matrix(2+3*n)\n",
"for i, (x, y) in enumerate(pairs):\n",
" m[0,i] = C*x\n",
" m[1,i] = y\n",
" m[0*n+2+i,i] = C*P\n",
" m[1*n+2+i,i] = M\n",
" m[2*n+2+i,i] = P\n",
" \n",
"bounds = [1] * n + [P] * 2\n",
"bounds += [pt for pt, ct in pairs]\n",
"bounds += [P*C / M] * n\n",
"bounds += [ct for pt, ct in pairs]\n",
"assert len(bounds) == m.ncols()"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"execution": {
"iopub.execute_input": "2020-06-29T13:36:02.232429Z",
"iopub.status.busy": "2020-06-29T13:36:02.231585Z",
"iopub.status.idle": "2020-06-29T13:36:06.011783Z",
"shell.execute_reply": "2020-06-29T13:36:06.011175Z",
"shell.execute_reply.started": "2020-06-29T13:36:02.232267Z"
}
},
"outputs": [],
"source": [
"# scale\n",
"for i, b in enumerate(bounds):\n",
" m.set_column(i, m.column(i)/b)\n",
"# LLL\n",
"m = m.LLL()\n",
"for i, b in enumerate(bounds):\n",
" m.set_column(i, m.column(i)*b)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"execution": {
"iopub.execute_input": "2020-06-29T13:36:06.012649Z",
"iopub.status.busy": "2020-06-29T13:36:06.012340Z",
"iopub.status.idle": "2020-06-29T13:36:06.024758Z",
"shell.execute_reply": "2020-06-29T13:36:06.023676Z",
"shell.execute_reply.started": "2020-06-29T13:36:06.012615Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Row 11: key recovered: 1df19a439748567 29ad0f3aac513b9\n"
]
}
],
"source": [
"for irow, row in enumerate(m):\n",
" k0, negk1i = row[n:n+2]\n",
" if gcd(negk1i, P) == 1:\n",
" k1 = inverse_mod(-int(negk1i), P)\n",
" for x, y in pairs:\n",
" tmp = x * k0 % P\n",
" tmp = tmp * C % M\n",
" tmp = tmp * k1 % P\n",
" if tmp != y:\n",
" break\n",
" else:\n",
" k0 %= P\n",
" k1 %= P\n",
" print(\"Row %d: key recovered: %x %x\" % (irow, k0, k1))\n",
" break\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"That was fast! Now let's decrypt the flag (recall that a couple of bits is missing, so we have to check a few candidates per block). Also the first reduction modulo $P$ destroys a few bits too."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"execution": {
"iopub.execute_input": "2020-06-29T13:36:06.027049Z",
"iopub.status.busy": "2020-06-29T13:36:06.026321Z",
"iopub.status.idle": "2020-06-29T13:36:06.049992Z",
"shell.execute_reply": "2020-06-29T13:36:06.047456Z",
"shell.execute_reply.started": "2020-06-29T13:36:06.026967Z"
}
},
"outputs": [],
"source": [
"k0i = inverse_mod(k0, P)\n",
"k1i = inverse_mod(k1, P)\n",
"Ci = inverse_mod(C, M)\n",
"\n",
"def decrypt_block(y): \n",
" for t in range(5):\n",
" v = y * k1i % P\n",
" v += t*P \n",
" if v >= M: continue\n",
" v = v * Ci % M\n",
" if v >= P: continue\n",
" v = v * k0i % P\n",
" while v < 2**64:\n",
" #assert encrypt_block(v) == y\n",
" yield v\n",
" v += P"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"execution": {
"iopub.execute_input": "2020-06-29T13:36:06.890826Z",
"iopub.status.busy": "2020-06-29T13:36:06.890285Z",
"iopub.status.idle": "2020-06-29T13:36:07.673682Z",
"shell.execute_reply": "2020-06-29T13:36:07.672780Z",
"shell.execute_reply.started": "2020-06-29T13:36:06.890736Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"b'_p4droNe'\n",
"b'_a5k3d_m'\n",
"b'3_7o_br1'\n",
"b'ng_tHis_'\n",
"b'foR_thE_'\n",
"b'5ign0Ra.'\n",
"b'flag{_p4droNe_a5k3d_m3_7o_br1ng_tHis_foR_thE_5ign0Ra.}'\n"
]
}
],
"source": [
"from struct import unpack, pack\n",
"ct = open(\"res\").read()[-200:].strip().split()[-1]\n",
"ct = bytes.fromhex(ct)\n",
"fmt = '%dQ' % (len(ct)/8)\n",
"ct = unpack(fmt, ct)\n",
"\n",
"flag = b\"\"\n",
"for block in ct:\n",
" for dec in decrypt_block(block):\n",
" dec = pack(\"<Q\", dec)\n",
" if all(0x20 <= v < 127 for v in dec):\n",
" print(dec)\n",
" flag += dec\n",
"\n",
"print(b\"flag{\" + flag + b\"}\")"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "SageMath 9.0",
"language": "sage",
"name": "sagemath3"
},
"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.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment