CRC32 Collision

Question

Я пытаюсь найти столкновение между двумя сообщениями, которые приведут к одному и тому же CRC-хешу. Учитывая, что я использую CRC32, есть ли способ сократить список возможных сообщений, которые я должен попробовать при атаке грубой силы?

Любые ссылки на сайты с подсказками на этом будут полезны. У меня уже есть алгоритм грубой силы, который будет делать это, но он просто увеличивает целые числа и видит, будет ли он соответствовать другим хэшам.

Answer 1

Это зависит полностью от того, что вы подразумеваете под «сообщением». Если вы можете добавить четыре байта таблеток к одному из сообщений. (I.E. четыре байта, которые не имеют смысла в контексте сообщения.) Затем он становится тривиальным в прямом смысле этого слова.

Думая о битах, проходящих через конечный автомат CRC32.

CRC32 основан на сдвиговом регистре обратной связи galois, каждый бит в его состоянии будет заменен индукцией 32 бит из данных полезной нагрузки. При индукции каждого бита позиции, обозначенные полиномом, будут исключаться с последовательностью, наблюдаемой с конца регистра сдвига. Данные последовательности не влияют на входные данные до тех пор, пока регистр сдвига не будет заполнен.

В качестве примера, представьте мы имеем сдвиговый регистр, заполненный начальным состоянием 10101110, 10000011 полином, и заполнение неизвестных битов, Х.

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 до тех пор, СР был заполнен! Итак, чтобы создать сообщение с предопределенной контрольной суммой, вы берете свое новое сообщение, генерируете его CRC и разрабатываете его следующие 32 бита обратной связи. Это можно сделать в 32 шагах функции CRC. Затем вам необходимо рассчитать эффект, который эта обратная связь имеет на содержимое регистра сдвига.

Ярлык для этого состоит в том, чтобы заполнить ваше сообщение четырьмя нулевыми байтами, а затем посмотреть на контрольную сумму. (Контрольная сумма - это состояние SR в конце, которое, если заполнено четырьмя нулевыми байтами, является влиянием обратной связи и пустых байтов.)

Эксклюзивный ИЛИ, который влияет на значение контрольной суммы, которое вы хотите, замените четырехбайтовый трейлер на это вычисленное значение и восстановите контрольную сумму. Вы можете сделать это с помощью любой программы, которая генерирует CRC32, шестнадцатеричный редактор и калькулятор, который может обрабатывать hex.

Если вы хотите сгенерировать два сообщения, которые имеют полный смысл и не содержат конечный мусор, все становится немного сложнее. Определите несколько разделов, в которых вы можете написать правдоподобные альтернативы с точно такой же длиной.

Использование английской прозы в качестве примера. «Я думаю, что это может работать» и «Я верю в этот подход» Имеют широко похожие значения и точно такую ​​же длину.

Идентификация достаточно примеров в вашем сообщении - это сложный бит (если вы не хотите обманывать пробелы!) CRC 32 является линейным, если данные имеют правильное смещение в сообщении. Таким образом, CRC ([messagea] [padding])^CRC ([padding] [messageb]) = CRC ([messagea] [messageb]) Есть некоторые оговорки со выравниванием слов, с которыми вам нужно будет справиться, намек, вы хотите расширить проходы в «фиксированные» части сообщения. Как правило, вы хотите иметь альтернативы для n * 1.5 проходов, где n - размер CRC.

Теперь вы можете вычислить CRC, что имеет скелетное сообщение, впечатление, что каждый альтернативный проход будет иметь на нем, а затем составить таблицу, сравнив влияние, которое будет иметь каждая альтернатива для каждого прохода. Затем вам нужно выбрать альтернативы, которые изменят CRC скелета, чтобы соответствовать требуемому CRC. Эта проблема на самом деле довольно забавная для решения. Прежде всего, найдите любые альтернативы, которые однозначно изменяют бит, если этот бит необходимо изменить для вашего CRC, выберите эту альтернативу и сбросьте ее влияние на CRC, а затем снова развернитесь. Это должно сократить пространство для решения, которое вам нужно искать.

Это очень сложная задача для кодирования, но это создаст ваши столкновения за очень короткий промежуток времени.

Answer 2

Я предполагаю, что вы имеете в виду «сообщение» вместо «ключа».

Если вам разрешено выбирать обе «ключи», то грубая сила будет довольно быстрой в любом случае из-за парадокса рождения. Выбирайте случайные сообщения, вычисляйте их CRC, помните все из них и связанный с ними CRC, и каждый новый имеет все больше шансов столкнуться с существующим, когда они накапливаются. Честно говоря, я ожидаю, что этот подход будет быстрее на современном компьютере, чем поиск известных подходов к тому, чтобы CRC32 столкнулся.

Answer 3

Я считаю, что CRC являются линейными, поэтому, если вы изменяете (на месте, без изменения длины) две разные части вашего файла, различия в CRC должны быть сопоставлены друг с другом.

- Корректировка: кажется, это не так просто. Тем не менее, это по-прежнему тот подход, который я бы предпринял в попытке построить столкновение - вам нужно следовать математике более подробно, чем я склонен сегодня делать ...

Answer 4

Только вчера было this question here on SO, a пара указателей, упомянутых там, может вам помочь.

Answer 5

Короткие изъян с моим исчислению, вероятность не найдя одно столкновение после 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% 

Другими словами, вероятность того, чтобы вычислить более чем 200000 CRC32 значений , прежде чем найти дубликат менее чем 1%, или, вероятность нахождения дубликата до 102000 попыток 70,2%
BTW это замечательно, потому что вероятность нахождения одного столкновения, скажем, the very 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.

Несколько идей реализовать все это

• Нужна простая библиотека ISAM или более формальный интерфейс СУБД, такие как MySql или даже SqlLite.
• При использовании псевдо генератора случайных чисел (PRNG), для получения сообщений, мы можем сохранить сообщение ключей (то есть то, что мы кормить ПСЧ, чтобы произвести данное сообщение), а не хранить всю сообщения. Это сделало бы базу данных вставками и поисками более эффективными, рискуя ошибочно подбирать PRNG (точнее, случайные числа на основе генератора сообщений на основе случайных чисел), то есть тот, который создавал (поначалу) сообщения, которые как-то менее вероятны для CRC32- collide ...
• Возможно, лучше работать партиями, т.е. производить 1000 новых CRC, а затем проверять наличие коллизий и хранить их вместо того, чтобы делать все это для одного CRC за раз. Это особенно актуально, если мы используем готовые СУБД

Answer 6

Грубая сила, которая вам нужна о сообщениях случайной длины sqrt (6N) для хэша размера N, чтобы получить вероятность 95% столкновения. Например. CRC32, N = 2^32, вам нужно около 160 000 сообщений