CTF Type Juggling с хешем ripemd160

Question

Я пытаюсь решить CTF, в котором следует использовать тип жонглирования. Код такой:

if ($_GET["hash"] == hash("ripemd160", $_GET["hash"]))
{
    echo $flag;
}
else
{
    echo "<h1>Bad Hash</h1>";
}

Я сделал скрипт на python, который проверяет случайные хэши в ripemd160, которые начинаются с "0e" и заканчиваются только числами. Код такой:

def id_generator(size, chars=string.digits):
    return ''.join(random.choice(chars) for _ in range(size))
param = "0e"
results = []
while True:
    h = hashlib.new('ripemd160')
    h.update("{0}".format(str(param)).encode('utf-8'))
    hashed = h.hexdigest()
    if param not in results:
        print(param)
        if hashed.startswith("0e") and hashed[2:].isdigit():
            print(param)
            print(hashed)
            break
        results.append(param)
    else:
        print("CHECKED")
    param = "0e" + str(id_generator(size=10))

Есть предложения по ее решению? Спасибо!

Answer 1

Похоже, что в комментариях есть небольшое недопонимание, поэтому я начну с объяснения проблемы немного подробнее:

Жонглирование типами относится к поведению PHP, при котором переменные неявно приводятся к разным типам данных при определенных условиях. Например, все следующие логические выражения будут оцениваться какtrue в PHP:

0 == 0                       // int vs. int
"0" == 0                     // str -> int
"abc" == 0                   // any non-numerical string -> 0
"1.234E+03" == "0.1234E+04"  // string that looks like a float -> float
"0e215962017" == 0           // another string that looks like a float

Последний из этих примеров интересен тем, что его хеш-значение MD5 представляет собой другую строку, состоящую из 0e с последующим набором десятичных цифр (0e291242476940776845150308577824). Итак, вот еще одно логическое выражение в PHP, которое будет оцениватьtrue:

"0e215962017" == md5("0e215962017")

Чтобы решить эту проблему CTF, вы должны найти строку, которая "равна" ее собственному хэш-значению, но с использованием алгоритма RIPEMD160 вместо MD5. Когда это предоставляется как переменная строки запроса (например,?hash=0e215962017), то скрипт PHP раскроет значение флага.

Подобные фальшивые коллизии хешей найти несложно. Примерно 1 из каждых 256 хешей MD5 будет начинаться с '0e', а вероятность того, что остальные 30 символов будут цифрами, составляет (10/16)^30. Если вы посчитаете, то обнаружите, что вероятность того, что хеш MD5 приравнивается к нулю в PHP, составляет примерно один к 340 миллионам. На поиск приведенного выше примера у меня ушло около минуты (почти 216 миллионов попыток).

Точно такой же метод можно использовать для поиска аналогичных значений, которые работают с RIPEMD160. Вам просто нужно протестировать больше хешей, поскольку лишние цифры хеширования означают, что вероятность "коллизии" будет примерно одна из 14,6 миллиарда. Довольно много, но все же послушно (на самом деле, я нашел решение этой проблемы примерно за 15 минут, но я не публикую его здесь).

С другой стороны, вашему коду потребуется гораздо больше времени, чтобы найти решение. Во-первых, нет никакого смысла генерировать случайные входные данные. Последовательные значения будут работать так же, и их будет намного быстрее генерировать.

Если вы используете последовательные входные значения, вам также не нужно беспокоиться о повторении тех же вычислений хеша. Ваш код использует структуру списка для хранения ранее хешированных значений. Это ужасная идея. Поиск элемента в списке - это операция O(n), поэтому, как только ваш код (безуспешно) протестировал миллиард входов, ему придется сравнивать каждый новый вход с каждым из этих миллиардов входов на каждой итерации, в результате чего ваш код будет растереть до полной остановки. Ваш код действительно работал бы намного быстрее, если бы вы не беспокоились о проверке дубликатов. Когда у вас будет время, я предлагаю вам узнать, когда использовать списки, словари и множества в Python.

Другая проблема заключается в том, что ваш код проверяет только 10-значные числа, что означает, что он может проверять не более 10 миллиардов возможных входных данных. Основываясь на приведенных выше цифрах, вы уверены, что это разумный предел?

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

Вот код, который я использовал, чтобы найти столкновение MD5, о котором я упоминал ранее. Вы можете легко адаптировать его для работы с RIPEMD160, и вы можете преобразовать его в Python, если хотите (хотя код PHP намного проще):

$n = 0;
while (1) {
    $s = "0e$n";
    $h = md5($s);
    if ($s == $h) break;
    $n++;
}
echo "$s : $h\n";

---

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