Я пытаюсь найти коллизию между двумя сообщениями, которая приведет к одному и тому же хешу 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 байтов (I где-то читал, что CRC32 был биективным в этом пространстве сообщений), и чтобы избегать сообщений, которые слишком похожи (т. е. отличаются только одним или двумя символами), поскольку после того, как исходная цель CRC32 состоит в обнаружении (и, возможно, автоматическом -правильно) такие маленькие отличия в сообщениях.
Таким образом, представляется, что сложность задания заключается не столько в поиске способов вычисления CRC32 с невероятной скоростью (хотя и с этим тоже не следует медлить), сколько в управлении базой данных с возможностью быстрого поиска. до 200 000 сообщений (или «ключ сообщения», подробнее об этом ниже) и связанное с ними значение CRC32.
Несколько идей для реализации всего этого
Буквально вчера был этот вопрос здесь, на SO, пара указателей, упомянутых там, может вам помочь.
Грубая сила вам нужна о сообщениях случайной длины sqrt (6N) для хэша размера N, чтобы получить вероятность столкновения 95%. Например. CRC32 , N = 2^32 , вам нужно около 160 000 сообщений
Я предполагаю, что вы имеете в виду «сообщение» вместо «ключ».
Если вам разрешено выбирать оба «ключа», то перебор в любом случае будет довольно быстрым из-за парадокса дня рождения. Выбирайте случайные сообщения, вычисляйте их CRC, запоминайте их все вместе со связанным CRC, и каждое новое имеет все больше и больше шансов столкнуться с существующим по мере их накопления. Честно говоря, я ожидаю, что этот подход будет быстрее на современном компьютере, чем поиск известных подходов к конфликту CRC32.
Я считаю, что CRC являются линейными, поэтому, если вы изменяете (на месте, без изменения длины) две разные части вашего файла, различия в CRC должны быть объединены xor вместе.
-- поправочка: не все так просто. Тем не менее, это все еще тот подход, который я бы использовал, пытаясь построить столкновение - вам нужно следовать математике более подробно, чем я склонен делать сегодня вечером...
