Когда лучше использовать CRC, чем MD5 / SHA1?

130

Когда уместно использовать CRC для обнаружения ошибок по сравнению с более современными функциями хеширования, такими как MD5 или SHA1? На встраиваемом оборудовании проще реализовать первое?

Гили
источник

Ответы:

114

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

CRC в вычислительном отношении намного проще, чем MD5 или SHA1. Использование хеш-функции, такой как MD5, вероятно, является излишним для обнаружения случайных ошибок. Однако использование CRC для любого вида проверки безопасности было бы гораздо менее безопасным, чем более сложная функция хеширования, такая как MD5.

И да, CRC намного проще реализовать на встроенном оборудовании, вы даже можете получить для этого разные пакетные решения на IC.

определяет
источник
1
@gili: вы всегда можете просто соединить двойные слова вместе, чтобы получить одно результирующее двойное слово.
Blindy
2
@Dustin: Вы полностью правы в своем ответе, но, возможно, подумайте об изменении «CRC в вычислительном отношении намного эффективнее» на «CRC в вычислительном отношении намного проще»? Алгоритмы MD5 / SHA-1 сложны, но не совсем «неэффективны» IMO.
Coxy 03
1
@coxymla, вы правы, мне следовало использовать слово «сложный», а не «неэффективный». Спасибо!
определяет
27
Чтобы уменьшить любой длинный хэш до 32 бит, просто возьмите первые 32 бита.
orip
1
Если ваша цель - безопасность, вы никогда не должны использовать MD5, SHA-1этого также следует избегать, SHA-2рекомендуется какой-либо вариант .
Питер
33

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

Также посмотрите это .

Лиран Ореви
источник
Самая важная часть ссылки в этом ответе: «(...) даже 2048-битный CRC был бы криптографически намного менее безопасным, чем 128-битный MD5»
Marc.2377,
3
Хотя ответ по-прежнему верен, в настоящее время MD5 и SHA1 находятся на одном уровне безопасности. Другими словами, хорош только для обнаружения непреднамеренных ошибок.
Писквор покинул здание
21

Я нашел исследование, которое показывает, насколько неуместны хеши CRC для хеш-таблиц . Это также объясняет фактические характеристики алгоритма. Исследование также включает оценку других алгоритмов хеширования и является хорошим справочником.

Соответствующий вывод по CRC для хешей:

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

ОБНОВИТЬ

Похоже, сайт не работает. В интернет-архиве есть копия .

Андре Луус
источник
Ссылка не работает. Может, ты сам объяснишь? В противном случае ответ бесполезен.
ceving
Хорошо, я включу заключение в свой ответ.
Андре Луус
Странно, согласно приведенному здесь тесту , CRC действительно неплохо справляется с точки зрения скорости и количества столкновений.
острокач
Действительно, очень интересно. Мне пришлось еще раз просмотреть исследование, с которым я связался, но если мне пришлось догадываться, это должно быть из-за различных реализаций тестирования. Если бы мне пришлось принимать решение, я бы обратился за советом из исследования, он кажется более обоснованным с научной точки зрения.
Андре Луус
По моему опыту хеширования миллионов URL-адресов, CRC64 столкнулся 8 раз, а MD5 - 5. Очевидно, MD5 был лучше, но CRC64 был отличным, гораздо более быстрым и простым хешем.
J. Dimeo
18

Я запускал каждую строку этого PHP-кода в цикле 1.000.000. Результаты в комментариях (#).

hash('crc32', 'The quick brown fox jumped over the lazy dog.');#  750ms   8 chars
hash('crc32b','The quick brown fox jumped over the lazy dog.');#  700ms   8 chars
hash('md5',   'The quick brown fox jumped over the lazy dog.');#  770ms  32 chars
hash('sha1',  'The quick brown fox jumped over the lazy dog.');#  880ms  40 chars
hash('sha256','The quick brown fox jumped over the lazy dog.');# 1490ms  64 chars
hash('sha384','The quick brown fox jumped over the lazy dog.');# 1830ms  96 chars
hash('sha512','The quick brown fox jumped over the lazy dog.');# 1870ms 128 chars

Мой вывод:

  • Используйте crc32b, если вам нужна http://en.wikipedia.org/wiki/Cyclic_redundancy_check и вам не важна безопасность.
  • Используйте «sha256» (или выше), когда вам нужен дополнительный уровень безопасности.

  • Не используйте «md5» или «sha1», потому что у них есть:

    1. некоторые проблемы с безопасностью, когда вы заботитесь о безопасности
    2. длиннее хеш-строки и медленнее, чем "crc32b", когда все, что вам нужно, это CRC
Мартин
источник
Вы имеете в виду биты, а не символы
esskar
На самом деле, нет. echo hash ('crc32', 'Быстрая коричневая лисица перепрыгнула через ленивого пса.'); повторяет «413a86af», что представляет собой строку длиной 8 символов. Кстати, это 32-битное число, хранящееся в формате HEX. Например, «sha256» имеет 256-битный хэш, который снова сохраняется как HEX, что дает строку длиной 64 символа.
Мартин
45
Эти результаты очень обманчивы. Когда эти алгоритмы хеширования применяются к большому набору данных ( вместо « Войны и мира»"The quick brown fox jumped over the lazy dog." ), вы увидите, насколько быстрее CRC, чем MD5.
ubiquibacon 07
1
Есть промежуточный случай (проверка дубликатов в библиотеках), где MD5 / Sha1 - правильное решение: им не нужно обрабатывать случай, когда противник тщательно обрабатывает исчезающе маловероятное хэш-коллизию, но им нужно обрабатывать случайные коллизии. Итак: Обнаружение битовых ошибок и повреждений: CRC32 Обнаружение конфликтов в библиотеках: MD5 / SHA1 Противоречивые приложения: Sha256 и выше. Конечно, если у вас есть библиотека с миллиардами записей, вам, вероятно, также потребуется увеличить хеш-биты.
Деви Морган
PHP? на платформе ARM, встроенный код, 16 МГц, CRC32 из 46 байтов, может быть, 12 микросекунд. У этого есть аппаратная помощь. Даже AES с аппаратной поддержкой будет в несколько сотен раз медленнее. CRC таблицы поиска без посторонней помощи все еще должен прийти примерно за 50 микросекунд.
ilgitano
11

Информацию о CRC по реализации, скорости и надежности см. В «Безболезненном руководстве по алгоритмам обнаружения ошибок CRC» . Там все на CRC.

Если только кто-то не попытается злонамеренно изменить ваши данные и скрыть изменение, достаточно CRC. Просто используйте «Хороший» (стандартный) полином.

Gerhard
источник
9

Все зависит от ваших требований и ожиданий.

Вот краткие различия между этими алгоритмами хэш-функции :

CRC (CRC-8/16/32/64)

  • это не криптографический алгоритм хэширования (он использует линейную функцию на основе циклической проверки избыточности)
  • может производить 9, 17, 33 или 65 бит
  • не предназначен для использования в криптографических целях, поскольку не дает никаких криптографических гарантий,
  • непригоден для использования в цифровых подписях, потому что он легко обратимый 2006 ,
  • не следует использовать в целях шифрования,
  • разные строки могут вызвать столкновение,
  • изобретен в 1961 году и используется в Ethernet и многих других стандартах,

MD5

  • это криптографический алгоритм хеширования,
  • создание 128-битного (16-байтового) хэш-значения (32-значные шестнадцатеричные числа)
  • это криптографический хеш, но он считается устаревшим, если вы беспокоитесь о безопасности,
  • известны строки с одинаковым значением хеш-функции MD5
  • может использоваться в целях шифрования,

SHA-1

  • это криптографический алгоритм хеширования,

  • создает 160-битное (20-байтовое) хеш-значение, известное как дайджест сообщения

  • это криптографический хэш, и с 2005 года он больше не считается безопасным,

  • может использоваться в целях шифрования,

  • найден пример столкновения sha1

  • впервые опубликовано в 1993 году (как SHA-0), затем в 1995 году как SHA-1,

  • серии: SHA-0, SHA-1, SHA-2, SHA-3,

    Таким образом, использование SHA-1 больше не считается безопасным против хорошо финансируемых противников, потому что в 2005 году криптоаналитики обнаружили атаки на SHA-1, что предполагает, что он может быть недостаточно безопасным для постоянного использования schneier . NIST США советует федеральным агентствам прекратить использование SHA1-1 для приложений, требующих защиты от столкновений, и должно использовать SHA-2 после NIST 2010 года .

Поэтому, если вы ищете простое и быстрое решение для проверки целостности файлов (от повреждения) или для некоторых простых целей кэширования с точки зрения производительности, вы можете рассмотреть CRC-32, для хеширования вы можете рассмотреть возможность использования MD5, однако, если вы разрабатываете профессиональное приложение (которое должно быть безопасным и согласованным), чтобы избежать любых вероятностей коллизии, используйте SHA-2 и выше (например, SHA-3).

Производительность

Несколько простых тестов производительности в PHP:

# Testing static text.

$ time php -r 'for ($i=0;$i<1000000;$i++) crc32("foo");'
real    0m0.845s
user    0m0.830s
sys     0m0.008s

$ time php -r 'for ($i=0;$i<1000000;$i++) md5("foo");'
real    0m1.103s
user    0m1.089s
sys     0m0.009s

$ time php -r 'for ($i=0;$i<1000000;$i++) sha1("foo");'
real    0m1.132s
user    0m1.116s
sys   0m0.010s

# Testing random number. 

$ time php -r 'for ($i=0;$i<1000000;$i++) crc32(rand(0,$i));'
real    0m1.754s
user    0m1.735s
sys     0m0.012s\

$ time php -r 'for ($i=0;$i<1000000;$i++) md5(rand(0,$i));'
real    0m2.065s
user    0m2.042s
sys     0m0.015s

$ time php -r 'for ($i=0;$i<1000000;$i++) sha1(rand(0,$i));'
real    0m2.050s
user    0m2.021s
sys     0m0.015s

Связанный:

kenorb
источник
8

Вы не говорите, что пытаетесь защитить.

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

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

Были комментарии, что хэш обеспечивает большую вероятность обнаружения повреждения, чем CRC с множественными битовыми ошибками. Это правда, и решение о том, использовать ли 16- или 32-битную CRC, будет зависеть от последствий для безопасности используемого поврежденного блока данных и от того, можете ли вы оправдать вероятность 1 из 2 ^ 16 или 2 ^ 32 блок данных неправильно объявлен действительным.

Многие устройства имеют встроенный генератор CRC для стандартных алгоритмов. Серия MSP430F5X из Техаса имеет аппаратную реализацию стандарта CRC-CCITT.

uɐɪ
источник
6

CRC32 работает быстрее, а длина хэша составляет всего 32 бита.

Используйте его, когда вам просто нужна быстрая и легкая контрольная сумма. CRC используется в сети Ethernet.

Если вам нужна большая надежность, предпочтительнее использовать современную функцию хеширования.

Франсуа
источник
5

Используйте CRC только в том случае, если вычислительные ресурсы очень ограничены (например, некоторые встраиваемые среды) или вам нужно хранить / транспортировать много выходных значений, а пространство / полоса пропускания ограничены (поскольку CRC обычно 32-битные, а выход MD5 - 128-битный, SHA1 160 bit и другие варианты SHA до 512 бит).

Никогда не используйте CRC для проверки безопасности, так как CRC очень легко «подделать».

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

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

Дэвид Спиллетт
источник
1
CRC уловит все случайные изменения данных, если вы используете правильный полином. 1/2 ^ 32 изменения пропускаются, если изменяются ровно несколько правых битов.
Герхард
И с правильным полиномом он также уловит все ошибки определенных общих классов, например, пакетные ошибки.
erikkallen
Я согласен с вашим ответом, за исключением того, что вопрос касается встроенных систем. Производительность криптографического алгоритма может быть проблематичной на небольших встроенных системах.
Craig McQueen,
Абсолютно не согласен с этим. Полиномы ошибок CRC тщательно выбираются, чтобы они могли доказуемо обнаруживать 1,2,3,5 и в некоторых случаях разносить ошибки примерно до 11 бит. Криптографический хэш является чисто статистическим, поэтому вы должны использовать большие значения дайджеста. 8-32 бита нереально для криптографического хеш-дайджеста, а также бессмысленно дорого для процессоров и вентилей. Определенно не ответ, который стоит брать на вооружение, если вы работаете со встроенными системами. Единственный раз, когда НЕ использовать CRC, - это если вам нужно иметь дело со сценарием разумного противника.
ilgitano
5

Недавно я столкнулся с умным использованием CRC. Автор средства выявления и удаления дубликатов файлов jdupe (он же автор популярного средства exif jhead) использует его при первом прохождении файлов. CRC вычисляется для первых 32 КБ каждого файла, чтобы отметить файлы, которые кажутся одинаковыми, а также файлы должны иметь одинаковый размер. Эти файлы добавляются в список файлов, для которых выполняется полное двоичное сравнение. Это ускоряет проверку больших медиафайлов.

Джон Райт
источник
Одна проблема с этим подходом заключается в том, что при запуске в файле, который содержит вложенный CRC32 внутри него, результирующий CRC может быть независимым от данных в файле (поскольку, если данные изменяются, CRC32 будет изменен, чтобы компенсировать разницу ). Простое изменение данных перед вычислением CRC32 позволит избежать этой проблемы.
supercat
1
@supercat - я действительно не верю, что это действительно проблема. Если файл содержит заголовок crc32, который является crc32 остальной части файла, то при обновлении файла каждый бит в заголовке crc32 будет иметь примерно 50% шанс отличия. Изменения в заголовке должны следовать довольно случайному распределению. Я не понимаю, как это приведет к тому, что CRC32 (заголовок + данные) всегда будет одинаковым или каким-либо образом не зависит от части данных файла.
teratorn
@teratorn: я видел несколько файлов, у которых в конце есть CRC32, вычисленный таким образом, что CRC32 всего файла, вычисленный с использованием какой-то конкретной исходной константы, всегда будет другим постоянным значением. Это довольно распространено с такими вещами, как изображения двоичного кода. Если DVD-проигрыватель Acme 1000 использует образы кода фиксированного размера для обновления прошивки и ожидает, что каждый образ кода будет иметь определенный CRC32, тогда процедура, вычисляющая CRC32 различных файлов, не сможет различать разные образы кода для Acme 1000.
supercat
Задача CRC в этом случае - быстро определить, что файлы разные. Если CRC возвращается прежним, теперь вам нужно выполнить дорогостоящее двоичное сравнение, чтобы встроенный CRC не нарушил алгоритм. Может случиться так, что некоторые файлы в конечном итоге будут сравниваться в двоичном формате, потому что первый проход CRC говорит, что они МОГУТ быть одинаковыми, но вряд ли их будет много, и вы можете избежать этого, используя настраиваемый полином.
ilgitano
4

CRC32 намного быстрее и иногда имеет аппаратную поддержку (например, на процессорах Nehalem). На самом деле, единственный раз, когда вы будете использовать его, это если вы взаимодействуете с оборудованием или если вы действительно ограничены в производительности.

Ана Беттс
источник
4

Начнем с основ.

В криптографии алгоритм хеширования преобразует многие биты в меньшее количество битов с помощью операции дайджеста. Хеши используются для подтверждения целостности сообщений и файлов.

Все алгоритмы хеширования создают коллизии. Конфликт - это когда несколько многобитовых комбинаций производят одинаковое меньшее количество битов на выходе. Криптографическая стойкость алгоритма хеширования определяется неспособностью человека определить, каким будет результат для данного входа, потому что, если бы он мог, он мог бы создать файл с хешем, который соответствует легитимному файлу, и поставить под угрозу предполагаемую целостность. системы. Разница между CRC32 и MD5 в том, что MD5 генерирует больший хэш, который труднее предсказать.

Когда вы хотите реализовать целостность сообщения, то есть сообщение не было изменено при передаче, невозможность предсказать коллизии является важным свойством. 32-битный хэш может описать 4 миллиарда различных сообщений или файлов , используя 4 миллиарда различных уникальных хешей. Если у вас 4 миллиарда и 1 файл, у вас гарантированно будет 1 коллизия. В 1 ТБ битового пространства возможны миллиарды конфликтов. Если я злоумышленник и могу предсказать, каким будет этот 32-битный хеш, я могу создать зараженный файл, который конфликтует с целевым файлом; с таким же хешем.

Кроме того, если я выполняю передачу со скоростью 10 Мбит / с, тогда вероятность того, что пакет будет поврежден, чтобы обойти crc32 и продолжить путь к месту назначения и выполнить, очень мала. Допустим, при 10 Мбит / с я получаю 10 ошибок в секунду . Если я увеличу это до 1 Гбит / с, теперь я получаю 1000 ошибок в секунду . Если я набираю до 1 эксабита в секунду, то частота ошибок составляет 1 000 000 000 ошибок в секунду . Скажем, у нас частота столкновений 1 \ 1,000,000Ошибки передачи. Это означает, что 1 из миллиона ошибок передачи приводит к тому, что поврежденные данные проходят незамеченными. На скорости 10 Мбит / с я бы получал данные об ошибках, отправляемые каждые 100 000 секунд или примерно раз в день. При 1 Гбит / с это происходило каждые 5 минут. На скорости 1 эксабит в секунду мы говорим несколько раз в секунду.

Если вы откроете Wireshark, вы увидите, что ваш типичный заголовок Ethernet имеет CRC32, ваш IP-заголовок имеет CRC32, а ваш заголовок TCP имеет CRC32, и это в дополнение к тому, что могут делать протоколы более высокого уровня; например, IPSEC может использовать MD5 или SHA для проверки целостности в дополнение к вышеуказанному. В типичных сетевых коммуникациях есть несколько уровней проверки ошибок, и они ВСЕ ЕЩЕ время от времени работают на скоростях ниже 10 Мбит / с.

Циклическая проверка избыточности (CRC) имеет несколько распространенных версий и несколько необычных, но обычно предназначена для того, чтобы просто определить, когда сообщение или файл были повреждены при передаче (переключение нескольких битов). CRC32 сам по себе не является очень хорошим протоколом проверки ошибок по сегодняшним стандартам в больших скалярных корпоративных средах из-за частоты конфликтов; на жестком диске обычного пользователя может быть до 100 тыс. файлов, а в общих файловых ресурсах компании могут быть десятки миллионов. Отношение хэш-пространства к количеству файлов слишком мало. CRC32 вычислительно дешев для реализации, тогда как MD5 - нет.

MD5 был разработан, чтобы остановить преднамеренное использование коллизий, чтобы вредоносный файл выглядел безвредным. Это считается небезопасным, потому что хэш-пространство было достаточно сопоставлено, чтобы позволить произойти некоторым атакам, а некоторые коллизии предсказуемы. SHA1 и SHA2 - новые дети в этом квартале.

Для проверки файлов Md5 начинает использоваться многими поставщиками, потому что вы можете быстро создавать с ним многогигабайтные или многотерабайтные файлы и складывать это поверх общего использования ОС и поддержки CRC32. Не удивляйтесь, если в течение следующего десятилетия файловые системы начнут использовать MD5 для проверки ошибок.

bobinator
источник
1

Код CRC проще и быстрее.

Для чего они вам нужны?

Macarse
источник