Я пытаюсь найти коллизию между двумя сообщениями, которая приведет к тому же хешу CRC. Учитывая, что я использую CRC32, можно ли как-нибудь сократить список возможных сообщений, которые я должен попробовать при проведении атаки методом перебора?
Любые ссылки на сайты с подсказками на это будут полезны. У меня уже есть алгоритм перебора, который будет делать это, но он просто увеличивает целые числа и проверяет, будет ли он соответствовать другим хэшам.
Это полностью зависит от того, что вы подразумеваете под "сообщением". Если вы можете добавить четыре байта бреда к одному из сообщений. (То есть четыре байта, которые не имеют смысла в контексте сообщения.) Тогда это становится тривиальным в прямом смысле этого слова.
Мышление в терминах битов, движущихся через конечный автомат CRC32.
CRC32 основан на регистре сдвига обратной связи Галуа, каждый бит в его состоянии будет заменен на 32 бита из данных полезной нагрузки. При вводе каждого бита позиции, указанные полиномом, будут исключены с последовательностью, наблюдаемой с конца регистра сдвига. На эту последовательность не влияют входные данные, пока регистр сдвига не будет заполнен.
В качестве примера представим, что у нас есть сдвиговый регистр, заполненный начальным состоянием 10101110, полиномом 10000011 и заполнением неизвестными битами X.
Polynomial * ** |feedback (End of SR.)
State 10101110 0
State X1010111 1
State XX101000 0
State XXX10100 0
State XXXX1010 0
State XXXXX101 1
State XXXXXX01 1
State XXXXXXX1 1
State XXXXXXXX 0
Обратная связь не в терминах X, пока SR не будет заполнено! Таким образом, чтобы сгенерировать сообщение с заранее определенной контрольной суммой, вы берете новое сообщение, генерируете его CRC и обрабатываете его следующие 32 бита обратной связи. Это вы можете сделать в 32 шагах функции CRC. Затем вам необходимо рассчитать влияние этой обратной связи на содержимое регистра сдвига.
Чтобы сделать это, нужно добавить в сообщение четыре нулевых байта, а затем посмотреть контрольную сумму. (Контрольная сумма - это состояние SR в конце, которое, если дополнено четырьмя нулевыми байтами, является влиянием обратной связи и пустых байтов.)
Исключительное ИЛИ, которое влияет на требуемое значение контрольной суммы, замените четырехбайтовый трейлер на это вычисленное значение и восстановите контрольную сумму. Вы можете сделать это с любой программой, которая генерирует CRC32, редактор шестнадцатеричных кодов и калькулятор, который может обрабатывать шестнадцатеричные значения.
Если вы хотите сгенерировать два сообщения, которые имеют полный смысл и не содержат завершающего мусора, все становится немного сложнее. Определите количество разделов, которые вы можете написать правдоподобные альтернативы, с одинаковой длиной.
Используя английскую прозу в качестве примера. "Я думаю, что это может сработать" и "Я верю в такой подход" имеют в целом одинаковое значение и одинаковую длину.
Определение достаточного количества примеров в вашем сообщении - хитрый бит (если только вы не хотите обманывать пробелами!) CRC 32 является линейным, если данные имеют правильное смещение в сообщении. Так что CRC ([messagea] [padding]) ^ CRC ([padding] [messageb]) = CRC ([messagea] [messageb]) Есть несколько предостережений с выравниванием слов, с которыми вам нужно справиться, как общая подсказка Вы хотите расширить отрывки на "фиксированные" части сообщения. Как правило, вы хотите иметь альтернативы для n * 1,5 пассажей, где n - это размер CRC.
Теперь вы можете рассчитать CRC, который имеет скелетное сообщение, впечатление, которое будет иметь каждый альтернативный пассаж, и затем составить таблицу, сравнивая влияние, которое окажет каждая альтернатива для каждого прохода. Затем вам нужно выбрать альтернативы, которые изменят CRC скелета, чтобы соответствовать CRC, который вы хотите. Эту проблему на самом деле довольно забавно решить. Прежде всего найдите любые альтернативы, которые однозначно изменяют немного, если этот бит нужно изменить для вашего CRC, выберите эту альтернативу и сложите ее влияние в CRC, а затем снова обойдите. Это должно уменьшить пространство решения, которое вам нужно искать.
Это довольно сложная задача для кодирования, но это приведет к возникновению коллизий за очень короткий промежуток времени.
Если не считать ошибки в моем исчислении, вероятность того, что не будет найдено ни одного столкновения после N испытаний, аппроксимирована в следующей таблице:
N Probability ------- ----------- 50,000 74.7% 77,000 50.1% 78,000 49.2% 102,000 29.8% 110,000 24.5% 128,000 14.8% 150,000 7.3% 200,000 0.95%
Другими словами, вероятность вычисления более 200 000 значений CRC32 до нахождения дубликата составляет менее 1%, или вероятность нахождения дубликата до 102 000 попыток составляет 70,2%.
Кстати, это замечательно, потому что вероятность нахождения одного столкновения, скажем, на самой 200 000-й попытке все еще составляет порядка 1/1000-й от 1% ((4M - 200,0000)/4M), но, вероятно, обнаружила одно коллизия перед 200 000-й попыткой является квази определенностью (ну, в любом случае, выше 99%). Это показывает интерес к сохранению базы данных CRC, рассчитанной до настоящего времени.
Конечно, мы могли бы потратить некоторое время на изучение алгоритма CRC32 и лежащей в его основе математики, пытаясь найти сообщения с большей вероятностью вызвать коллизии CRC32, но относительно небольшое число действительно случайных попыток, необходимых для нахождения хотя бы одного коллизии с квазиопределенностью, делает этот вид криптоанализа вряд ли стоит усилий. Например, если предположить, что мы можем найти способ выбора сообщений, которые в 10 раз чаще сталкиваются друг с другом, нам все равно придется попробовать порядка 63 000 раз, прежде чем достичь вероятности 99% иметь хотя бы одно коллизия ( лучше, чем 200 000, но все еще требует примерно того же типа приложения.)
Единственное, что мы можем рассмотреть в этой области, - это избегать сообщений короче 4-х байтов (я где-то читал, что CRC32 был биективным в этом пространстве сообщений) и избегать слишком похожих сообщений (то есть отличающихся только один или два символа), поскольку после CRC32 первоначальной целью является обнаружение (и, возможно, автоматическое исправление) таких небольших различий в сообщениях.
Следовательно, похоже, что сложность назначения заключается не столько в том, чтобы найти способы вычисления CRC32 с невероятной скоростью (хотя мы не должны быть слишком медленными с этим), а скорее в том, чтобы управлять быстро ищущейся базой данных до 200 000 сообщений (или "ключ" сообщения, подробнее об этом ниже) и соответствующее значение CRC32.
Несколько идей для реализации всего этого
Я предполагаю, что вы имеете в виду "сообщение" вместо "ключ".
Если вам разрешат выбрать оба "ключа", то грубая сила все равно будет довольно быстрой из-за парадокса дня рождения. Выбирайте случайные сообщения, вычисляйте их CRC, запоминайте их все и связанный CRC, и у каждого нового появляется все больше и больше шансов столкнуться с существующим по мере их накопления. Честно говоря, я ожидаю, что этот подход будет быстрее на современном компьютере, чем поиск известных подходов, чтобы заставить CRC32 сталкиваться.
Я считаю, что CRC являются линейными, поэтому, если вы изменяете (на месте, не изменяя длину) две разные части вашего файла, различия в CRC должны быть сведены воедино.
- исправление: все не так просто. Тем не менее, это все еще тот способ, которым я бы воспользовался, пытаясь построить коллизия - вы должны следовать математике более подробно, чем я склонен сделать сегодня вечером...
Буквально вчера здесь был такой вопрос на SO, пара упомянутых там указателей может вам помочь.
Грубой силой вам нужно около 6 сообщений случайной длины sqrt для хэша размера N, чтобы получить 95% вероятности столкновения. Например, CRC32, N = 2 ^ 32, вам нужно около 160 000 сообщений.