14.01 // Lyra – новая функция получения ключа из пароля
Функции получения ключей из паролей (Password Based Key Derivated Functions) позволяют из произвольной строки пароля получить псевдослучайный ключ с равномерным плоским статистическим распределением. Впоследствии такой ключ может использоваться в различных протоколах.
Поскольку пароль имеет невысокую энтропию и подвержен атакам по словарю, то для замедления его подбора часто используют добавление т.н. фиктивной или вычислительной энтропии. Для этого используется три принципа:
- Использование уникальной соли, которая добавляется к паролю. «Соль» — это случайное, уникальное, но несекретное значение, целью которого служит затруднение составления хэш-отпечатков заранее просчитанных словарей паролей в виде т.н. радужных таблиц.
- Использование многократного хэширования. Обычно пароль хэшируют столько раз, сколько требуется на целевой платформе, чтобы затратить время, равное одной секунде. Т.о. образом, на схожей платформе противнику потребуется затратить по одной секунде на проверку каждого кандидата на пароль. К сожалению, специализированное железо, специально адаптированное к параллельным вычислениям, делает такую меру малоэффективной, позволяя подбирать пароль намного быстрее, чем на процессорах универсального назначения.
- Использование сравнительно большого расхода памяти. Хотя специализированные схемы для параллельного подбора пароля могут быть созданы при сравнительно небольших финансовых затратах по сравнению с выигрышем скорости, это не так для схем, оснащаемых большим количеством памяти, что делает создание последних экономически невыгодным.
Из числа наиболее известных наиболее современной функцией, выполняющей п. 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.
Впоследствии такой ключ может
Логическая ошибка. «Если A, то B» означает «B верно, если верно A». В данном случае факт высокой и потому неокупаемой цены на оснащение системы большим числом памяти никак не связан с тем фактом, что для параллельного подбора пароля специализированное железо эффективно. Сказанное не отменяет того, что такие обороты в ходу, на слуху и все ими пользуются. Однако, в научных текстах они неприемлемы, это грубая ошибка. Правильнее сказать так: «Хотя специализированные схемы для параллельного подбора пароля могут быть созданы при сравнительно небольших финансовых затратах по сравнению с выигрышем скорости, это не так для схем, оснащаемых большим количеством памяти, что делает создание последних экономически невыгодным.»
Запятая после «известных» ненужна.
Диапазон чисел записывается через дефис, насколько я знаю, а не через тире, причём слитно с цифрами.
Правый причастный оборот, запятой справа не хватает.
После «алгоритмов» не хватает доветочия.
Русский язык — не английский. Уточнение географического положения через запятую — грубое нарушение правил. Если уточнения вставляются, они пишутся в скобках: «из политехнической школы Университета Сан-Паулу (Бразилия) предложили...».
После «неудивительно» требуется запятая, т.к. это простые предложения «(оно) неудивительно» и «один ... является» в сложном.
исключаетуменьшает вероятность ошибки в реализации.[readability + искажение смысла]
У «пожалуй» роль вводного слова, с обеих сторон запятыми отделяйте.
экспоненциальных затрат памяти (а не квадратичных, как в Scrypt)
[readаbility + gramma]
Через пробел вроде нужно, да? Список прилагательных русского языка, которые должны писаться через дефис, строго регалментирован законами Розенталя.
«Числа памяти» не существует, поэтому перед «памяти» надо добавить «количеств{ом,о}».
комментариев: 9796 документов: 488 редакций: 5664
Само собой.
Новость не для практических рекомендаций. Просто иллюстрация того, что современным PBKDF ещё есть куда стремиться, указано интересное направление для реализации изменений и ещё раз показано, что Sponge будут всё больше появляться в самых неожиданных областях и конструкциях. Даже если f-Keccak поломают, то сама Sponge — это третье по значимости изобретение в разработке примитивов симметричной криптографии после сети Файстеля и SP-сети.
Грамматика пофиксена, спасибо.
комментариев: 9796 документов: 488 редакций: 5664
Походу, да.
Убрал из новости упоминание о связи с авторством. Paulo S. L. M. Barreto действительно много публиковался с разработчиками Keccak, в т.ч. и в исследованиях по хэш-функциям, но официальным соавтором Keccak он не являлся.
комментариев: 9796 документов: 488 редакций: 5664
Это ваши фантазии или реальность? Где об этом почитать?
ASIC как таковой для scrypt выпустить нельзя, но можно просто наставить чипов на плату и сильно оптимизировать энергопотребление. Колоссального разрыва в производительности не будет, как для sha2, но, мне кажется, этим много кто затарится. Эти уже сделали прототип и все их места в предзаказе уже заняли. Обещают примерно через полгода доставить устройства. Самое печальное, что а scrypt-форков расплодили немерено, и они сейчас наиболее прибыльны для рядого добытчика с видеокартами. Если вспомнить, что litecoin задумывался именно с упором на невозможность создания специальных железяк, можно предположить, что появится еще-что, например scrypt с подстраивающимся параметром, отвечающим за потребление памяти, или другая функция.
Ага, для этого тоже создаются специальные форки. Например, накидать в кучу 6 произвольных хэш-функций, как это сделано в quarkcoin – и до сих пор никто не написал вменяемого майнера для видеокарт. Но у них другая проблема – собрать ферму из ЦП сложнее и дороже, чем из видеокарт, а имея ботнет (или будучи администратором чего-нибудь), можно иметь очень большой % мощности сети. Особенно важно в начале, если нет пулов и все майнят соло – тогда все блоки будет забирать ботнет. И в целом, защищенность сети падает, потому что любой суперкомпьютер из TOP-100 сможет провести атаку 51%.
Вот лучше объясните, зачем под пароли городить отдельную хэш-функцию и почему недостаточно, например, обычной SHA-3?
комментариев: 9796 документов: 488 редакций: 5664
Можно обойтись и SHA-3. Правда, в паре с AES.
комментариев: 9796 документов: 488 редакций: 5664
Подразумевается, что практически никто из пользователей 128-битный (а тем более 256-битный) пароль использовать не будет и это надо как-то компенсировать фиктивной вычислительной энтропией — попыткой замедлить перебор разными методами.
> owerflow как следствие, вопрос снят :)
комментариев: 9796 документов: 488 редакций: 5664
Побочный эффект этих исследований — замедление возможности создания спецжелеза для майнинга криптовалют и преодоления других протоколов, где используется концепция "proof of work", за счёт внедрения "proof of computational work with memory".