Хеши: отпечатки данных

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

Как можно «расшифровать» то, что не было зашифровано? Почему сайт хранил не пароли, а какие-то хеши? И что он сделал не так? Чтобы ответить, разберёмся с самой полезной функцией в криптографии — той, которая ничего не прячет, а только оставляет отпечаток.

Отпечаток данных

Хеш-функция берёт любые данные — слово, книгу, фильм на десять гигабайт — и выдаёт строку фиксированной длины. Эту строку называют хешем (от англ. hash — «мешанина, фарш»). Например, у функции SHA-256 хеш всегда занимает 256 битов, то есть 64 шестнадцатеричных знака. Вот хеш слова «пароль»:

2dbc574daca52689a24fb60e835f8c19a36400830df7350859dd32d1abaaec5d

Хорошая хеш-функция обладает четырьмя свойствами:

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

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

Лавинный эффект

Самое удивительное свойство — лавина. Хеш похожих текстов не похож ни капли. Поменяли «9» на «8» — и перевернулась примерно половина из 256 битов, причём заранее не скажешь, какие именно.

Почему ровно половина? Потому что так ведёт себя случайность. Если хеш выглядит как случайная строка, то каждый бит нового хеша совпадает со старым с вероятностью ½ — как монетка. Из 256 монеток орлом ляжет около 128. Если бы перевернулось сильно меньше — скажем, 10 битов, — по хешу можно было бы судить, насколько похожи входы, и это стало бы зацепкой для взломщика.

Как хранят пароли

Вы регистрируетесь на сайте и придумываете пароль. Хранить его как есть было бы опасно: любой, кто доберётся до базы данных — взломщик, нечестный сотрудник, вор резервной копии, — увидит пароли всех пользователей. А люди, увы, используют один пароль везде.

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

Но необратимость не значит, что пароль не подобрать. Взломщик не может пройти от хеша к паролю, зато может пойти от пароля к хешу: взять вероятный пароль, посчитать хеш и сравнить. А пароли у людей поразительно одинаковые: «123456», «qwerty», «password» годами возглавляют списки самых частых. Достаточно один раз посчитать хеши для словаря популярных паролей — и затем просто искать готовые хеши в утёкшей базе.

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

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

Соль

Защита от готовых таблиц удивительно простая. Перед хешированием к паролю каждого пользователя приписывают соль — случайную строку, свою у каждого. В базе хранят соль и хеш от «соль + пароль». Соль не секретна, она лежит рядом с хешем. Но она делает две важные вещи.

Во-первых, готовые таблицы становятся бесполезными: никто не считал заранее хеш «7f3a» + «qwerty». Во-вторых, у двух пользователей с одинаковым паролем теперь разные хеши, поэтому взломщику приходится перебирать словарь для каждого отдельно. Эту идею использовали ещё в Unix конца 1970-х годов: её описали Роберт Моррис и Кен Томпсон в статье 1979 года о безопасности паролей.

Второй приём — сделать каждую попытку дорогой. SHA-256 создан, чтобы быть быстрым, и это плохо для паролей: быстрый хеш — быстрый перебор. Для паролей придумали нарочно медленные функции: bcrypt (1999), scrypt (2009), Argon2 (победитель конкурса 2015 года). Одна проверка у них занимает, скажем, десятую долю секунды. Пользователь при входе этого не заметит, а взломщик со словарём из миллиарда слов застрянет на годы. Утилита «Шифрование AES по паролю» использует для того же PBKDF2 — 250 000 повторов SHA-256.

Коллизии и дни рождения

Хешей SHA-256 — 2²⁵⁶ разных, число из 78 цифр. А возможных входов бесконечно много. Значит, у каких-то разных входов хеши обязательно совпадают. Такое совпадение называется коллизией. Они существуют у любой хеш-функции; вопрос лишь в том, можно ли их найти.

Тут помогает задача о днях рождения. Сколько человек надо собрать, чтобы с вероятностью больше половины у двоих совпал день рождения? Не 183, а всего 23. Ведь мы ищем совпадение любой пары, а пар среди 23 человек уже 253. Для хешей правило такое: у хеша длиной k битов коллизия находится примерно за 2^k/2 попыток — корень из числа всех возможных хешей.

Для полного SHA-256 это 2¹²⁸ попыток — больше, чем все компьютеры Земли успеют за время существования Вселенной. А вот у старых функций нашлись обходные пути, гораздо быстрее перебора.

• MD5 (1991, 128 битов). В 2004 году группа китайского математика Ван Сяоюнь показала, как быстро строить коллизии. Сейчас обычный ноутбук находит их за секунды. В 2012 году вредоносная программа Flame использовала коллизию MD5, чтобы подделать цифровой сертификат Microsoft.
• SHA-1 (160 битов). В 2017 году Google вместе с голландским институтом CWI опубликовал два разных PDF-файла с одинаковым SHA-1. Проект назвали SHAttered.
• SHA-256 и его родственники. Ни одной коллизии не найдено, ими пользуются повсюду.

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

Что взять с собой

• Хеш — отпечаток данных фиксированной длины. Его нельзя обратить, и он меняется целиком от любой правки (лавинный эффект: около половины битов).
• Сайты хранят хеши паролей, а не пароли. Но хеши подбирают: считают хеши словаря и сравнивают. Простой пароль находится мгновенно.
• Соль — случайная строка у каждого пользователя. Она обесценивает готовые и радужные таблицы и заставляет перебирать для каждого отдельно. Медленные хеши (bcrypt, scrypt, Argon2) делают каждую попытку дорогой.
• Коллизии есть у любого хеша, но у хорошего их не найти: для k битов нужно около 2^k/2 попыток. MD5 и SHA-1 сломаны, SHA-256 — нет.

И у шифров, и у хешей до сих пор оставалась одна общая проблема: как вообще договориться о секрете с человеком, которого вы никогда не видели? Тысячи лет считалось, что никак. Дальше: открытый ключ →