PBKDF2

PBKDF2 (англ. Password-Based Key Derivation Function) — стандарт формирования ключа (англ.) на основе пароля. Является частью PKCS #5 v2.0 (RFC 2898). Заменил PBKDF1, который ограничивал длину порождаемого ключа 160 битами.

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

Алгоритм

Общий вид вызова 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-байтовое целое с первым msb байтом.

$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 с параметрами^[1]

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

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

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

Системы

• Wi-Fi Protected Access (WPA и WPA2)
• Microsoft Windows Data Protection API (DPAPI)^[4]
• Шифрование в формате OpenDocument (OpenOffice.org)
• Схема шифрования AES в WinZip^[5][6]
• Lastpass для хеширования паролей.^[7]

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

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

Примечания

1. ↑ WPA key calculation: From passphrase to hex
2. ↑ http://openciphers.sourceforge.net/oc/wpa.php
3. ↑ http://openciphers.sourceforge.net/oc/lm.php
4. ↑ Windows Data Protection
5. ↑ WinZip® - AES Coding Tips for Developers
6. ↑ BRG Main SIte
7. ↑ LastPass : The last password you'll have to remember: LastPass Security Notification
8. ↑ http://crypto.nsa.org/vilefault/23C3-VileFault.pdf

Литература

• RFC 2898, стр. 9-11