3 заметки с тегом

python

Заметки про язык программирования питон.

Заметка пятая. Разбор задания Crypto Backdoor с Google CTF 2017

Это заметка о том, как мы с Костей Плотниковым решали задание на ассиметричную криптографию с Google CTF, который прошёл неделю назад. Она кишит кодом на питоне, несложными терминами из теории групп и математическими выкладками. Смело пропускайте, если боитесь чего-нибудь из этого.

Формулировка как всегда бесконечно расплывчата:

This public-key cryptosystem has a flaw. Can you exploit it? crypto_backdoor.py

Костя попробовал меня ввести в курс дела, когда я присоединился к нему. Он рассказал, что в скрипте реализовано что-то вроде эллиптической криптографии. Работает она так: сначала на плоскости рисуется специальная кривая, а затем для каждой пары точек на ней определяется операция сложения. Сумма двух точек с кривой тоже лежит на кривой за исключением случая, когда получается особое значение — ноль. После этого естественным образом определяется умножение точки на натуральное число.

В эллиптической криптографии Боб, желающий получать зашифрованные сообщения от Алисы, выбирает секретное число $N$ и точку на эллиптической кривой $g$. Последняя называется генератором и сообщается всем желающим, а вот секретное число становится закрытым ключом Боба. Открытым ключом в этом случае называется произведение генератора и закрытого ключа; $B = Ng$.

Собственно, на мысли об эллиптических кривых Костю натолкнули наличие в скрипте точки-генератора и двух открытых ключей:

# Modulus
p = 606341371901192354470259703076328716992246317693812238045286463
# g is the generator point.
g = (160057538006753370699321703048317480466874572114764155861735009, 255466303302648575056527135374882065819706963269525464635673824)
# Alice's public key A:
A = (460868776123995205521652669050817772789692922946697572502806062, 263320455545743566732526866838203345604600592515673506653173727)
# Bob's public key B:
B = (270400597838364567126384881699673470955074338456296574231734133, 526337866156590745463188427547342121612334530789375115287956485)

Модуль $p$ здесь тоже неслучаен — в эллиптической криптографии как раз рассматриваются кривые над полем $\mathbb{Z}_p$. Позже, правда, мы пришли к выводу, что эллиптическая криптография тут совсем ни при чём... Но сначала мы внимательно изучили операцию сложения двух точек:

def add(a, b, p):
  if a == -1:
    return b
  if b == -1:
    return a
  x1, y1 = a
  x2, y2 = b
  x3 = ((x1*x2 - x1*y2 - x2*y1 + 2*y1*y2) * modinv(x1 + x2 - y1 - y2 - 1, p)) % p
  y3 = ((y1*y2) * modinv(x1 + x2 - y1 - y2 - 1, p)) % p
  return (x3, y3)

Нейтральный элемент (он же ноль) обозначен как $-1$, поэтому первые четыре строки функции очевидны. Функция $modinv(x, p)$ находит обратный элемент к $x$ в кольце $\mathbb{Z}_p$ с помощью расширенного алгоритма Евклида. Значит, сумма точек $(x_1, y_1)$ и $(x_2, y_2)$ это точка
$$\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)$$

Дробь означает целочисленное деление в кольце $\mathbb{Z}_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$. Если переписать операцию сложения в новой системе координат, то получится

$$(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)$$

Получившаяся формула в некотором смысле даже симметрична. Это дало нам оптимизм на несколько следующих часов.

Мастер-секрет

Однако в скрипте само по себе сложение нигде не используются. Зато используется умножение точки на число:

from secret_data import aliceSecret, bobSecret, flag

assert A == mul(aliceSecret, g, p)
assert B == mul(bobSecret, g, p)

aliceMS = mul(aliceSecret, B, p)
bobMS = mul(bobSecret, A, p)
assert aliceMS == bobMS
masterSecret = aliceMS[0]*aliceMS[1]

Настало время разобраться, что вообще происходит в скрипте и что нужно найти.

$aliceSecret$ — это натуральное число, закрытый ключ Алисы, он умножается на известный нам генератор, и в результате получается известный нам открытый ключ Алисы. Аналогичное проделывается с ключами Боба. После этого открытый ключ Боба умножается на закрытый ключ Алисы, получая точку $aliceMS = aliceSecret \times bobSecret \times g$. Симметричная операция вычисляет $bobMS = bobSecret \times aliceSecret \times g$. Очевидно, что эти две точки должны совпасть, что и проверяется последним assert’ом. Мастер-секретом объявляется произведение координат этой общей точки. Этот мастер-секрет и надо найти, так как в конце скрипта он ксорится с флагом:

def encrypt(message, key):
  return message ^ key

length = len(flag)
encrypted_message = encrypt(I(flag), masterSecret)
print "length = %d, encrypted_message = %d" % (length, encrypted_message)
# length = 31, encrypted_message = 137737300119926924583874978524079282469973134128061924568175107915062758827931077214500356470551826348226759580545095568667325

Умножение в новых координатах

Раз для подсчёта мастер-секрета используется умножение, то вернёмся к нашим формулам и выясним, как точка в новых координатах $(t, y)$ умножается на число $k$. Переберём несколько маленьких коэффициентов:

$$2(t, y) = (t, y) + (t, y) = \left(\frac{t^2}{2t-1}, \frac{y^2}{2t-1}\right)$$

$$3(t, y) = 2(t, y) + (t, y) = \left(\frac{t^2}{2t-1}, \frac{y^2}{2t-1}\right) + (t, y) =
\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) =
\left(\frac{t^3}{3t^2-3t+1}, \frac{y^3}{3t^2-3t+1}\right)$$

$$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) =
\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) =
\left(\frac{\frac{t^4}{2t-1}}{2t^2-2t+1}, \frac{\frac{y^4}{2t-1}}{2t^2-2t+1}\right) =
\left(\frac{t^4}{4t^3-6t^2+4t-1}, \frac{y^4}{4t^3-6t^2+4t-1}\right) $$

Умножать дальше становилось всё сложнее, поэтому пора найти закономерность. В числителях всё время получается $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$.

Итоговую формулу

$$k \times (t, y) = \left(\frac{t^k}{(t+1)^k — t^k}, \frac{y^k}{(t+1)^k — t^k}\right)$$

теперь можно доказать по индукции по $k$. Делать я этого, конечно же, не буду.

Решение

Задача будет решена, если мы узнаем закрытый ключ Алисы или Боба. В случае с Бобом нам достаточно найти такое $k \in \mathbb{Z}_p$, что $kg = B$. В наших новых координатах и формулах это выглядит так:

$$\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)$$

где $(g_t, g_y)$ — координаты генератора $g$ в системе $(t, y)$, а $(B_t, B_y)$ — аналогичные координаты точки $B$. Взяв из этого равенства первую координату, получаем:

$$ \frac{g_t^k}{(g_t+1)^k — g_t^k} = B_t$$

$$g_t^k = B_t ((g_t+1)^k — g_t^k)$$

$$g_t^k (1 + B_t) = B_t (g_t+1)^k$$

$$\left(\frac{g_t}{g_t+1}\right)^k = \frac{B_t}{1 + B_t}$$

Чтобы найти искомое $k$, достаточно вычислить логарифм в кольце $\mathbb{Z}_p$, то есть решить задачу дискретного локарифмирования. Здесь мы с Костей приуныли, потому что поняли, что зашли в тупик. Дискретное логарифмирование — задача, которую нельзя решить за нормальное время.

Только через час Костя догадался проверить данный нам модуль $p$ на простоту. Совершенно неожиданно он оказался составным:

$$p = 961236149 \times 951236179 \times 941236273 \times 911236121 \times 931235651 \times 921236161 \times 901236131$$

Наверняка все знают, как посчитать дискретный логарифм по непростому основанию. А мы не знаем. Так что мы взяли бумажку и стали придумывать алгоритм.

Когда-то Асанов рассказывал байку, что студенты УПИ обычно знают способ решить задачу, а студенты матмеха не знают. Зато студенты матмеха могут придумать решение. Кажется, теперь я понял эту байку.

Дискретный логарифм по составному основанию

Пусть мы нашли дискретный логарифм от $b$ по основанию $a$ в кольцах $\mathbb{Z}_p$ и $\mathbb{Z}_q$. То есть мы нашли такие $n$ и $m$, что

$$a^n \equiv b \pmod{p}$$
$$a^m \equiv b \pmod{q}$$

Теперь мы хотим решить задачу в кольце $\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$.

Ну а найти такое число — дело техники и расширенного алгоритма Евклида. Если $n + ?u = m + ?v$, то $?u — ?v = m — n$. Если $m-n$ не делится на $НОД(u, v)$, то решения нет, иначе расширенный алгоритм Евклида решит это линейное диофантово уравнение, и всё станет хорошо.

Так как данный в задании модуль $p$ мы разложили на простые множители $p_1 \times p_2 \times \dots \times p_7$, которые к тому же получились не очень большими, то мы можем решить задачу дискретного логарифмирования в каждом из $\mathbb{Z}_{p_i}$. Соединить семь чисел в один большой ответ поможет описанный только что алгоритм.

Как решить дискретный логарифм для  $p_i$

Простые делители модуля $p$ были не очень большими, но и не настолько маленькими, чтобы дискретный логарифм можно было найти простым перебором. К счастью, есть алгоритм Baby Steps Giant Steps, который позволяет сделать это намного быстрее — за $O(\sqrt{n})$. Его мы и реализовали. Да, мы думали о том, что Baby Steps Giant Steps уже реализован в куче библиотек, но лично меня это только раззадоривает — так интересно ведь всё сделать самому.

Как найти порядок элемента в кольце

На часах было уже около часа ночи, а мне предстояло запрограммировать на питоне поиск порядка элемента в кольце $\mathbb{Z}_p$. Теорема Эйлера шептала, что $x^{\phi(p)} \equiv 1 \pmod{p}$, но $\phi(p)$ могло оказаться не минимальным числом с таким свойством. Значит, искомый порядок — это делитель $\phi(p)$. Но делителей слишком много, чтобы перебирать их все. Так что пришла пора узнать более быстрый способ находить порядок элемента. На помощь пришла пдфка из интернета, в которой есть чудесный алгоритм 4.79, я реализовал его и научился быстро находить порядок элемента в кольце, зная разложение на простые множители у $\phi(p)$.

Заключение

Применив всю магию сверху, мы нашли закрытый ключ Боба $bobSecret$. Умножив его на открытый ключ Алисы, мы нашли мастер-секрет, который и выдал нам флаг:

Master secret found: (254828745614253797280016043417264027645246572307317271091197847, 540509273347153402828726537667691800163306365090607497812000946)
Flag: CTF{Anyone-can-make-bad-crypto}

Если вкратце повторить всё наше решение, то оно перестаёт казаться страшным и длинным:

  1. переходим в систему координат $(t, y)$,
  2. вычисляем $a = \frac{g_t}{g_t+1}$ и $b = \frac{B_t}{1 + B_t}$,
  3. решаем задачу дискретного логарифма $a^{?} = b$ в кольце $\mathbb{Z}_p$, зная разложение $p$ на простые множители,
  4. умножаем полученный ответ на открытый ключ Алисы $A$, это и есть мастер-секрет,
  5. переходим обратно в координаты $(x, y)$, перемножаем координаты мастер-секрета, расшифровываем флаг.
 Нет комментариев    21   2017   crypto   CTF   math   python   writeup

Заметка вторая. О сервисе на PHDays CTF

Продолжение истории о необычном поведении юникода и CSV в питоне

Для тех, кому лень читать предыдущую заметку или вспоминать, о чём там было

Если использовать стандартные питоновские codecs.open, csv.DictWriter и csv.DictReader, то можно столкнуться с интересным поведением. Создаём в программе файл в кодировке UTF-8, пишем туда с помощью DictWriter, а затем читаем через DictReader. Если в данных встречались юникодные символы Pararaph separator или Line separator, то мы считаем больше записей, чем было записано, а их CSV-структура будет поломана.

Читайте первую заметку для подробностей.

Как из этого получился сервис для классического CTF

В апреле мы с ребятами из Хакердома как раз готовили онлайновый CTF для форума PHDays. Темой был выбран интернет вещей, а сервисами были умный чайник, термометр, дверной замок, телевизор и даже холодильник. Мне достался последний, потому что я слишком люблю еду.

Чтобы органично встроить уязвимость в сервис, мне нужно было сделать так, чтобы кто-то писал в CSV-файл, а кто-то другой — читал. В итоге сервис состоял из двух частей — веб-приложения для удобного управления человеком и API для других умных кухонных гаджетов, которым нужна информация от холодильника.

Веб-интерфейс позволял пользователям регистрироваться и создавать холодильные камеры или просто холодильники. У каждого холодильника был владелец, и увидеть чужие просто так нельзя. В холодильники можно добавлять еду. Для этого сначала было необходимо зарегистрировать новый продукт (например, картошку или молоко) и указать, в чём он измеряется — в граммах, пачках или литрах. Выглядело это так:

Кроме холодильников можно было создавать рецепты. Про каждый ингредиент рецепта известно, сколько и какого продукты нужно положить, а также что с ним надо сделать и сколько после этого подождать.

Рецепты были очень важны для функционирования сервиса, ведь в том самом API было всего две команды — получить список твоих холодильников и получить список рецептов, которые можно приготовить из еды, лежащей в одном из твоих холодильников. Звучит сложно, но идея очень простая — если у вас есть умная мультиварка, то она хочет узнать, какие блюда можно сегодня приготовить из продуктов, лежащих у вас в холодильнике.

Принадлежность выдаваемых рецептов владельцу холодильника в API не проверялась, но должно было работать само: в рецепте должен присутствовать хотя бы один продукт из холодильника, а в холодильник мы можем добавлять только принадлежащие нам продукты. Моё молоко и молоко Васи — два разных продукта, я могу добавить в холодильники и рецепты только первое, а про второе даже не смогу узнать.

Уязвимость

Итак, где же тут наши подозреваемые — юникод и CSV?

Сервис API не имеет доступа к базе данных, поэтому информация для него складывалась веб-приложением в специальные CSV-файлы, откуда считывались API-приложением раз в секунду. Вот пример такого файла:

id,recipe_id,food_type_id,what_to_do,count,pause_after
1,10,15,Yhws aqx vpjhtlyhw ruv tbcyis,11,7
2,11,16,Ok jbso gtpzs ndgoz udeksmvk,10,16
3,12,17,Y ap mculltvedfwwabbnnnco um,6,19
4,13,18,cniyvdjsyuctaamupp zm  qj nwvm,10,9
5,14,19,Kfdvm ref wtb pdtitb,14,15

В нём хранятся ингредиенты рецептов. Столбцы, соответственно — id ингредиента, id рецепта (сами рецепты лежат в другом файле), id продукта, что нужно сделать, сколько взять продукта и какую выдержать после этого паузу.

Давайте посмотрим, что будет, если в поле what_to_do добавить тот самый Paragraph separator:

6,15,20,blablabla
13503,14,20

При чтении этот файл будет выглядеть для DictReader’а как

6,15,20,blablabla

13503,14,20

То есть так, будто мы добавили продукт №20 в рецепт №14. Продукт №20 принадлежит нам, значит, мы смогли добавить нашу еду в чужой рецепт №14! Теперь API сможет вывести этот рецепт, если в каком-нибудь из наших холодильников будет лежать продукт №20.

Для полноты картины покажу, как выглядели сохранение и загрузка данных в CSV.

Сохранение:

def dump_model_to_file(model, filename):
    # Use Django API to get all model fields
    columns = [field.attname for field in model._meta.fields]

    with codecs.open(filename, 'w', encoding='utf-8') as opened_file:
        # Open csv writer and dump header: special row with columns names
        writer = csv.DictWriter(opened_file, fieldnames=columns)
        writer.writeheader()

        # Iterate over all objects of the model
        for obj in model.objects.all():
            object_dict = {}
            for column in columns:
                # Don't worry about newlines (\n and \r): csv.DictWriter will enclose such strings in quotes (")
                # So I think there is no vulnerability here
                object_dict[column] = str(getattr(obj, column, ''))

            # Dump dictionary for current object
            writer.writerow(object_dict)

Загрузка:

class Model:
    def __init__(self, dictionary):
        for key, value in dictionary.items():
            if value is None:
                value = '0'
            if value.isnumeric():
                value = int(value)
            setattr(self, key, value)


def load_models_from_file(filename):
    objects = {}
    with codecs.open(filename, 'r', encoding='utf-8') as opened_file:
        reader = csv.DictReader(opened_file)
        for row in reader:
            objects[model.id] = Model(row)
    return objects

Ещё две уязвимости

В Холодильнике мной была заложена ещё одна уязвимость. Но так получилось, что в итоге уязвимостей оказалось не две, а три. Так бывает на CTF, и в этом нет ничего страшного. Иногда бывает обидно, что ты заложил сложную уязвимость, а случайно оставил простую. Но в данном случае всё случилось удачно: незапланированная уязвимость была проще первой, а запланированная — совсем элементарной (правда, позволяла украсть только 20% флагов). Так как в целом соревнование получилось очень сложным, то появление одной незапланированной уязвимости средней сложности сыграло нам на руку.

Итак, сначала о запланированной уязвимости. Каждый сервис находился в своём докер-контейнере. Докер (docker) — это удобный способ изолировать своё приложение от других, в линуксе работает за счёт его фирменных LXC-контейнеров и ограничений в cgroup. Подробнее о докере можно почитать на официальном сайте.

Мой сервис состоял из четырёх докер-контейнеров: для веб-приложения, для API-приложения, для базы данных и для веб-сервера nginx. Во время старта первого накатывались миграции, собиралась статика и выполнялись другие служебные команды. В том числе такая:

# DON'T RUN IT IN PRODUCTION. SOME EVIL GUYS CAN BRUTEFORCE PASSWORD AND WHO KNOW WHAT HAPPENS...
echo "[+] [DEBUG] Django setup, executing: add superuser"
PGPASSWORD=${POSTGRES_PASSWORD} psql -U ${POSTGRES_USER} -h ${POSTGRES_HOST} -c "INSERT INTO auth_user (password, last_login, is_superuser, username, first_name, last_name, email, is_staff, is_active, date_joined) VALUES ('pbkdf2_sha256\$36000\$k36V24q60mNo\$v5og9qcgc2sqkVwGjZDKNK+wcJy60ix8DIt9E8Yg48c=', '1970-01-01 00:00:00.000000', true, 'admin', 'admin', 'admin', 'admin@admin', true, true, '1970-01-01 00:00:00.000000') ON CONFLICT (username) DO NOTHING"

Эта команда добавляет напрямую в базу данных супер-пользователя с логином admin. Его пароль мы не знаем, так что сразу зайти под ним не можем, но доступен хеш от пароля: ’pbkdf2_sha256$36000$k36V24q60mNo$v5og9qcgc2sqkVwGjZDKNK+wcJy60ix8DIt9E8Yg48c=’. Подбор пароля не занимает много времени, так как он словарный и встречается во всех списках самых частых паролей.

Попрактикуйтесь — сможете ли вы подобрать пароль? pbkdf2_sha256 — это тип хеша и подписи, а 36000 — количество итераций. Справиться с задачей поможет hashcat, john the ripper или любой другой подборщик прообразов хешей.

Незапланированная уязвимость

Последняя уязвимость нашлась в функции добавлении продукта в холодильник. Здесь не проверялось, что вы являетесь владельцем добавляемого продукта. Можно было создать супер-холодильник, содержащий все продукты с номерами от 1 до 1000, а затем попросить API выдать рецепты, содержащие хотя бы какой-нибудь продукт из этого холодильника. Конечно, он находил и чужие рецепты, а вместе с ними выдавал и флаги, хранящиеся в описаниях этих рецептов.

Выводы

Никогда не используйте csv.DictReader/csv.DictWriter вместе с файлами, открытыми модулем codecs. В новых питонах открывайте CSV-файлы с помощью стандартной функции open, передавая ей аргументы encoding и newline.

Бонус для дочитавших до конца

Все исходники сервиса, докер-файлы, чекер для проверяющей системы и мой авторский эксплойт для первой уязвимости можно найти в репозитории разработки, который мы открыли сразу после окончания соревнования.

Заметка первая. Про необычное поведение юникода и CSV в питоне

Посвящается Полине, которая рассказала мне про странное поведение своей питоновской программы и тем самым подсказала потрясающую идею для сервиса на CTF.

Всё началось месяца полтора назад. Полина рассказала мне, как она со своим начальником долго искала проблему в скрипте, который всего-навсего читал большой юникодный файл и как-то его обрабатывал. Проблема заключалась в том, что в файле было, например, 4 миллиона строк, а объектов в итоге оказывалось на два больше — 4 000 002. Это при том, что файл обрабатывался стандартной для питона конструкцией:

import codecs

with codecs.open('file.txt', 'r', 'utf-8') as f:
    for line in f:
        # Обрабатываем строчку line

Я никак не мог за такое не ухватиться. Расспросил Полину подробно, выяснил, что ничего стороннего для работы с файлом не использовалось, и вообще конструкция была проста как топор. Откуда она берёт лишние строчки?

Пришёл домой и сразу сел проверять:

import codecs

with codecs.open('file.txt', 'r', 'utf-8') as f:
    print(len(f.readlines()))

Попробовал на нескольких файлах и всё, конечно, работает верно. Но Полина упоминала, что в её файле были какие-то плохие символы, из-за которых и возникали лишние строчки. Я решил сгенерировать файл с кучей случайных юникодных символов:

import codecs
import random

def generate_string():
    """
    Генерируем строчку случайных символов длины 100.
    Специально обходим символы с кодами 10 и 13, чтобы строка не содержала переводов строк
    """
    return ''.join(chr(random.randint(20, 10000)) for _ in range(100))

with codecs.open('file.txt', 'w', 'utf-8') as f:
    # Печатаем в файл 1000 строк
    for i in range(1000):
        f.write(generate_string() + '\n')

На всякий случай открываю файл в Фаре. Его немножко корёжит, но строчек он показывает ровно 1001, что абсолютно верно, ведь в файле 1000 переводов строк:

Запустил скрипт и удивился: он видит в файле 1076 строчек, а вовсе не 1000 и не 1001, как можно было бы предположить. Разобравшись и сгенерировав файл поменьше, нашёл тот самый символ, который всё портит. Им оказался символ с кодом 8233 — Paragraph Separator. Рядом с ним есть ещё один такой же символ — Line Separator, он имеет код 8232. И если подумать, то нет ничего странного, что с точки зрения модуля codecs в файле за этими символами начинаются новые строки.

Кстати, новый open() в третьем питоне сам умеет читать файлы в UTF-8, модуль codecs можно не использовать. Но в данном случае он ведёт себя иначе:

with open('file.txt', 'r', encoding='utf-8') as f:
    print(len(f.readlines()))

На том же самом файле этот код выводет 1000. Такая разница в поведении уже кажется странной и неприятной, но давайте вернёмся к коду с модулем codecs и копнём поглубже.

В юникоде есть символы, которые заставляют модуль codecs думать, что в файле началась новая строка. Это же отличное место для модифицированной CRLF-инъекции! Правда, в данном случае она будет скорее ParagraphSeparator-инъекцией, но сути это не меняет. Представим код, который сохраняет пользовательские строчки в файл, одну за другой. Чтобы злоумышленник не мог повлиять на структуру файла, из строчек выкидываются все символы ’\r’ и ’\n’. Раньше мы могли думать, что мы в безопасности, но теперь мы знаем — злоумышленник может использовать Paragraph Separator или Line Separator, чтобы повлиять на структуру файла.

Приглашаем на наш праздник CSV

Ну что ж, разобрались с Paragraph Separator. Теперь пора на основе этой фичи вытворить что-нибудь совсем интересное. Наш следующий скрипт будет сохранять юникодные данные в CSV-файл, а другой — считывать эти данные строчка за строчкой. Включаем питоновский модуль csv и экспериментируем:

import codecs
import csv

with codecs.open('file.txt', 'w', 'utf-8') as f:
    writer = csv.DictWriter(f, fieldnames=['first', 'second'])
    writer.writeheader()
    writer.writerow({'first': 'Hello world', 'second': 'Text with\n newline'})

В полученном файле оказывается три строки:

first,second
Hello world,"Text with
 newline"

Умный DictWriter поставил кавычки в нужных местах, и теперь симметричный ему DictReader отлично считает эти данные:

import codecs
import csv

with codecs.open('file.txt', 'r', 'utf-8') as f:
    reader = csv.DictReader(f)
    for row in reader:
        print(row)

Выводит то, что надо, отлично:

{'first': 'Hello world', 'second': 'Text with\n newline'}

Начинаем вставлять везде где ни попадя Paragraph Separator:

writer.writerow({'first': 'Hello world', 'second': 'Text with' + chr(8233) + ' paragraph separator'})

Внезапно на выходе получаем файл без кавычек. DictWriter не считает этот символ чем-то опасным:

first,second
Hello world,Text with
 paragraph separator

Ну что ж, натравим теперь на этот файл DictReader. В первый раз не мог поверить своим глазам, если честно:

{'first': 'Hello world', 'second': 'Text with\u2029'}
{'first': ' paragraph separator', 'second': None}

То есть DictReader повёл себя несимметрично по отношению к DictWriter’у — сохраняли одну строчку, а получили две! Пользователь, влияющий на данные во втором поле первой строки, смог повлиять на первое поле во второй строке.

Кульминация

Собираем всё вместе и задаём вопрос знатокам питона:

import codecs
import csv

data = {'first': '...', 'second': '...'}

with codecs.open('file.txt', 'w', 'utf-8') as f:
    writer = csv.DictWriter(f, fieldnames=data.keys())
    writer.writeheader()
    writer.writerow(data)

count = 0
with codecs.open('file.txt', 'r', 'utf-8') as f:
    reader = csv.DictReader(f)
    for row in reader:
        count += 1

print(count)

Каким может быть вывод переменной count в конце программы?

Теперь-то мы знаем, что абсолютно любым — хоть 1, хоть 30, хоть 100. Например, инициализировав переменную data так:

P_SEP = chr(8233)
data = {'first': P_SEP * 10, 'second': P_SEP * 10}

получим ответ 20.

Известно ли про это что-нибудь миру?

В документации к модулю csv написано: если вы используете csv.reader(), открывайте файл с опцией newline=’’:

Но, во-первых, мы используем не простой csv.reader(), а более умный csv.DictReader(), а, во-вторых, модуль codecs не поддерживает опцию newline, мы просто не сможем открыть файл с ней.

Интернет про эту проблему мне тоже ничего не рассказал. Но, может, я просто плохо искал?..

В следующей заметке я рассказал, как из этого получился отличный сервис для PHDays CTF.