Хеширование: полное руководство

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

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

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

Что такое хеш и хеш-функция

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

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

Что такое хеш

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

Если захешировать сервисом hashes.com секретное сообщение Читай «Код», то в зависимости от алгоритма мы получим такие хеши:

А вот как выглядит результат хеширования этой строки разными алгоритмами.

Если мы поменяем хотя бы один символ в сообщении, например заменим одну кавычку-ёлочку на кавычку-лапку, то хеш полностью изменится:

Почему так, разберём дальше.

Как работает хеш-функция

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

Поэтому сильная хеш-функция всегда обладает такими свойствами:

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

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

Есть разные популярные алгоритмы хеширования — SHA-1, SHA-256 и другие. Они работают с блоками от 160 до 512 бит. Если размер данных больше, алгоритмы как бы нарезают входные данные на куски определённого размера, создавая массив блоков, а потом обрабатывают их один за другим.

Если длина данных меньше, чем размер блока, то добавляются дополнительные биты, чтобы заполнить пробел. Строка Читай «Код» занимает меньше 512 бит, поэтому алгоритм дополнит её нулями или другими значениями, чтобы размер соответствовал блоку. Это нужно для того, чтобы алгоритм работал стабильно, независимо от длины входных данных.

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

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

Хеш-коллизии

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

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

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

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

Принципы работы хеширования

Хеш-функция — это только часть алгоритма хеширования. Чтобы данные могли через неё пройти, они идут через несколько этапов подготовки: разбиваются на блоки и дополняются. Затем на каждом шаге обработки используются рабочие переменные, в которых накапливается промежуточный результат обработки. Переменные постоянно обновляются после обработки каждого блока и постепенно формируют итоговый хеш. Благодаря этому результат зависит от всех блоков данных, а любые изменения во входной строке сразу приводят к совершенно другому хешу.

Алгоритмы хеширования

Теперь о самих алгоритмах. Каждый алгоритм хеширования имеет свои особенности и подходит для разных задач.

Раньше повсеместно использовались алгоритмы MD5 и SHA-1: в сертификатах безопасности, шифрованных соединениях и различных криптографических протоколах SSL/TLS. Сейчас эти алгоритмы считаются небезопасными, поскольку в них нашли уязвимости, допускающие коллизии. В 2001 году Агентство национальной безопасности США разработало новый алгоритм SHA-2 как преемник SHA-1. Его улучшили, добавив больше операций и увеличив длину хеша до 256 и 512 бит, чтобы алгоритм был более устойчивым к атакам.

Вслед за SHA-2 появился алгоритм SHA-3, который был утверждён как новый стандарт хеширования в 2015 году. В отличие от других алгоритмов, SHA-3 основан на совершенно иной архитектуре — так называемой «губке». Такой подход использует две стадии: «впитывание», когда данные перемешиваются с помощью случайных перестановок, и «выжимание», где создаётся итоговый хеш. SHA-3 более устойчив к атакам и меньше подвержен коллизиям. Применяется для цифровых подписей, в блокчейнах и в системах, требующих высокой степени безопасности.

Другой популярный алгоритм — bcrypt. Его особенность в том, что он добавляет соль — уникальную строку, которая объединяется с исходными данными перед хешированием. Это предотвращает атаки методом перебора и использование предвычисленных таблиц. Bcrypt часто используется для хеширования паролей в веб-приложениях, обеспечивая их защиту даже в случае утечки базы данных.

Есть также алгоритм Scrypt, разработанный для защиты паролей. Его особенность — в высокой требовательности к ресурсам, как вычислительным, так и памяти, что делает атаки перебором очень затратными. Для выполнения операции требуется не только процессорное время, но и значительный объём оперативной памяти. Scrypt — это улучшенная версия алгоритма SHA-256, он часто используется в криптовалютах, например в алгоритме майнинга Litecoin, и для защиты паролей.

Применение хеширования

Сейчас хеширование применяется в самых разных областях: от кибербезопасности и блокчейна до защиты данных.

Хранение паролей и защита данных

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

Проверка подлинности сообщений и данных

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

Цифровая подпись

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

Блокчейн

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

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

Управление базами данных

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

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

Такой подход сокращает время поиска: не нужно перебирать все данные, система сразу обращается к нужной ячейке.

Будущее хеширования

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

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

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