пятница, 23 октября 2015 г.

KrasCTF 2015. Итоги

А вы еще не видели крутой текст про итоги KrasCTF 2015?
Держите - http://ctfnews.ru/news/132

P.S. Надо бы написать статью про "кухню krasctf", но пока руки не доходят. А еще ведь готовить анонс нашей чек-системы. Кому интересно - пишите мне. Особенно, если вы готовите свою игру и хотите прервать процесс написания велосипедов и присоединиться к разработке универсального инструмента.

воскресенье, 18 октября 2015 г.

Linear feedback shift register writeup SPBCTF 2015


11 октября в Санкт-Петербурге во второй раз прошли межвузовские соревнования по информационной безопасности SPbCTF-2015. Участие в соревнованиях приняли 5 команд из ведущих ВУЗов Санкт-Петербурга, среди которых:
  • Санкт-Петербургский государственный университет (СПбГУ);
  • Санкт-Петербургский государственный экономический университет (СПбГЭУ);
  • Санкт-Петербургский государственный университет телекоммуникаций имени профессора М. А. Бонч-Бруевича (СПбГУТ);
  • ИТМО (Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики).
Выступали мы в составе команды ИТМО hardc0de и даже победили. Таски были, на мой взгляд, сложные для обычного очного CTF, поэтому нарешали мы не слишком много. Хочу поделиться writeup'ом задания на 200 баллов.

Дан файл crypto200.cpp (он чуть отличается, но у меня не осталось оригинального файла).

Данный код выполняет операцию зашифрования неизвестного нам текста с ключом 0x1a2b4de1219435c6 и выводит шифротекст. Шифротекст дан в условии задачи: 4b36342e80be9bce9c268becd18a5789fc.

Очевидно, что придется обращать функцию encrypt и писать декриптор. Впрочем, функция ничего сложного не делает – генерирует гамму от вектора инициализации, в качестве которого выступает ключ и затем производит побитовое сложение по модулю 2 с открытым текстом. Казалось бы, что все просто, однако количество итераций гаммы INIT_ROUNDS = 18446744073709550615, что не представляется возможным для перебора.

Первой мыслью было осознание того факта, что 18446744073709550615 = 2**64 – 1001. Возможно, что такие числа подобраны не случайно и где-нибудь произойдет зацикливание алгоритма. Поэтому я переписал код на питон и сделал обычный брутфорс с небольшими оптимизациями. Результирующая строка проверялась на соответствие ascii и выводилась на экран. Код я стер, поэтому приводить его не буду. В результате брутфорса было перебрано порядка миллиона итераций, среди которых ничего вразумительного не оказалось. Возможно, код был написан с ошибкой, или же данный вектор задачу решать не позволял.
    
Далее, уже после соревнований я решил задачу по-правильному (спасибо voz и hiruma52).
 
Для начала немного теории про LFSR (linear feedback shift register). Весь алгоритм генерации гаммы заключался в сдвиге битов состояния lfsrState влево и заполнению правого бита ксором 63-его, 62-го, 60-го и 59-го.


feedbackBit = ((lfsrState >> 63) ^ (lfsrState >> 62) ^ (lfsrState >> 60) ^ (lfsrState >> 59) ) & 1

lfsrState = ((lfsrState << 1) % 2**64) | feedbackBit

Главный интерес в том, что данное действие можно представить как умножение некоторой матрицы перехода на наш стобец состояния из 64 элементов. Покажем это на примере из 4 элементов:

lfsrState = [0, 1, 0, 1] – это наша переменная состояния в виде вектора из 4-х битовых элементов.
TransitionMatrix = [ [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 1, 1, 1] ]

Каким образом она строится? Первые три строки иллюстрируют тот самый бинарный сдвиг элементов налево. Четвертая строка заполняется единицами соответственно тем элементам, которые участвуют в xor-е. Проводя аналогию с заданием, можно получить такой код:


feedbackBit = ((lfsrState >> 2) ^ (lfsrState >> 1) ^ (lfsrState >> 0) ) & 1

lfsrState = ((lfsrState << 1) % 2**4) | feedbackBit

Это хорошо описано на следующем слайде:



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

lfsrState_next = [1, 0, 1, 0]. (первые три бита – просто сдвинуты, а правый заполнен результатом 1^0^1=0).

Теперь проделаем умножение матрицы TransitionMatrix на столбец lfsrState.



 = (1, 0, 1, 0).



Думаю, что здесь хорошо видно как происходит преобразование. Теперь вопрос – зачем городить матричную форму цикла? А затем, что поскольку мы свели задачу нахождения lfsrState_next к умножению TransitionMatrix на lfsrState, то мы можем получить произвольный элемент просто умножая первый lfsrState на TransitionMatrix слева много раз. А значит нам нужно лишь возвести матрицу в определенную степень, что мы можем сделать очень быстро при помощи бинарного возведения в степень.

Осталось чуть-чуть кода и готово.


четверг, 15 октября 2015 г.

KrasCTF уже на этой неделе

KrasCTF - это межрегиональные межвузовские соревнования в области информационной безопасности по принципам игры формата CTF, проводимые Сибирским федеральным университетом (СФУ), при поддержке Межрегиональной общественной организации «Ассоциация руководителей служб информационной безопасности»
Соревнования KrasCTF-2015 состоятся с 17 по 19 октября 2015 года в Институте космических и информационных технологий Сибирского федерального университета в рамках XII специализированной выставки-форума «itCOM – Информационные технологии. Телекоммуникации».

Легенда соревнований:
Каждый  юноша  мечтает  стать  офицером... Мы  конечно  не  столь всемогущи, чтобы дать Вам погоны. Однако мы предлагаем Вам ненадолго окунуться в мир политического сыска, разведки и госбезопасности.
«Кофе, алкоголь, сахар, воспоминания, злость,
все вместе прогоняют сон».
В. Миронов(«Глаза войны»)
Представьте себя в роли молодого сотрудника, которому выпала честь решать самые сложные задачи нашей Конторы, связанные с криптографией, web-уязвимостями, программированием, стеганографией и обратной разработкой.
Теперь запасёмся необходимым количеством материально-технических средств (вкусняшками и кофе), запишемся в Книгу учёта участников KrasCTF и на 8 часов погрузимся в атмосферу борьбы «с контрреволюцией и саботажем».
На данный момент зарегистрированы уже более 10 команд из Красноярска, Томска, Новосибирска, Барнаула, Владивостока, Москвы и Нижневартовска.