Позднее Ctrl + ↑

Заметка восьмая. TED-клуб, часть 2

Продолжаю рассказывать о видяшках, которые показывал этим летом на TED-клубе в ЛКШ.

Вторая встреча называлась «Математика, технологии и любовь». Объединил я их неслучайно: среди выбранных докладов были и рассказ о любви к математики (уверенно входит в топ-3 моих любимых выступлений всех времён), и видео о математике любви. В общем, смотрите сами.

Энди Йен: Думаете, ваша почта — личная? Подумайте ещё раз

Ребята хотят сделать шифрованную электронную почту. Здесь сложно придумать что-то новое, GPG существует уже двадцать лет. Но Энди Йен и его коллеги из ЦЕРНа постарались сделать удобную и простую в и использовании шифрованную электронную почту. Естественно, она по-прежнему гарантирует, что никто, кроме получателя, не прочитает ваш текст.

https://www.ted.com/talks/andy_yen_think_your_email_s_private_think_again?language=ru

Эдуардо Саэнц де Кабесон: Математика — это навсегда

Ох, это просто моя любовь. Харизматичный и чувственный итальянец (собственно, а какой он ещё может быть? Он же итальянец!) начинает с объяснения, зачем нужна математика, а заканчивает аналогией между бриллиантами и теоремами. Если вам лень смотреть все видео, посмотрите только это.

https://www.ted.com/talks/eduardo_saenz_de_cabezon_math_is_forever?language=ru

Анна Фрай: Математика любви

Что будет, если проанализировать кучу данных с сайтов знакомств современными математическими инструментами? Оказывается, всплывёт куча неожиданных выводов о том, как устроена любовь. Ну или по крайней мере о том, какой мы эту любовь сами себе представляем.

https://www.ted.com/talks/hannah_fry_the_mathematics_of_love?language=ru

Тасос Франзолас: Всё, что вы слышите в фильме — ложь

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

Звук — это язык. Он может обмануть нас, перенеся в другой конец света, может изменить наше настроение, может задать темп, может вызвать смех или испуг.

https://www.ted.com/talks/tasos_frantzolas_everything_you_hear_on_film_is_a_lie?language=ru

Терри Мур: Почему неизвестная обозначается как x?

Мини-расследование о том, почему именно букву x выбрали для обозначения неизвестного в математике. Всего 4 минуты, а все равно кайф:

https://www.ted.com/talks/terry_moore_why_is_x_the_unknown/transcript?language=ru

Тим Бернес-Ли: Конституция всемирной паутины

Тима Бернеса-Ли представлять, кажется, не надо: это один из главных авторов интернета. В своём выступлении он говорит о дальнейшем развитии веба и задаёт вопрос: каким мы сами хотим его видеть? Кроме того, рассуждает о государственной цензуре в интернете и дроблении всемирной паутины на части. Видео 2014 года, но спустя три года актуальность, по-моему, только увеличилась.

https://www.ted.com/talks/tim_berners_lee_a_magna_carta_for_the_web?language=ru

Майкл Рубинштейн: Увидеть неуловимое движение, услышать бесшумный звук. Здорово?

Потрясающее видео о том, как научились по микро-движениям на обычном видео измерять пульс человека. А ещё распознавать речь, усилив микроскопические движения от звуковых волн на видео лежащей на полу упаковки чипсов. Это выступление посоветовал мне Даня Рязановский, за что ему большое спасибо.

https://www.ted.com/talks/michael_rubinstein_see_invisible_motion_hear_silent_sounds_cool_creepy_we_can_t_decide?language=ru

Том Аглоу: Так мог бы выглядеть интернет без экрана

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

Человечеству нравятся простые инструменты. Ваш телефон — не очень простой инструмент. Вилка — простой инструмент.

https://www.ted.com/talks/tom_uglow_an_internet_without_screens_might_look_like_this?language=ru

Дэвид Иглмен: Можем ли мы создать для людей новые чувства?

Ещё одно видео, посоветованное Даней Рязановским. Нейробиолог Дэвид Иглмен делает достаточно необычную вещь: он подключает к человеческому телу новые периферийные устройства — нечто, что, как и обычные органы чувств вроде глаз, рта и носа, может отправлять электрические сигналы в мозг. В будущем это может добавить людям инфракрасное зрение, сонары или супер-чувствительный нос, а пока ребята развлекаются более простыми (но не менее интересными) вещами.

https://www.ted.com/talks/david_eagleman_can_we_create_new_senses_for_humans?language=ru

Ричард Браунинг: Как я построил джет-костюм

Большой мотивации выступление. На самом деле оно вовсе не о джет-костюме, оно о том, как не сдаваться и продолжать пробовать. При этом желательно не переставая верить в себя.

https://www.ted.com/talks/richard_browning_how_i_built_a_jet_suit?language=ru

На сегодня всё. Подписывайтесь, ставьте лайки. Об ещё двух встречах TED-клуба напишу попозже.

Заметка седьмая. TED-клуб

В этом году я провёл в Летней компьютерной школе четыре встречи TED-клуба. Клубы в ЛКШ — это такие нетематические мероприятия между обедом и ужином, цель которых — развлечь школьников и познакомить их с чем-нибудь новым. За все годы в ЛКШ была проведена сотня или две разных клубов.

Разносторонность преподавателей на самом деле поражает. В этом году мы провели (ух, приготовьтесь, сейчас будет перечисление на много строчек, можно вдохнуть воздуха и быстро-быстро прочитать): гитарный клуб, клубы изготовления браслетов и фенечек, клуб любителей Лего, клуб рисования пиксель-арта, клуб настольных ролевых игр (его, кстати, проводил школьник), школу юного покер-крупье, мастер-классы по баскетболу, волейболу и фрисби, фирменную серию клубов «... из ничего» от Калана Абе, клуб пои, клуб игры в Шляпу (а потом и клуб игры в Шляпу на английском языке), клуб аргентинского танго, вокальный кружок, кино-, аниме- и мюзикл-клубы, клуб рисования с натуры, клуб портретной фотографии, клуб изготовления объёмных звёздочек из бумаги, клуб языка эсперанто, клуб стрельбы из лука, клуб поэзии, клуб философии, клуб игры в преферанс, фестиваль Холи, клуб рисования 3D-ручкой и TED-клуб.

Выдохнули? Вот про последний из этих клубов я и хочу рассказать. Наверняка вы слышали о ежегодной конференции TED. Её миссия, как заявляют сами организаторы — распространение уникальных идей. Кроме собственно международной конференции во многих городах есть ещё небольшие местные аналоги — конференции TEDx.

Идея провести TED-клуб в ЛКШ появилась ещё в конце прошлого года: я тогда увлёкся просмотром записей докладов с TED и заметил, что некоторые из них настолько классные, что мне хочется делиться ними почти со всеми подряд. Потихоньку я отбирал понравившееся видео, и в итоге показал летом 8 часов субъективно на мой взгляд лучших из увиденных выступлений.

Каждая встреча TED-клуба предвещалась анонсом, в котором был поминутный план видео:

TED-сообщество дружелюбно перевело субтитры практически для всех видео, опубликованных на официальном сайте. Субтитры доступны на 40+ языках, в том числе на русском, так что с пониманием никаких проблем нет.

В этой и следующей заметке я хочу опубликовать список всех видео, которые я показал во время TED-клубов в ЛКШ. К каждому видео напишу аннотацию, чтобы заинтересовать вас перейти по ссылке и потратить от 5 до 15 минут на видео. Эти видео — отличный способ провести свободное время или занять свои глаза и уши во время завтрака. Ну а если какое-то не понравилось — просто переключайте на следующее :-)

Первая встреча TED-клуба была посвящена науке. Это одна из самых популярных тем на конференциях TED, на то они и конференции. У меня получился небольшой перекос в сторону астрономии и космонавтики, но в этом и смысл личной подборки: сюда попало то, что интереснее всего мне. Ну а доклады о математике и программировании я специально сюда не добавлял, для них была заготовлена вторая встреча клуба.

Джек Хорнер. Вырастим динозавра из курицы

Способ воскрешения динозавров, описанный в «Парке Юрского периода» нереалистичен: найти ДНК динозавра в окаменелых насекомых не получится. Зато можно взять курицу, выключить у её эмбриона некоторые гены, и получить животное, очень похожее на динозавров, живших миллионы лет назад. Этим Джек Хорнер и занимается.

https://www.ted.com/talks/jack_horner_building_a_dinosaur_from_a_chicken?language=ru

Латиф Нассер. Вы и не представляете, откуда на самом деле происходят верблюды

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

https://www.ted.com/talks/latif_nasser_you_have_no_idea_where_camels_really_come_from?language=ru

Даниэлла Фейнберг. Волшебный ингредиент, благодаря которому оживают фильмы Pixar

Даниэлла рассказывает о том, что меня жутко интересует последние лет пять: как делаются крутые полнометражные мультфильмы. Не обо всём сразу, конечно, а обо одной маленькой детали. И об использовании науки в производстве мультфильмов.

https://www.ted.com/talks/danielle_feinberg_the_magic_ingredient_that_brings_pixar_movies_to_life?language=ru

Грег Гейдж. Как своим мозгом контролировать чужую руку

Короткое видео, из которого я не узнал ничего нового. Зато увидел захватывающий своей простотой эксперимент: мужик подключает мозг девушки (на самом деле нерв под её локтём) к руке парня, и теперь ей достаточно подумать, чтобы пальцы на его руке задвигались.

https://www.ted.com/talks/greg_gage_how_to_control_someone_else_s_arm_with_your_brain?language=ru

Ейтор Бендер. Экзоскелеты для людей

Кажется, что это что-то из прекрасного будущего. Экзоскелеты, помогающие людям встать из инвалидных кресел, в которых они провели большую часть своей жизни. Не обошлось, правда, без военного применения для этих костюмов, но, видимо, без этого в США ребята бы просто не получили на исследования деньги.

https://www.ted.com/talks/eythor_bender_demos_human_exoskeletons?language=ru

Кэти Борман. Как сфотографировать чёрную дыру?

В общем-то в названии всё сказано. Сфотографировать чёрную дыру невозможно, потому что она поглощает весь свет, направленный на неё. Зато можно попробовать сфотографировать тень от горизонта событий чёрной дыры, находящейся в центре нашей Галактики. Однако для этого нужен телескоп размером с Землю...

https://www.ted.com/talks/katie_bouman_what_does_a_black_hole_look_like?language=ru

Аньяли Трипатхи. Почему Земля однажды будет выглядеть как Марс

Однажды наша планета станет сухой и красной — совсем как Марс. Но это будет нескоро, где-то через миллиард лет. А, может, через два, а, может, и через десять. Зачем же тогда изучать это сейчас? Аньяли объясняет.

https://www.ted.com/talks/anjali_tripathi_why_earth_may_someday_look_like_mars?language=ru

Табета Бояджян. Самая загадочная звезда во вселенной

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

https://www.ted.com/talks/tabetha_boyajian_the_most_mysterious_star_in_the_universe?language=ru

Калеб Харпер. Этот компьютер в будущем станет выращивать нашу еду

Достаточно экцентричное выступление мужика, который (не первый в этом мире) решил соорудить прибор, выращивающий еду по строгим рецептам из интернета: столько-то воды, столько-то удобрений, столько-то кислорода. Зачем-то он называет этот прибор компьютером, хотя, мне кажется, это лишнее. Сама идея тоже не нова, зато он уже достиг кое-каких результатов.

https://www.ted.com/talks/caleb_harper_this_computer_will_grow_your_food_in_the_future?language=ru

Русс Альтман. Что на самом деле происходит, когда вы смешиваете лекарства?

Самый кайф, как всегда, происходит на стыке наук. В данном случае взяли машинное обучение и медицину. В общем, выяснили, что некоторые лекарства нельзя принимать вместе, хотя раньше о них такого не знали. Медики и химики пока не нашли объяснение, почему так происходит, но, возможно, теперь врачи будут аккуратнее выписывать одновременно несколько лекарств. Заодно Русс Альтман затрагивает тему открытых медицинских данных, которые очень сложно достать в век повёрнутости на всеобщей приватности.

https://www.ted.com/talks/russ_altman_what_really_happens_when_you_mix_medications?language=ru

Про видео с остальных встреч TED-клуба напишу в следующей заметке.

Заметка шестая. Диалог выбора папки

Если вы программируете пользовательский интерфейс, то, пожалуйста, никогда не используйте вот такой диалог выбора папки:

Взгляните, в это окно даже нельзя вставить путь до нужной папки из буфера обмена! (А я, кстати, регулярно это делаю: в большинстве случаев я прихожу в этот диалог из Фара).

Не понимаю, зачем в Майкрософте вообще придумали этот недоделанный диалог, и почему до сих пор не запретили использовать. Справедливости ради, у него есть версия, когда путь до папки всё-таки можно ввести:

Но ведь этого тоже недостаточно! Сравните, например, эти окна с нормальным диалогом выбора файла:

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

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

В MacOS, кстати, всё тоже плохо с этим:

Опытные люди знают, что нужно нажать Cmd+Shift+G, чтобы можно было ввести путь до папки, но ведь до этого ещё догадаться надо.

Необязательно делать такое навороченное окно, как у Хрома. Вот, например, нормальные диалоги, использованные в SourceTree и VLC:

Заметка пятая. Разбор задания 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)$, перемножаем координаты мастер-секрета, расшифровываем флаг.

Заметка четвёртая. Идеальные продукты

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

Идеальность нельзя померить. Она не коррелирует с количеством пользователей, не зависит напрямую от стоимости на рынке и вообще глубоко субъективна. То есть идеальный для меня продукт может показаться кому-то обычным приложением для заказа такси.

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

Додо-пицца, железо от Apple, сиропы Монин, RDP, рюкзаки Deuter, Телеграм, Макдональдс, ReSharper, документация к Джанго, ИКЕА, Samsung Pay — я одинаково восхищаюсь всеми этим вещами.

Несколько фактов об идеальных продуктах:

  • Идеальный продукт не получится, если не поставить перед собой цель сделать идеальный продукт.
  • Иногда продукт, выглядящий снаружи как идеальный, ужасен внутри. До тех пор, пока мы не знаем, что под капотом, он может оставаться идеальным
  • Надо стремиться делать идеальные продукты. Получится это только у единиц, но для делающего в этом случае важен не результат, а процесс.
  • Делать идеальный продукт зачастую экономически невыгодно.
  • Наличие у вас идеального продукта не гарантирует успех.

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

 2 комментария    3   2017  

Заметка третья. Брошюра об ЛКШ

Три года назад, в июне 2014 года, директор Летней компьютерной школы Андрей Станкевич написал письмо во внутреннюю рассылку. Вот начало этого письма:

Есть мысль сделать небольшую методичку формата A6 на 1-3 разворота, напечатать ее промышленно на ламинированной бумаге и раздавать на регистрации в ЛКШ.

Большинству идея сразу не понравилась. Кто-то критиковал слишком маленький размер: пользоваться такой методичкой неудобно, нужно сделать как минимум А5, а лучше А4, кому-то размер показался слишком большим: нужно, чтобы бумажка помещалась в бейдж. Говорили, что вся база «Берендеевы поляны» будет усыпана бумажками в первый же вечер, а первое, вводное собрание, на котором детям рассказывают главные правила, все равно не уменьшится ни на минуту.

Я был в меньшинстве: среди тех, кому идея пришлась по душе. Я видел, какую красивую брошюру выдают новичкам в Контуре, читал руководство пользователя о Хакердоме и знал, что такие вещи можно сделать хорошо. Оставалось лишь убедить в этом остальных:

Открытие — это двухчасовое перечисление того, что нельзя. Скука полнейшая, как ни пытаться ее разбавлять шутками.

Любой скучный текст куда интереснее запоминать и изучать, если он подается красочно и в интересной форме, легким и доступным языком. Если бы правила ЛКШ можно было бы изучить, играя в какую-нибудь игру — это было бы замечательно.

Хотите, чтобы большинство детей с радостью увезли книжки домой как сувениры? Тогда надо делать их красивыми, добавлять туда фотографии прошлых лет (дети найдут себя, своих знакомых, своих преподавателей), делать их интерактивными (сделать возможность вклеивать туда листочки с условиями практик? Страничка с контактами друзей на после-смены? Надо только включить фантазию).

Хотите, чтобы дети не боялись делать что-то из-за стеснения? Так надо добавить полезной информации, снабдив ее удобным оглавлением и красотой. Как работать со стиральной машиной? Как отметить день рождения? Почему в озере Лель нельзя купаться? И многое другое.

Украсить текст картинками тоже недостаточно — надо сделать его интересным, захватывающим. Нас опять ограничивает только фантазия. Да хоть опишите правила ЛКШ как переписанные правила Хогвартса. Запретный лес — территория, куда нельзя заходить. Правый коридор третьего этажа — 10-й домик. Парад параллелей — конкурс между факультетами.

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

Вообще защищать новые идеи в ЛКШ тяжело. Несмотря на то, что многие вещи в итоге сделать всё-таки получается, большинство инициатив сталкиваются со шквалом критики. Надо иметь много терпения и сил, чтобы начать что-то действительно делать. И лучше не показываться на глаза другим без первых результатов.

В большинстве случаев не стоит рассказывать об идее до тех пор, пока нет чего-то, на что можно посмотреть вживую

Паша Маврин оперативно сделал первую версию брошюры:

Конечно, она была неидеальной. Даже плохой по многим параметрам. Никто из нас не умел ни писать нормальные тексты, ни рисовать нормальные картинки. У нас даже не было подходящих фотографий из ЛКШ. Но эта пдфка стала важной для меня: увидев её, я понял, что хочу поучаствовать в создании хорошей брошюры:

Я тут повертел разные бумажки в руках, и мне показалось, что A5 лучше, чем A6. Чтобы читать А6, надо всматриваться — это практически как читать с телефона (с учетом полей и прочего). А5 — это все-таки форм-фактор планшета, его читать должно быть удобнее. Потребности положить в карман у школьников, скорее всего, не будет. Зачем? Будет лежать вместе с тетрадями и книгами. А это опять же А5, а не А6. На А5 можно уместить в два раза больше информации, фотографий, да и вообще — он, как ни удивительно, в два раза больше :-)

В то время я только учился объяснять свои решения людям. Для меня было большой неожиданностью, что недостаточно просто озвучить правильный ответ, к которому я пришёл в своих размышлениях. После такого люди обычно обижаются и не соглашаются с моим абсолютно правильным решением.

Объясняйте людям, почему вы приняли то или иное решение *

* если только не считаете их мудаками: тогда можно ничего не объяснять, всё равно бесполезно

Я скачал себе Adobe InDesign и даже купил на него лицензию — очень уж мне хотелось сделать всё правильно и хорошо. Я потратил два или три полных дня на вёрстку четырёх страницы: сначала рисовал схемы на бумажке, потом осваивался с новым инструментом, затем подбирал фотографии и шрифты, и размещал всё на макете.

Глядя на эти страницы сейчас я вижу кучу ошибок: да такие, которые надо исправлять немедленно. Но тогда это было максимумом, на который я способен. Как ни странно, эту версию почти не критиковали в ЛКШ, и я взялся нарисовать и остальные страницы.

В один из дней я открыл группу ЛКШ вконтакте и попытался найти фотографии, подходящие по качеству для печати в брошюре. Оказалось, что за пятнадцать лет таких фотографий набралось ужасно мало, около двадцати штук:

Чтобы исправить это, летом того года я взял в руки чей-то фотоаппарат и пошёл снимать всё, что видел. Делать брошюру через год, в 2015-ом, было уже намного проще.

В какой-то момент мне стало очевидно, что карта в середине брошюры должна быть большая, размера А3, и разворачиваться вниз, когда читатель дошёл до центрального разворота. Но, к сожалению, эту очевидную мысль снова пришлось объяснять и доказывать остальным.

Спустя много правок, замен картинки на обложке, споров про заднюю обложку, мы обо всём договорились, нашли деньги для печати и заказали брошюры. Я был на седьмом небе от счастья. Спустя три года брошюра немного потрепалась, но я до сих пор очень бережно её храню:

Идея объединить на последней обложке фотографий людей и список экстренных телефонов, кстати, до сих пор считаю одной из самых удачных: получилось и красиво, и полезно.

2015 год

Прошёл год. Я был убеждён: нельзя просто взять и напечатать старые брошюры для уже новой ЛКШ. Во-первых, мы сделали летом 2014 года много хороших фотографий, а во-вторых за год я вырос в вопросах дизайна: не терпелось применить эти знания на практике.

Поэтому я взял прошлогодний файл и начал его переделывать. Текст почти не изменился, зато появились обновлённое оформление и кайфовые фотографии.

И даже нашлась для обложки подходящая ЛКШатская фотография.

2016 год

Наконец-то я осознал, что тексты в брошюре никуда не годятся, и сел их переписывать. На это у меня ушло две недели. Ушло бы и больше, но близился дедлайн, поэтому часть текстов так и остались непереписанными.

Кроме того, я решил переделать оформление в духе минимализма. Избавился от больших цветных заголовков, полосок, сфокусировав внимание читателя на тексте и фотографиях.

Брошюра, которая получилась в итоге, стала лучшей из всех. Я вложил в неё всё, чему научился за эти три года, и до сих пор получаю кайф, листая её. Похожие ощущения я испытывал несколько раз от своих PowerPoint-презентаций, когда замечал, что с каждым разом они становятся всё круче и круче.

Есть только один способ научиться делать что-то хорошо — сделать это достаточное количество раз. Каждый раз вы будете становиться всё лучше и лучше

В конце концов у брошюры 2016 года единственная за три год обложка, которая меня полностью устраивает.

Кстати, на карте в брошюре 2016 года я спрятал себя. Найдёте?

Когда-нибудь эти брошюры станут раритетом, а я буду гордиться, что их сделал я.

В этом году я решил не делать брошюры для ЛКШ. Надеюсь, что остальные подхватят инициативу и сделают что-нибудь ещё более прекрасное. А чтобы им было проще, я выложил все пдфки и indd-файлики на гитхаб: https://github.com/andgein/sis-guide. Это, к тому же, сочетается с идеей максимальной открытости, о которой я ещё обязательно напишу.

Заметка вторая. О сервисе на 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.