Хеш-функция: что это, для чего нужна и как работает

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

Сегодня вы узнаете:

• что такое хеш-функция;
• для чего она нужна;
• где используется;
• как она работает;
• насколько она безопасна.

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

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

Исходным сообщением может быть что угодно: строчка из песни, код программы или, скажем, роман «Ловец снов» Стивена Кинга на китайском языке. Неважно, какой длины будет исходный текст, — на выходе всё равно получится битовый массив одного и того же размера. Например, для функции SHA-1 это 160 бит, или ровно 40 символов.

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

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

С хешированием такой номер не пройдёт — прокрутить этот фарш назад не выйдет вообще ни у кого, даже у Павла Дурова.

Для чего нужна хеш-функция

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

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

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

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

Чтобы избежать таких атак, каждому паролю при регистрации добавляют соль — то есть случайный набор символов. Когда вы вводите пароль, алгоритм добавляет к нему уникальную соль, потом всё это дело хешируется и получается совершенно новый хеш. Даже если ваш пароль — это банальный qwerty, parol или 12345, жулики об этом не узнают :)

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

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

Где используется хеш-функция

Вот ещё несколько сфер, где используется хеширование:

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

Читайте также:

Что такое блокчейн и как он работает

• Цифровые подписи — чтобы дистанционно подписывать документы без поездок в офисы и встреч с курьерами.
• Хеш-таблицы — это своего рода базы данных, где все данные защищены от перезаписи.
• Антивирусы — хранят вирусы в виде так называемого нечёткого хеша, который позволяет искать новые модификации зловредных программ.
• Системы контроля версий (Git) — для проверки целостности объектов в репозитории: файлов, коммитов, деревьев и так далее.

Теперь подробнее: как работает криптографическая хеш-функция

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

Хешировать будем обычную программистскую «рыбу» — фразу «Hello, world!». Так как компьютер общается только на языке нулей и единиц, первым делом алгоритм переведёт текст в двоичный код:

01001000 01100101 01101100 01101100 01101111 00101100 00100000 
01110111 01101111 01110010 01101100 01100100 00100001

Нюанс в том, что хеш-функция оперирует только блоками по 512 бит — а в нашей фразе только 104 бита. Поэтому дополним блок — начнём с единицы, а остальное заполним нулями. В самом конце блока добавим двоичный код, обозначающий размер сообщения в битах, — у нас это 104, или 1101000.

01001000 01100101 01101100 01101100 01101111 00101100 00100000
01110111 01101111 01110010 01101100 01100100 00100001 10000000 
00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 00000000 00000000 0000000 
00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 00000000 00000000 01011000

После этого алгоритм подготовит основу для будущего хеша. По умолчанию это пять констант по восемь символов — на выходе как раз получится фраза длиной 40 символов и размером 160 бит.

Выглядят константы так:

• h0 = 0×67452301
• h1 = 0xEFCDAB89
• h2 = 0×98BADCFE
• h3 = 0×10325476
• h4 = 0xC3D2E1F0

А дальше начинается магия. Алгоритм дробит исходное сообщение на 80 кусочков и перемешивает с каждой из констант. Каждая итерация цикла обновляет значения h0–h4 до тех пор, пока не закончится исходное сообщение. Постепенно хеш будет выглядеть всё более и более случайным.

   for i from 0 to 79
        if 0 ≤ i ≤ 19 then
            f = (b and c) or ((not b) and d)
            k = 0x5A827999
        else if 20 ≤ i ≤ 39 then
            f = b xor c xor d
            k = 0x6ED9EBA1
        else if 40 ≤ i ≤ 59 then
            f = (b and c) or (b and d) or (c and d)
            k = 0x8F1BBCDC
        else if 60 ≤ i ≤ 79 then
            f = b xor c xor d
            k = 0xCA62C1D6
        temp = (a leftrotate 5) + f + e + k + w[i]
        e = d
        d = c
        c = b leftrotate 30
        b = a
        a = temp

Выполняется функция в несколько раундов: один блок длиной 512 бит — одна итерация. Так как во фразе «Hello, world!» меньше 512 бит, алгоритм обработает её в один заход. Но даже если бы мы подали на вход все четыре тома «Войны и мира», хеширование всё равно заняло бы всего пару секунд.

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

digest = hash = h0 append h1 append h2 append h3 append h4

На выходе получаем готовый хеш:

943a702d06f34599aee1f8da8ef9f7296031d699

Насколько безопасны хеш-функции

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

• Уникальность — два разных сообщения не могут выдать одинаковый хеш (на самом деле бывают исключения — об этом позже).
• «Лавинный эффект» — если в исходных данных поменять хотя бы одну букву, получится совершенно другой хеш.
• Предсказуемость — для одного и того же сообщения всегда получается одинаковый хеш.
• Необратимость — нельзя просто так взять и прочитать то, что захешировано.
• Скорость — чтобы данные быстро обрабатывались в высоконагруженных системах.

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

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

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

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

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

Коротко о главном

Подытожим основные тезисы статьи:

• Криптографическая хеш-функция — это алгоритм, который принимает на вход сообщение и превращает его в хеш, то есть битовый массив фиксированного размера. Например, для SHA-1 это 160 бит, а для SHA-256 — 256 бит.
• Для каждого сообщения создаётся свой уникальный хеш. Если поменять во входных данных хотя бы один символ, хеш изменится до неузнаваемости.
• Хеш можно присвоить любому файлу: тексту, песне или компьютерной игре. Ключевой смысл — убедиться, что данные нельзя изменить или подделать.
• Результат работы хеш-функции необратимый — алгоритм нельзя запустить в обратную сторону и получить исходное сообщение. Этим хеширование отличается от шифрования, где, как правило, есть ключ дешифровки.
• Хеширование используется для разных задач: для безопасного хранения паролей на сайте, создания цифровых подписей, защиты игровых данных, подтверждения транзакций в блокчейне и многого другого.