Как мы штурмовали sapka contest, часть первая

    Несколько дней назад закончилась неделя проведения контеста Sapka, для тех, кто пропустил новости о Sapka — это соревнование программистов созданное как аналог ICFPC contest, но для русского и украинского сегмента сети.

    Мне всегда было очень интересно читать о процессе решения ICFPC, поэтому я не могу упустить шанс написать подобный отчёт от первого лица, так что встречайте первую часть рассказа о штурме контестных высот от маленькой, но гордой команды minime занявшей 7-е место в контесте :)



    День 1-й
    В котором команда minime знакомится с правила контеста и делает первые шаги

    Итак, в 19-00 по GMT+3 на сайте stanfy.com.ua/contest появляется информация о проведение контеста. Для начала участия необходимо скачать некий сервер написанный на модифицированном ява коде и получив предварительно набор ключей попытаться реализовать в нём логику устройства sapka. Что такое sapka, как и откуда брать ключи и для чего они нужны совершенно непонятно.

    Пока сервер неторопливо скачивается, открываю IRC клиент и подключаюсь к каналу sapka, на котором уже активно идут обсуждения внутренностей сервера. Распаковываю сервер, запускаю и по инструкции подключаюсь телнетом к порту 20015 дабы лицезреть приглашение сервера и просьбу указать имя команды в формате team teamname;.
    Сказано — сделано. Результат нулевой. Ещё несколько попыток — аналогично. Переключаюсь на IRC там эта проблема уже активно обсуждается, оказывается надо в начале каждой команды добавлять дополнительную точку с запятой. Указываю — система сообщает об успешной регистрации и выдав напутственное сообщение предлагает запустить конфигурирование памяти устройства командой memconfig;.
    И вот первая задачка, memconfig для запуска просит ввести пароль. Откуда его брать совершенно непонятно, в бой идут sapka, god, sex, love, password и т.п. Результат нулевой — становистя грустно от такого быстрого затыка. В бесплодных попытках проходит почти час когда внезапно становится понятно что пароль нужно тоже начинать с ";". Ладно, повторяем все пароли по новой и… подходит "password". Чтож, вполне логичный пароль. Хотя потерянного времени очень жалко. «Свежевзломаная» система предлагает попробовать свои силы в двух заданиях: engine и lexinterpr

    Тут приходит печальная новость. Участники разбирающиеся в java подменили оригинальный загрузчик превращающий оригинальный(т.е. нестандартный) ява код в нормальный и получили весь набор токенов(т.е. ключей), фактически решив все задачи в первый час соревнования. Это, конечно, очень огорчило, потому что хотелось принять участие в контесте программистов, а не в контесте программистов на Яве. Появилось желание бросит конкурс, но… что-то остановило, благо задачки показались интересными. Зато из приятного — стало понятно общее число ключей.

    Обновляю сервер сапки до версии 1.1 и приступаю к lexinterpr. Как становится понятно это утилита умеющая расшифровывать информацию отсылаемую сервером если запустить его в режиме sapka-игры, причём объём расшифровымаемых данных тоже зависит от количества уже активированных токенов. Помимо этого, в качестве текущий данных для расшифровки загруженна огромная строка билеберды. К счастью, последняя часть строки несёт в себе понятную информацию. Становится понятно что из это строки надо последовательно вырезать понятную часть отмеченую в конце символами! и * и выполнять указанное преобразование. Для первого шага это взятие каждого третьего символа.

    Быстро пишется 10 строковая программа на питоне производящая операцию, на выходе очередное задание, но теперь правила взятия значимых символов изменились. Ок, повторяя итерацию 6 или 7 раз получаю на выходе свою первую пару токенов и соощение о том, что мол правила можно и по другому интерпретировать. Тут стоит заметить что в реальности это оказалось не так, но породило легендарную ненайдённую вторую пару токенов на взлом которой многие участники потратили прилично времени(И мы в том числе :) ).

    Решение интерпретатора позволяет получить доступ к целому набору задач: dnalab, sattelite, fifth, aar, clock

    Но откладываю эти задачки пока на следующий день и приступая к решению engine, который после запуска сообщает о себе свою версию "Caesar-1-3ci.5p5-h.23e.r ' ' — '~'" и выдаёт очередной зашифрованный текст. Из версии видна строка Caesar cipher, т.е. Шифр Цезаря и память подсказала что это шифрование сдвигом, что подтвердила википедия. Ок, ещё 10 минут и очередной скрипт на питоне пробегает по тексту с всеми возможными сдвигами. Тут становится понятно что не так всё просто — расшифровались только заглавные буквы, а их в тексте всего 1 строка. Ещё час уходит на попытки найти ошибку в программе или логике работы — ответ не находится, и даже подсказка в виде буквы Y закодированной как-то иначе не помогает. Прохожусь по оставшемуся тексту частотным анализом и вооружившись собственным словарём перевода начинаю собирать текст посимвольно. Работа идёт не быстро, на место часто встречающихся символов пробуется подставление «а» и «е» и попытка угадать какое-то часто встречающееся слово. Потом подстановка символов из него и прогон скрипта по тексту в надежде что слово опознано правильно и что теперь можно разгадать ещё слова. Через почти два часа текст сдаётся и обнажает ещё пару токенов, а также правила игры в сапку.

    Оказывается, финальная задача каждой команды — написать АИ для клона бомбермена. В тексте содержаться получаемые очки за подрывы объектов бомбами и команды для движения\установки бомб.

    На этом первый день заканчивается, на часах 4 ночи.

    День 2-й
    В котором команда minime проигрывает в шашки злобному вирусу и ломает себе мозги брэинфаком и часами

    Итак, преступаю к прохождению sattelite — спутник захватил злобный вирус и требует играть с ним в шашки. Ну раз требует — поиграем, единственное осложнение, игровое поле никак не визуализируется после первого хода и приходится отмечать ходу в открытом экселе. С другой стороны, становится понятно(из хамоватых выкриков вируса), что в игре свой подвох. Через некоторое время сотоварищ по команде enchantner сообщает что так и есть, выйгрыш у вируса ни к чему не приводит и играть видимо надо в поддавки. Понимаю, что мой метод с экселем не так эффективен как флеш шашки и продолжаю решать clock.

    Как станет потом ясно, clock одна из задач заставивших многих участников долго и злобно ругаться. Простая по сути, она заставила многих потратить не по одному часу на своё решение.

    Итак, задача — необходимо решить 2 задачки, base clock и eXtended clOck Routines. Из второго становится понятно, что в задаче тем или иным способом будет фигурировать XOR. Исходные данные — строка вида \0\39\34\20...(очевидно кодирующая ASCII коды символов) и фраза «I came, I saw, I conquered.».
    Первая попытка проксорить оригинальную строку высказыванием Цезаря не приводят к успехам. За этим следует попытка проксорить всеми символами алфавита. Затем фразой «Veni, vidi, vici». Затем числом 42. Всё без результата. В IRC люди разгадавшие задачу потихонько потешаются над теми кто в процессе, и рассказывают о совершенно простом ключе.

    К позднему вечер становится понятно, что задача хоть и простая, но понять как её решать нам невозможно. Тогда приходит гениальная идея, взять строки выдаваемые командам с разными именами(а токены зависят от имени команды), найти различающиеся части и исходя из того что все токены начинаются на CFG и имеют фиксированную длину определить первые 3 символа для XOR.

    Через пять минут я начинаю биться в истерике. Первые три буквы кодового слова "Cae". Ксорю злополучную строку Цезарем и получаю очередной токен. Basic часть разгадана, но расшифрованная строка содержит ещё одну строку для анализа. К счастью с ней всё сразу становится предельно просто — по длине она равна токену, а первые три символа — 0. Ксорю строку только что полученным токеном и получаю второй токен(три 0 в начале наводяд на мысль что это CFG, т.к. CFG xor 000 = CFG ). Часы разгаданы, можно идти на IRC и следить за мучениями нерешивших.

    Незадолго до окончания мучений с часами enchantner доносит вторую хорошую новость — злобный вирус сдался, и aar тоже решён. Для этого потребовалось поменять местами операторы по совету вируса из спутника, запустить полученную программу в интерпретаторе брэинфака, получить ещё одну программу, запустить её и наконец то узнать токен. Задачку эту, на самом деле, можно было легко решить и без подсказки вируса, и многим она показалось лишней. Изначальный код на brainfuck человеку ознакомившемуся с операторами языка сразу бы дал подсказку в виде выхода за границу допустимой памяти в первых же операторах.

    На часах опять за полночь и мы идём спать.

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 13

      +3
      Мда, по тексту мы с тобой эдакие злобные кодеры-маньяки :) А за все спасибо Гвидо ван Россуму, Python forever!
        +2
        Прочитал весь текст — выходит более похоже на соревнования по криптоанализу, чем по программированию.
        Как программисты поступили те ребята, которые сделали реверс инжиниринг кода этой головоломки ;-)
          +3
          Не совсем. Часы, энджин и лекс были действительно похожи. Шашки были просто забавной задачей. брэинфак если бы не подсказка был бы итересной задачкой.

          В следующей часте будут задачки на «фифте», вот там программисткий контест чувствовался.

          Ну а те кто сломал загрузчик в результате сели решать задачки сами, интересно же.
            +2
            что то так корежит от слова «контест»… есть же отличное русское слово «соревнование»
              +1
              меня тоже, но я использовал терминологию авторов конкурса.
          +2
          занятно) рад, что это появилось у нас. вы наверно не были на таких «контестах» в 1991-93х когда у нас были кубики-ваксы в ИКИ на Калужской)))) А вообще — молодцы!
            0
            Я в 93 году пошёл в школу :) Так что увы, пролетел мимо.
            +1
            слово длиНа пишется с одной Н!
              0
              Поправлено, правда думаю там ещё много чего править :)
              +1
              А я тут — представитель THIRTEEN =)
              0-e место в обоих раундах Сапки)))
                0
                Вы безусловно круты :) Но ничего, в следующий раз соберёмся и толпой всех завалим :)
                +1
                Молодцы ребята, спасибо за отчет, прочитал на одном дыханьи!
                  0
                  Старались. Вторая часть на подходе :)

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое