[Перевод] Развлечения с хеш-коллизиями03.07.2023 13:02

Мой друг и коллега по цеху, блоггер Сэм, недавно опубликовал своё третье иллюстрированное руководство, темой которого стало хеширование. Нет острой необходимости читать его руководство перед прочтением моей статьи, но я очень рекомендую вам это сделать. Хотя бы ради того, чтобы посмотреть на восхитительные анимации, от которых невозможно оторваться. Честно — они просто потрясающие. Тут, к сожалению, анимаций вы не найдёте, поэтому насмотритесь на них в той статье, а потом возвращайтесь сюда. Здесь вы сможете немного позабавиться поиском коллизий алгоритма хеширования MurmurHash3.

Сразу хочу отметить, что этот материал я писал исключительно ради развлечения. Ничто из того, что я тут покажу, не предназначено для продакшн-кода. И вот, как всегда,  ссылка на GitHub-репозиторий, в котором можно найти код к этой статье.

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

Змеи и лестницы

Сэм любезно поделился соответствующим Python-скриптом. На моей дряхлеющей машине (i7–6700k) этот скрипт выдал 3311080 хешей за 10 секунд:

import time
import mmh3
from uuid import uuid4

start = time.perf_counter()
inc = 0

while True:
   val = str(uuid4())
   h = mmh3.hash(val)
   if h == 1228476406:
      print(val)
   stop = time.perf_counter()
   duration = stop - start
   inc = inc + 1
   if duration >= 10:
      print(inc)
      break

Этот скрипт у меня работал примерно полчаса, ни одной коллизии я за это время не обнаружил. Мой рабочий язык программирования — C#, поэтому я решил перенести вычисления в более привычную для меня среду.

Заточка инструментов

Первая попытка переписать этот Python-скрипт на C#, не прибегая к каким-то ухищрениям, дала 37759012 хешей за 10 секунд:

while (true)
{
    var guidString = Guid.NewGuid().ToString();
    var stringBytes = Encoding.ASCII.GetBytes(guidString);
    var computeHash = murmurHash32.ComputeHash(stringBytes);
    var int32 = BitConverter.ToInt32(computeHash);

    if (int32 == 1228476406)
    {
        Console.WriteLine(guidString);
    }
}

Это неплохо, но я подумал, что кое-что тут можно и улучшить. Во-первых — решил перейти от UTF8 к ASCII. Это довело скорость до 39656732 хешей за 10 секунд:

39,656,732 hashes per ten seconds
Took: 10,000 ms
Allocated: 7,435,745 kb
Peak Working Set: 26,180 kb
Gen 0 collections: 1820
Gen 1 collections: 1
Gen 2 collections: 0

Я запускал эту версию кода в 4–6 экземплярах и смог найти примерно за полчаса штук двадцать коллизий.

Случайные байты

Сейчас мы, для получения GUID v4, пользуемся методом Guid.NewGuid(). Но нам, на самом деле, не особо нужен именно GUID v4. Нас вполне устроит значение, похожее на такой идентификатор:

byte[] guidBytes = new byte[16];
var random = new Random();

while (true)
{
    Array.Clear(guidBytes);
    random.NextBytes(guidBytes);

    var guidString = new Guid(guidBytes).ToString();
    // сокращено
}

Благодаря тому, что мы заполняем байтовый массив случайными значениями и конструируем на его основе наш вариант GUID, удалось добиться скорости в 49788883 хешей за 10 секунд:

49,788,883 hashes per ten seconds
Took: 10,000 ms
Allocated: 9,335,517 kb
Peak Working Set: 26,416 kb
Gen 0 collections: 2285
Gen 1 collections: 1
Gen 2 collections: 0

А переключение с байтового массива на Span дало ещё небольшой, но приятный, прирост скорости:

Span guidBytes = stackalloc byte[16];
var random = new Random();

while (true)
{
    guidBytes.Clear();
    random.NextBytes(guidBytes);

    var guidString = new Guid(guidBytes).ToString();
    // сокращено
}

Вот как показал себя этот вариант кода:

53,015,764 hashes per ten seconds
Took: 10,016 ms
Allocated: 9,940,562 kb
Peak Working Set: 26,448 kb
Gen 0 collections: 2434
Gen 1 collections: 1
Gen 2 collections: 0

Более быстрая реализация хеш-функции

Ещё немного производительности можно добыть, преобразовав и строку в структуру Span:

Span guidBytes = stackalloc byte[16];
Span stringBytes = stackalloc byte[36];

while (true)
{
    guidBytes.Clear();
    stringBytes.Clear();
    random.NextBytes(guidBytes);

    var guidString = new Guid(guidBytes).ToString().AsSpan();
    Encoding.ASCII.GetBytes(guidString, stringBytes);
    // сокращено
}

На данном этапе развития нашего кода наиболее значительное улучшение, которое можно было бы в него внести, заключается в отказе от работы со строками (потому что строки — это зло). Сейчас мы пользуемся реализацией алгоритма MurmurHash3 из библиотеки FastHashes. Прежде чем избавляться от строк — посмотрим, существуют ли другие реализации этого алгоритма. Для оценки производительности кода будем пользоваться BenchmarkDotNet — это позволит обеспечить точные и сравнимые результаты исследований.

Обратившись к Google, я тут же нашёл статью Орена Эйни, идеи которого, в комментариях, доработал Стюарт Лэнг. Код, написанный под влиянием всего этого, я назвал OrenAndStu. Оценка производительности моего изначального кода (A_FastHashes в следующей таблице) и нового (B_OrenAndStu) на миллионе итераций показала, что вариант OrenAndStu гораздо быстрее, чем вариант FastHashes:

Теперь моя задача состояла в том, чтобы найти реализацию алгоритма, которая была бы быстрее, чем OrenAndStu. Мне лень было разводить бурную деятельность, поэтому я просто установил несколько пакетов из nuget и дал поработать BenchmarkDotNet:

Единственной реализацией алгоритма, которая была быстрее, чем OrenAndStu, оказалась JeremyEspresso. Переход на неё позволил преодолеть барьер в 60000000 хешей за 10 секунд:

60,358,517 hashes per ten seconds
Took: 10,000 ms
Allocated: 5,658,711 kb
Peak Working Set: 25,992 kb
Gen 0 collections: 1385
Gen 1 collections: 1
Gen 2 collections: 0

Байты и ничего кроме байтов

Если в программе имеется много строк (а значит — много операций по выделению памяти) — это обычно не очень хорошо для производительности. Сейчас мы работаем так:

• Генерируем случайные байты.

• Конвертируем то, что получилось, в GUID.

• Преобразуем этот GUID в строку.

• Вытаскиваем байты из строкового представления GUID.

В идеале стоило бы всё время работать только с байтами. Тогда удалось бы избавиться от большей части операций по выделению памяти, и, хочется надеяться, удалось бы ускорить код. Для того чтобы это сделать, нам надо заглянуть в класс, ответственный за работу с GUID, и позаимствовать оттуда несколько внутренних методов:

Span guidBytes = stackalloc byte[16];
Span stringBytes = stackalloc byte[36];

while (true)
{
    guidBytes.Clear();
    stringBytes.Clear();
    random.NextBytes(guidBytes);

    Ugly.GuidBytesToRegularBytes(guidBytes, stringBytes);

    ReadOnlySpan stringBytes1 = stringBytes;
    var int32 = MurmurHash.MurmurHash3.Hash32(ref stringBytes1, 0);
}

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

64,052,282 hashes per ten seconds
Took: 10,031 ms
Allocated: 110 kb
Peak Working Set: 21,224 kb
Gen 0 collections: 0
Gen 1 collections: 0
Gen 2 collections: 0

Избавляемся от GUID

Учитывая то, что нас интересует нахождение любых входных данных, имеющий конкретный хеш (то есть — коллизий), нам не нужно цепляться за GUID. Нас устраивают любые входные данные. Попробуем сгенерировать восьмибайтовый массив на основе алфавитно-цифровых данных (a-z,  A-Z,  0-9) и посмотрим на то, что произойдёт:

Span stringBytes = stackalloc byte[8];
var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789".Select(x => (byte)x).ToArray();

while (true)
{
    stringBytes.Clear();
    stringBytes[0] = chars[random.Next(0, chars.Length)];
    stringBytes[1] = chars[random.Next(0, chars.Length)];
    stringBytes[2] = chars[random.Next(0, chars.Length)];
    stringBytes[3] = chars[random.Next(0, chars.Length)];
    stringBytes[4] = chars[random.Next(0, chars.Length)];
    stringBytes[5] = chars[random.Next(0, chars.Length)];
    stringBytes[6] = chars[random.Next(0, chars.Length)];
    stringBytes[7] = chars[random.Next(0, chars.Length)];
    // сокращено
}

А произошло вот что:

156,659,240 hashes per ten seconds
Took: 10,047 ms
Allocated: 102 kb
Peak Working Set: 22,132 kb
Gen 0 collections: 0
Gen 1 collections: 0
Gen 2 collections: 0

А что если убрать алфавитно-цифровые данные и ограничиться восьмибайтовым массивом, заполненным, как раньше, случайными значениями?

Span stringBytes = stackalloc byte[8];

while (true)
{
    stringBytes.Clear();
    random.NextBytes(stringBytes);
}

Вот результат:

329,339,000 hashes per ten seconds
Took: 10,031 ms
Allocated: 102 kb
Peak Working Set: 21,076 kb
Gen 0 collections: 0
Gen 1 collections: 0
Gen 2 collections: 0

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

(Hash)cat: кошка среди голубей

До сих пор узким местом нашей системы вычисления хешей был CPU. Но дело в том, что подобные нагрузки, если честно, не очень хорошо подходят для процессоров. С такой работой лучше всего справляются GPU. Hashcat — это программа, существующая только в виде инструмента командной строки, которая создана для взлома хешей паролей (вот ещё интересная история: мы использовали её в работе для взлома продакшн-паролей, но об этом — в другой раз). К ней подготовлена хорошая справка.

В применении Hashcat есть одна тонкость. Дело в том, что эта программа ожидает, чтобы целевое значение было бы представлено в определённом формате. Обычно это — hash:salt. Выполнение команды hashcat.exe --hash-info -m 27800 показывает, что значение hashcat, представленное в виде обычного текста, имеет хеш 23e93f65. Это являет собой некоторую проблему, так как до сих пор мы использовали для представления хешей целые числа. Если пропустить hashcat через одну из версий нашего кода — мы получим целочисленное значение 602488677. После этого, чтобы получить ту же самую строку, нам нужно обратить массив хешированных байтов и сгенерировать строку, представляющую шестнадцатеричное значение:

var buffer = Encoding.ASCII.GetBytes("hashcat");
var computeHash = new FastHashes.MurmurHash32().ComputeHash(buffer);
Console.WriteLine(BitConverter.ToString(computeHash.Reverse().ToArray()).Replace("-", "").ToLower());
Console.WriteLine(BitConverter.ToInt32(computeHash, 0));

Я вполне уверен в том, что массив надо обращать из-за порядка байтов в системе, поэтому, если вы воспроизводите у себя мои эксперименты, убедитесь в том, что у вас всё представляется в правильном виде. После того, как мы сделали то же самое для одного из известных нам входных значений «целочисленного» хеширования (1228476406), мы узнали, что интересующая нас «шестнадцатеричная» строка — 49390ff6.

.\hashcat.exe -a 3 -m 27800 49390ff6:00000000 ?a?a?a?a?a?a?a?a --keep-guessing --runtime=10

Моя древняя видеокарта HD6950 выдала 31 входное значение, имеющее интересующие нас хеш-коллизии. Hashcat, кроме того, выводит статистические данные после завершения работы:

Session..........: hashcat
Status...........: Aborted (Runtime)
Hash.Mode........: 27800 (MurmurHash3)
Hash.Target......: 49390ff6:00000000
Time.Started.....: Sun Jun 18 00:04:22 2023 (10 secs)
Time.Estimated...: Sun Jun 25 01:15:33 2023 (7 days, 1 hour; Runtime limit exceeded)
Kernel.Feature...: Optimized Kernel
Guess.Mask.......: ?a?a?a?a?a?a?a?a [8]
Guess.Queue......: 1/1 (100.00%)
Speed.#1.........: 10892.3 MH/s (4.10ms) @ Accel:128 Loops:256 Thr:64 Vec:4
Recovered........: 0/1 (0.00%) Digests
Progress.........: 107105746944/6634204312890625 (0.00%)
Rejected.........: 0/107105746944 (0.00%)
Restore.Point....: 0/7737809375 (0.00%)
Restore.Sub.#1...: Salt:0 Amplifier:544512-544768 Iteration:0-256
Candidate.Engine.: Device Generator
Candidates.#1....: Uz#erane -> C3$B?tan

Арендуем GPU

Учитывая то, что моя видеокарта сделана в 2010 году, я уверен в том, что современное железо поможет улучшить ситуацию с семидневным ожиданием результатов, о котором предупредила нас Hashcat:  Time.Estimated...: Sun Jun 25 01:15:33 2023 (7 days, 1 hour; Runtime limit exceeded). Я решил арендовать RTX 3090 на genesiscloud.com (не хочу ничего скрывать — ссылка это реферальная, воспользовавшись ей, вы получите бонусы на $50). Создавать новые инстансы в этом сервисе очень просто, а вот установка Hashcat на Ubuntu оказалась не такой простой задачей. Дело в том, что я, преимущественно, работаю в Windows. Но мне, тем не менее, удалось всё запустить (пришлось, признаюсь, изрядно покопипастить). В результате тот же самый код выдал уже 433 входных значения.

Session..........: hashcat
Status...........: Aborted (Runtime)
Hash.Mode........: 27800 (MurmurHash3)
Hash.Target......: 49390ff6:00000000
Time.Started.....: Sat Jun 17 23:21:21 2023 (10 secs)
Time.Estimated...: Sun Jun 18 07:57:16 2023 (8 hours, 35 mins; Runtime limit exceeded)
Kernel.Feature...: Optimized Kernel
Guess.Mask.......: ?a?a?a?a?a?a?a?a [8]
Guess.Queue......: 1/1 (100.00%)
Speed.#1.........:   214.3 GH/s (6.32ms) @ Accel:64 Loops:1024 Thr:256 Vec:1
Recovered........: 0/1 (0.00%) Digests
Progress.........: 2112133758976/6634204312890625 (0.03%)
Rejected.........: 0/2112133758976 (0.00%)
Restore.Point....: 1343488/7737809375 (0.02%)
Restore.Sub.#1...: Salt:0 Amplifier:714752-715776 Iteration:0-1024
Candidate.Engine.: Device Generator
Candidates.#1....: UcX}eTON -> xw(>N223
Hardware.Mon.#1..: Temp: 49c Fan:  0% Util: 99% Core:1890MHz Mem:9501MHz Bus:16

Мораль сей басни такова: если надо искать хеш-коллизии (для некриптографических хеш-алгоритмов) — не морочьте голову написанием своего кода. Просто позовите кота (Hash)cat.

О, а приходите к нам работать?

© Habrahabr.ru