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

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

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

Процесс [ править ]

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

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

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

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

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

На основе хеша [ править ]

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

Сила и время [ править ]

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

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

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

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

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

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

История [ править ]

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

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

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

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

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

Некоторые, но не все программы шифрования дисков (см. сравнение программ шифрования дисков ):

7-Zip ^[12]
Apache .htpasswd «APR1» и OpenSSL «passwd» используют 1000 раундов растяжения ключа MD5 .
KeePass и KeePassXC — с открытым исходным кодом утилиты управления паролями . По состоянию на 2020 год последняя версия использует Argon2d с задержкой растяжения клавиши по умолчанию в 1 секунду. ^[13]^[14]
Linux и некоторые другие Unix-подобные системы предлагают режимы SHAcrypt, которые по умолчанию выполняют 5000 итераций хэша SHA256 или SHA512, минимум 1000 и максимум 999 999 999. ^[15]
Password Safe . с открытым исходным кодом Менеджер паролей
PGP , программа шифрования GPG . GPG по умолчанию повторяет хеш 65536 раз. ^[16]
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 .
^ Макмиллан, Трой (7 июля 2022 г.). Руководство по сертификату CAS-004 CompTIA Advanced Security Practitioner (CASP+) . Сертификация Pearson IT. ISBN 978-0-13-734870-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: несколько имен: список авторов ( ссылка )
^ Сценарий
^ сценарий: новая функция получения ключей , Колин Персиваль , BSDCan 2009, по состоянию на 1 февраля 2011 г.
^ Конкурс хеширования паролей
^ «Формат 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] Макмиллан, Трой (7 июля 2022 г.). Руководство по сертификату CAS-004 CompTIA Advanced Security Practitioner (CASP+) . Сертификация Pearson IT. ISBN 978-0-13-734870-1 .

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

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

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

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

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

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

[9] Сценарий

[10] сценарий: новая функция получения ключей , Колин Персиваль , BSDCan 2009, по состоянию на 1 февраля 2011 г.

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

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

[13] КБДФ 4

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

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

[16] RFC 4880

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]