Хеширование (иногда хэширование, англ. hashing) — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения (англ. message digest).
Существует множество алгоритмов хеширования с различными характеристиками (разрядность, вычислительная сложность, криптостойкость и т.п.). Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшими примерами хеш-функций могут служить контрольная сумма или CRC.
В общем случае однозначного соответствия между исходными данными и хеш-кодом нет. Поэтому существует множество массивов данных, дающих одинаковые хеш-коды - так называемые коллизии. Вероятность возникновения коллизий играет немаловажную роль в оценке «качества» хеш-функций.
Контрольные суммы
Несложные, крайне быстрые и легко реализуемые аппаратно алгоритмы, используемые для защиты от непреднамеренных искажений, в т.ч. ошибок аппаратуры.
По скорости вычисления в десятки и сотни раз быстрее, чем криптографические хеш-функции, и значительно проще в аппаратной реализации.
Платой за столь высокую скорость является отсутствие криптостойкости - легкая возможность подогнать сообщение под заранее известную сумму. Также обычно разрядность контрольных сумм (типичное число: 32 бита) ниже, чем криптографических хешей (типичные числа: 128, 160 и 256 бит), что означает возможность возникновения непреднамеренных коллизий.
Простейшим случаем такого алгоритма является деление сообщения на 32- или 16- битные слова и их суммирование, что применяется, например, в TCP/IP.
Как правило к такому алгоритму предъявляются требования отслеживания типичных аппаратных ошибок, таких, как несколько подряд идущих ошибочных бит до заданной длины. Семейство т.н. полиномиальных алгоритмов ("циклический контроль избыточности", англ CRC - Cyclic Redundancy Check) удовлетворяет этим требованиям. К ним относится, например, CRC-32, применяемый в аппаратуре Ethernet и в формате упакованных файлов ZIP.
Алгоритм полиномиальной контрольной суммы выглядит так: входной поток понимается побитово, разрядность результата N bit, существует также жестко заданная константа в N бит, называемая "полином".
Шаг алгоритма:
если следующий бит входного потока есть 1 - выполнить XOR N следующих бит входного потока с полиномом, результат заменяет эти биты входного потока (Input ^= Poly)
если во входном потоке осталось всего N бит - то алгоритм окончен, входной поток есть результат
иначе потребить 1 бит из входного потока и перейти к следующему шагу
Несложно догадаться, что это напоминает деление столбиком, с той разницей, что вместо вычитания используется XOR. Контрольная сумма, таким образом, является остатком от "XOR-деления" входного сообщения на полином.
Технические реализации алгоритма обычно оптимизируются с использованием заранее посчитанной таблицы значений функции для всех возможных 8- или 16- битных слов, чтобы сильно уменьшить количество побитовых сдвигов. Оптимизация основана на следующем свойстве алгоритма: crc(a cat b) == crc(Xor(b, crc(a))), где cat означает конкатенацию сообщений, а Xor(m, w) - сообщение m, в котором первые N бит заменены на результат XOR этих бит с N-битным словом w. Это свойство позволяет рассчитывать алгоритм для всех возможных конкатенаций байт, имея таблицу значений для отдельных байт.
Математический анализ видов искажений, отслеживаемых этим алгоритмом, опирается на свойство линейности алгоритма: crc(a xor b) == crc(a) xor crc(b). Это сводит задачу к задаче поиска всех входных сообщений, для которых алгоритм даст нуль, или же, что технически важнее, поиска всех классов входных сообщений, для которых алгоритм гарантированно даст не нуль.
Эти классы сообщений сильно зависят от конкретного значения константы полинома, например, от количества единичных бит в ней или же ее четности/нечетности. Доказательства, связанные со свойствами CRC для конкретных классов значений констант полиномов, рассмотрены в алгебре полиномов (отсюда название константы в алгоритме).
Полином для CRC-32 есть 0x04c11db7 (в оптимизированных реализациях может иметь совсем другой вид).
Криптографические хеш-функции
Среди множества существующих хеш-функций принято выделять криптографически стойкие, применяемые в криптографии. Криптостойкая хеш-функция прежде всего должна обладать стойкостью к коллизиям двух типов:
Стойкость к коллизиям первого рода: для заданного сообщения должно быть практически невозможно подобрать другое сообщение , имеющее такой же хеш. Это свойство также называется необратимостью хеш-функции.
Стойкость к коллизиям второго рода: должно быть практически невозможно подобрать пару сообщений , имеющих одинаковый хеш.
Согласно парадоксу о днях рождения, нахождение коллизии для хеш-функции с длиной значений n бит требует в среднем перебора около 2n / 2 операций. Поэтому n-битная хеш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для нее близка к 2n / 2.
Простейшим (хотя и не всегда приемлемым) способом усложнения поиска коллизий является увеличение разрядности хеша, например, путем параллельного использования двух или более различных хеш-функций.
Для криптографических хеш-функций также важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось. В частности, значение хеша не должно давать утечки информации даже об отдельных битах аргумента. Это требование является залогом криптостойкости алгоритмов шифрования, хеширующих пользовательский пароль для получения ключа.
Применение хеширования
Хеш-функции также используются в некоторых структурах данных — хеш-таблицаx и декартовых деревьях. Требования к хеш-функции в этом случае другие:
хорошая перемешиваемость данных
быстрый алгоритм вычисления
Сверка данных
В общем случае это применение можно описать, как проверка некоторой информации на идентичность оригиналу, без использования оригинала. Для сверки используется хеш-значение проверяемой информации. Различают два основных направления этого применения:
Проверка на наличие ошибок
Например, контрольная сумма может быть передана по каналу связи вместе с основным текстом. На приёмном конце, контрольная сумма может быть рассчитана заново и её можно сравнить с переданным значением. Если будет обнаружено расхождение, то это значит, что при передаче возникли искажения и можно запросить повтор.
Бытовым аналогом хеширования в данном случае может служить приём, когда при переездах в памяти держат количество мест багажа. Тогда для проверки не нужно вспоминать про каждый чемодан, а достаточно их посчитать. Совпадение будет означать, что ни один чемодан не потерян. То есть, количество мест багажа является его хеш-кодом.
Проверка парольной фразы
В большинстве случаев парольные фразы не хранятся на целевых объектах, хранятся лишь их хеш-значения. Хранить парольные фразы нецелесообразно, так как в случае несанкционированного доступа к файлу с фразами злоумышленник узнает все парольные фразы и сразу сможет ими воспользоваться, а при хранении хеш-значений он узнает лишь хеш-значения, которые не обратимы в исходные данные, в данном случае в парольную фразу. В ходе процедуры аутентификации вычисляется хеш-значение введённой парольной фразы, и сравнивается с сохранённым.
Примером в данном случае могут служить ОС GNU/Linux и Microsoft Windows XP. В них хранятся лишь хеш-значения парольных фраз из учётных записей пользователей.
Ускорение поиска данных
Основная статья: Хеш-таблица
Например, при записи текстовых полей в базе данных может рассчитываться их хеш код и данные могут помещаться в раздел, соответствующий этому хеш-коду. Тогда при поиске данных надо будет сначала вычислить хеш-код текста и сразу станет известно, в каком разделе их надо искать, то есть, искать надо будет не по всей базе, а только по одному её разделу (это сильно ускоряет поиск).
Бытовым аналогом хеширования в данном случае может служить помещение слов в словаре по алфавиту. Первая буква слова является его хеш-кодом, и при поиске мы просматриваем не весь словарь, а только нужную букву.
Список алгоритмов
Adler-32
CRC
SHA-1
SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
HAVAL
MD2
MD4
MD5
N-Hash
RIPEMD-160
RIPEMD-256
RIPEMD-320
Skein
Snefru
Tiger (TTH)
Whirlpool
ГОСТ Р34.11-94 (ГОСТ 34.311-95)
IP Internet Checksum (RFC 1071)