Ключевая растяжка

В криптографии за счет увеличения ресурсов (времени и, возможно, пространства) , методы растяжения ключей используются для того, чтобы сделать потенциально слабый ключ, обычно пароль или парольную фразу , более защищенным от атаки методом перебора необходимых для проверки каждого возможного ключа. Пароли или парольные фразы, созданные людьми, часто бывают достаточно короткими или предсказуемыми, чтобы их можно было взломать , а растяжение ключей предназначено для того, чтобы затруднить такие атаки, усложняя базовый этап проверки одного кандидата на пароль. Растяжение ключей также повышает безопасность в некоторых реальных приложениях, где длина ключа ограничена, путем имитации более длинного ключа с точки зрения злоумышленника методом перебора. ^[1]

Существует несколько способов выполнения растяжки клавиш. Один из способов — многократное применение криптографической хэш-функции или блочного шифра в цикле. Например, в приложениях, где ключ используется для шифрования , расписание ключей в шифре может быть изменено так, чтобы его выполнение занимало определенный промежуток времени. Другой способ — использовать криптографические хэш-функции, требующие больших требований к памяти. Они могут быть эффективными в предотвращении атак злоумышленников, ограниченных в памяти. ^[2]

Процесс

Алгоритмы растяжения ключа зависят от алгоритма, который получает входной ключ, а затем затрачивает значительные усилия на создание расширенного шифра (называемого расширенным ключом). ^{[ нужна ссылка ]}), имитируя случайность и большую длину ключа. Алгоритм не должен иметь известного сокращения, поэтому наиболее эффективный способ связать ввод и шифрование — это повторить сам алгоритм растяжения ключа. Это вынуждает злоумышленников перебором затрачивать одинаковые усилия для каждой попытки. Если эти дополнительные усилия сравнить с перебором всех ключей с определенной длиной ключа, то входной ключ можно описать как растянутый на ту же длину. ^[1]

Растяжение ключей оставляет злоумышленнику два варианта:

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

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

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

На основе хеша

Многие библиотеки предоставляют функции, которые выполняют растяжение клавиш как часть своей функции; см crypt(3) . . пример ^[4] PBKDF2 предназначен для генерации ключа шифрования из пароля и не обязательно для аутентификации пароля. PBKDF2 можно использовать и для того, и для другого, если количество выходных битов меньше или равно внутреннему алгоритму хеширования, используемому в PBKDF2, который обычно представляет собой SHA-2 (до 512 бит), или используется в качестве ключа шифрования для шифрования статических данных. ^[5]

Сила и время

В этих примерах предполагается, что потребительский процессор может выполнить около 65 000 хэшей SHA-1 за одну секунду. Таким образом, программа, использующая растяжение ключей, может использовать 65 000 раундов хеширования и задерживать пользователя максимум на одну секунду.

Для проверки пробного пароля или кодовой фразы обычно требуется одна операция хеширования. Но если использовалось растяжение ключа, злоумышленнику придется вычислить усиленный ключ для каждого проверяемого ключа, а это означает, что за один тест необходимо вычислить 65 000 хешей. Это увеличивает рабочую нагрузку злоумышленника в 65 000 раз, примерно в 2 раза. ¹⁶, что означает, что расширенный ключ имеет дополнительную силу ключа примерно на 16 бит.

Закон Мура утверждает, что скорость компьютера удваивается примерно каждые 2 года. Согласно этому предположению, каждые 2 года еще один бит прочности ключа, вероятно, будет перебором. Это означает, что 16 дополнительных бит прочности стоят примерно 16 × 2 = 32 года взлома, но это также означает, что количество раундов растяжения ключей, которые использует система, должно удваиваться примерно каждые 2 года, чтобы поддерживать тот же уровень безопасности (поскольку большинство ключей более безопасны, чем необходимо, системы, требующие последовательной детерминированной генерации ключей, скорее всего, не будут обновлять количество итераций, используемых при расширении ключей. В таком случае разработчику следует учитывать, как долго, по его мнению, будет работать система получения ключей. неизменен и должен выбрать подходящее количество хэшей на протяжении всего срока службы системы).

Хэш-функции, привязанные к процессору, по-прежнему уязвимы для аппаратных реализаций . Такие реализации SHA-1 существуют, используя всего лишь 5000 вентилей и 400 тактов. ^[6] Поскольку многомиллионные вентильные FPGA стоят менее 100 долларов, ^[7] Злоумышленник может создать полностью развернутый аппаратный взломщик примерно за 5000 долларов. ^{[ нужна ссылка ]} Такая конструкция с тактовой частотой 100 МГц может тестировать около 300 000 ключей в секунду. Злоумышленник может выбрать хороший компромисс между ценой и скоростью, например, вариант со скоростью 150 000 ключей в секунду за 2500 долларов США. ^{[ нужна ссылка ]} Растяжение ключа все равно замедляет атакующего в такой ситуации; проект стоимостью 5000 долларов, атакующий прямой хэш SHA-1, сможет попробовать 300 000÷2 ¹⁶ ≈ 4,578 клавиш/секунду. ^{[ нужна ссылка ]}

Точно так же современные потребительские графические процессоры могут значительно ускорить хеширование. Например, в тесте Nvidia RTX 2080 SUPER FE вычисляет более 10 миллиардов хэшей SHA1 в секунду. ^[8]

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

История

Первая намеренно медленная функция получения ключей на основе пароля «CRYPT» была описана в 1978 году Робертом Моррисом для шифрования паролей Unix . ^[9] он использовал число итераций 25, 12-битную соль и вариант DES В качестве подфункции . (Собственно DES избегали в попытке сорвать атаки с использованием стандартного оборудования DES.) Пароли были ограничены максимум восемью символами ASCII . Хотя для своего времени это было большим достижением, CRYPT(3) сейчас считается неадекватным. Число итераций, разработанное для эпохи PDP-11 , слишком мало, 12 бит соли доставляют неудобства, но не останавливают заранее рассчитанные атаки по словарю, а ограничение в восемь символов не позволяет использовать более сильные парольные фразы .

Современные функции получения ключей на основе пароля, такие как PBKDF2 , используют криптографический хеш, например SHA-2 , более длинную соль (например, 64 бита) и большое количество итераций. Национальный институт стандартов и технологий США (NIST) рекомендует минимальное количество итераций 10 000. ^[10]^: 5.1.1.2 «Для особенно важных ключей или для очень мощных систем или систем, где производительность, воспринимаемая пользователем, не имеет решающего значения, может быть подходящим количество итераций в 10 000 000». ^[11]^: 5.2

В 2009 году был представлен алгоритм усиления ключей с интенсивным использованием памяти, scrypt , с целью ограничить использование специального высокопараллельного оборудования для ускорения тестирования ключей. ^[12]

В 2013 году был проведен конкурс по хэшированию паролей с целью выбора улучшенного стандарта растяжения ключей, который будет противостоять атакам со стороны графических процессоров и оборудования специального назначения. Победитель, Argon2 , был выбран 1 июля 2015 года. ^[13]

Некоторые системы, использующие растяжение клавиш

Некоторые, но не все программы шифрования дисков (см. сравнение программ шифрования дисков )
7-Zip ^[14]
Apache .htpasswd «APR1» и OpenSSL «passwd» используют 1000 раундов растяжения ключа MD5 .
KeePass и KeePassXC — с открытым исходным кодом утилиты управления паролями . По состоянию на 2020 год последняя версия использует Argon2d с задержкой растяжения клавиши по умолчанию в 1 секунду. ^[15]^[16]
Linux и некоторые другие Unix-подобные системы предлагают режимы SHAcrypt, которые по умолчанию выполняют 5000 итераций хэша SHA256 или SHA512, минимум 1000 и максимум 999 999 999. ^[17]
Password Safe . с открытым исходным кодом Менеджер паролей
PGP , программа шифрования GPG . GPG по умолчанию повторяет хеш 65536 раз. ^[18]
Wi-Fi Protected Access Протокол шифрования беспроводной сети (WPA и WPA2) в персональном режиме использовал PBKDF2 с 4096 итерациями. (WPA3 использует одновременную аутентификацию равных , которая утверждает, что не раскрывает хэши паролей.)

См. также

Функция получения ключа – часто использует растяжение ключа.
- PBKDF2 , bcrypt , scrypt , Argon2 — широко используемые алгоритмы растяжения ключей.
Хэш-цепочка

Ссылки

^ Jump up to: ^а ^б ^с Келси, Джон; Шнайер, Брюс; Холл, Крис; Вагнер, Дэвид А. (1997). «Безопасное применение ключей с низкой энтропией». В Окамото, Эйдзи; Давида, Джордж I .; Мамбо, Масахиро (ред.). Информационная безопасность, Первый международный семинар, ISW '97, Тацунокучи, Япония, 17-19 сентября 1997 г., Материалы . Конспекты лекций по информатике. Том. 1396. Спрингер. стр. 121–134. дои : 10.1007/BFb0030415 . ISBN 978-3-540-64382-1 .
^ Рейнхольд, Арнольд (15 июля 1999 г.). «HEKS: семейство алгоритмов растяжения ключей» (PDF) .
^ Макмиллан, Трой (7 июля 2022 г.). Руководство по сертификации CompTIA Advanced Security Practitioner (CASP+) CAS-004 . Сертификация Pearson IT. ISBN 978-0-13-734870-1 .
^ crypt(3) – FreeBSD функциям библиотеки Руководство по
^ Мориарти, Кэтлин (2017). «PKCS #5: Спецификация шифрования на основе пароля, версия 2.1» .
^ О'Нил, Мэр. «Недорогая архитектура хэш-функции SHA-1 для RFID-тегов» (PDF) . Архивировано из оригинала (PDF) 19 марта 2012 г.
^ «Новые 90-нм FPGA Xilinx Spartan-3 меняют ландшафт полупроводников (0333): Пресс-релизы Xilinx» . Архивировано из оригинала 16 июля 2011 г. Проверено 8 августа 2010 г.
^ https://gist.github.com/epixoip/47098d25f171ec1808b519615be1b90d , PBKDF2-HMAC-SHA1 с 1000 итерациями стоит 2002 хеша SHA-1 со скоростью 5 164,9 кГц/с, что составляет 10 340 129 800 SHA- 1 хеш в секунду.
^ Моррис, Роберт; Томпсон, Кен (3 апреля 1978 г.). «Безопасность паролем: история болезни» . Лаборатории Белла . Архивировано из оригинала 22 марта 2003 г. Проверено 9 мая 2011 г.
^ Грасси Пол А. (июнь 2017 г.). SP 800-63B-3 – Рекомендации по цифровой идентификации, аутентификации и управлению жизненным циклом . НИСТ. doi : 10.6028/NIST.SP.800-63b .
^ Мельтем Сёнмез Туран, Элейн Баркер, Уильям Берр и Лили Чен (декабрь 2010 г.). SP 800-132 – Рекомендации по получению ключей на основе пароля, Часть 1: Приложения хранения . НИСТ. дои : 10.6028/NIST.SP.800-132 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Персиваль, Колин (2009). scrypt: новая функция получения ключей . BSDCan 2009. Архивировано из оригинала 29 июня 2024 г.
^ Конкурс хеширования паролей
^ «Формат 7z» .
^ КБДФ 4
^ KeePassXC — Создание вашей первой базы данных
^ Дреппер, Ульрих. «Шифрование Unix с использованием SHA-256 и SHA-512» .
^ RFC 4880

[ISW97-1] Jump up to: ^а ^б ^с Келси, Джон; Шнайер, Брюс; Холл, Крис; Вагнер, Дэвид А. (1997). «Безопасное применение ключей с низкой энтропией». В Окамото, Эйдзи; Давида, Джордж I .; Мамбо, Масахиро (ред.). Информационная безопасность, Первый международный семинар, ISW '97, Тацунокучи, Япония, 17-19 сентября 1997 г., Материалы . Конспекты лекций по информатике. Том. 1396. Спрингер. стр. 121–134. дои : 10.1007/BFb0030415 . ISBN 978-3-540-64382-1 .

[2] Рейнхольд, Арнольд (15 июля 1999 г.). «HEKS: семейство алгоритмов растяжения ключей» (PDF) .

[3] Макмиллан, Трой (7 июля 2022 г.). Руководство по сертификации CompTIA Advanced Security Practitioner (CASP+) CAS-004 . Сертификация Pearson IT. ISBN 978-0-13-734870-1 .

[4] crypt(3) – FreeBSD функциям библиотеки Руководство по

[5] Мориарти, Кэтлин (2017). «PKCS #5: Спецификация шифрования на основе пароля, версия 2.1» .

[6] О'Нил, Мэр. «Недорогая архитектура хэш-функции SHA-1 для RFID-тегов» (PDF) . Архивировано из оригинала (PDF) 19 марта 2012 г.

[7] «Новые 90-нм FPGA Xilinx Spartan-3 меняют ландшафт полупроводников (0333): Пресс-релизы Xilinx» . Архивировано из оригинала 16 июля 2011 г. Проверено 8 августа 2010 г.

[8] ttps://gist.github.com/epixoip/47098d25f171ec1808b519615be1b90d , PBKDF2-HMAC-SHA1 с 1000 итерациями стоит 2002 хеша SHA-1 со скоростью 5 164,9 кГц/с, что составляет 10 340 129 800 SHA- 1 хеш в секунду.

[9] Моррис, Роберт; Томпсон, Кен (3 апреля 1978 г.). «Безопасность паролем: история болезни» . Лаборатории Белла . Архивировано из оригинала 22 марта 2003 г. Проверено 9 мая 2011 г.

[sp800-63B-10] Грасси Пол А. (июнь 2017 г.). SP 800-63B-3 – Рекомендации по цифровой идентификации, аутентификации и управлению жизненным циклом . НИСТ. doi : 10.6028/NIST.SP.800-63b .

[sp800-132-11] Мельтем Сёнмез Туран, Элейн Баркер, Уильям Берр и Лили Чен (декабрь 2010 г.). SP 800-132 – Рекомендации по получению ключей на основе пароля, Часть 1: Приложения хранения . НИСТ. дои : 10.6028/NIST.SP.800-132 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[12] Персиваль, Колин (2009). scrypt: новая функция получения ключей . BSDCan 2009. Архивировано из оригинала 29 июня 2024 г.

[13] Конкурс хеширования паролей

[14] «Формат 7z» .

[15] КБДФ 4

[16] KeePassXC — Создание вашей первой базы данных

[shacryptcode-17] Дреппер, Ульрих. «Шифрование Unix с использованием SHA-256 и SHA-512» .

[18] RFC 4880

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]