Мать всех блокчейнов, хранительница паролей и просто интересная технология.
Про хеш-функции мало говорят за пределами узкой прослойки экспертов по сетевой безопасности. А зря. Без неё у нас не было бы ни блокчейна, ни NFT, ни даже электронных справок в «Госуслугах» — а украсть пароль из любого сервиса было бы делом пары минут. В этой статье мы пошагово разберём, как работает алгоритм хеш-функции и чем он отличается от шифрования.
Сегодня вы узнаете:
Что такое хеш-функция
Исходным сообщением может быть что угодно: строчка из песни, код программы или, скажем, роман «Ловец снов» Стивена Кинга на китайском языке. Неважно, какой длины будет исходный текст, — на выходе всё равно получится битовый массив одного и того же размера. Например, для функции SHA-1 это 160 бит, или ровно 40 символов.
Так работает алгоритм хеширования SHA-1
Инфографика: Оля Ежак для Skillbox Media
Для каждого сообщения алгоритм создаёт свой уникальный хеш. Если пропустить одно и то же сообщение через алгоритм, хеш на выходе будет неизменным. Но если заменить в исходных данных хотя бы одну букву, хеш изменится до неузнаваемости:
Получили другой хеш, но такой же длины
Инфографика: Оля Ежак для Skillbox Media
Ключевое свойство хеш-функции — необратимость. Нельзя просто так взять и развернуть алгоритм вспять и прочитать исходное сообщение. Поэтому, если хакеру в руки попадёт база данных с захешированными паролями, взломать он их сможет только полным перебором — а на это может уйти несколько месяцев и даже лет.
Этим, кстати, хеширование отличается от шифрования. В случае с шифрованием всегда есть ключ, который позволит тем, кому вы доверяете, расшифровать сообщение. Например, при общении в секретном чате в Telegram создаётся дешифратор, который позволит читать сообщения участникам переписки — а спецслужбам, хакерам и марсианам не позволит.
С хешированием такой номер не пройдёт — прокрутить этот фарш назад не выйдет вообще ни у кого, даже у Павла Дурова.
Для чего нужна хеш-функция
Один из популярных вариантов использования хеша — хранение паролей на сайте. Когда вы заходите в личный кабинет, ваши данные не передаются в базу данных в открытом виде — иначе хакеры давно украли бы все аккаунты в мире.
Во время авторизации пароль сначала хешируется и только потом записывается в базу данных. При следующей попытке входа пароль снова переводится в хеш и сличается с хешем на сервере. Если хеши совпали, вы попадаете в личный кабинет.
Инфографика: Оля Ежак для Skillbox Media
Однако у хакеров и на этот случай есть хитрость. Так как один и тот же текст выдаёт одинаковый хеш, можно просто хешировать самые популярные пароли и подставлять их при взломе. В Сети можно найти целые словари, которые содержат тысячи когда-то слитых дехешированных паролей.
Чтобы избежать таких атак, каждому паролю при регистрации добавляют соль — то есть случайный набор символов. Когда вы вводите пароль, алгоритм добавляет к нему уникальную соль, потом всё это дело хешируется и получается совершенно новый хеш. Даже если ваш пароль — это банальный qwerty, parol или 12345, жулики об этом не узнают 🙂
Инфографика: Оля Ежак для Skillbox Media
Ещё один пример использования хешей — проверка целостности файлов. Например, когда вы запускаете игру из Steam, лаунчер следит, что всё установлено правильно и никакой предприимчивый пользователь не залез в файлы игры и не нашпиговал их под завязку разными модами и читами.
Для этого разработчики хешируют игровые файлы — если их изменить хотя бы чуть-чуть, хеши не совпадут и клиент Steam не даст запустить игру.
И это всё происходит перед каждым запуском игры, чтобы игроки не читерили
Инфографика: Оля Ежак для Skillbox Media
Где используется хеш-функция
Вот ещё несколько сфер, где используется хеширование:
- Блокчейн — чтобы гарантировать подлинность транзакций. В каждый блок цепи добавляется хеш предыдущей операции — если поменять данные хоть чуть-чуть, хеши не совпадут и сеть не примет изменения.
- Цифровые подписи — чтобы дистанционно подписывать документы без поездок в офисы и встреч с курьерами.
- Хеш-таблицы — это своего рода базы данных, где все данные защищены от перезаписи.
- Антивирусы — хранят вирусы в виде так называемого нечёткого хеша, который позволяет искать новые модификации зловредных программ.
- Системы контроля версий (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 бит.
- Для каждого сообщения создаётся свой уникальный хеш. Если поменять во входных данных хотя бы один символ, хеш изменится до неузнаваемости.
- Хеш можно присвоить любому файлу: тексту, песне или компьютерной игре. Ключевой смысл — убедиться, что данные нельзя изменить или подделать.
- Результат работы хеш-функции необратимый — алгоритм нельзя запустить в обратную сторону и получить исходное сообщение. Этим хеширование отличается от шифрования, где, как правило, есть ключ дешифровки.
- Хеширование используется для разных задач: для безопасного хранения паролей на сайте, создания цифровых подписей, защиты игровых данных, подтверждения транзакций в блокчейне и многого другого.
Нечёткое хеширование — это когда при небольшом изменении входных данных результат меняется не полностью.
Простыми словами — присоединения.