Что такое хэширование и для чего оно нужно

Содержание

• 1 Историческая справка
• 2 Хеширование данных
• 3 Описание
• 4 Зачем нужен хэш
• 5 Особенности
• 6 Что такое хеш-сумма файла
  • 6.1 Как пользоваться HashTab
• 7 О популярных хэш-алгоритмах
• 8 Какими свойствами должна обладать хеш-функция
  • 8.1 Применения в реальной жизни

Историческая справка

Конечно, история хеширования появилась задолго до криптовалют и появления цепи блокчейн. Впервые, идею подобного кодирования предоставил на рассмотрения сотрудник IBM Ханс Петер Лун еще в далеком 1953 году. В последующие годы предложение было актуальным для решения проблем поиска слова в большом толковом словаре. В 80-х процедура стала популярна для алгоритмизации любых структурных данных, в том числе и компьютерных.

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

Хеширование данных

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

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

Известными алгоритмами хеширования являются MD5, SHA-1 и SHA-2.

Основные принципы хеширования:

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

Одним из самых простых применений хеширования является хранение паролей (считается более защищённым способом, чем хранение паролей в явном виде).

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

Описание

В настоящее время практически ни одно приложение криптографии не обходится без использования хэширования.

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

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

• построения систем контроля целостности данных при их передаче или хранении,
• аутентификация источника данных.

Хэш-функцией называется всякая функция h:X -> Y, легко вычислимая и такая, что для любого сообщения M значение h(M) = H (свертка) имеет фиксированную битовую длину. X — множество всех сообщений, Y — множество двоичных векторов фиксированной длины.
Как правило хэш-функции строят на основе так называемых одношаговых сжимающих функций y = f(x1, x2) двух переменных, где x1, x2 и y — двоичные векторы длины m, n и n соответственно, причем n — длина свертки, а m — длина блока сообщения.

Для получения значения h(M) сообщение сначала разбивается на блоки длины m (при этом, если длина сообщения не кратна m то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам M1, M2,.., MN применяют следующую последовательную процедуру вычисления свертки:

Ho = v,
Hi = f(Mi,Hi-1), i = 1,.., N,
h(M) = HN
Здесь v — некоторая константа, часто ее называют инициализирующим вектором. Она выбирается
из различных соображений и может представлять собой секретную константу или набор случайных данных (выборку даты и времени, например).

При таком подходе свойства хэш-функции полностью определяются свойствами одношаговой сжимающей функции.

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

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

Зачем нужен хэш

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

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

Особенности

Типичные особенности хеш-функций —

• Выход фиксированной длины (значение хэша)
  • Хэш-функция охватывает данные произвольной длины до фиксированной длины. Этот процесс часто называют хэшированием данных .
  • В общем, хеш намного меньше, чем входные данные, поэтому хеш-функции иногда называют функциями сжатия .
  • Поскольку хэш представляет собой меньшее представление больших данных, его также называют дайджестом .
  • Хеш-функция с n-битным выходом называется n-битной хеш-функцией . Популярные хеш-функции генерируют значения от 160 до 512 бит.
• Эффективность операции
  • Обычно для любой хеш-функции h с входом x вычисление h (x) является быстрой операцией.
  • Вычислительные хеш-функции намного быстрее, чем симметричное шифрование.

Выход фиксированной длины (значение хэша)

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

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

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

Хеш-функция с n-битным выходом называется n-битной хеш-функцией . Популярные хеш-функции генерируют значения от 160 до 512 бит.

Эффективность операции

Обычно для любой хеш-функции h с входом x вычисление h (x) является быстрой операцией.

Вычислительные хеш-функции намного быстрее, чем симметричное шифрование.

Что такое хеш-сумма файла

Всё очень и очень просто с этим самым хешем — давайте возьмём два файла, с первого взгляда, совершенно одинаковых…

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

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

Такой изменённый файл можно распространять в сети Интернет под видом официального, белого и пушистого. Кстати, идеального антивируса не существует и Ваш защитник может Вас подвести в любой момент, если не знали.

Ещё одна ситуация — выбрали и начали скачивание какой-либо программы, файла или архива через торрент? В таком случае, подсунуть Вам маленький бездомный вирус ещё проще, ведь файл закачивается в Ваш компьютер крохотными частями, от огромного количества человек и собирается в кучу только у Вас.

Как же проверить подлинность любого файла, как его идентифицировать со 100% гарантии? Сравнить его хеш-сумму (контрольную сумму)!

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

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

Файлы с одинаковым хешем являются абсолютно идентичными, даже если у них разное название или расширение.

Как пользоваться HashTab

При установке программа HashTab интегрируется в окно свойств Проводника. После установки программы HashTab на ваш компьютер, вы можете проверять хэш-суммы файлов. Для этого кликните по какому-нибудь файлу правой кнопкой мыши.

В контекстном меню выберите пункт «Свойства». После открытия окна, в окне «Свойства» вы увидите новую вкладку «Хеш-суммы файлов».

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

После нажатия на ссылку «Настройки», откроется окно настроек программы HashTab, где во кладке «Отображаемые хеш-суммы» можно выбрать соответствующие пункты алгоритмов проверки.

Для проверки файлов будет достаточно выбрать главные алгоритмы проверки: CRC32, MD5, SHA-1. После выбора алгоритмов проверки нажимаете на кнопку «OK».

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

Также можно проверить хеш другим способом. Для этого, нажимаете на кнопку «Сравнить файл…», а затем выбираете в окне Проводника файл для сравнения.

После этого нажимаете на кнопку «Открыть», а потом в открывшемся окне, вы увидите полученный результат сравнения контрольной суммы файла.

Кликнув правой кнопкой мыши по соответствующей контрольной сумме, вы можете скопировать эту сумму или все контрольные суммы, а также перейти к настройкам программы, если выберете в контекстном меню соответствующий пункт.

Можно также одновременно проверить два файла поодиночке и сравнить результат в двух окнах. На этом изображении видно, что контрольные суммы двух файлов совпадают.

О популярных хэш-алгоритмах

• Алгоритмы CRC16/32 — контрольная сумма (не криптографическое преобразование).
• Алгоритмы MD2/4/5/6. Являются творением Рона Райвеста, одного из авторов алгоритма RSA.
• Алгоритм MD5 имел некогда большую популярность, но первые предпосылки взлома появились еще в конце девяностых, и сейчас его популярность стремительно падает.
• Алгоритм MD6 — очень интересный с конструктивной точки зрения алгоритм. Он выдвигался на конкурс SHA-3, но, к сожалению, авторы не успели довести его до кондиции, и в списке кандидатов, прошедших во второй раунд этот алгоритм отсутствует.
• Алгоритмы линейки SHA. Широко распространенные сейчас алгоритмы. Идет активный переход от SHA-1 к стандартам версии SHA-2. SHA-2 — собирательное название алгоритмов SHA224, SHA256, SHA384 и SHA512. SHA224 и SHA384 являются по сути аналогами SHA256 и SHA512 соответственно, только после расчета свертки часть информации в ней отбрасывается. Использовать их стоит лишь для обеспечения совместимости с оборудованием старых моделей.

Какими свойствами должна обладать хеш-функция

1. Функция должна уметь приводить любой объем данных (а все они цифровые, т.е. двоичные, как вы понимаете) к числу заданной длины (по сути это сжатие до битовой последовательности заданной длины хитрым способом).
2. При этом малейшее изменение (хоть на один бит) входных данных должно приводить к полному изменению хеша.
3. Она должна быть стойкой в обратной операции, т.е. вероятность восстановления исходных данных по хешу должна быть весьма низкой (хотя последнее сильно зависит от задействованных мощностей)
4. В идеале она должна иметь как можно более низкую вероятность возникновения коллизий. Согласитесь, что не айс будет, если из разных массивов данных будут часто получаться одни и те же значения хэша.
5. Хорошая хеш-функция не должна сильно нагружать железо при своем исполнении. От этого сильно зависит скорость работы системы на ней построенной. Как я уже говорил выше, всегда имеется компромисс между скорость работы и качеством получаемого результата.
6. Алгоритм работы функции должен быть открытым, чтобы любой желающий мог бы оценить ее криптостойкость, т.е. вероятность восстановления начальных данных по выдаваемому хешу.

Применения в реальной жизни

• Чек-суммы. Простой и быстрый способ проверить целостность большого передаваемого файла — посчитать хэш-функцию на стороне отправителя и на стороне получателя и сравнить.
• Хэш-таблица. Класс unordered_set из STL можно реализовать так: заведём (n) изначально пустых односвязных списков. Возьмем какую-нибудь хэш-функцию (f) с областью значений ([0, n)). При обработке .insert(x) мы будем добавлять элемент (x) в (f(x))-тый список. При ответе на .find(x) мы будем проверять, лежит ли (x)-тый элемент в (f(x))-том списке. Благодаря «равномерности» хэш-функции, после (k) добавлений ожидаемое количество сравнений будет равно (frac{k}{n}) = (O(1)) при правильном выборе (n).
• Мемоизация. В динамическом программировании нам иногда надо работать с состояниями, которые непонятно как кодировать, чтобы «разгладить» в массив. Пример: шахматные позиции. В таком случае нужно писать динамику рекурсивно и хранить подсчитанные значения в хэш-таблице, а для идентификации состояния использовать его хэш.
• Проверка на изоморфизм. Если нам нужно проверить, что какие-нибудь сложные структуры (например, деревья) совпадают, то мы можем придумать для них хэш-функцию и сравнивать их хэши аналогично примеру со строками.
• Криптография. Правильнее и безопаснее хранить хэши паролей в базе данных вместо самих паролей — хэш-функцию нельзя однозначно восстановить.
• Поиск в многомерных пространствах. Детерминированный поиск ближайшей точки среди (m) точек в (n)-мерном пространстве быстро не решается. Однако можно придумать хэш-функцию, присваивающую лежащим рядом элементам одинаковые хэши, и делать поиск только среди элементов с тем же хэшом, что у запроса.

Хэшируемые объекты могут быть самыми разными: строки, изображения, графы, шахматные позиции, просто битовые файлы.