Расширение ключа

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

История и предпосылки

Идея расширения ключа возникла в 1970-х годах в связи с развитием криптографии с открытым ключом и необходимостью защиты паролей, хранящихся в системах аутентификации. Ранние системы, такие как UNIX, использовали для хранения паролей хеш-функции (например, DES-based crypt), которые уже включали в себя элементы расширения — например, добавление «соли» (salt) и многократное хеширование. Однако с ростом вычислительных мощностей и появлением специализированных устройств (GPU, ASIC) стало очевидно, что однократное хеширование пароля (например, через MD5 или SHA-1) не обеспечивает достаточной защиты: современные атаки могут перебирать миллиарды комбинаций в секунду.

В 1999 году был предложен алгоритм PBKDF2 (Password-Based Key Derivation Function 2), ставший первым стандартизированным методом расширения ключа. Позднее появились более устойчивые к аппаратному ускорению алгоритмы, такие как bcrypt (1999), scrypt (2009) и Argon2 (2015), победивший в конкурсе Password Hashing Competition.

Принцип работы

Расширение ключа обычно реализуется через итеративное применение криптографически стойкой хеш-функции или блочного шифра. Основные этапы:

1. Приём исходного ключа (пароля) — обычно короткой длины (от 6 до 64 символов) и низкой энтропии.
2. Добавление соли — случайного значения, уникального для каждого пользователя, что предотвращает атаки по предвычисленным таблицам (rainbow tables).
3. Многократное итеративное хеширование — функция применяется к результату предыдущего шага заданное число раз (например, 10 000 или 100 000 итераций). Каждая итерация требует фиксированного времени вычислений.
4. Формирование выходного ключа — результатом является последовательность битов фиксированной длины (например, 256 бит), которая используется как ключ шифрования или для проверки пароля.

Ключевой параметр — число итераций (или «стоимость»): чем оно больше, тем выше вычислительная нагрузка на легитимного пользователя (например, 0,5 секунды при проверке пароля) и тем сильнее замедляется атака перебором.

Виды и алгоритмы

PBKDF2 (Password-Based Key Derivation Function 2)

Стандартизирован в RFC 2898 и RFC 8018. Использует псевдослучайную функцию (обычно HMAC-SHA256) и многократное хеширование. Параметры: соль, число итераций, длина выходного ключа. Широко применяется в системах, где важна совместимость (например, в Wi-Fi Protected Access 2 (WPA2) для генерации ключей). Недостаток: относительно легко ускоряется на GPU и ASIC из-за простоты операций.

bcrypt

Разработан Нильсом Провосом и Дэвидом Мазьером в 1999 году. Основан на блочном шифре Blowfish. Включает в себя встроенную соль и параметр «стоимости» (cost factor), который определяет число итераций (2^cost). Устойчив к атакам на GPU, так как требует значительного объёма памяти (около 4 КБ) для хранения таблицы ключей Blowfish. Используется в системах аутентификации (например, в OpenBSD, некоторых веб-фреймворках).

scrypt

Предложен Колином Персивалем в 2009 году. Отличается высокой требовательностью к оперативной памяти (параметр «memory hardness»). Алгоритм генерирует большой массив случайных данных в памяти и затем многократно обращается к нему, что делает атаки на GPU и ASIC неэффективными из-за ограничений по пропускной способности памяти. Параметры: соль, число итераций, размер памяти, степень параллелизма. Используется в криптовалютах (например, Litecoin) и в системах хранения паролей (например, в Tarsnap).

Argon2

Победитель конкурса Password Hashing Competition (2015). Имеет три варианта: Argon2d (устойчив к атакам по времени, оптимизирован для GPU), Argon2i (устойчив к атакам по побочным каналам) и Argon2id (комбинированный). Параметры: соль, время, память, степень параллелизма. Argon2id считается наиболее сбалансированным и рекомендован к использованию (например, в RFC 9106). Применяется в современных библиотеках (libsodium, OpenSSL).

Применение

Расширение ключа используется в следующих областях:

• Хранение паролей — в базах данных пользовательских систем (веб-сайты, операционные системы, корпоративные приложения). Вместо хранения пароля в открытом виде или его простого хеша сохраняется результат расширения ключа с солью.
• Генерация ключей шифрования — из пароля низкой энтропии (например, для шифрования файлов в программах вроде VeraCrypt, BitLocker, LUKS) получается стойкий ключ для симметричного шифрования (AES, ChaCha20).
• Криптовалюты — в алгоритмах доказательства работы (Proof of Work) и для генерации ключей кошельков (например, в Bitcoin используется PBKDF2 для получения ключа из мнемонической фразы).
• Протоколы аутентификации — в некоторых реализациях SSH, TLS (при использовании парольной аутентификации) и в системах одноразовых паролей (TOTP).

Критика и ограничения

Несмотря на эффективность, расширение ключа не является панацеей. Основные недостатки:

• Увеличение времени для легитимного пользователя — при большом числе итераций (например, 10 млн) проверка пароля может занимать несколько секунд, что неудобно для пользователей.
• Чувствительность к выбору параметров — если число итераций слишком мало, алгоритм не обеспечивает защиты; если слишком велико — падает производительность системы.
• Атаки на аппаратном уровне — для некоторых алгоритмов (PBKDF2, bcrypt) существуют специализированные ASIC, которые могут выполнять миллионы итераций в секунду, хотя и с меньшей эффективностью, чем для простых хешей.
• Необходимость защиты соли — если соль становится известна злоумышленнику, атака по словарю остаётся возможной, хотя и замедленной.

Интересные факты

• В 2012 году компания Dropbox сообщила, что использует bcrypt с 10 000 итераций для хранения паролей пользователей, что было признано стандартом безопасности на тот момент.
• Алгоритм Argon2 был разработан командой криптографов из России (Алексей Бирюков, Дмитрий Ховратович, Сергей Белов) и Польши (Кшиштоф Петрашкевич). В 2019 году он был включён в рекомендации Национального института стандартов и технологий США (NIST) как один из одобренных методов.
• В некоторых системах (например, в Android 9+) используется scrypt с параметрами, требующими около 1 МБ памяти, что делает атаки на мобильных устройствах практически невозможными.

Источники

• RFC 2898 — PKCS #5: Password-Based Cryptography Specification Version 2.0
• RFC 8018 — PKCS #5: Password-Based Cryptography Specification Version 2.1
• RFC 9106 — Argon2 Memory-Hard Function for Password Hashing and Proof-of-Work Applications
• Provos, N., Mazières, D. (1999). «A Future-Adaptable Password Scheme». USENIX Annual Technical Conference.
• Percival, C. (2009). «Stronger Key Derivation via Sequential Memory-Hard Functions». BSDCan 2009.
• NIST Special Publication 800-63B — Digital Identity Guidelines: Authentication and Lifecycle Management