{
    "version": "https:\/\/jsonfeed.org\/version\/1.1",
    "title": "Заметки Андрея Гейна: posts tagged python",
    "_rss_description": "Заметки про язык программирования питон",
    "_rss_language": "en",
    "_itunes_email": "",
    "_itunes_categories_xml": "",
    "_itunes_image": "",
    "_itunes_explicit": "",
    "home_page_url": "https:\/\/andgein.ru\/blog\/tags\/python\/",
    "feed_url": "https:\/\/andgein.ru\/blog\/tags\/python\/json\/",
    "icon": "https:\/\/andgein.ru\/blog\/pictures\/userpic\/userpic@2x.jpg?1631100411",
    "authors": [
        {
            "name": "Андрей Гейн",
            "url": "https:\/\/andgein.ru\/blog\/",
            "avatar": "https:\/\/andgein.ru\/blog\/pictures\/userpic\/userpic@2x.jpg?1631100411"
        }
    ],
    "items": [
        {
            "id": "5",
            "url": "https:\/\/andgein.ru\/blog\/all\/5-crypto-backdoor-writeup\/",
            "title": "Заметка пятая. Разбор задания Crypto Backdoor с Google CTF 2017",
            "content_html": "<p>Это заметка о том, как мы с Костей Плотниковым решали задание на ассиметричную криптографию с Google CTF, который прошёл неделю назад. Она кишит кодом на питоне, несложными терминами из теории групп и математическими выкладками. Смело пропускайте, если боитесь чего-нибудь из этого.<\/p>\n<script type=\"text\/x-mathjax-config\">\nMathJax.Hub.Config({\n  tex2jax: {\n     inlineMath: [['$','$'], ['\\\\(','\\\\)']]\n  },\n  \"HTML-CSS\": {\n     linebreaks: { automatic: true, width: \"75% container\" }\n   }, \n  \"SVG\": {\n     linebreaks: { automatic: true, width: \"75% container\" }\n   } \n});\n<\/script>\n<script async src='https:\/\/cdnjs.cloudflare.com\/ajax\/libs\/mathjax\/2.7.0\/MathJax.js?config=TeX-AMS_CHTML'><\/script>\n<p>Формулировка как всегда бесконечно расплывчата:<\/p>\n<blockquote>\n<p>This public-key cryptosystem has a flaw. Can you exploit it? <a href=\"\/files\/blog\/5\/crypto_backdoor.py\">crypto_backdoor.py<\/a><\/p>\n<\/blockquote>\n<p>Костя попробовал меня ввести в курс дела, когда я присоединился к нему. Он рассказал, что в скрипте реализовано что-то вроде <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%AD%D0%BB%D0%BB%D0%B8%D0%BF%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BA%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F\">эллиптической криптографии<\/a>. Работает она так: сначала на плоскости рисуется специальная <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%AD%D0%BB%D0%BB%D0%B8%D0%BF%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BA%D1%80%D0%B8%D0%B2%D0%B0%D1%8F\">кривая<\/a>, а затем для каждой пары точек на ней определяется операция сложения. Сумма двух точек с кривой тоже лежит на кривой за исключением случая, когда получается особое значение — ноль. После этого естественным образом определяется умножение точки на натуральное число.<\/p>\n<p>В эллиптической криптографии Боб, желающий получать зашифрованные сообщения от Алисы, выбирает секретное число $N$ и точку на эллиптической кривой $g$. Последняя называется генератором и сообщается всем желающим, а вот секретное число становится закрытым ключом Боба. Открытым ключом в этом случае называется произведение генератора и закрытого ключа; $B = Ng$.<\/p>\n<p>Собственно, на мысли об эллиптических кривых Костю натолкнули наличие в скрипте точки-генератора и двух открытых ключей:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\"># Modulus\np = 606341371901192354470259703076328716992246317693812238045286463\n# g is the generator point.\ng = (160057538006753370699321703048317480466874572114764155861735009, 255466303302648575056527135374882065819706963269525464635673824)\n# Alice&#039;s public key A:\nA = (460868776123995205521652669050817772789692922946697572502806062, 263320455545743566732526866838203345604600592515673506653173727)\n# Bob&#039;s public key B:\nB = (270400597838364567126384881699673470955074338456296574231734133, 526337866156590745463188427547342121612334530789375115287956485)<\/code><\/pre><p>Модуль $p$ здесь тоже неслучаен — в эллиптической криптографии как раз рассматриваются кривые над полем $\\mathbb{Z}_p$. Позже, правда, мы пришли к выводу, что эллиптическая криптография тут совсем ни при чём... Но сначала мы внимательно изучили операцию сложения двух точек:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">def add(a, b, p):\n  if a == -1:\n    return b\n  if b == -1:\n    return a\n  x1, y1 = a\n  x2, y2 = b\n  x3 = ((x1*x2 - x1*y2 - x2*y1 + 2*y1*y2) * modinv(x1 + x2 - y1 - y2 - 1, p)) % p\n  y3 = ((y1*y2) * modinv(x1 + x2 - y1 - y2 - 1, p)) % p\n  return (x3, y3)<\/code><\/pre><p>Нейтральный элемент (он же <i>ноль<\/i>) обозначен как $-1$, поэтому первые четыре строки функции очевидны. Функция $modinv(x, p)$ находит обратный элемент к $x$ в кольце $\\mathbb{Z}_p$ с помощью расширенного алгоритма Евклида. Значит, сумма точек $(x_1, y_1)$ и $(x_2, y_2)$ это точка<br \/>\n$$\\left(\\frac{x_1x_2 – x_1y_2 – x_2y_1 + 2y_1y_2}{x_1+x_2-y_1-y_2-1}, \\frac{y_1y_2}{x_1+x_2-y_1-y_2-1}\\right)$$<\/p>\n<p>Дробь означает целочисленное деление в кольце $\\mathbb{Z}_p$.<\/p>\n<h2>Упрощаем сложение<\/h2>\n<p>Математик во мне захотел разобраться с этой операцией. Больше всего смущали одинаковые знаменатели и сложный числитель первой координаты. Стало проще, когда я переписал числитель как $(x_1-y_1)(x_2-y_2)+y_1y_2$, а знаменатель как $(x_1-y_1) + (x_2-y_2)$. Давайте перейдём из системы координат $(x, y)$ в систему $(t, y)$, где $t = x-y$. Обратный переход тоже очень простой: $x = t + y$. Если переписать операцию сложения в новой системе координат, то получится<\/p>\n<p>$$(t_1, y_1) + (t_2, y_2) = \\left(\\frac{t_1t_2+y_1y_2}{t_1+t_2-1} – \\frac{y_1y_2}{t_1+t_2-1}, \\frac{y_1y_2}{t_1+t_2-1}\\right) = \\left(\\frac{t_1t_2}{t_1+t_2-1}, \\frac{y_1y_2}{t_1+t_2-1}\\right)$$<\/p>\n<p>Получившаяся формула в некотором смысле даже симметрична. Это дало нам оптимизм на несколько следующих часов.<\/p>\n<h2>Мастер-секрет<\/h2>\n<p>Однако в скрипте само по себе сложение нигде не используются. Зато используется умножение точки на число:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">from secret_data import aliceSecret, bobSecret, flag\n\nassert A == mul(aliceSecret, g, p)\nassert B == mul(bobSecret, g, p)\n\naliceMS = mul(aliceSecret, B, p)\nbobMS = mul(bobSecret, A, p)\nassert aliceMS == bobMS\nmasterSecret = aliceMS[0]*aliceMS[1]<\/code><\/pre><p>Настало время разобраться, что вообще происходит в скрипте и что нужно найти.<\/p>\n<p>$aliceSecret$ — это натуральное число, закрытый ключ Алисы, он умножается на известный нам генератор, и в результате получается известный нам открытый ключ Алисы. Аналогичное проделывается с ключами Боба. После этого открытый ключ Боба умножается на закрытый ключ Алисы, получая точку $aliceMS = aliceSecret \\times bobSecret \\times g$. Симметричная операция вычисляет $bobMS = bobSecret \\times aliceSecret \\times g$. Очевидно, что эти две точки должны совпасть, что и проверяется последним assert’ом. Мастер-секретом объявляется произведение координат этой общей точки. Этот мастер-секрет и надо найти, так как в конце скрипта он ксорится с флагом:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">def encrypt(message, key):\n  return message ^ key\n\nlength = len(flag)\nencrypted_message = encrypt(I(flag), masterSecret)\nprint &quot;length = %d, encrypted_message = %d&quot; % (length, encrypted_message)\n# length = 31, encrypted_message = 137737300119926924583874978524079282469973134128061924568175107915062758827931077214500356470551826348226759580545095568667325<\/code><\/pre><h2>Умножение в новых координатах<\/h2>\n<p>Раз для подсчёта мастер-секрета используется умножение, то вернёмся к нашим формулам и выясним, как точка в новых координатах $(t, y)$ умножается на число $k$. Переберём несколько маленьких коэффициентов:<\/p>\n<p>$$2(t, y) = (t, y) + (t, y) = \\left(\\frac{t^2}{2t-1}, \\frac{y^2}{2t-1}\\right)$$<\/p>\n<p>$$3(t, y) = 2(t, y) + (t, y) = \\left(\\frac{t^2}{2t-1}, \\frac{y^2}{2t-1}\\right) + (t, y) =<br \/>\n\\left(\\frac{\\frac{t^3}{2t-1}}{\\frac{t^2}{2t-1} + t – 1}, \\frac{{\\frac{y^3}{2t-1}}}{\\frac{t^2}{2t-1} + t – 1}\\right) =<br \/>\n\\left(\\frac{t^3}{3t^2-3t+1}, \\frac{y^3}{3t^2-3t+1}\\right)$$<\/p>\n<p>$$4(t, y) = 2(t, y) + 2(t, y) = \\left(\\frac{t^2}{2t-1}, \\frac{y^2}{2t-1}\\right) + \\left(\\frac{t^2}{2t-1}, \\frac{y^2}{2t-1}\\right)  =<br \/>\n\\left(\\frac{\\frac{t^4}{(2t-1)^2}}{\\frac{2t^2}{2t-1} – 1}, \\frac{\\frac{y^4}{(2t-1)^2}}{\\frac{2t^2}{2t-1} – 1}\\right) =<br \/>\n\\left(\\frac{\\frac{t^4}{2t-1}}{2t^2-2t+1}, \\frac{\\frac{y^4}{2t-1}}{2t^2-2t+1}\\right) =<br \/>\n\\left(\\frac{t^4}{4t^3-6t^2+4t-1}, \\frac{y^4}{4t^3-6t^2+4t-1}\\right) $$<\/p>\n<p>Умножать дальше становилось всё сложнее, поэтому пора найти закономерность. В числителях всё время получается $t^k$ и $y^k$, а в знаменателях видны биномиальные коэффициенты. Смотрите, $4t^3-6t^2+4t-1$ похоже на $t^4 + (4t^3-6t^2+4t-1)$, что в свою очередь равно $(t + 1)^4$. Так у нас появилась гипотеза, что знаменатель равен $(t+1)^k – t^k$.<\/p>\n<p>Итоговую формулу<\/p>\n<p>$$k \\times (t, y) = \\left(\\frac{t^k}{(t+1)^k – t^k}, \\frac{y^k}{(t+1)^k – t^k}\\right)$$<\/p>\n<p>теперь можно доказать по индукции по $k$. Делать я этого, конечно же, не буду.<\/p>\n<h2>Решение<\/h2>\n<p>Задача будет решена, если мы узнаем закрытый ключ Алисы или Боба. В случае с Бобом нам достаточно найти такое $k \\in \\mathbb{Z}_p$, что $kg = B$. В наших новых координатах и формулах это выглядит так:<\/p>\n<p>$$\\left(\\frac{g_t^k}{(g_t+1)^k – g_t^k}, \\frac{g_y^k}{(g_t+1)^k – g_t^k}\\right) = (B_t, B_y)$$<\/p>\n<p>где $(g_t, g_y)$ — координаты генератора $g$ в системе $(t, y)$, а $(B_t, B_y)$ — аналогичные координаты точки $B$. Взяв из этого равенства первую координату, получаем:<\/p>\n<p>$$ \\frac{g_t^k}{(g_t+1)^k – g_t^k} = B_t$$<\/p>\n<p>$$g_t^k = B_t ((g_t+1)^k – g_t^k)$$<\/p>\n<p>$$g_t^k (1 + B_t) = B_t (g_t+1)^k$$<\/p>\n<p>$$\\left(\\frac{g_t}{g_t+1}\\right)^k = \\frac{B_t}{1 + B_t}$$<\/p>\n<p>Чтобы найти искомое $k$, достаточно вычислить логарифм в кольце $\\mathbb{Z}_p$, то есть решить задачу <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%BE%D0%B5_%D0%BB%D0%BE%D0%B3%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5\">дискретного локарифмирования<\/a>. Здесь мы с Костей приуныли, потому что поняли, что зашли в тупик. Дискретное логарифмирование — задача, которую нельзя решить за нормальное время.<\/p>\n<p>Только через час Костя догадался проверить данный нам модуль $p$ на простоту. Совершенно неожиданно он оказался составным:<\/p>\n<p>$$p = 961236149 \\times 951236179 \\times 941236273 \\times 911236121 \\times 931235651 \\times 921236161 \\times 901236131$$<\/p>\n<p>Наверняка все знают, как посчитать дискретный логарифм по непростому основанию. А мы не знаем. Так что мы взяли бумажку и стали придумывать алгоритм.<\/p>\n<blockquote>\n<p><i>Когда-то Асанов рассказывал байку, что студенты УПИ обычно знают способ решить задачу, а студенты матмеха не знают. Зато студенты матмеха могут придумать решение. Кажется, теперь я понял эту байку.<\/i><\/p>\n<\/blockquote>\n<h2>Дискретный логарифм по составному основанию<\/h2>\n<p>Пусть мы нашли дискретный логарифм от $b$ по основанию $a$ в кольцах $\\mathbb{Z}_p$ и $\\mathbb{Z}_q$. То есть мы нашли такие $n$ и $m$, что<\/p>\n<p>$$a^n \\equiv b \\pmod{p}$$<br \/>\n$$a^m \\equiv b \\pmod{q}$$<\/p>\n<p>Теперь мы хотим решить задачу в кольце $\\mathbb{Z}_{pq}$, то есть найти такое $k$, что $a^k \\equiv b \\pmod{pq}$. Порядком числа $a$ в кольце называется такое минимальное натуральное $z$, что $a^z = 1$. Пусть число $a$ имеет порядки $u$ и $v$ в кольцах $\\mathbb{Z}_p$ и $\\mathbb{Z}_q$ соответственно. Тогда $b \\equiv a^n \\equiv a^{n + u} \\equiv a^{n+2u} \\equiv a^{n+3u} \\equiv \\dots \\pmod{p}$ и $b \\equiv a^m \\equiv a^{m + v} \\equiv a^{m+2v} \\equiv a^{m+3v} \\equiv \\dots \\pmod{q}$. Если мы найдём число, которое можно выразить и как $n + ?u$, и как $m + ?v$, то оно станет ответом задачи дискретного логарифмирования по модулю $pq$.<\/p>\n<p>Ну а найти такое число — дело техники и расширенного алгоритма Евклида. Если $n + ?u = m + ?v$, то $?u – ?v = m – n$. Если $m-n$ не делится на $НОД(u, v)$, то решения нет, иначе расширенный алгоритм Евклида решит это <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%94%D0%B8%D0%BE%D1%84%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D0%BE_%D1%83%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5#.D0.9B.D0.B8.D0.BD.D0.B5.D0.B9.D0.BD.D1.8B.D0.B5_.D0.B4.D0.B8.D0.BE.D1.84.D0.B0.D0.BD.D1.82.D0.BE.D0.B2.D1.8B_.D1.83.D1.80.D0.B0.D0.B2.D0.BD.D0.B5.D0.BD.D0.B8.D1.8F\">линейное диофантово уравнение<\/a>, и всё станет хорошо.<\/p>\n<p>Так как данный в задании модуль $p$ мы разложили на простые множители $p_1 \\times p_2 \\times \\dots \\times p_7$, которые к тому же получились не очень большими, то мы можем решить задачу дискретного логарифмирования в каждом из $\\mathbb{Z}_{p_i}$. Соединить семь чисел в один большой ответ поможет описанный только что алгоритм.<\/p>\n<h2>Как решить дискретный логарифм для  $p_i$<\/h2>\n<p>Простые делители модуля $p$ были не очень большими, но и не настолько маленькими, чтобы дискретный логарифм можно было найти простым перебором. К счастью, есть алгоритм <i>Baby Steps Giant Steps<\/i>, который позволяет сделать это намного быстрее — за $O(\\sqrt{n})$. Его мы и реализовали. Да, мы думали о том, что Baby Steps Giant Steps уже реализован в куче библиотек, но лично меня это только раззадоривает — так интересно ведь всё сделать самому.<\/p>\n<h2>Как найти порядок элемента в кольце<\/h2>\n<p>На часах было уже около часа ночи, а мне предстояло запрограммировать на питоне поиск порядка элемента в кольце $\\mathbb{Z}_p$. Теорема Эйлера шептала, что $x^{\\phi(p)} \\equiv 1 \\pmod{p}$, но $\\phi(p)$ могло оказаться не минимальным числом с таким свойством. Значит, искомый порядок — это делитель $\\phi(p)$. Но делителей слишком много, чтобы перебирать их все. Так что пришла пора узнать более быстрый способ находить порядок элемента. На помощь пришла <a href=\"http:\/\/cacr.uwaterloo.ca\/hac\/about\/chap4.pdf\">пдфка из интернета<\/a>, в которой есть чудесный алгоритм 4.79, я реализовал его и научился быстро находить порядок элемента в кольце, зная разложение на простые множители у $\\phi(p)$.<\/p>\n<h2>Заключение<\/h2>\n<p>Применив всю магию сверху, мы нашли закрытый ключ Боба $bobSecret$. Умножив его на открытый ключ Алисы, мы нашли мастер-секрет, который и выдал нам флаг:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">Master secret found: (254828745614253797280016043417264027645246572307317271091197847, 540509273347153402828726537667691800163306365090607497812000946)\nFlag: CTF{Anyone-can-make-bad-crypto}<\/code><\/pre><p>Если вкратце повторить всё наше решение, то оно перестаёт казаться страшным и длинным:<\/p>\n<ol start=\"1\">\n<li>переходим в систему координат $(t, y)$,<\/li>\n<li>вычисляем $a = \\frac{g_t}{g_t+1}$ и $b = \\frac{B_t}{1 + B_t}$,<\/li>\n<li>решаем задачу дискретного логарифма $a^{?} = b$ в кольце $\\mathbb{Z}_p$, зная разложение $p$ на простые множители,<\/li>\n<li>умножаем полученный ответ на открытый ключ Алисы $A$, это и есть мастер-секрет,<\/li>\n<li>переходим обратно в координаты $(x, y)$, перемножаем координаты мастер-секрета, расшифровываем флаг.<\/li>\n<\/ol>\n",
            "date_published": "2017-06-24T13:10:53+01:00",
            "date_modified": "2018-06-29T15:55:44+01:00",
            "tags": [
                "crypto",
                "CTF",
                "python",
                "writeup",
                "математика"
            ],
            "_date_published_rfc2822": "Sat, 24 Jun 2017 13:10:53 +0100",
            "_rss_guid_is_permalink": "false",
            "_rss_guid": "5",
            "_e2_data": {
                "is_favourite": false,
                "links_required": [
                    "highlight\/highlight.js",
                    "highlight\/highlight.css"
                ],
                "og_images": []
            }
        },
        {
            "id": "2",
            "url": "https:\/\/andgein.ru\/blog\/all\/2-phdays-ctf-2017-service\/",
            "title": "Заметка вторая. О сервисе на PHDays CTF",
            "content_html": "<p><i>Продолжение истории о <a href=\"\/blog\/all\/1-unicode-and-csv-in-python\/\">необычном поведении<\/a> юникода и CSV в питоне<\/i><\/p>\n<h2>Для тех, кому лень читать предыдущую заметку или вспоминать, о чём там было<\/h2>\n<p>Если использовать стандартные питоновские <a href=\"https:\/\/docs.python.org\/3\/library\/codecs.html#codecs.open\">codecs.open<\/a>, <a href=\"https:\/\/docs.python.org\/3\/library\/csv.html#csv.DictWriter\">csv.DictWriter<\/a> и <a href=\"https:\/\/docs.python.org\/3\/library\/csv.html#csv.DictReader\">csv.DictReader<\/a>, то можно столкнуться с интересным поведением. Создаём в программе файл в кодировке UTF-8, пишем туда с помощью DictWriter, а затем читаем через DictReader. Если в данных встречались юникодные символы Pararaph separator или Line separator, то мы считаем больше записей, чем было записано, а их CSV-структура будет поломана.<\/p>\n<p>Читайте <a href=\"\/blog\/all\/1-unicode-and-csv-in-python\/\">первую заметку<\/a> для подробностей.<\/p>\n<h2>Как из этого получился сервис для классического CTF<\/h2>\n<p>В апреле мы с ребятами из Хакердома как раз готовили онлайновый CTF для форума <a href=\"https:\/\/phdays.com\">PHDays<\/a>. Темой был выбран интернет вещей, а сервисами были умный чайник, термометр, дверной замок, телевизор и даже холодильник. Мне достался последний, потому что я слишком люблю еду.<\/p>\n<p>Чтобы органично встроить уязвимость в сервис, мне нужно было сделать так, чтобы кто-то писал в CSV-файл, а кто-то другой — читал. В итоге сервис состоял из двух частей — веб-приложения для удобного управления человеком и API для других умных кухонных гаджетов, которым нужна информация от холодильника.<\/p>\n<p>Веб-интерфейс позволял пользователям регистрироваться и создавать холодильные камеры или просто холодильники. У каждого холодильника был владелец, и увидеть чужие просто так нельзя. В холодильники можно добавлять еду. Для этого сначала было необходимо зарегистрировать новый продукт (например, картошку или молоко) и указать, в чём он измеряется — в граммах, пачках или литрах. Выглядело это так:<\/p>\n<div class=\"e2-text-picture\">\n<div class=\"fotorama\" data-width=\"1122\" data-ratio=\"2.5384615384615\">\n<img src=\"https:\/\/andgein.ru\/blog\/pictures\/2017-05-16_17-12-56-(2).png\" width=\"1122\" height=\"442\" alt=\"\" \/>\n<img src=\"https:\/\/andgein.ru\/blog\/pictures\/2017-05-16_17-14-21.png\" width=\"1125\" height=\"676\" alt=\"\" \/>\n<img src=\"https:\/\/andgein.ru\/blog\/pictures\/2017-05-16_17-23-56.png\" width=\"1124\" height=\"597\" alt=\"\" \/>\n<img src=\"https:\/\/andgein.ru\/blog\/pictures\/2017-05-16_20-56-37.png\" width=\"1127\" height=\"398\" alt=\"\" \/>\n<img src=\"https:\/\/andgein.ru\/blog\/pictures\/2017-05-16_20-58-25-(2).png\" width=\"1159\" height=\"584\" alt=\"\" \/>\n<\/div>\n<\/div>\n<p>Кроме холодильников можно было создавать рецепты. Про каждый ингредиент рецепта известно, сколько и какого продукты нужно положить, а также что с ним надо сделать и сколько после этого подождать.<\/p>\n<div class=\"e2-text-picture\">\n<img src=\"https:\/\/andgein.ru\/blog\/pictures\/2017-05-16_21-07-14.png\" width=\"1122\" height=\"669\" alt=\"\" \/>\n<\/div>\n<p>Рецепты были очень важны для функционирования сервиса, ведь в том самом API было всего две команды — получить список твоих холодильников и получить список рецептов, которые можно приготовить из еды, лежащей в одном из твоих холодильников. Звучит сложно, но идея очень простая — если у вас есть умная мультиварка, то она хочет узнать, какие блюда можно сегодня приготовить из продуктов, лежащих у вас в холодильнике.<\/p>\n<p>Принадлежность выдаваемых рецептов владельцу холодильника в API не проверялась, но должно было работать само: в рецепте должен присутствовать хотя бы один продукт из холодильника, а в холодильник мы можем добавлять только принадлежащие нам продукты. Моё молоко и молоко Васи — два разных продукта, я могу добавить в холодильники и рецепты только первое, а про второе даже не смогу узнать.<\/p>\n<h2>Уязвимость<\/h2>\n<p>Итак, где же тут наши подозреваемые — юникод и CSV?<\/p>\n<p>Сервис API не имеет доступа к базе данных, поэтому информация для него складывалась веб-приложением в специальные CSV-файлы, откуда считывались API-приложением раз в секунду. Вот пример такого файла:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">id,recipe_id,food_type_id,what_to_do,count,pause_after\n1,10,15,Yhws aqx vpjhtlyhw ruv tbcyis,11,7\n2,11,16,Ok jbso gtpzs ndgoz udeksmvk,10,16\n3,12,17,Y ap mculltvedfwwabbnnnco um,6,19\n4,13,18,cniyvdjsyuctaamupp zm  qj nwvm,10,9\n5,14,19,Kfdvm ref wtb pdtitb,14,15<\/code><\/pre><p>В нём хранятся ингредиенты рецептов. Столбцы, соответственно — id ингредиента, id рецепта (сами рецепты лежат в другом файле), id продукта, что нужно сделать, сколько взять продукта и какую выдержать после этого паузу.<\/p>\n<p>Давайте посмотрим, что будет, если в поле what_to_do добавить тот самый Paragraph separator:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">6,15,20,blablabla\u202913503,14,20<\/code><\/pre><p>При чтении этот файл будет выглядеть для DictReader’а как<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">6,15,20,blablabla\u2029\n13503,14,20<\/code><\/pre><p>То есть так, будто мы добавили продукт №20 в рецепт №14. Продукт №20 принадлежит нам, значит, мы смогли добавить нашу еду в чужой рецепт №14! Теперь API сможет вывести этот рецепт, если в каком-нибудь из наших холодильников будет лежать продукт №20.<\/p>\n<p>Для полноты картины покажу, как выглядели сохранение и загрузка данных в CSV.<\/p>\n<h3>Сохранение:<\/h3>\n<pre class=\"e2-text-code\"><code class=\"\">def dump_model_to_file(model, filename):\n    # Use Django API to get all model fields\n    columns = [field.attname for field in model._meta.fields]\n\n    with codecs.open(filename, &#039;w&#039;, encoding=&#039;utf-8&#039;) as opened_file:\n        # Open csv writer and dump header: special row with columns names\n        writer = csv.DictWriter(opened_file, fieldnames=columns)\n        writer.writeheader()\n\n        # Iterate over all objects of the model\n        for obj in model.objects.all():\n            object_dict = {}\n            for column in columns:\n                # Don&#039;t worry about newlines (\\n and \\r): csv.DictWriter will enclose such strings in quotes (&quot;)\n                # So I think there is no vulnerability here\n                object_dict[column] = str(getattr(obj, column, &#039;&#039;))\n\n            # Dump dictionary for current object\n            writer.writerow(object_dict)<\/code><\/pre><h3>Загрузка:<\/h3>\n<pre class=\"e2-text-code\"><code class=\"\">class Model:\n    def __init__(self, dictionary):\n        for key, value in dictionary.items():\n            if value is None:\n                value = &#039;0&#039;\n            if value.isnumeric():\n                value = int(value)\n            setattr(self, key, value)\n\n\ndef load_models_from_file(filename):\n    objects = {}\n    with codecs.open(filename, &#039;r&#039;, encoding=&#039;utf-8&#039;) as opened_file:\n        reader = csv.DictReader(opened_file)\n        for row in reader:\n            objects[model.id] = Model(row)\n    return objects<\/code><\/pre><h2>Ещё две уязвимости<\/h2>\n<p>В Холодильнике мной была заложена ещё одна уязвимость. Но так получилось, что в итоге уязвимостей оказалось не две, а три. Так бывает на CTF, и в этом нет ничего страшного. Иногда бывает обидно, что ты заложил сложную уязвимость, а случайно оставил простую. Но в данном случае всё случилось удачно: незапланированная уязвимость была проще первой, а запланированная — совсем элементарной (правда, позволяла украсть только 20% флагов). Так как в целом соревнование получилось очень сложным, то появление одной незапланированной уязвимости средней сложности сыграло нам на руку.<\/p>\n<p>Итак, сначала о запланированной уязвимости. Каждый сервис находился в своём докер-контейнере. Докер (docker) — это удобный способ изолировать своё приложение от других, в линуксе работает за счёт его фирменных LXC-контейнеров и ограничений в cgroup. Подробнее о докере можно почитать на <a href=\"https:\/\/docker.com\/\">официальном сайте<\/a>.<\/p>\n<p>Мой сервис состоял из четырёх докер-контейнеров: для веб-приложения, для API-приложения, для базы данных и для веб-сервера nginx. Во время старта первого накатывались миграции, собиралась статика и выполнялись другие служебные команды. В том числе такая:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\"># DON&#039;T RUN IT IN PRODUCTION. SOME EVIL GUYS CAN BRUTEFORCE PASSWORD AND WHO KNOW WHAT HAPPENS...\necho &quot;[+] [DEBUG] Django setup, executing: add superuser&quot;\nPGPASSWORD=${POSTGRES_PASSWORD} psql -U ${POSTGRES_USER} -h ${POSTGRES_HOST} -c &quot;INSERT INTO auth_user (password, last_login, is_superuser, username, first_name, last_name, email, is_staff, is_active, date_joined) VALUES (&#039;pbkdf2_sha256\\$36000\\$k36V24q60mNo\\$v5og9qcgc2sqkVwGjZDKNK+wcJy60ix8DIt9E8Yg48c=&#039;, &#039;1970-01-01 00:00:00.000000&#039;, true, &#039;admin&#039;, &#039;admin&#039;, &#039;admin&#039;, &#039;admin@admin&#039;, true, true, &#039;1970-01-01 00:00:00.000000&#039;) ON CONFLICT (username) DO NOTHING&quot;<\/code><\/pre><p>Эта команда добавляет напрямую в базу данных супер-пользователя с логином admin. Его пароль мы не знаем, так что сразу зайти под ним не можем, но доступен хеш от пароля: ‘pbkdf2_sha256$36000$k36V24q60mNo$v5og9qcgc2sqkVwGjZDKNK+wcJy60ix8DIt9E8Yg48c=’. Подбор пароля не занимает много времени, так как он словарный и встречается во всех списках самых частых паролей.<\/p>\n<p>Попрактикуйтесь — сможете ли вы подобрать пароль? pbkdf2_sha256 — это тип хеша и подписи, а 36000 — количество итераций. Справиться с задачей поможет hashcat, john the ripper или любой другой подборщик прообразов хешей.<\/p>\n<h2>Незапланированная уязвимость<\/h2>\n<p>Последняя уязвимость нашлась в функции добавлении продукта в холодильник. Здесь не проверялось, что вы являетесь владельцем добавляемого продукта. Можно было создать супер-холодильник, содержащий все продукты с номерами от 1 до 1000, а затем попросить API выдать рецепты, содержащие хотя бы какой-нибудь продукт из этого холодильника. Конечно, он находил и чужие рецепты, а вместе с ними выдавал и флаги, хранящиеся в описаниях этих рецептов.<\/p>\n<h2>Выводы<\/h2>\n<p>Никогда не используйте csv.DictReader\/csv.DictWriter вместе с файлами, открытыми модулем codecs. В новых питонах открывайте CSV-файлы с помощью стандартной функции open, передавая ей аргументы encoding и newline.<\/p>\n<h2>Бонус для дочитавших до конца<\/h2>\n<p>Все исходники сервиса, докер-файлы, чекер для проверяющей системы и мой авторский эксплойт для первой уязвимости можно найти в <a href=\"https:\/\/github.com\/HackerDom\/phdctf-2017\">репозитории разработки<\/a>, который мы открыли сразу после окончания соревнования.<\/p>\n",
            "date_published": "2017-05-17T15:23:38+01:00",
            "date_modified": "2017-08-17T19:24:59+01:00",
            "tags": [
                "csv",
                "CTF",
                "PHDays",
                "python",
                "unicode",
                "программирование"
            ],
            "image": "https:\/\/andgein.ru\/blog\/pictures\/2017-05-16_20-58-25.png",
            "_date_published_rfc2822": "Wed, 17 May 2017 15:23:38 +0100",
            "_rss_guid_is_permalink": "false",
            "_rss_guid": "2",
            "_e2_data": {
                "is_favourite": false,
                "links_required": [
                    "jquery\/jquery.js",
                    "fotorama\/fotorama.css",
                    "fotorama\/fotorama.js",
                    "highlight\/highlight.js",
                    "highlight\/highlight.css"
                ],
                "og_images": [
                    "https:\/\/andgein.ru\/blog\/pictures\/2017-05-16_20-58-25.png",
                    "https:\/\/andgein.ru\/blog\/pictures\/2017-05-16_17-12-56-(2).png",
                    "https:\/\/andgein.ru\/blog\/pictures\/2017-05-16_17-14-21.png",
                    "https:\/\/andgein.ru\/blog\/pictures\/2017-05-16_17-23-56.png",
                    "https:\/\/andgein.ru\/blog\/pictures\/2017-05-16_20-56-37.png",
                    "https:\/\/andgein.ru\/blog\/pictures\/2017-05-16_20-58-25-(2).png",
                    "https:\/\/andgein.ru\/blog\/pictures\/2017-05-16_21-07-14.png"
                ]
            }
        },
        {
            "id": "1",
            "url": "https:\/\/andgein.ru\/blog\/all\/1-unicode-and-csv-in-python\/",
            "title": "Заметка первая. Про необычное поведение юникода и CSV в питоне",
            "content_html": "<p><i>Посвящается Полине, которая рассказала мне про странное поведение своей питоновской программы и тем самым подсказала потрясающую идею для сервиса на CTF. <\/i><\/p>\n<p>Всё началось месяца полтора назад. Полина рассказала мне, как она со своим начальником долго искала проблему в скрипте, который всего-навсего читал большой юникодный файл и как-то его обрабатывал. Проблема заключалась в том, что в файле было, например, 4 миллиона строк, а объектов в итоге оказывалось на два больше — 4 000 002. Это при том, что файл обрабатывался стандартной для питона конструкцией:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">import codecs\n\nwith codecs.open(&#039;file.txt&#039;, &#039;r&#039;, &#039;utf-8&#039;) as f:\n    for line in f:\n        # Обрабатываем строчку line<\/code><\/pre><p>Я никак не мог за такое не ухватиться. Расспросил Полину подробно, выяснил, что ничего стороннего для работы с файлом не использовалось, и вообще конструкция была проста как топор. Откуда она берёт лишние строчки?<\/p>\n<p>Пришёл домой и сразу сел проверять:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">import codecs\n\nwith codecs.open(&#039;file.txt&#039;, &#039;r&#039;, &#039;utf-8&#039;) as f:\n    print(len(f.readlines()))<\/code><\/pre><p>Попробовал на нескольких файлах и всё, конечно, работает верно. Но Полина упоминала, что в её файле были какие-то <i>плохие символы<\/i>, из-за которых и возникали лишние строчки. Я решил сгенерировать файл с кучей случайных юникодных символов:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">import codecs\nimport random\n\ndef generate_string():\n    &quot;&quot;&quot;\n    Генерируем строчку случайных символов длины 100.\n    Специально обходим символы с кодами 10 и 13, чтобы строка не содержала переводов строк\n    &quot;&quot;&quot;\n    return &#039;&#039;.join(chr(random.randint(20, 10000)) for _ in range(100))\n\nwith codecs.open(&#039;file.txt&#039;, &#039;w&#039;, &#039;utf-8&#039;) as f:\n    # Печатаем в файл 1000 строк\n    for i in range(1000):\n        f.write(generate_string() + &#039;\\n&#039;)<\/code><\/pre><p>На всякий случай открываю файл в Фаре. Его немножко корёжит, но строчек он показывает ровно 1001, что абсолютно верно, ведь в файле 1000 переводов строк:<\/p>\n<div class=\"e2-text-picture\">\n<img src=\"https:\/\/andgein.ru\/blog\/pictures\/2017-05-14_23-42-40.png\" width=\"1365\" height=\"717\" alt=\"\" \/>\n<\/div>\n<p>Запустил скрипт и удивился: он видит в файле 1076 строчек, а вовсе не 1000 и не 1001, как можно было бы предположить. Разобравшись и сгенерировав файл поменьше, нашёл тот самый символ, который всё портит. Им оказался символ с кодом 8233 — <a href=\"http:\/\/www.fileformat.info\/info\/unicode\/char\/2029\/index.htm\">Paragraph Separator<\/a>. Рядом с ним есть ещё один такой же символ — <a href=\"http:\/\/www.fileformat.info\/info\/unicode\/char\/2028\/index.htm\">Line Separator<\/a>, он имеет код 8232. И если подумать, то нет ничего странного, что с точки зрения модуля codecs в файле за этими символами начинаются новые строки.<\/p>\n<p>Кстати, новый open() в третьем питоне сам умеет читать файлы в UTF-8, модуль codecs можно не использовать. Но в данном случае он ведёт себя иначе:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">with open(&#039;file.txt&#039;, &#039;r&#039;, encoding=&#039;utf-8&#039;) as f:\n    print(len(f.readlines()))<\/code><\/pre><p>На том же самом файле этот код выводет 1000. Такая разница в поведении уже кажется странной и неприятной, но давайте вернёмся к коду с модулем codecs и копнём поглубже.<\/p>\n<p>В юникоде есть символы, которые заставляют модуль codecs думать, что в файле началась новая строка. Это же отличное место для модифицированной <a href=\"https:\/\/www.owasp.org\/index.php\/CRLF_Injection\">CRLF-инъекции<\/a>! Правда, в данном случае она будет скорее ParagraphSeparator-инъекцией, но сути это не меняет. Представим код, который сохраняет пользовательские строчки в файл, одну за другой. Чтобы злоумышленник не мог повлиять на структуру файла, из строчек выкидываются все символы ‘\\r’ и ‘\\n’. Раньше мы могли думать, что мы в безопасности, но теперь мы знаем — злоумышленник может использовать Paragraph Separator или Line Separator, чтобы повлиять на структуру файла.<\/p>\n<h2>Приглашаем на наш праздник CSV<\/h2>\n<p>Ну что ж, разобрались с Paragraph Separator. Теперь пора на основе этой <i>фичи<\/i> вытворить что-нибудь совсем интересное. Наш следующий скрипт будет сохранять юникодные данные в CSV-файл, а другой — считывать эти данные строчка за строчкой. Включаем питоновский модуль <a href=\"https:\/\/docs.python.org\/3.5\/library\/csv.html\">csv<\/a> и экспериментируем:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">import codecs\nimport csv\n\nwith codecs.open(&#039;file.txt&#039;, &#039;w&#039;, &#039;utf-8&#039;) as f:\n    writer = csv.DictWriter(f, fieldnames=[&#039;first&#039;, &#039;second&#039;])\n    writer.writeheader()\n    writer.writerow({&#039;first&#039;: &#039;Hello world&#039;, &#039;second&#039;: &#039;Text with\\n newline&#039;})<\/code><\/pre><p>В полученном файле оказывается три строки:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">first,second\nHello world,&quot;Text with\n newline&quot;<\/code><\/pre><p>Умный DictWriter поставил кавычки в нужных местах, и теперь симметричный ему DictReader отлично считает эти данные:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">import codecs\nimport csv\n\nwith codecs.open(&#039;file.txt&#039;, &#039;r&#039;, &#039;utf-8&#039;) as f:\n    reader = csv.DictReader(f)\n    for row in reader:\n        print(row)<\/code><\/pre><p>Выводит то, что надо, отлично:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">{&#039;first&#039;: &#039;Hello world&#039;, &#039;second&#039;: &#039;Text with\\n newline&#039;}<\/code><\/pre><p>Начинаем вставлять везде где ни попадя Paragraph Separator:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">writer.writerow({&#039;first&#039;: &#039;Hello world&#039;, &#039;second&#039;: &#039;Text with&#039; + chr(8233) + &#039; paragraph separator&#039;})<\/code><\/pre><p>Внезапно на выходе получаем файл без кавычек. DictWriter не считает этот символ чем-то опасным:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">first,second\nHello world,Text with\u2029 paragraph separator<\/code><\/pre><p>Ну что ж, натравим теперь на этот файл DictReader. В первый раз не мог поверить своим глазам, если честно:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">{&#039;first&#039;: &#039;Hello world&#039;, &#039;second&#039;: &#039;Text with\\u2029&#039;}\n{&#039;first&#039;: &#039; paragraph separator&#039;, &#039;second&#039;: None}<\/code><\/pre><p>То есть DictReader повёл себя несимметрично по отношению к DictWriter’у — сохраняли одну строчку, а получили две! Пользователь, влияющий на данные во втором поле первой строки, смог повлиять на первое поле во второй строке.<\/p>\n<h2>Кульминация<\/h2>\n<p>Собираем всё вместе и задаём вопрос знатокам питона:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">import codecs\nimport csv\n\ndata = {&#039;first&#039;: &#039;...&#039;, &#039;second&#039;: &#039;...&#039;}\n\nwith codecs.open(&#039;file.txt&#039;, &#039;w&#039;, &#039;utf-8&#039;) as f:\n    writer = csv.DictWriter(f, fieldnames=data.keys())\n    writer.writeheader()\n    writer.writerow(data)\n\ncount = 0\nwith codecs.open(&#039;file.txt&#039;, &#039;r&#039;, &#039;utf-8&#039;) as f:\n    reader = csv.DictReader(f)\n    for row in reader:\n        count += 1\n\nprint(count)<\/code><\/pre><p>Каким может быть вывод переменной count в конце программы?<\/p>\n<p>Теперь-то мы знаем, что абсолютно любым — хоть 1, хоть 30, хоть 100. Например, инициализировав переменную data так:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">P_SEP = chr(8233)\ndata = {&#039;first&#039;: P_SEP * 10, &#039;second&#039;: P_SEP * 10}<\/code><\/pre><p>получим ответ 20.<\/p>\n<h2>Известно ли про это что-нибудь миру?<\/h2>\n<p>В документации к модулю csv написано: если вы используете csv.reader(), открывайте файл с опцией newline=’’:<\/p>\n<div class=\"e2-text-picture\">\n<img src=\"https:\/\/andgein.ru\/blog\/pictures\/2017-05-15_00-49-29.png\" width=\"1084\" height=\"101\" alt=\"\" \/>\n<\/div>\n<div class=\"e2-text-picture\">\n<img src=\"https:\/\/andgein.ru\/blog\/pictures\/2017-05-15_01-09-05.png\" width=\"1058\" height=\"130\" alt=\"\" \/>\n<\/div>\n<p>Но, во-первых, мы используем не простой csv.reader(), а более умный csv.DictReader(), а, во-вторых, модуль codecs не поддерживает опцию newline, мы просто не сможем открыть файл с ней.<\/p>\n<p>Интернет про эту проблему мне тоже ничего не рассказал. Но, может, я просто плохо искал?..<\/p>\n<p><i>В <a href=\"\/blog\/all\/2-phdays-ctf-2017-service\">следующей заметке<\/a> я рассказал, как из этого получился отличный сервис для PHDays CTF.<\/i><\/p>\n",
            "date_published": "2017-05-14T19:49:57+01:00",
            "date_modified": "2017-11-19T14:00:40+01:00",
            "tags": [
                "csv",
                "python",
                "unicode",
                "программирование"
            ],
            "image": "https:\/\/andgein.ru\/blog\/pictures\/2017-05-14_23-42-40.png",
            "_date_published_rfc2822": "Sun, 14 May 2017 19:49:57 +0100",
            "_rss_guid_is_permalink": "false",
            "_rss_guid": "1",
            "_e2_data": {
                "is_favourite": true,
                "links_required": [
                    "highlight\/highlight.js",
                    "highlight\/highlight.css"
                ],
                "og_images": [
                    "https:\/\/andgein.ru\/blog\/pictures\/2017-05-14_23-42-40.png",
                    "https:\/\/andgein.ru\/blog\/pictures\/2017-05-15_00-49-29.png",
                    "https:\/\/andgein.ru\/blog\/pictures\/2017-05-15_01-09-05.png"
                ]
            }
        }
    ],
    "_e2_version": 4134,
    "_e2_ua_string": "Aegea 11.3 (v4134)"
}