Лабиринт, устранение шумов, схемотехника и многое другое

20:34 / 28 декабря, 2012

Обзор интересных заданий PHDays CTF Quals

На прошлой неделе завершились отборочные соревнования по защите информации PHDays CTF Quals. 493 команды из более чем 30 стран мира соревновались в выполнении заданий по взлому и защите информации, которые были разбиты на пять категории от обратной разработки до задач из реального мира (подробности и результаты соревнований в нашем предыдущем посте). Каждая категория включала в себя пять заданий разного уровня сложности (от 100 до 500 баллов).

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

Misc 400

Задание представляло собой интерактивный сервис, который предлагал участникам найти путь в 3D-лабиринте (куб 50х50 с множеством коридоров внутри).

После прохождения одного такого лабиринта появлялся следующий, потом еще — всего 16 повторений. В середине соревнования была опубликована подсказка: "A point of view does matter" («Важен угол зрения»). Действительно, если смотреть в одной из трех проекций, то путь в каждом из лабиринтов -— это одна буква ответа.

Таким образом, 16 решений дают 16 букв флага: "NOF3ARNO3XITHER3".

После прохождения последнего лабиринта, сервис выдавал сообщение "You win! How do you like the flag? ;)" и закрывал соединение. Благодаря эффекту неожиданности этот момент вызывал когнитивный диссонанс у многих участников. J

Проекции путей можно посмотреть здесь.

Bin300 (HashME) – Hash with Modular Exponent

Дан бинарный файл размером 754 байта.
Задание формулируется так: «Найдя правильный пароль, вы найдете заветный флаг» (“Find the valid password, and you will find the cherished flag”).

Внутри файла просматриваются строки: "Bad pwd", "hex", "sys", "hashlib", "argv", "isalnum", "len", "Exception", "chr", "pow", "int", "encode", "md5", "hexdigest", "<module>".

По строкам можно догадаться, что в файле байт-код Python, что подтверждает и “GNU-file”:
python 2.7 byte-compiled

Для Python 2.7 существует декомпилятор uncompyle: https://bitbucket.org/gstarnberger/uncompyle
Устанавливаем tuj, запускаем и получаем декомпилированный текст:

import sys, hashlib (5, 1, 3, 6,) =(100186274256679440101921843746169540349323362889720706022677641748 49233338727414964592990350312034463496546535924460513481267263055398790908691402854122123L, 7548218116432136940925610514648634474612691039131890951895054656437277296127635726026902728 136306678987800886118938655787775411887815467753774352743068577L, 61921282623124215136448885 06697421915171917575080330421897398651929773466194971539791158995262083381167771056580666419 101167108372547406447696753234781064L, sys.argv[-1]) if not 6.isalnum() or len(6) > 10: raise Exception('Bad pwd') 0 = (chr(len(6)) + 6) * 32 2 = pow(1, int(0[:64].encode('hex'), 16), 5) if 3 != 2: print hex(2) else: print hashlib.md5(6).hexdigest()

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

Для исправления достаточно перед каждым однозначным числом вставить любую букву. Или воспользоваться первой подсказкой:
Python 2.7, "pgxweh" <=> "513602"

Работоспособный код должен выглядеть примерно так:

import sys, hashlib (p, g, x, w,) = (1001862742566794401019218437461695403493233628897207060226776417484 9233338727414964592990350312034463496546535924460513481267263055398790908691402854122123L, 7548218116432136940925610514648634474612691039131890951895054656437277296127635726026902728 136306678987800886118938655787775411887815467753774352743068577L, 619212826231242151364488850669742191517191757508033042189739865192977346619497153979115899526208 3381167771056580666419101167108372547406447696753234781064L, sys.argv[-1]) if not w.isalnum() or len(w) > 10: raise Exception('Bad pwd') e = (chr(len(w)) + w) * 32 h = pow(g, int(e[:64].encode('hex'), 16), p) if x != h: print hex(h) else: print hashlib.md5(w).hexdigest()

По коду видно, что если в качестве последнего аргумента командной строки указать правильный пароль, будет выведено шестнадцатеричное значение MD5 от этого пароля (флаг). Пароль состоит только из букв и цифр, допустима длина от 1 до 10 символов включительно.

Пароль превращается в Pascal-строку (lenth byte + data), которая повторяется, пока не получится 64 байта. Эти 64 байта интерпретируются как длинное целое число и становятся экспонентой е. Пароль признается правильным, если pow(g,e,p)==x

Известны значения p, g и x, p — простое число, g — генератор мультипликативной группы, нужно найти e. Это задача дискретного логарифмирования. Для 512-битового p в “домашних условиях” за 48 часов она не решается (насколько нам известно ;). Но остается возможность подобрать пароль.

Возможный набор символов: “0-9A-Za-z“, т. е. 62 варианта. Максимальная длина – 10, таким образом общее количество возможных паролей:

62¹ + 62² + 62³ + … + 62¹⁰ == 853058371866181866 ≈ 2^59.6

Вычисление 512-битовой модульной экспоненты происходит довольно медленно, и за 48 часов на одном компьютере вряд ли удастся перебрать даже 2²⁸ вариантов.

Но вовсе необязательно для каждого пароля считать модульную экспоненту, и на это указывает вторая подсказка:

g^(a+b) == g^a * g^b

Допустим, мы перебираем пароли длиной 3 символа. Тогда экспонента в шестнадцатеричной записи будет выглядеть так:
е = 03 XX YY ZZ 03 XX YY ZZ 03 XX YY ZZ … 03 XX YY ZZ

где XX YY и ZZ – символы пароля.

Учитывая подсказку, экспоненту можно записать как 4 числа:

e0 = 03 00 00 00 03 00 00 00 03 00 00 00 … 03 00 00 00
e1 = 00 XX 00 00 00 XX 00 00 00 XX 00 00 … 00 XX 00 00
e2 = 00 00 YY 00 00 00 YY 00 00 00 YY 00 … 00 00 YY 00
e3 = 00 00 00 ZZ 00 00 00 ZZ 00 00 00 ZZ … 00 00 00 ZZ

И тогда

pow(g,e,p) == (pow(g,e0,p) * pow(g,e1,p) * pow(g,e2,p) * pow(g,e3,p)) % p

Примечательно, что для паролей фиксированной длины значение e0, а значит и pow(g,e0,p), будет постоянно. А pow(g,e[i],p) может принимать одно из 62 возможных значений, которые достаточно вычислить один раз. При изменении одного символа пароля будет меняться только один из сомножителей. Мы видим, что модульное экспоненцирование можно свести к модульному умножению, что позволяет увеличить скорость более чем в 500 раз.

Однако даже после этого перебрать 2⁶⁰ вариантов за 48 часов вряд ли получится. И тут на помощь может прийти третья подсказка:

Meet In The Middle

Дело в том, что модульное умножение – обратимая операция (по крайней мере, в нашем случае). При помощи расширенного алгоритма Евклида можно вычислить g^-1==g’ – алгебраическое дополнение g по модулю p, такое, что (g*g’)%p==1

Тогда, если:
(pow(g,e0,p) * pow(g,e1,p) * pow(g,e2,p) * pow(g,e3,p)) % p == x

то истинным будет равенство:
(pow(g,e2,p) * pow(g,e3,p)) % p == (x * pow(g’,e0,p) * pow(g’,e1,p)) % p

Это дает нам возможность устроить «встречу посередине».

Мысленно делим пароль заданной длины на две части максимально близко к середине. Перебираем все варианты более короткой части и последовательно умножаем x на каждое из значений pow(g’,e[i],p). Сохраняем результирующие значения в таблице.

Перебираем все варианты другой части и последовательно умножаем 1 на каждое из значений pow(g,e[i],p). Все умножения нужно выполнять по модулю p. Результирующее значение ищем в таблице. В случае совпадения остается только “вспомнить” значение короткой части пароля, породившее найденный элемент таблицы.

Т. к. размер пароля не превышает 10 символов, то половина пароля будет не длиннее 5 символов, а 62⁵ == 916132832 ≈ 2^29.8. Т. е. решение задачи можно гарантированно найти, выполнив менее чем 2³¹ модульных умножений, что вполне реализуемо даже на одной машине. Правда для хранения 2^29.8 512-битовых значений потребуется почти 55 гигабайт памяти.

Но, во-первых, можно сохранять меньше чем 512 бит (40 бит должно хватить, чтобы число коллизий оказалось близко к нулю). А во-вторых, пароль-ответ содержал всего 9 символов, a для 62⁴ вариантов даже двух гигабайт оперативной памяти вполне достаточно.

При правильной реализации однопоточная Python-программа на компьютере с процессором Core-i5 3.1GHz гарантированно находит любой пароль длиной до 8 символов включительно примерно за 4 минуты, а любой 9-символьный пароль – за полтора часа.

Binary – 400 (BoobFs)

Очень интересное задание, которое не смогла решить ни одна команда.

Входные данные:

BMP-изображение (образ файловой системы).
Программа для создания образа файловой системы из файлов.

Рисунок 1. Образ файловой системы в формате изображения

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

struct FS_HEADER { DWORD signature; // BOOB DWORD dirOffset; DWORD firstBlockSize; }; struct DIR_BLOCK_HEADER { BYTE signature; // D DWORD nextBlockOffset; DWORD nextBlockSize; DWORD numberOfFiles; }; struct FILE_ENTRY { CHAR fileName[MAX_FNAME]; // MAX_FNAME = 20 DWORD fileSizeInBytes; DWORD firstBlockOffset; DWORD firstBlockSize; }; struct FILE_BLOCK_HEADER { BYTE signature; // F DWORD nextBlockOffset; DWORD nextBlockSize; };

Рисунок 2. Пример структуры файловой системы (S – количество блоков в каталоге, N_i – количество файлов в i-м блоке, P – общее количество файлов, равное N₀ + … + N_S)

После того как файловая система сформирована, все данные подвергаются некоторому преобразованию (модификация алгоритма Base64) и записываются в двумерный массив по специальной математической формуле, а все свободное место заполняется псевдослучайными числами, и на основании данного массива создается BMP-файл.

Рисунок 3. Функция, по которой записывается информация в массив

Программа написана на C++ и использует STL, ООП и виртуальные методы, что значительно усложняет анализ данного приложения.

Процесс решения задания можно разбить на несколько этапов:

Считать данные из файла в двумерный массив (убрать избыточность формата BMP).
Понять формулу, по которой надо считывать данные из двумерного массива.
Разобраться, каким образом преобразованы данные, и инвертировать алгоритм (модифицированный Base64).
Подобрать ключ (pin) шифрования файловой системы (brute force).
Понять структуру файловой системы, написать программу для ее обхода и вытащить все файлы (16 штук).
Из имен файлов составить предложение, которое поможет получить флаг.

Архив с заданием

Forensics500

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

Обратив внимание на порт 554/udp, можно было понять, что это RTP-поток. И, судя по всему, аудио-поток.

Рисунок 4. Задание, открытое в программе-анализаторе трафика Wireshark

При попытке прослушать аудио становится ясно, что на фоне какого-то шума играет музыка и периодически возникают более зашумленные отрывки. Поток на самом деле состоит из двух потоков. В спецификации протокола RTP (http://tools.ietf.org/html/rfc1889) описан 1 бит, который используется на уровне приложения и определяется профилем. Если это поле установлено, то данные пакета имеют особый признак, по которому можно разделить трафик на два потока. Теперь в одном играет музыка, а во втором слышны шумы и что-то похожее на голос - это финальная часть задания. Необходимо понять природу шумов и устранить их. Скажем сразу: шум это XOR аудио-данных с байтом 0xCC.

Существуют несколько путей дальнейшего решения задачи. Вот один из них.

Менее зашумленные участки — скорее всего тишина и шум. При известном кодеке (смотрим в дампе) создаем свой аудио-файл с тишиной. Анализируя его и поток из задания можно выйти на природу и тип шума.

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

В результате после устранения шума искомый флаг проговаривался по-английски женским голосом.

За время отборочного тура участникам были предоставлены следующие подсказки, указывающие на основные этапы решения:

Listen... the strange noise

Simple noise over alphabet

a?x=b b?x=a x?????

После 3-й подсказки команда PPP решила задание, а некоторые участники были очень близки к успеху. Используя свои методы устранения шума, они добились позитивных результатов, и ошибка составляла всего 1-2 символа во флаге.

Misc500

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

Рисунок 5. Внешний вид схемы

Схема обфусцирована и состоит из двух частей. Первая часть включает в себя элементы, необходимые для вывода мигающей надписи “PHD3” на индикаторы. Вторая (независимая) часть – это совокупность из 32 двоичных/десятичных/двоично-десятичных счетчиков, коэффициент пересчета каждого из которых является символом флага. Обратить внимание на счетчики помогала подсказка “Follow the counters”. Длина флага в формате MD5 – 32 символа в HEX-представлении, коэффициенты пересчета счетчиков лежат в диапазоне [2;15]. Порядок символов флага подсказан ни к чему не подключенным проводом со стрелками.

Команда ufologists за 10 минут до окончания PDays Quals пыталась сдать MD5 лишь в паре символов отличающийся от флага. Однако, к сожалению, им не хватило времени на устранение ошибки.

Forensic400

В качестве задания командам была предоставлена картинка 512x512 пикселей в формате PNG.

Рисунок 6. Задание для конкурса Forensic 400

При изучении изображения в любом графическом редакторе можно заметить, что картинка не трехцветная: белый и красный цвета не однородны, на что и была направлена первая подсказка “Not all white pixels are the same white :)”. Заливка черным выявляет пиксели «почти белого» и «почти красного» цветов:

Рисунок 7. Результат после заливки черным цветом

Видно, что расположение пикселей имеет некоторый закономерный порядок. Понять/вспомнить/догадаться, что это за порядок, сложно, поэтому была приведена вторая и ключевая подсказка “a,b,c,d,e,f,g,h <-> a,e,c,g,b,f,d,h”, которая является примером бит-реверсивной перестановки индексов. Чтобы применить эту перестановку, необходимо убедиться в равенстве длины исходной последовательности степени двойки. Размер изображения этому условию соответствует.

Далее требовалось ~~сделать преобразование в уме~~ написать утилиту, реализовывающую вышеописанную перестановку индексов, в результате чего получаем следующее изображение:

Рисунок 8. Результат перестановки индексов

Скобки четко видны, значит предыдущий шаг был верным! Однако текст явно наложен друг на друга. Попробовав удалить часть изображения и применив перестановку, получим часть флага:

Рисунок 9. Получение части флага

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

Рисунок 10. Получение оставшихся частей флага

Задание было решено двумя командами. Первыми были Magic-Hat (RU),чуть позже задание решили Plaid Parliament of Pwning (US). Справедливости ради надо отметить, что тема бит-реверсивной перестановки пикселей изображения была освещена несколько месяцев назад на русскоязычном ресурсе habrahabr.ru, поэтому результат команды PPP заслуживает особого уважения!

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

О том, как участники решали эти и другие задания, можно узнать из их отчетов:

http://ppp.cylab.cmu.edu/wordpress/?p=1076

https://ctftime.org/event/56/tasks/

http://lobotomy.me/2012-12-17-phdays2012-quals---pwn100-writeup/

http://lobotomy.me/2012-12-17-phdays2012-quals---pwn400-writeup/

http://blog.sergeybelove.ru/ctf/426

http://blog.ipwned.it/phdaysctf-2012-realworld-200-2/

http://blog.ipwned.it/phdaysctf-2012-misc200/

http://darkbyte.ru/2012/61/phdays-quals-2012-writeup/

http://smokedchicken.org/2012/12/phdays-ctf-quals-2013-real-world-500.html

http://bitsmash.wordpress.com/tag/phdays/

http://f00l.de/blog/?tag=phdays

http://kmkz-web-blog.blogspot.ru/

http://f00l.de/blog/?tag=phdays

http://yw720.net/382