BackdoorCTF

2 апреля 2015

Мы тут участвовали в BackdoorCTF, и я решил написать небольшой врайтап по поводу таска, который решил.

Решил я, конечно, не один таск, но в основном это были простые таски типа получить 100 QR кодов и быстро их сосканить (т.к. по-быстрому найти что-нибудь подходящее для питона не удалось, взял консольную ZBar для винды и просто вызывал в нужный момент).

Но это не тот таск, о котором я собрался рассказывать. Самым интересным для меня таском оказался bbad. Нам даны 4 файла, один бесполезен, в другом лежит то, что надо расшифровать, и оставшиеся два нужны для того, чтобы понять, как это расшифровывать.

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

Сразу бросается в глаза то, что если вторым параметром идёт 1, то в выводе вторым идёт 0. Так как разделены они символом ’^’, я подумал, что это степень, и что шифруется так, чтобы выражение в указанной степени было равно второму параметру (по модулю, конечно).

Ещё сразу видим, что шифруемый текст разбивается на слова по пробелам, и каждое слово отображается в выводе отдельной парой чисел.

Несложно также заметить множество простых чисел в выводе (для нас специально сделали подборку команд, в которых шифруется только один символ). В голову приходит, что символу соответствует какое-то число, и можно попробовать выяснить закономерность. Сгруппировав команды от ’1′, ’2′, ’3′, ’9′, ’0′, замечаешь, что числа подозрительно простые, и к тому же ’9′ соответствует девятое простое, а ’0′ - десятое.

Вскоре замечаешь, что ’q’ соответствует 11-ое простое число. И другим буквам тоже соответствуют простые, но закономерности не видишь. Смотришь на клавиатуру — а ’q’ идёт сразу после ’0′. Вооружившись первой сотней простых чисел и пробежавшись по клавиатуре, я с помощью регулярки генерирую тело функции, которая будет переводить символ в соответствующее число (кто-то не знает про dict в питоне, да).

Запускаем на всех односимвольных входах с ключом 1 — и выходное первое число всегда совпадает с соответствующим простым. Успех! Идём дальше. Время попробовать более длинный текст с ключом 1: ’abcd’. Вероятно, символы всё ещё кодируются простыми числами, но непонятно, складываются их коды, перемножаются и зависят ли они от позиции символа. Сначала пробуем просто перемножить их все, и получаем неверный ответ. Тогда пробуем возвести код символа в степень, соответствующую его позиции в тексте. Получается. Круто, мы решили таск для ключа, равного 1.

Теперь надо разобраться с тем, как зависит ответ от ключа. Тут нам пригодится группа команд, которые работают с текстом ’V’, но используют разные ключи. Для 1 наш ответ уже совпадает. Если присмотреться, то закрадывается мысль, что ответ примерно в <ключ> раз меньше простого числа, соответствующего нашему символу. Проверяем на калькуляторе — делим нацело — полностью совпадает.

Непонятно только, нужно ли делить на ключ код каждого символа или получающееся сообщение и сколько раз на него нужно делить. Пару раз попробовав, выясняю, что на ключ делят один раз. Это, конечно, неплохо, но что делать с числом, которое стоит после ’^’? Мы ещё не придумали, как вычислить его, если только это не случай с ключом, равным 1 (там просто ставим 0).

Я пробовал свою догадку с возведением в степень и взятием остатка от 12000 (число, встречающееся в условии), но она оказалась неверной. Довольно очевидная идея о том, что это остаток от деления, пришла ко мне не сразу, причём довольно случайно — я просто решил это проверить, хотя и не думал, что это окажется верным решением. В общем, так мы выяснили, как получить оба числа, печатаемых в ответ.

Осталось лишь декодировать зашифрованное сообщение. Правда, у нас нет ключа, который используется для кодирования. В условии написано, что он не может быть больше 12000. Кроме того, мы знаем, что второе число — остаток от деления на наш ключ. Так как остаток от деления больше ключа быть не может, а ключ на всё сообщение один, то минимальный ключ, которым можно было его зашифровать, должен быть больше любого из остатков, указанных в нашем зашифрованном тексте. Максимальный остаток — 8923, так что начинаем перебирать ключи с 8924, и заканчиваем 12000. Отметим также, что у нас в сообщении есть два небольших частных от ключа — 33 и 47. Вероятно, это короткие слова, которые будет несложно декодировать и по ним понять, подходящий ли ключ был найден.

Отметим, что код слова мы можем получить как a*key+b, где a, b — пара чисел, указанных в зашифрованном тексте. Кроме того, код слова — произведение простых чисел, соответствующих символам 0-9a-zA-Z, поэтому если при разложении кода мы получаем слишком большое простое число, можно сразу отбросить подобранный ключ. Более того, каждое число должно встречаться уникальное число раз, и это число раз должно находиться в диапазоне от 1 до количества уникальных простых чисел в разложении. (Сейчас, при написании этого поста, я понял, что если в слове один и тот же символ встречается дважды, то степень при соответствующем ему простом числе будет суммой номеров позиций, в которых находятся эти символы. Я просто отбрасывал подобные комбинации.) Таким образом, мы можем отбросить очень большое число различных неподходящих ключей.

Где-то третий найденный подходящий ключ выдал слово «is». Я остановил перебор и попробовал дешифровать всё сообщение этим ключом. Так я получил сообщение, в котором говорилось, что флаг — sha-256 от xY3wL1Sg. Его и сдаём.

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

Если что — мы восьмые.


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