ZeroNights 2013 hackquest - A problem

Дмитрий DarkByte Москин

Мой блог, да.
logo

ZeroNights 2013 hackquest - A problem

Опубликовано 23.10.2013 автором Дмитрий Москин
What mathematical problem criteria is provided by given file? 
Decrypt rP4XPry8FI3bQZoUViEy+a36nWr90RGF2BRyfF0+UJ4+4uM=
with correct key specified by criteria and post answer string.


Бинари и реверс это не мой профиль, но решил попробовать. IDA не смогла нормально разобрать файл, предположив, что он чем-то упакован, PEiD ничего хорошего не сказал. Пробежался глазами по файлу, в памяти всплыли слова Go и cygwin, google по запросу "Go decompiler" ничего хорошего не выдал, и дальнейшее желание ковыряться в бинарнике отпало.

Но инвайт то получить хотелось. После первой подсказки:
[22/10 23:05] The given file provides criteria for some mathematical problem. The given criteria creates the keyspace for given ciphertext. You can discover the criteria and the cryptoalgo by reversing or fuzzing (that will be a lot harder, than reversing, but still possible) given file.

вернулся к таску, поняв, что его можно решить фаззингом. Запустил бинарь, а в ответ:

X:\>a_problem_criteria_solver.exe
.:[ Welcome to ZeroNights 0x03 Reverse Puzzle ]:.
Send solving problem name as flag to complete the task.
Result: OK


При повторном запуске Result стало FAIL, и менялось каждый раз случайным образом. Начал подбирать параметры. На символы программа никак не реагировала, а вот при вводе двух чисел вывод изменился. Выводилось случайное число от 1 до 15.
X:\>a_problem_criteria_solver.exe 1 2
.:[ Welcome to ZeroNights 0x03 Reverse Puzzle ]:.
Send solving problem name as flag to complete the task.
4
Result: FAIL


Как раз вовремя подоспела крупная подсказка:
[23/10 12:27] Answer the following questions:
1) The question from Hint 3 (what is the distance between given chars?)
2) What happens when you supply first two arguments to program? Try to fuzz and supply strigs, chars, digits.
3) Can you force program to give you constant result (only 'OK' or only 'FAIL') by varying command line arguments (or number of arguments)? How much arguments do you need to force the constant result?
4) Can you provide more arguments to program and what will happen then?


Начал перебирать количество параметров, и на 15 штуках вывод стабилизировался.
X:\>a_problem_criteria_solver.exe 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
.:[ Welcome to ZeroNights 0x03 Reverse Puzzle ]:.
Send solving problem name as flag to complete the task.
8
Result: OK


Начал проверять, какие параметры влияют на вывод, выяснилось, что параметры №3-14 на вывод совсем не влияют, если не указать параметр №15, то выдаётся одно случайное число, а при указании - вывод числа стабилизируется.
X:\>a_problem_criteria_solver.exe 1 2 0 0 0 0 0 0 0 0 0 0 0 0 1
.:[ Welcome to ZeroNights 0x03 Reverse Puzzle ]:.
Send solving problem name as flag to complete the task.
13
Result: FAIL


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

X:\>a_problem_criteria_solver.exe 1 2 0 0 0 0 0 0 0 0 0 0 0 0 1
13
X:\>a_problem_criteria_solver.exe 1 3 0 0 0 0 0 0 0 0 0 0 0 0 1
13 5
X:\>a_problem_criteria_solver.exe 1 4 0 0 0 0 0 0 0 0 0 0 0 0 1
13 5 3
X:\>a_problem_criteria_solver.exe 1 5 0 0 0 0 0 0 0 0 0 0 0 0 1
13 5 3 14
X:\>a_problem_criteria_solver.exe 2 6 0 0 0 0 0 0 0 0 0 0 0 0 1
5 3 14 11
X:\>a_problem_criteria_solver.exe 3 7 0 0 0 0 0 0 0 0 0 0 0 0 1
3 14 11 1
X:\>a_problem_criteria_solver.exe 4 8 0 0 0 0 0 0 0 0 0 0 0 0 1
14 11 1 4


Сразу на это не обратил внимания, но когда сдампил все значения для первого параметра 1-12 и второго 5-16, заметил, что первый параметр отвечает за начальную позицию
13 5 3 14
5 3 14 11
3 14 11 1
14 11 1 4
11 1 4 12
1 4 12 8
4 12 8 6
12 8 6 9
8 6 9 2
6 9 2 10
9 2 10 15
2 10 15 7
10 15 7 939
15 7 939 624


После 15 позиции начинались большие числа, решил их не учитывать. Вспомнил про последний параметр, дописал дампер и достал все числа:
13 5 3 14 11 1 4 12 8 6 9 2 10 15 7
4 1 7 12 9 2 11 5 8 13 10 15 14 6 3
9 7 5 14 4 8 15 13 3 1 10 2 11 6 12
15 6 5 4 1 8 10 9 11 2 13 7 3 14 12
12 3 5 2 13 8 1 9 7 6 10 4 14 11 15
1 7 5 6 4 3 9 12 13 2 8 15 11 14 10
11 15 14 4 2 7 10 9 13 8 3 1 5 6 12
12 5 3 11 10 13 4 1 9 6 2 7 15 8 14
5 15 10 3 12 1 13 7 9 6 11 2 14 8 4
2 3 9 5 15 13 6 14 10 12 1 11 4 8 7
4 15 13 7 5 2 1 9 10 8 6 11 3 12 14
11 3 7 2 5 1 14 8 13 12 9 6 10 15 4
3 9 13 4 5 14 2 8 10 6 7 12 15 11 1
14 1 7 11 5 15 3 6 12 8 2 9 10 13 4
8 13 7 1 9 11 10 5 2 4 14 12 3 15 6


Попытки дешифровать сообщение с использованием данных ключей не увенчались успехом. После подсказки про "RC4 test vectors", проверил используемый алгоритм, но он зафейлился. Нашёл реализацию, которая прошла тесты, но текст по-прежнему не расшифровался. Несмотря на то, что весь таск был основан на числе 15, решил попробовать расшифровать текст ключём меньшей длины. Доработал скрипт, направил вывод в файл, пробежался глазами - ничего нового. Попробовал ещё несколько вариантов, но результат не поменялся. До конца таска осталось 30 минут, рабочий день уже давно кончился, пора идти домой, идей больше нет. Решил на всякий случай натравить на получившийся файл с кучей мусора strings, и заметил там несколько упоминаний флага "WTFCryptoPuzzle15forZeroNights2013!" :)

В итоге оказалось, что ключ был 0x0F0605.