Каким критериям должна удовлетворять хорошая хеш-функция
Обновлено: 02.07.2024
Хорошая хеш-функция необходима для хорошей производительности хэш-таблицы. Неправильный выбор хеш-функции может привести к кластеризации, при которой вероятность сопоставления ключей с одним и тем же хэш-сегментом (т. е. коллизия) значительно выше, чем могла бы быть. ожидать от случайной функции. Ненулевая вероятность коллизий неизбежна в любой реализации хеширования, но количество операций по разрешению коллизий обычно масштабируется линейно с количеством ключей, сопоставленных с одним и тем же сегментом, поэтому лишние коллизии значительно снижают производительность. Кроме того, некоторые хеш-функции требуют значительных вычислительных ресурсов, поэтому время (а в некоторых случаях и память), необходимое для вычисления хэша, может быть обременительным.
Выбрать хорошую хеш-функцию непросто. Литература изобилует примерами плохого выбора, по крайней мере, по современным меркам. Например, очень популярный мультипликативный хэш, за который выступает Кнут в книге «Искусство компьютерного программирования», имеет особенно плохое поведение при кластеризации. Однако, поскольку плохое хеширование просто снижает производительность хеш-таблицы для определенных распределений входных ключей, такие проблемы слишком часто остаются незамеченными.
Кроме того, в литературе мало информации о критериях выбора хеш-функции. В отличие от большинства других фундаментальных алгоритмов и структур данных, не существует единого мнения о том, что такое «хорошая» хэш-функция. Оставшаяся часть этого раздела организована по трем критериям: простота, скорость и надежность, и будут рассмотрены алгоритмы, которые, как известно, хорошо работают по этим критериям.
Простоту и скорость легко измерить объективно (например, по количеству строк кода и тестам ЦП), но сила — более скользкое понятие. Очевидно, что криптографическая хеш-функция, такая как SHA-1, удовлетворяла бы относительно слабым требованиям к надежности, предъявляемым к хеш-таблицам, но их медлительность и сложность делают их непривлекательными. На самом деле, даже криптографический хеш не обеспечивает защиты от злоумышленника, который хочет снизить производительность хеш-таблицы, выбирая все хэшированные ключи в одном сегменте. В этих особых случаях следует использовать универсальную хеш-функцию вместо любого статического хэша, каким бы сложным он ни был.
В отсутствие стандартного показателя надежности хеш-функции в настоящее время используется ряд статистических тестов, позволяющих определить, можно ли легко отличить хеш-функцию от случайной функции. Возможно, наиболее важным из таких тестов является определение того, отображает ли хэш-функция лавинный эффект, который, по сути, утверждает, что любое изменение одного бита во входном ключе должно повлиять в среднем на половину битов в выходных данных. Брет Малви выступает за проверку, в частности, строгого лавинного условия, которое гласит, что для любого однобитового изменения каждый из выходных битов должен измениться с вероятностью, равной половине, независимо от других битов в ключе. . Чисто аддитивные хеш-функции, такие как CRC, с треском проваливают это строгое условие.
Очевидно, что сильная хеш-функция должна иметь равномерное распределение хеш-значений. Брет Малви предлагает использовать критерий хи-квадрат для однородности, основанный на мощности двух размеров хэш-таблицы в диапазоне от 2 1 до 2 16 . Этот тест значительно более чувствителен, чем многие другие, предлагаемые для измерения хеш-функций, и обнаруживает проблемы во многих популярных хеш-функциях.
К счастью, существуют хорошие хеш-функции, удовлетворяющие всем этим критериям. Самый простой класс потребляет один байт входного ключа на итерацию внутреннего цикла. В этом классе простота и скорость тесно связаны, так как быстрые алгоритмы просто не успевают выполнять сложные вычисления. Из них особенно хорошо себя зарекомендовал хеш Jenkins One-at-a-time, адаптированный из статьи его создателя Боба Дженкинса.
Ниже показано лавинное поведение этого хэша. Изображение было сделано с помощью AvalancheTest Брета Малви в его наборе инструментов Hash.cs. Каждая строка соответствует одному биту на входе, а каждый столбец — биту на выходе. Зеленый квадрат указывает на хорошее смешивание, желтый квадрат указывает на слабое смешивание, а красный указывает на отсутствие смешивания. Только несколько битов в последнем байте слабо перемешаны, что намного лучше, чем у ряда широко используемых хэш-функций.
Рисунок \(\PageIndex\): Лавинное поведение Jenkins One-at-a-time hash над 3-байтовыми ключами
Многие часто используемые хеш-функции плохо работают при таком строгом лавинном тестировании. Например, широко распространенный хэш FNV показывает много битов вообще без смешивания, особенно для коротких ключей. Более подробный анализ см. в оценке FNV Брета Малви.
Если скорость важнее простоты, то может быть интересен класс хэш-функций, использующих многобайтовые фрагменты за итерацию.Одним из самых сложных является «lookup3» Боба Дженкинса, который потребляет входные данные фрагментами по 12 байт (96 бит). Обратите внимание, однако, что любое улучшение скорости от использования этого хэша, вероятно, будет полезно только для больших ключей, и что повышенная сложность также может иметь последствия для скорости, такие как предотвращение встраивания хеш-функции оптимизирующим компилятором. Брет Малви проанализировал более раннюю версию, lookup2, и обнаружил, что она отлично справляется с лавинами.
Одним желательным свойством хеш-функции является то, что преобразование из хеш-значения (обычно 32-битного) в индекс сегмента для хеш-таблицы определенного размера может быть выполнено просто путем маскирования, сохраняя только младшие k битов для таблицы из size 2 k (операция, эквивалентная вычислению хеш-значения по модулю размера таблицы). Это свойство позволяет использовать технику постепенного удвоения размера хеш-таблицы — каждое ведро в старой таблице отображается только на два в новой таблице. Из-за использования XOR-свертывания хэш FNV не имеет этого свойства. Некоторые старые хэши еще хуже, требуя, чтобы размеры таблиц были простыми числами, а не степенью двойки, опять же вычисляя индекс корзины как хеш-значение по модулю размера таблицы. В общем случае такое требование является признаком принципиально слабой функции; использование простого размера таблицы - плохая замена использованию более сильной функции.
Хеш-функции можно использовать для решения множества различных задач, от проверки целостности и подлинности (см. главу 6 «Алгоритмы кода аутентификации сообщений») до генерации псевдослучайных чисел (см. главу 3 «Генерация случайных чисел») и получения ключа. Теперь мы исследуем последнее свойство.
Функции деривации ключей (KDF) извлекают ключевой материал из другого источника энтропии, сохраняя при этом энтропию входных данных и являясь односторонними. Вывод ключей часто используется не только для создания ключевого материала. Он также используется для получения начальных значений (IV) и одноразовых номеров (см. главу 6) для криптографических сеансов. Типичное использование функции получения ключа состоит в том, чтобы взять секрет, такой как пароль или общий секрет (см. главу 9), и соль для создания ключа и IV. Соль генерируется случайным образом при первом создании сеанса для предотвращения атак по словарю. Это не так важно, когда используется случайный общий секрет, так как атака по словарю не применяется.
Алгоритм, который мы собираемся представить, использует алгоритм, известный как HMAC (код проверки подлинности хэш-сообщения), который мы еще не обсуждали. Сбитым с толку читателям рекомендуется прочитать обсуждение HMAC в главе 6, прежде чем вернуться к этому алгоритму (рис. 5.6).
< бр />
Значение blkNo добавляется к соли в виде 32-битного числа с обратным порядком байтов. Алгоритм начинается с вычисления HMAC соли с добавленным значением blkNo. Это дает нам начальное значение для этого прохода алгоритма. Мы делаем копию этого значения в U, а затем повторно HMAC значение T, выполняя операцию XOR с выводом в U на каждой итерации. Цель подсчета итераций — сделать атаки по словарю и полный поиск еще медленнее. Например, если установлено значение 1024, мы фактически добавляем 10 бит к нашему секретному ключу.
Данные, сгенерированные этой функцией, предназначены для использования как в качестве ключей шифрования, так и в качестве начальных значений сеанса, таких как IV и одноразовые номера. Например, чтобы использовать AES-128 в режиме CTR, вызывающая сторона должна использовать этот KDF для генерации 32 байтов данных. Первые 16 байтов могут быть ключом AES, а вторые 16 байтов могут быть начальным значением CTR. Если бы мы использовали SHA-256 в качестве хэша для HMAC, мы бы зациклились только один раз, так как на шаге 4 мы бы сгенерировали требуемые 32 байта. Например, если бы мы использовали SHA-1, нам пришлось бы выполнить цикл дважды, создав 40 байтов, которые затем были бы усечены до 32 байтов.
Эта функция требует, чтобы злоумышленник не мог предсказать секрет. Соль должна быть случайной, но не может быть секретом, так как получатель должен знать ее, чтобы генерировать те же значения сеанса. соль может быть любой длины. На практике он должен быть не больше secret и не меньше восьми байтов.
Наука и кибербезопасность
Томас В. Эдгар , Дэвид О. Манц, Методы исследования кибербезопасности, 2017 г.
Криптографический хеш
Хеш-функция – это вычислительный метод, который может преобразовать данные неопределенного размера в данные фиксированного размера. Или, проще говоря, он предоставляет числовое значение, которое представляет входные данные. Криптографическая хэш-функция использует односторонние математические функции, которые легко вычислить для создания хеш-значения из входных данных, но очень сложно воспроизвести входные данные, выполняя вычисления сгенерированного хеш-функции. Одним из распространенных способов создания криптографических хэшей является использование блочных шифров.Некоторые распространенные хэш-функции: MD5 (неработающая и устаревшая), SHA-1, SHA-2 и SHA-3.
Шифрование
III.А. Основные принципы
Хеш-функция, также известная как односторонняя хэш-функция, принимает произвольное сообщение произвольной длины и создает выходные данные (хэш) фиксированной длины. Основные характеристики криптографической хеш-функции заключаются в том, что для данного сообщения легко вычислить хэш; учитывая хэш, трудно вычислить сообщение; и что для данного сообщения трудно найти другое сообщение, которое давало бы такой же хэш (это называется коллизией)
Хеш-функции используются для обеспечения целостности данных и часто в сочетании с цифровыми подписями. С хорошей хэш-функцией даже изменение 1 бита в сообщении приведет к другому хэшу (в среднем меняется половина битов). При использовании цифровых подписей сообщение хэшируется, а затем подписывается сам хэш. Подпись покажет, было ли изменено хеш-значение, и хэш покажет, было ли сообщение изменено. Два типа хеш-функций: без ключа (MD5, SHA-1) и с ключом (MAC).
Контроль доступа и технология блокчейн на основе классификаторов в приложениях электронного здравоохранения
3.3.2 Важные элементы BT
Распределенный реестр. Конфиденциальные данные электронного здравоохранения находятся в распределенном реестре, который обеспечивает определенную степень надежности, ограничивая влияние эпизода цифровой безопасности, с которым сталкивается любой отдельный узел. Это гарантирует честность, поскольку изменения не могут быть выполнены обманным путем, когда каждый имеет одновременный доступ ко всем записям, что является фундаментальным фактором для распознавания записей и использования блокчейна в цепочках поставок. Это нововведение, используемое в блокчейнах, предлагает стратегии публично-частного шифрования для характера и оцифровки записей. Записи хорошо реагируют на любое подозрительное движение или изменение. Поскольку никто не может изменить запись, и все быстро обновляется, протокол BT для всех этих узлов прост в использовании в соответствии с записью.
Хеш-функции. Эта емкость используется для защиты данных в облачных системах хранения; это затрудняет воссоздание информации только из хэша. Криптографическая хеш-работа «h» берется в качестве входных данных для сообщения произвольной длины и создает сжатие сообщения или «хэш» фиксированной длины. Что касается криптографически безопасных хэш-емкостей, обычно считается невероятным, что два важных сообщения могут иметь общий хэш.
Предлагаемый подход к защите данных предполагает, что для этого исследования необходимо выполнить хеш-функцию с тремя функциями.
Хеши прошлых блоков могут состоять из нескольких чисел, если цепочка блоков растянута и добавляется каждый из них.
Каждый блок содержит хеш блока с хэшем прошлого блока, деньгами и отметкой времени, форму блока с одноразовым номером и целевой адрес, который включает в себя сообщение.
Роль технологии блокчейн в приложениях Интернета вещей
Хэни Ф. Атлам, Гэри Б. Уиллс, Достижения в области компьютеров, 2019 г.
2.3.3 Хэш
Хеш-функция — это сложная математическая задача, которую майнеры должны решить, чтобы найти блок. Понятие хеш-функции используется как способ поиска данных в базе данных. Хеш-функции не допускают коллизий, а это означает, что очень сложно найти два одинаковых хэша для двух разных сообщений. Следовательно, блоки идентифицируются по их хешу, что служит двум целям; идентификация и проверка целостности [17] .
Чтобы связать блоки вместе, каждый блок включает хэш своего родителя в свой собственный заголовок, который создает цепочку, идущую от первого блока, который создает последовательность хэшей. Хэш-значения хранятся в хэш-таблице, которая представляет собой хорошо организованный механизм индексации для повышения производительности операций поиска [18].
Криптография
Хеш-функции
Хэш-функции представляют собой третий тип криптографии наряду с симметричной и асимметричной криптографией, которую мы могли бы назвать криптографией без ключа. Хеш-функции, также называемые дайджестами сообщений, не используют ключ, а вместо этого создают в значительной степени уникальное хеш-значение фиксированной длины, обычно называемое хешем, на основе исходного сообщения, что-то вроде отпечатка пальца. . Любое незначительное изменение сообщения приведет к изменению хэша.
Хэши нельзя использовать для обнаружения содержимого исходного сообщения или каких-либо других его характеристик, но их можно использовать для определения того, изменилось ли сообщение. Таким образом, хэши обеспечивают конфиденциальность, но не целостность. Хэши можно использовать в программах (чтобы определить, изменил ли кто-то приложение, которое вы хотите загрузить), в открытых текстовых сообщениях или файлах операционной системы. Хэши очень полезны при распространении файлов или отправке сообщений, поскольку хэш можно отправить вместе с сообщением, чтобы получатель мог проверить его целостность.Получатель просто снова хеширует сообщение, используя тот же алгоритм, а затем сравнивает два хэша. Если хэши совпадают, сообщение не изменилось. Если они не совпадают, сообщение было изменено.
Хотя теоретически возможно спроектировать совпадающий хеш для двух разных наборов данных, называемый коллизией, это действительно очень сложная задача, и обычно для ее выполнения требуется, чтобы алгоритм хеширования был взломан. Некоторые алгоритмы, такие как алгоритм Message-Digest 5 (MD5), были атакованы таким образом, хотя создание коллизии по-прежнему нетривиально. В таких случаях скомпрометированный алгоритм обычно выходит из употребления. Алгоритмы хэширования, такие как SHA-2 и SHA-3, который скоро появится, заменили MD5 в тех случаях, когда требуется строгая безопасность хэширования.
Существует множество других алгоритмов хэширования, которые используются в различных ситуациях, например MD2, MD4 и RACE.
Проекты по обеспечению безопасности для системных и сетевых специалистов
Леонидас Делигианнидис, . Хамид Р. Арабния, Новые тенденции в безопасности ИКТ, 2014 г.
Присваивание в хеш-функциях
Криптографические хэш-функции играют важную роль в современных коммуникационных технологиях. Входными данными для хэш-функции является файл или поток любого размера, а выходными данными является цифровое представление файла фиксированного размера, которое обычно не превышает 1 КБ и служит отпечатком исходного файла (часто называемым дайджестом сообщения). Невозможно восстановить исходный файл только по отпечатку пальца. Более того, изменение одного бита информации во входных данных приведет к значительному изменению отпечатка пальца. Эти алгоритмы предназначены для предотвращения столкновений. Другими словами, очень маловероятно, что два сообщения, M и M', создадут один и тот же отпечаток с помощью криптографической хеш-функции H: Н(М) != Н(М'). Многие криптографические хеш-функции основаны на так называемом алгоритме MD4, первоначально предложенном в [14], и им было уделено наибольшее внимание.
Учащиеся пишут программу для вычисления дайджеста сообщения с учетом различных входных потоков. Затем они модифицируют ввод, чтобы получить существенно разные дайджесты. Перед учащимися ставится задача найти два входа, которые дают один и тот же дайджест сообщения. Затем мы демонстрируем, как они могут взломать MD5, используя методы, описанные в [15,16]. В частности, мы создаем два разных исполняемых файла, которые имеют существенно разные цели, но чьи дайджесты MD5 идентичны. Это показывает, что можно иметь два разных файла с одним и тем же дайджестом сообщения MD5 и что использование хеширования MD5 для проверки загрузки файлов небезопасно.
Шифрование данных
Доктор. Бхушан Капур, д-р Прамод Пандья, Кибербезопасность и защита ИТ-инфраструктуры, 2014 г.
Криптографические хеш-функции
Криптографическая хэш-функция должна удовлетворять трем критериям:
Сопротивление второму прообразу (слабое сопротивление столкновению)
Высокое сопротивление столкновению
Сопротивление прообразу
Дано сообщение m и хеш-функция hash, если задано значение хеш-функции h=hash(m), должно быть трудно найти любое m такое, что h=hash(m).
Сопротивление второму прообразу (слабое сопротивление столкновению)
Учитывая входные данные m1, должно быть сложно найти другое сообщение m2, такое что hashing)=hash(m2) и что m1≠m2
Высокая устойчивость к столкновениям
Должно быть сложно найти два сообщения m1≠m2, такие что hash(m1)=hash(m< под>2 ). Хэш-функция принимает входную n-битную строку фиксированного размера и создает выходную m-битную строку фиксированного размера, такую, что m меньше, чем n в длину. Первоначальная хэш-функция была определена Мерклем-Дамгардом и представляет собой итерированную хеш-функцию. Эта хэш-функция сначала разбивает исходное сообщение на блоки фиксированного размера размером n. Затем устанавливается исходный вектор H0 (дайджест), который объединяется с блоком сообщений M1 для получения дайджеста сообщения H1. , который затем объединяется с M2 для создания дайджеста сообщения H1, и так далее, пока последний блок сообщения не создаст окончательный дайджест сообщения.
Дайджесты сообщений MD2, MD4 и MD5 были разработаны Роном Ривестом. MD5 в качестве входного блока размером 512 бит и создает дайджест сообщения размером 128 бит [1] .
Алгоритм безопасного хеширования (SHA) был разработан Национальным институтом стандартов и технологий (NIST). SHA-1, SHA-224, SHA-256, SHA-384 и SHA-512 являются примерами алгоритма безопасного хеширования. SHA-512 создает 512-битный дайджест сообщения.
Что такое хорошая хэш-функция? Я видел много хеш-функций и приложений на своих курсах по структурам данных в колледже, но в основном понял, что сделать хорошую хеш-функцию довольно сложно. Как правило, чтобы избежать столкновений, мой профессор сказал следующее:
(mod — это оператор % в C и подобных языках)
где простое число соответствует размеру хеш-таблицы. Я понимаю, что это довольно хорошая функция для предотвращения столкновений и быстрая, но как я могу сделать ее лучше? Существуют ли лучшие хэш-функции для строковых ключей по сравнению с числовыми ключами?
В fnv_func тип p[i] — char, что произойдет с h после первой итерации? Было ли это сделано намеренно?
9 ответов 9
Не существует такого понятия, как "хорошая хеш-функция" для универсальных хэшей (и да, я знаю, что существует такое понятие, как "универсальное хэширование", но я имел в виду не это). В зависимости от контекста различные критерии определяют качество хэша. Два человека уже упомянули SHA. Это криптографический хэш, и он совсем не подходит для хеш-таблиц, которые вы, вероятно, имеете в виду.
К хеш-таблицам предъявляются совсем другие требования. Но, тем не менее, найти хорошую хэш-функцию универсально сложно, потому что разные типы данных предоставляют разную информацию, которую можно хешировать. Как правило, лучше рассматривать всю информацию, которую тип содержит одинаково. Это не всегда легко или даже возможно. Из соображений статистики (и, следовательно, столкновений) также важно создать хороший разброс по проблемному пространству, то есть по всем возможным объектам. Это означает, что при хешировании чисел от 100 до 1050 нецелесообразно позволять старшей значащей цифре играть большую роль в хэше, потому что для ~ 90% объектов эта цифра будет равна 0. Гораздо важнее, чтобы последние три цифры определяют хеш.
Точно так же при хешировании строк важно учитывать все символы, за исключением случаев, когда заранее известно, что первые три символа во всех строках будут одинаковыми; считать это пустой тратой времени.
На самом деле это один из тех случаев, когда я советую прочитать, что Кнут говорит в The Art of Computer Programming, vol. 3. Еще одно хорошее чтение — «Искусство хеширования» Жюльен Уокер.
Хеш-функции чрезвычайно полезны и используются практически во всех приложениях для обеспечения информационной безопасности.
Хэш-функция – это математическая функция, которая преобразует входное числовое значение в другое сжатое числовое значение. Входные данные хеш-функции имеют произвольную длину, но выходные данные всегда имеют фиксированную длину.
Значения, возвращаемые хеш-функцией, называются дайджестом сообщения или просто хэш-значением. Следующая картинка иллюстрирует хэш-функцию —
Возможности хеш-функций
Типичные особенности хеш-функций —
Вывод фиксированной длины (хэш-значение)
Хеш-функция преобразует данные произвольной длины в фиксированную длину. Этот процесс часто называют хешированием данных.
Как правило, хэш намного меньше входных данных, поэтому хеш-функции иногда называют функциями сжатия.
Поскольку хеш представляет собой уменьшенное представление больших данных, его также называют дайджестом.
Хеш-функция с n-битным выходом называется n-битной хэш-функцией. Популярные хэш-функции генерируют значения от 160 до 512 бит.
Эффективность работы
Как правило, для любой хеш-функции h с входными данными x вычисление h(x) является быстрой операцией.
Вычислительные хэш-функции намного быстрее, чем симметричное шифрование.
Свойства хеш-функций
Чтобы быть эффективным криптографическим инструментом, желательно, чтобы хеш-функция обладала следующими свойствами —
Сопротивление перед изображением
Это свойство означает, что обращение хеш-функции должно быть сложным с вычислительной точки зрения.
Другими словами, если хэш-функция h выдает хеш-значение z, то найти любое входное значение x, которое хешируется до z, должно быть сложно.
Это свойство защищает от злоумышленника, у которого есть только хеш-значение и который пытается найти ввод.
Второе сопротивление перед изображением
Это свойство означает, что при заданном вводе и его хэше будет сложно найти другой ввод с таким же хэшем.
Другими словами, если хэш-функция h для входных данных x дает хэш-значение h(x), то должно быть трудно найти любое другое входное значение y, такое что h(y) = h(x).
Это свойство хэш-функции защищает от злоумышленника, который имеет входное значение и его хэш и хочет заменить исходное входное значение другим значением в качестве допустимого.
Сопротивление столкновениям
Это свойство означает, что будет трудно найти два разных ввода любой длины, которые приводят к одному и тому же хэшу. Это свойство также называется хеш-функцией без коллизий.
Другими словами, для хэш-функции h трудно найти любые два разных входа x и y, такие что h(x) = h(y).
Поскольку хеш-функция сжимает функцию с фиксированной длиной хеш-функции, хеш-функция не может не иметь коллизий.Это свойство отсутствия коллизий только подтверждает, что эти коллизии трудно найти.
Из-за этого свойства злоумышленнику очень сложно найти два входных значения с одинаковым хешем.
Кроме того, если хэш-функция устойчива к коллизиям, то она устойчива ко второму прообразу.
Проектирование алгоритмов хеширования
В основе хеширования лежит математическая функция, которая работает с двумя блоками данных фиксированного размера для создания хэш-кода. Эта хеш-функция является частью алгоритма хеширования.
Размер каждого блока данных зависит от алгоритма. Обычно размер блока составляет от 128 до 512 бит. На следующем рисунке показана хэш-функция —
Алгоритм хеширования включает в себя раунды вышеуказанной хеш-функции, как блочный шифр. Каждый раунд принимает входные данные фиксированного размера, обычно это комбинация самого последнего блока сообщения и выходных данных последнего раунда.
Этот процесс повторяется столько раз, сколько требуется для хеширования всего сообщения. Схема алгоритма хеширования изображена на следующем рисунке —
Поскольку хеш-значение первого блока сообщений становится входом для второй хэш-операции, вывод которой изменяет результат третьей операции и так далее. Этот эффект известен как лавинный эффект хеширования.
Эффект лавины приводит к существенно разным значениям хеш-функции для двух сообщений, которые отличаются даже одним битом данных.
Правильно поймите разницу между хеш-функцией и алгоритмом. Хэш-функция генерирует хеш-код, оперируя двумя блоками двоичных данных фиксированной длины.
Алгоритм хеширования – это процесс использования хеш-функции, определяющий, как сообщение будет разбито на части и как результаты предыдущих блоков сообщения будут объединены в цепочку.
Популярные хеш-функции
Давайте кратко рассмотрим некоторые популярные хэш-функции —
Дайджест сообщения (MD)
MD5 была самой популярной и широко используемой хэш-функцией в течение нескольких лет.
Дайджесты MD5 широко используются в мире программного обеспечения для обеспечения уверенности в целостности передаваемого файла. Например, файловые серверы часто предоставляют предварительно вычисленную контрольную сумму MD5 для файлов, чтобы пользователь мог сравнить с ней контрольную сумму загруженного файла.
В 2004 году в MD5 были обнаружены коллизии. Сообщалось, что аналитическая атака была успешной только через час с использованием компьютерного кластера. Эта атака столкновений привела к скомпрометации MD5, поэтому ее больше не рекомендуется использовать.
Защищенная хэш-функция (SHA)
Семейство SHA состоит из четырех алгоритмов SHA; SHA-0, SHA-1, SHA-2 и SHA-3. Хотя они из одного семейства, они структурно разные.
Первоначальная версия SHA-0, 160-битная хэш-функция, была опубликована Национальным институтом стандартов и технологий (NIST) в 1993 году. В ней было мало недостатков, и она не стала очень популярной. Позднее, в 1995 году, SHA-1 был разработан для исправления предполагаемых недостатков SHA-0.
SHA-1 — наиболее широко используемая из существующих хеш-функций SHA. Он используется в нескольких широко используемых приложениях и протоколах, включая безопасность Secure Socket Layer (SSL).
В 2005 году был найден метод обнаружения коллизий для SHA-1 в пределах практических временных рамок, что сделало долгосрочное использование SHA-1 сомнительным.
Семейство SHA-2 включает еще четыре варианта SHA: SHA-224, SHA-256, SHA-384 и SHA-512, в зависимости от количества битов в их хеш-значении. Об успешных атаках на хэш-функцию SHA-2 пока не сообщалось.
Хотя SHA-2 — это надежная хэш-функция. Несмотря на то, что он значительно отличается, его базовая конструкция по-прежнему соответствует конструкции SHA-1. Поэтому NIST призвал к разработке новых конкурентоспособных хеш-функций.
В октябре 2012 года NIST выбрал алгоритм Keccak в качестве нового стандарта SHA-3. Keccak предлагает множество преимуществ, таких как эффективная работа и хорошая устойчивость к атакам.
РИПЕМД
RIPEMD — это аббревиатура от RACE Integrity Primitives Evaluation Message Digest. Этот набор хеш-функций был разработан открытым исследовательским сообществом и широко известен как семейство европейских хеш-функций.
В комплект входят RIPEMD, RIPEMD-128 и RIPEMD-160. Также существуют 256- и 320-битные версии этого алгоритма.
RIPEMD-160 — это улучшенная и наиболее широко используемая версия в семействе. 256- и 320-битные версии снижают вероятность случайного столкновения, но не имеют более высокого уровня безопасности по сравнению с RIPEMD-128 и RIPEMD-160 соответственно.
Водоворот
Это 512-битная хеш-функция.
Он основан на модифицированной версии расширенного стандарта шифрования (AES).Одним из дизайнеров был Винсент Раймен, один из создателей AES.
Выпущено три версии Whirlpool; а именно WHIRLPOOL-0, WHIRLPOOL-T и WHIRLPOOL.
Применение хеш-функций
Есть два прямых применения хеш-функции, основанные на ее криптографических свойствах.
Хранилище паролей
Хэш-функции обеспечивают защиту хранилища паролей.
Вместо того, чтобы хранить пароль в открытом виде, в большинстве случаев все процессы входа в систему сохраняют хеш-значения паролей в файле.
Файл паролей состоит из таблицы пар в форме (идентификатор пользователя, h(P)).
Процесс входа показан на следующем рисунке —
Злоумышленник может видеть только хэши паролей, даже если он получил доступ к паролю. Он не может ни войти в систему, используя хэш, ни получить пароль из хеш-значения, поскольку хеш-функция обладает свойством устойчивости к прообразу.
Проверка целостности данных
Проверка целостности данных является наиболее распространенным применением хеш-функций. Он используется для генерации контрольных сумм в файлах данных. Это приложение гарантирует пользователю правильность данных.
Процесс показан на следующем рисунке —
Проверка целостности помогает пользователю обнаружить любые изменения, внесенные в исходный файл. Однако это не дает никаких гарантий относительно оригинальности. Злоумышленник, вместо того, чтобы изменять данные файла, может изменить весь файл и вычислить все вместе новый хэш и отправить получателю. Это приложение для проверки целостности полезно только в том случае, если пользователь уверен в подлинности файла.
Читайте также: