Когда CRC более подходит для использования, чем MD5/SHA1?
Когда целесообразно использовать CRC для обнаружения ошибок по сравнению с более современными функциями хеширования, такими как MD5 или SHA1? Первый легче реализовать на встроенном оборудовании?
14 ответов
CRC отлично работает для обнаружения случайных ошибок в данных, которые могут возникнуть, например, из-за сетевых помех, помех в линии, искажений и т. Д.
CRC в вычислительном отношении намного менее сложен, чем MD5 или SHA1. Использование хэш-функции, такой как MD5, вероятно, излишне для обнаружения случайных ошибок. Однако использование CRC для любого вида проверки безопасности будет гораздо менее безопасным, чем более сложная функция хеширования, такая как MD5.
И да, CRC намного проще реализовать на встроенном оборудовании, вы можете даже получить различные пакетные решения для этого на IC.
CRC разработан против непреднамеренных изменений в данных. Таким образом, это хорошо для обнаружения непреднамеренных ошибок, но будет бесполезным как способ гарантировать, что данные не были обработаны злонамеренно.
Также посмотрите это.
Я нашел исследование, которое показывает, насколько неподходящие хэши CRC для хеш-таблиц. Это также объясняет фактические характеристики алгоритма. Исследование также включает оценку других алгоритмов хеширования и является хорошим справочным материалом.
Соответствующее заключение о CRC для хэшей:
CRC32 никогда не предназначался для использования хеш-таблиц. Нет никаких веских причин использовать его для этой цели, и я рекомендую вам избегать этого. Если вы решите использовать CRC32, важно, чтобы вы использовали хеш-биты конца, противоположного тому, в котором вводятся ключевые октеты. Какой это конец, зависит от конкретной реализации CRC32. Не рассматривайте CRC32 как хеш-функцию "черного ящика" и не используйте ее в качестве хеш-функции общего назначения. Обязательно проверяйте каждое его применение на пригодность.
ОБНОВИТЬ
Кажется, сайт не работает. В интернет-архиве есть копия.
Я запустил каждую строку этого 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", потому что они имеют:
- некоторые проблемы безопасности, когда вы заботитесь о безопасности
- длинная строка хеша и она медленнее, чем "crc32b", когда все, что вам нужно, это CRC
Все зависит от ваших требований и ожиданий.
Вот быстрые краткие различия между этими алгоритмами хэш-функции:
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,
серия: ША-0, ША-1, ША-2, ША-3,
Таким образом, использование SHA-1 больше не считается безопасным против хорошо финансируемых противников, потому что в 2005 году криптоаналитики обнаружили атаки на SHA-1, что говорит о том, что он может быть недостаточно безопасным для постоянного использования schneier. US NIST рекомендует федеральным агентствам прекратить использование SHA1-1 для приложений, требующих устойчивости к столкновениям, и использовать SHA-2 после NIST2010 года.
Поэтому, если вы ищете простое и быстрое решение для проверки целостности файлов (на предмет повреждения) или для каких-то простых целей кэширования с точки зрения производительности, вы можете рассмотреть 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
Связанные с:
Для получения информации о реализации, скорости и надежности CRC см . Безболезненное руководство по алгоритмам обнаружения ошибок CRC. В нем есть все на КПР.
Если кто-то не попытается злонамеренно изменить ваши данные и скрыть изменение, то CRC достаточно. Просто используйте "Хороший" (стандартный) полином.
Короткие CRC гораздо лучше , чем псевдослучайные хэши той же длины, обнаруживают случайные ошибки.
На этот вопрос накопилось большое количество ответов, в большинстве ненужных, за многие годы, но ни один из них до сих пор не указал на этот решающий факт. Вы никогда не должны использовать короткий случайный хеш (такой как усеченный MD5 или SHA-1) для обнаружения случайных перевернутых битов, даже если вы можете позволить себе вычислительные затраты, потому что процент ложноотрицательных результатов будет высоким.
Вот рабочий пример. Скажем, ваши сообщения состоят из 12 октетов (96 бит) полезной нагрузки плюс 1 октет для обнаружения ошибок. Также предположим, что каждый бит имеет независимую вероятность 1 из 10000 быть поврежденным (перевернутым) при передаче. Обратите внимание, что это означает, что примерно в 1% пакетов будет хотя бы один перевернутый бит, примерно в 0,01% пакетов будет как минимум 2 перевернутых бита и так далее.
Если биты обнаружения ошибок представляют собой псевдослучайный хэш (например, MD5 или SHA-1, усеченный до 8 бит), то искажение, ограниченное контрольными битами, всегда будет обнаруживаться, в то время как искажение, не ограниченное этими битами, будет обнаруживаться около 255/256. времени. В целом, примерно (12/13)×(1/256) ≈ 0,36% всех поврежденных пакетов не будут обнаружены.
Если биты обнаружения ошибок представляют собой простую контрольную сумму (сумма остальных байтов по модулю 256), то будут обнаружены все однобитовые ошибки (99% от общего числа), а из оставшегося 1% лучше, чем 7/. 8 будут обнаружены. Будет пропущено менее 0,13% поврежденных пакетов. Таким образом, даже простая контрольная сумма превосходит случайный хэш.
Если биты обнаружения ошибок представляют собой CRC-8 с соответствующим образом выбранным полиномом (например, CRC-8-CCITT), то будут обнаружены все ошибки 1, 2 или 3 перевернутых бита и примерно 127/128 других ошибок. будет обнаружено. Будет пропущено менее 0,00000002% поврежденных пакетов.
CRC используются не только потому, что они быстро вычисляются (хотя это так, особенно на аппаратном уровне), но и потому, что они действительно очень хорошо обнаруживают определенные типы ошибок. Даже если вы работаете с оборудованием, которое может вычислить усеченный MD5 быстрее, чем оно может вычислить CRC-8, вам, вероятно, все же следует использовать CRC.
Если у вас гораздо больше места для контрольной суммы — скажем, 128 бит — тогда ситуация другая. CRC-128 по-прежнему имеет теоретическое преимущество перед 128-битным случайным хэшем, но частота ложноотрицательных результатов случайного хэша (около 2−128) уже настолько низка, что ее также можно принять за ноль; нет никакой реальной выгоды в том, чтобы сделать его ниже. Если вы можете позволить себе использовать хэш MD5 в этой ситуации, вы также можете использовать его.
Если вы пытаетесь обнаружить злонамеренно введенные ошибки, все становится намного сложнее. В этой ситуации необходимо использовать какой-то криптографический хеш (не CRC), но этого далеко не достаточно. Если вам действительно нужно разработать протокол, защищенный от злонамеренного вмешательства, вам следует спросить об этом на Cryptography Stack Exchange. Не думайте, что использования современных хэшей, таких как SHA-3 или BLAKE2, достаточно для вашей безопасности. Вероятно, это не так.
Вы не говорите, что вы пытаетесь защитить.
CRC часто используется во встроенных системах в качестве проверки от случайного повреждения данных, а не для предотвращения злонамеренной модификации системы. Примеры мест, где CRC может быть полезен, - это проверка образа EPROM во время инициализации системы для защиты от повреждения встроенного программного обеспечения. Системный загрузчик вычислит CRC для кода приложения и сравнит его с сохраненным значением, прежде чем разрешить выполнение кода. Это защищает от возможности случайного повреждения программы или неудачной загрузки.
CRC также может использоваться аналогичным образом для защиты данных конфигурации, хранящихся во FLASH или EEPROM. Если CRC неверен, то данные могут быть помечены как недействительные и использоваться набор данных по умолчанию или резервный набор данных. CRC может быть недействительным из-за сбоя устройства или если пользователь отключил питание во время обновления хранилища данных конфигурации.
Были комментарии, что хеш обеспечивает большую вероятность обнаружения повреждения, чем CRC с множественными битовыми ошибками. Это действительно так, и решение о том, следует ли использовать 16- или 32-битный CRC, будет зависеть от последствий безопасности используемого поврежденного блока данных и от того, сможете ли вы оправдать вероятность 1 к 2^16 или 2^32 блок данных ошибочно объявлен действительным.
Многие устройства имеют встроенный генератор CRC для стандартных алгоритмов. Серия MSP430F5X из Техаса имеет аппаратную реализацию стандарта CRC-CCITT.
Я недавно столкнулся с использованием CRC, который был умным. Автор средства идентификации и удаления дубликатов файлов jdupe (тот же автор популярного инструмента exif jhead) использует его при первом прохождении файлов. CRC вычисляется на первых 32 КБ каждого файла, чтобы пометить файлы, которые кажутся одинаковыми, также файлы должны иметь одинаковый размер. Эти файлы добавляются в список файлов, по которым необходимо выполнить полное двоичное сравнение. Ускоряет проверку больших медиа файлов.
CRC32 быстрее, а длина хеша составляет всего 32 бита.
Используйте его, когда вам нужна быстрая и легкая контрольная сумма. CRC используется в Ethernet.
Если вам нужно больше надежности, предпочтительнее использовать современную функцию хеширования.
CRC32 намного быстрее и иногда имеет аппаратную поддержку (т.е. на процессорах Nehalem). Действительно, единственный раз, когда вы используете его, это если вы взаимодействуете с аппаратным обеспечением, или если вы действительно ограничены в производительности
Используйте CRC только в том случае, если вычислительные ресурсы очень ограничены (т. Е. В некоторых средах для встраивания), или вам нужно хранить / транспортировать много выходных значений, а пространство / полоса пропускания ограничены (поскольку CRC обычно 32-битные, где выход MD5128-битный, SHA1 160 бит и другие варианты SHA до 512 бит).
Никогда не используйте CRC для проверки безопасности, так как CRC очень легко "подделать".
Даже для обнаружения случайных ошибок (а не обнаружения злонамеренных изменений) хэши лучше, чем простой CRC. Частично из-за простого способа вычисления CRC (и частично из-за того, что значения CRC обычно короче, чем обычные выходные данные хэш-функции, поэтому имеют гораздо меньший диапазон возможных значений), гораздо более вероятно, что в ситуации, когда есть две или более ошибок одна ошибка будет маскировать другую, поэтому вы получите тот же CRC, несмотря на две ошибки.
Короче говоря: если у вас нет причин не использовать приличный алгоритм хеширования, избегайте простых CRC.
Давайте начнем с основ.
В криптографии алгоритм хеширования преобразует многие биты в меньшее количество бит посредством операции дайджеста. Хэши используются для подтверждения целостности сообщений и файлов.
Все алгоритмы хеширования генерируют коллизии. Столкновение - это когда несколько многоразрядных комбинаций производят одинаково меньшее количество битов. Криптографическая стойкость алгоритма хеширования определяется неспособностью индивида определить, какими будут выходные данные для данного ввода, потому что если бы они могли, они могли бы создать файл с хешем, который соответствует допустимому файлу, и поставить под угрозу предполагаемую целостность системы. Разница между CRC32 и MD5 заключается в том, что MD5 генерирует больший хэш, который труднее предсказать.
Когда вы хотите реализовать целостность сообщения - то есть сообщение не было подделано при передаче - невозможность предсказать коллизии является важным свойством. 32-битный хэш может описывать 4 миллиарда различных сообщений или файлов, используя 4 миллиарда различных уникальных хэшей. Если у вас есть 4 миллиарда и 1 файл, вы гарантированно получите 1 столкновение. Битпейс 1 ТБ имеет возможность для миллиардов столкновений. Если я злоумышленник и могу предсказать, каким будет этот 32-битный хеш, я могу создать зараженный файл, который сталкивается с целевым файлом; с таким же хешем
Кроме того, если я выполняю передачу со скоростью 10 Мбит / с, вероятность того, что пакет будет поврежден как раз в обход обхода crc32 и продолжения по пути к месту назначения и выполнения, очень мала. Допустим, на скорости 10 Мбит / с я получаю 10 ошибок \ секунду. Если я увеличу скорость до 1 Гбит / с, теперь я получаю 1000 ошибок в секунду. Если я увеличиваю до 1 exabit в секунду, то у меня уровень ошибок в 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 для проверки ошибок.