id: Гость   вход   регистрация
текущее время 04:00 19/09/2019
Владелец: unknown (создано 14/01/2014 14:53), редакция от 05/02/2014 11:42 (автор: unknown) Печать
Категории: криптография, алгоритмы, протоколы
https://www.pgpru.com/Новости/2014/LyraНоваяФункцияПолученияКлючаИзПароля
создать
просмотр
редакции
ссылки

14.01 // Lyra – новая функция получения ключа из пароля


Функции получения ключей из паролей (Password Based Key Derivated Functions) позволяют из произвольной строки пароля получить псевдослучайный ключ с равномерным плоским статистическим распределением. Впоследствии такой ключ может использоваться в различных протоколах.


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


  1. Использование уникальной соли, которая добавляется к паролю. «Соль» — это случайное, уникальное, но несекретное значение, целью которого служит затруднение составления хэш-отпечатков заранее просчитанных словарей паролей в виде т.н. радужных таблиц.
  2. Использование многократного хэширования. Обычно пароль хэшируют столько раз, сколько требуется на целевой платформе, чтобы затратить время, равное одной секунде. Т.о. образом, на схожей платформе противнику потребуется затратить по одной секунде на проверку каждого кандидата на пароль. К сожалению, специализированное железо, специально адаптированное к параллельным вычислениям, делает такую меру малоэффективной, позволяя подбирать пароль намного быстрее, чем на процессорах универсального назначения.
  3. Использование сравнительно большого расхода памяти. Хотя специализированные схемы для параллельного подбора пароля могут быть созданы при сравнительно небольших финансовых затратах по сравнению с выигрышем скорости, это не так для схем, оснащаемых большим количеством памяти, что делает создание последних экономически невыгодным.

Из числа наиболее известных наиболее современной функцией, выполняющей п. 1-2, является PBKDF2, а наиболее современной функцией, выполняющей все три пункта, является Scrypt.


Однако, Scrypt также не лишён недостатков. Если адаптировать Scrypt на выполнение в железе с малым объёмом памяти, то снижение скорости будет лишь квадратично пропорциональным этому объёму. Другой недостаток Scrypt — использование одновременно двух алгоритмов: HMAC-SHA-256 и Salsa 20/8. Помимо громоздкости конструкции, есть опасения по поводу некоторых уязвимостей Salsa 20/8, которые хотя и некритичны в данной конструкции, но в перспективе такой алгоритм желательно заменить более стойким. Наконец, объём расходуемой памяти в Scrypt не может быть выделен достаточно гибким образом, чтобы избежать распараллеливания.


Исследователи Leonardo C. Almeida, Ewerton R. Andrade, Paulo S. L. M. Barreto, и Marcos A. Simplicio Jr. из политехнической школы Университета Сан-Паулу (Бразилия) предложили новый алгоритм PBKDF — Lyra. Функция Lyra основана на конструкции Sponge, лежащей в основе алгоритма Keccak (см. «Хэш-функция Keccak и конструкция Sponge как универсальный криптопримитив» и «Перспективные режимы Sponge-шифрования»). При этом, поскольку сам алгоритм Keccak оптимизирован для выполнения в «железе», в качестве бесключевой перестановки авторы предложили использовать вместо f-Keccak функцию от другого финалиста SHA-3: функцию сжатия Blake2b, неудобную для реализации в железе и плохо распараллеливаемую саму по себе.


Таким образом исследователям удалось представить простую и гибкую конструкцию на основе преобразования Duplex-Sponge, состоящую из одного криптопримитива. Ещё одним интересным свойством является затирание пароля сразу после его использования в самом алгоритме, что уменьшает ошибки в реализации.


Но, пожалуй, одним из самых интересных свойств алгоритма Lyra является строго непараллельное выполнение операций. За счёт этого авторам удалось добиться экспоненциальных затрат памяти (а не квадратичных как в Scrypt), что оставляет мало шансов разработчикам специализированного оборудования по ускоренному взлому паролей. Помимо такого жёстко консервативного решения, есть и частичные компромиссные режимы распараллеливания для легитимных пользователей на своей платформе, позволяющие выбрать максимально выигрышную стратегию между числом проводимых операций и количеством памяти: у пользователя может быть определённое число ядер и количество памяти, а в специализированном оборудовании такой баланс будет смещён к другому значению, что сделает перебор неоптимальным для противника.


Другой оптимизацией по сравнению с Scrypt является возможность рэндомизированного доступа к памяти, который является более медленным на удешевлённых специализированных устройствах. И если в Scrypt такой доступ требуется только на чтение, то в Lyra — ещё и на запись.


Исследование проведено при поддержке национального совета Бразилии по вопросам технологических и научных разработок и научно-исследовательского фонда Сан-Паулу.


В дальнейшем авторы предполагают изучение возможностей своего алгоритма на различных программных и аппаратных платформах.


Источник: Cryptology ePrint Archive: Report 2014/030, Original Publication (with minor differences): Journal of Cryptographic Engineering.


 
Много комментариев (14) [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3