PBKDF2

PBKDF2
Разработчики	RSA Security

PBKDF2 (образовано от англ. password-based key derivation function) — стандарт формирования ключа на основе пароля. Является частью PKCS #5 v2.0 (RFC 2898). Заменил PBKDF1, который ограничивал длину генерируемого ключа 160 битами.

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

В Российской Федерации использование функции PBKDF2 регламентируется рекомендациями по стандартизации Р 50.1.111-2016 «Парольная защита ключевой информации», при этом в качестве псевдослучайной функции рекомендуется использовать функцию выработки имитовставки HMAC на основе бесключевой функции хеширования «Стрибог» (ГОСТ Р 34.11-2012).

Алгоритм

Общий вид вызова PBKDF2:

$DK=PBKDF2(PRF,P,S,c,dkLen)$

Опции алгоритма:

• PRF — псевдослучайная функция, с выходом длины hLen
• P — мастер-пароль
• S — соль (salt)
• c — количество итераций, положительное целое число
• dkLen — желаемая длина ключа (не более ($2^{32}$ — 1) * hLen)
• Выходной параметр: DK — сгенерированный ключ длины dkLen

Ход вычислений:

1. l — количество блоков длины hLen в ключе (округление вверх), r — количество байт в последнем блоке:

$l=\lceil (dkLen/hLen)\rceil$

$r=dkLen-(l-1)*hLen$

2. Для каждого блока применить функцию F с параметрами P, S, c и номером блока:

$T_{1}=F(P,S,c,1)$

$T_{2}=F(P,S,c,2)$

$...$

$T_{l}=F(P,S,c,l)$

F определена как операция XOR ($\oplus$) над первыми c итерациями функции PRF, применённой к P и объединению S и номера блока, записанного как 4-байтовое целое число в формате big-endian.

$F(P,S,c,i)=U_{1}\oplus U_{2}\oplus ...\oplus U_{c}$

$U_{1}=PRF(P,S||INT(i))$

$U_{2}=PRF(P,U_{1})$

$...$

$U_{c}=PRF(P,U_{c-1})$

3. Объединение полученных блоков составляет ключ DK. От последнего блока берётся r байт.

$DK=T_{1}||T_{2}||...||T_{l}<0..r-1>$

Скорость работы

Одной из задач при создании PBKDF2 было усложнить перебор паролей. Благодаря множеству зацепленных вычислений PRF скорость генерации ключа является небольшой. Например, для WPA-PSK с параметрами.

$DK=PBKDF2(HMAC-SHA1,passphrase,ssid,4096,256)$

были достигнуты скорости перебора ключей 70 штук в секунду для Intel Core2 и около 1 тысячи на ПЛИС Virtex-4 FX60. Для сравнения, классические функции хеширования пароля LANMAN имеют скорость перебора около сотен миллионов вариантов в секунду.

Использование

Алгоритмы

• Используется как первая и последняя стадия в адаптивной криптографической функции формирования ключа на основе пароля scrypt. Данная функция была специально разработана для приложений, где вычисление PBKDF2 оказывается слишком быстрым.

Системы

• Wi-Fi Protected Access (WPA и WPA2)
• Microsoft Windows Data Protection API (DPAPI)
• Шифрование в формате OpenDocument (OpenOffice.org)
• Схема шифрования AES в WinZip
• LastPass для хеширования паролей
• 1Password для хеширования паролей
• Roboform для хеширования паролей
• Apple iOS мобильная операционная система, для защиты пользовательских кодов доступа и паролей

Шифрование дисков

• FileVault (macOS)
• FreeOTFE (Windows и КПК)
• LUKS — Linux Unified Key Setup (Linux)
• TrueCrypt (Windows, Linux, macOS)
• VeraCrypt (Windows, Linux, macOS)
• DiskCryptor (Windows)
• Cryptographic disk (NetBSD)
• GEOM ELI модуль для ОС FreeBSD
• Шифрование softraid из OpenBSD
• EncFS (Linux) с версии v1.5.0

Литература

• RFC 2898, стр. 9—11
• NIST Special Publication 800-132. Recommendation for Password-Based Key Derivation. // NIST