Хеш-код и контрольная сумма - в чем разница?

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

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

Итак, есть ли у нас два слова для обозначения одного и того же, или есть важные различия между хэш-кодами и контрольными суммами?

Я хотел бы сказать , что контрольная сумма обязательно хэш - код . Однако не все хэш-коды дают хорошие контрольные суммы.

Контрольная сумма имеет особое назначение - она ​​проверяет или проверяет целостность данных (некоторые могут выходить за рамки этого, допуская исправление ошибок ). «Хорошие» контрольные суммы легко вычислить, и они могут обнаруживать многие типы повреждений данных (например, один, два, три ошибочных бита).

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

У каждого из них своя цель:

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

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

Различия действительно есть:

• Контрольные суммы просто должны быть разными, если входные данные разные (как можно чаще), но почти так же важно, чтобы они были быстрыми для вычисления.
• Хэш-коды (для использования в хэш-таблицах) предъявляют те же требования, и, кроме того, они должны быть равномерно распределены по пространству кода, особенно для аналогичных входных данных.
• К криптографическим хешам предъявляются гораздо более строгие требования: с учетом хеша вы не можете создать вход, который производит этот хеш. Время вычисления занимает второе место, и в зависимости от приложения может быть даже желательно, чтобы хэш был очень медленным для вычисления (для борьбы с атаками грубой силы).

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

Яркий пример - струны. Контрольная сумма для строки должна включать каждый бит, и порядок имеет значение. С другой стороны, хэш-код часто может быть реализован как контрольная сумма префикса ограниченной длины. Это означало бы, что «aaaaaaaaaaba» будет хешировать так же, как «aaaaaaaaaaab», но алгоритмы хеширования могут справляться с такими коллизиями.

Википедия хорошо об этом говорит:

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

Контрольная сумма защищает от случайных изменений.

Криптографический хеш защищает от очень мотивированного злоумышленника.

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

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

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

Источник: CompTIA ® Security + Руководство по основам сетевой безопасности - Пятое издание - Марк Чампа - стр. 191

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

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

• Контрольная сумма используется, чтобы узнать, изменилось ли что-то во входных данных.

• Хэш-код используется, чтобы узнать, изменилось ли что-то во входных данных, и чтобы иметь как можно большее «расстояние» между отдельными значениями хэш-кода.

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

  А если вы добавите некоторую общую начальную рандомизацию, вы получите концепцию современного шифрования / обмена ключами.

О вероятности:

Например, предположим, что входные данные на самом деле всегда меняются (в 100% случаев). Предположим, у вас есть «идеальная» функция хеширования / контрольной суммы, которая генерирует 1-битное значение хеш-функции / контрольной суммы. Следовательно, вы будете получать разные значения хэша / контрольной суммы в 50% случаев для случайных входных данных.

• Если изменился ровно 1 бит в ваших случайных входных данных, вы сможете обнаружить это в 100% случаев, независимо от того, насколько велики входные данные.

• Если 2 бита в ваших случайных входных данных изменились, ваша вероятность обнаружения «изменения» делится на 2, потому что оба изменения могут нейтрализовать друг друга, и никакая функция хеширования / контрольной суммы не обнаружит, что 2 бита во входных данных фактически различаются. ,

  ...

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

Я обычно использую слово «контрольная сумма» при обращении к коду (числовому или другому), созданному для файла или фрагмента данных, который можно использовать для проверки того, что файл или данные не были повреждены. Чаще всего я использую для проверки того, что файлы, передаваемые по сети, не были изменены (намеренно или иным образом).

В сегментировании данных кластера Redis он использует a, hash slotчтобы решить, к какому узлу перейти. Возьмем, например, операцию по модулю ниже:

123 % 9 = 6
122 % 9 = 5
141 % 9 = 6

6Приходит дважды через различные входы. Цель хэша - просто сопоставить входное значение с выходным значением, а уникальность не является частью сделки. Так что два разных входа, которые производят один и тот же результат, прекрасны в мире хешей.

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

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

Циклический контроль избыточности (CRC) - это нечто совершенно иное, более сложное и НЕ называется контрольной суммой. Это приложение полиномиального ряда, которое может исправлять любое выбранное количество отдельных поврежденных битов в поле данных, из которого он был сгенерирован. Создание CRC приводит к числу, большему по размеру, чем исходное поле данных (в отличие от контрольной суммы) - отсюда и название, включающее слово «избыточность» и цену, которую вы платите за возможность исправления ошибок. Таким образом, CRC НЕ является хешем, и его нельзя путать или называть контрольной суммой, потому что избыточность обязательно увеличивает размер исходных данных.