Лаборатория LabyREnth 2016, Windows stash, task 4

timcess
, 15 августа 2016

Задание - JugsOfBeer.exe

Самое интересное из всех представленных crackme заданий. Сначала попробовал скормить бинарь Angr-у, но он упал с Segmentation Fault после 15 минут раздумий. После ковыряния скрипта Angr смог пройти первую из двух проверок, которая и так была очевидна. Первый чек проверяет, что длина вводимой строки чётная, >=32 и что строка состоит из символов ‘1’, ‘2’ и ‘3’. Затем выполняется второй чек – функция sub_140001750.

И если к ней внимательно присмотреться, то можно понять, что бинарь не зря назван БочонкиПива.exe. В функции реализован алгоритм проверки нашей строки на соответствие решению задачи о переливаниях.   Есть захардкоженная константа xmmword_1400190D0, которая определяет содержимое бочонков в начальный момент – 1 бочонок – 0 литров, 2 – 13 л., 3 – 7 л. Их максимальные объёмы, как видно из switch а втором скрине – 19л., 13л. и 7л.

Первый кусок функции просто преобразует символ цифры в саму цифру

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

По скрину видно, что наша задача разделить 20 имеющихся литров пополам в две первые бочки.

Есть несколько алгоритмов решения, я взял вот этот алгоритм на графах - https://habrahabr.ru/sandbox/27416/

Скрипт решалка - требует библиотечки networkx для работы с графами.