Коллизия CRC16 (2 значения CRC блоков разного размера)

Проблема

У меня есть текстовый файл, который содержит одну строку в строке (разрыв строки \r\n). Этот файл защищен с помощью CRC16 двумя различными способами.

  1. CRC16 блоков по 4096 байт
  2. CRC16 блоков по 32768 байт

Теперь мне нужно изменить любой из этих 4096-байтовых блоков, чтобы он (блок)

  • содержит определенную строку
  • не изменяет размер текстового файла
  • имеет то же значение CRC, что и исходный блок (то же самое для блока 32 КБ, который содержит этот блок 4 КБ)

Помимо этих ограничений, я могу вносить любые изменения в блок, необходимые для его заполнения, если сам файл не нарушает его формат. Я думаю, что лучше всего использовать любой из полностью заполненных блоков 4k, а не последний блок, который может быть очень коротким.

Вопрос

Как мне начать решать эту проблему? Первое, что я бы придумал, это какой-то брутфорс, но не потребуется ли очень много времени, чтобы найти изменения, которые приведут к тому, что оба значения CRC останутся прежними? Возможно, есть математический способ решить это?

Это должно быть сделано в секундах или макс. несколько минут.


security crc crc16 hash-collision
person grubi    schedule 02.09.2013    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Есть есть математические способы решения этой проблемы, но я их не знаю. Я предлагаю грубое решение:

Блок выглядит так:

SSSSSSSMMMMEEEEEEE

Каждый символ представляет собой байт. S = начальные байты, M = байты, которые вы можете изменить, E = конечные байты.

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

Вам также не нужно пересчитывать следующие байты. Вам просто нужно проверить, является ли состояние CRC таким же или другим после внесенной вами модификации. Если это то же самое, весь блок также будет таким же. Если он отличается, весь блок, скорее всего, будет другим (не гарантируется, но вам следует прервать пробную версию). Таким образом, вы вычисляете CRC только части S+M' (где M' — это измененные байты). Если он равен состоянию CRC(S+M), вы выиграли.

Таким образом, у вас будет гораздо меньше данных для обработки, а последний настольный компьютер или сервер сможет выполнить необходимые 2^32 испытания за несколько минут. Используйте параллелизм.

person usr    schedule 02.09.2013
comment
Эта оптимизация настолько проста, что мне это и в голову не пришло... (Не так уж важно, но почему 2^32?) Я надеюсь, что кто-то еще мог бы предоставить дополнительные данные по математике, которые могли бы быть с даже лучшая производительность. - person grubi; 02.09.2013
comment
CRC32 имеет 2^32 возможных значения. Вероятность того, что одна модификация станет хитом, составляет 1/2^32. В среднем вы должны рискнуть 2^32. - person usr; 02.09.2013
comment
Хорошо. CRC16 - это то, что у меня есть, поэтому я был немного раздражен. Я только что реализовал ваш подход, и он работает как шарм. Спасибо еще раз. - person grubi; 02.09.2013

arrow_upward
0
arrow_downward

Взгляните на spoof.c. Это напрямую решит вашу проблему с CRC блока 4K. Однако вам потребуется изменить код, чтобы решить проблему одновременно для CRC блока 4K и CRC окружающего блока 32K. Это просто вопрос добавления большего количества уравнений для решения. Код работает очень быстро и выполняется за O(log(n)) раз, где n — длина сообщения.

Основная идея состоит в том, что вам нужно будет решить 32 линейных уравнения над полем GF(2) с 32 или более неизвестными, где каждое неизвестное — это битовая позиция, которую вы разрешаете изменять. Важно предоставить более 32 неизвестных для решения задачи, поскольку, если вы выберете ровно 32, вполне вероятно, что вы получите сингулярную матрицу и не получите решения. Поддельный код автоматически найдет неоднозначные варианты 32 неизвестных битовых местоположений из > 32, которые вы предоставили.

person Mark Adler    schedule 02.09.2013
comment
Это выглядит интересно (с большим количеством комментариев), но довольно сложно. Я посмотрю и постараюсь понять, что он делает. Спасибо. - person grubi; 03.09.2013