Функции вывода ключей: принципы и современные алгоритмы

Введение

Функция, извлекающая секретные ключи из секретного значения.

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

История

Первая намеренно медленная (с растяжкой ключа) функция получения ключей на основе пароля называлась "crypt" (или "crypt(3)" по названию страницы руководства), и была изобретена Робертом Моррисом в 1978 году. Она шифровала константу (ноль), используя первые 8 символов пароля пользователя в качестве ключа, выполняя 25 итераций модифицированного алгоритма шифрования DES (в котором 12-битное число, считываемое с системных часов реального времени, использовалось для внесения возмущений в вычисления). Полученное 64-битное число кодировалось в виде 11 печатных символов и затем сохранялось в файле паролей Unix. Хотя в то время это было большим достижением, увеличение скорости процессоров с момента появления PDP 11 сделало возможными атаки полным перебором на crypt, а прогресс в области хранения данных сделал 12-битный salt недостаточным. Конструкция функции crypt также ограничивает длину пароля пользователя 8 символами, что сужает пространство ключей и делает невозможным использование надежных парольных фраз. Хотя высокая пропускная способность является желательным свойством для хэш-функций общего назначения, в приложениях безопасности паролей, где защита от взлома полным перебором является первостепенной задачей, все обстоит с точностью до наоборот. Растущее использование массово-параллельного оборудования, такого как GPU, FPGA и даже ASIC для атак полным перебором, сделало выбор подходящего алгоритма еще более критичным, поскольку хороший алгоритм должен обеспечивать определенные вычислительные затраты не только на CPU, но и противостоять преимуществам в соотношении цена/производительность современных массово-параллельных платформ для подобных задач. Для этой цели были разработаны различные алгоритмы, включая bcrypt, scrypt и, более недавно, Lyra2 и Argon2 (последний стал победителем конкурса по хешированию паролей). Масштабная утечка данных Ashley Madison, в результате которой злоумышленники похитили около 36 миллионов хэшей паролей, наглядно продемонстрировала важность выбора алгоритма для защиты паролей. Хотя bcrypt использовался для защиты хэшей (что делало крупномасштабный взлом полным перебором дорогостоящим и трудоемким), значительная часть учетных записей в скомпрометированных данных также содержала хэш пароля, основанный на быстром алгоритме общего назначения MD5, что позволило взломать более 11 миллионов паролей за несколько недель. В июне 2017 года Национальный институт стандартов и технологий США (NIST) опубликовал новую редакцию своих рекомендаций по цифровой аутентификации, NIST SP 800 63B 3, в которой указано: "Для особо важных ключей или для очень мощных систем, или систем, где воспринимаемая пользователем производительность не является критичной, количество итераций 10 000 000 может быть уместным".

The first deliberately slow (key stretching) password based key derivation function was called "crypt" (or "crypt(3)" after its man page), and was invented by Robert Morris in 1978. It would encrypt a constant (zero), using the first 8 characters of the user's password as the key, by performing 25 iterations of a modified DES encryption algorithm (in which a 12 bit number read from the real time computer clock is used to perturb the calculations). The resulting 64 bit number is encoded as 11 printable characters and then stored in the Unix password file. While it was a great advance at the time, increases in processor speeds since the PDP 11 era have made brute force attacks against crypt feasible, and advances in storage have rendered the 12 bit salt inadequate. The crypt function's design also limits the user password to 8 characters, which limits the keyspace and makes strong passphrases impossible. Although high throughput is a desirable property in general purpose hash functions, the opposite is true in password security applications in which defending against brute force cracking is a primary concern. The growing use of massively parallel hardware such as GPUs, FPGAs, and even ASICs for brute force cracking has made the selection of a suitable algorithms even more critical because the good algorithm should not only enforce a certain amount of computational cost not only on CPUs, but also resist the cost/performance advantages of modern massively parallel platforms for such tasks. Various algorithms have been designed specifically for this purpose, including bcrypt, scrypt and, more recently, Lyra2 and Argon2 (the latter being the winner of the Password Hashing Competition). The large scale Ashley Madison data breach in which roughly 36 million passwords hashes were stolen by attackers illustrated the importance of algorithm selection in securing passwords. Although bcrypt was employed to protect the hashes (making large scale brute force cracking expensive and time consuming), a significant portion of the accounts in the compromised data also contained a password hash based on the fast general purpose MD5 algorithm, which made it possible for over 11 million of the passwords to be cracked in a matter of weeks. In June 2017, The U. S. National Institute of Standards and Technology (NIST) issued a new revision of their digital authentication guidelines, NIST SP 800 63B 3,
"For especially critical keys, or for very powerful systems or systems where user perceived performance is not critical, an iteration count of 10,000,000 may be appropriate.”

Вывод ключа

Первоначальное применение KDF – это вывод ключей, то есть генерация ключей из секретных паролей или парольных фраз. Вариации этого применения включают:

* В сочетании с несекретными параметрами для получения одного или нескольких ключей из общего секретного значения (которое иногда также называют "диверсификацией ключей"). Такое использование может предотвратить получение злоумышленником полезной информации о входном секретном значении или любом из других полученных ключей, если он получит производный ключ. KDF также может использоваться для обеспечения желаемых свойств производных ключей, таких как исключение "слабых ключей" в некоторых конкретных системах шифрования.
* В качестве компонентов многосторонних протоколов согласования ключей. Примеры таких функций вывода ключей включают KDF1, определенный в IEEE Std 1363 2000, и аналогичные функции в ANSI X9.42.
* Для вывода ключей из секретных паролей или парольных фраз (KDF на основе пароля).
* Для вывода ключей другой длины, чем предоставленные. KDF, разработанные для этой цели, включают HKDF и SSKDF. Они принимают битовую строку "info" в качестве дополнительного параметра "info", который может быть критически важен для привязки полученного ключевого материала к информации, специфичной для приложения и контекста.
* Растяжка ключей и усиление ключей.

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

Функции получения ключей также используются в приложениях для получения ключей из секретных паролей или парольных фраз, которые обычно не обладают необходимыми свойствами для непосредственного использования в качестве криптографических ключей. В таких приложениях обычно рекомендуется намеренно замедлять работу функции получения ключа, чтобы затруднить атаку полным перебором или словарную атаку на входное значение пароля или парольной фразы. Такое использование можно представить в виде 1=DK = KDF(ключ, соль, итерации), где 1=DK – это полученный ключ, 1=KDF – функция получения ключа, 1=ключ – исходный ключ или пароль, 1=соль – случайное число, выполняющее роль криптографической соли, и 1=итерации – количество итераций подфункции. Полученный ключ используется вместо исходного ключа или пароля в качестве ключа системы. Значения соли и количество итераций (если они не фиксированы) хранятся вместе с хешированным паролем или передаются в открытом виде (незашифрованными) вместе с зашифрованным сообщением. Сложность атаки полным перебором возрастает с увеличением количества итераций. Практическим ограничением на количество итераций является нежелание пользователей терпеть ощутимую задержку при входе в компьютер или просмотре расшифрованного сообщения. Использование соли не позволяет злоумышленникам предварительно вычислить словарь полученных ключей. Это вынуждает как злоумышленника, так и легитимных пользователей выполнять поиск методом полного перебора для определения значения соли. Хотя в работе, представившей растяжку ключей, упоминалась эта более ранняя техника и было намеренно выбрано другое название, термин "усиление ключа" теперь часто (возможно, ошибочно) используется для обозначения растяжки ключей.