Шифровальная машина M-209, на основе которой создана первая в истории функция хэширования crypt в Unix

Прошло 25 лет с момента изобретения алгоритма хэширования bcrypt (1997), но он до сих пор считается одним из самых стойких к брутфорсу хэшей.

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

Если посмотреть в историю, то концепция компьютерных паролей возникла на заре многопользовательских вычислительных систем, когда потребовался способ аутентификации и защиты данных. В Массачусетском технологическом институте в 1960-е разработали систему Compatible Time-Sharing System (CTSS) с парольной аутентификацией аккаунтов, одну из первых в мире таких систем. Любопытно, что это произошло несмотря на упорные возражения Ричарда Столлмана, который пытался противостоять введению паролей в MIT в 1970-е. Об этом вспоминал Стивен Леви в документальной книге «Хакеры: герои компьютерной революции».

Однако истинные истоки современной парольной защиты можно отнести к разработке Unix и её нативной функции хэширования crypt. Первоначальная версия crypt в Unix (6th Edition) была реализована Робертом Моррисом и базировалась на шифровальной машине Хагелина (модель M-209).


Конвертер M-209B Бориса Хагелина

О легендарном изобретателе шифровальных машин Борисе Хагелине рассказывали на Хабре. Родившийся в Российской империи, этот мальчик отучился в Баку, а отправился на дальнейшую учёбу за границу, где и стал знаменитым благодаря созданию уникальных шифровальных машин и основанию швейцарской компании Crypto AG в 1952-м, в течение десятилетий мирового лидера на рынке криптографических устройств.

Возвращаясь к Unix, специалисты ещё в 70-е годы осознавали проблему слишком быстрого выполнения функции crypt. В Unix (7-я редакция) функция была усовершенствована путём введения 12-битной соли и итерации шифра Data Encryption Standard (DES) для хэширования пароля. В результате использования соли получилось семейство из 2¹² различных хэш-функций, и каждый пользователь случайным образом выбирал из этого семейства свой пароль. Цель использования соли заключалась не только в том, чтобы обеспечить уникальность хэшей даже для одинаковых паролей, но и в том, чтобы существенно затруднить атаки с предварительным вычислением хэша. Хэшированный пароль с солью хранился в файле паролей, что позволяло системе аутентифицировать пользователей, не храня пароли в открытом виде.

Для своего времени crypt считался безопасным, однако развитие вычислительных мощностей и экспортные ограничения на криптографию в США открыли дорогу новым алгоритмам хеширования паролей, таким как MD5crypt (1994).


Запрещённый к экспорту из США код RSA распечатан на футболке в знак протеста против ограничения свободы слова. Одетый таким образом гражданин имел право выехать за границу и показать футболку иностранным гражданам

Опасения по поводу безопасности новых алгоритмов привели к разработке bcrypt в 1997 году. В нём впервые реализовали концепцию адаптивного хеширования, благодаря которой атаки методом брутфорса и по словарю стали вычислительно более сложными (алгоритм защищён от будущего роста производительности оборудования). С момента своего появления в июне 1997 года в составе OpenBSD 2.1 и публикации в USENIX в 1999 году bcrypt оказал глубокое влияние на индустрию безопасности.


Оригинальная научная статья с описанием bcrypt (1999)

В целом четверть века развития функций хэширования и индустрии брутфорса можно изобразить в такой таблице:

Сравнение функций хэширования и их безопасности. Адаптируемый коэффициент (work factor) означает, что нагрузку на CPU можно увеличить. Вычисления с расходом памяти (memory-hardness) означает, что кроме CPU алгоритм хеширования масштабируется и по памяти

Производительность брутфорса

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

Чтобы продемонстрировать этот прогресс, вот примерные оценки скорости брутфорса на компьютерах разных лет, а также в разных программах (Hashcat и John the Ripper). Следует иметь в виду, что эти цифры просто демонстрируют общий тренд, их нельзя напрямую сопоставлять из-за различий в оборудовании и ПО. Для наглядности цифры публикуются со всеми разрядами, без сокращения до «млн» и «млрд».


Можно заметить, что с годами растёт не только сложность алгоритмов, но и производительность железа, а также эффективность специализированных программ.

Например, за 34 года скорость перебора хэшей des-crypt выросла с 45 штук до 6,3 млрд в секунду.

В то же время старый bcrypt остаётся одним из самых сложных для взлома хэшей, особенно с максимальным коэффициентом сложности (work factor). Хотя формально он считается устаревшим, но на практике теоретически вполне пригоден к использованию, наряду с более современными, стойкими к брутфорсу алгоритмами scrypt и Argon2.

Пароли навсегда

Что будет дальше?

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

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

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