id: Гость   вход   регистрация
текущее время 18:23 28/03/2024
Владелец: unknown (создано 14/01/2014 14:53), редакция от 05/02/2014 11:42 (автор: unknown) Печать
Категории: криптография, алгоритмы, протоколы
http://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.


 
— Зануда (15/01/2014 00:37)   <#>
Спасибо за новость, но как-то даже сказать нечего. Нужно, чтобы функцию проанализировали другие, чтобы она устоялась как стандарт, а только потом рекомендовать для использования.




Впоследствии такой ключ может


Логическая ошибка. «Если A, то B» означает «B верно, если верно A». В данном случае факт высокой и потому неокупаемой цены на оснащение системы большим числом памяти никак не связан с тем фактом, что для параллельного подбора пароля специализированное железо эффективно. Сказанное не отменяет того, что такие обороты в ходу, на слуху и все ими пользуются. Однако, в научных текстах они неприемлемы, это грубая ошибка. Правильнее сказать так: «Хотя специализированные схемы для параллельного подбора пароля могут быть созданы при сравнительно небольших финансовых затратах по сравнению с выигрышем скорости, это не так для схем, оснащаемых большим количеством памяти, что делает создание последних экономически невыгодным.»


Запятая после «известных» ненужна.


Диапазон чисел записывается через дефис, насколько я знаю, а не через тире, причём слитно с цифрами.


Правый причастный оборот, запятой справа не хватает.


После «алгоритмов» не хватает доветочия.


Русский язык — не английский. Уточнение географического положения через запятую — грубое нарушение правил. Если уточнения вставляются, они пишутся в скобках: «из политехнической школы Университета Сан-Паулу (Бразилия) предложили...».


После «неудивительно» требуется запятая, т.к. это простые предложения «(оно) неудивительно» и «один ... является» в сложном.


[readability + искажение смысла]


У «пожалуй» роль вводного слова, с обеих сторон запятыми отделяйте.


экспоненциальных затрат памяти (а не квадратичных, как в Scrypt)
[readаbility + gramma]


Через пробел вроде нужно, да? Список прилагательных русского языка, которые должны писаться через дефис, строго регалментирован законами Розенталя.



«Числа памяти» не существует, поэтому перед «памяти» надо добавить «количеств{ом,о}».
— unknown (15/01/2014 10:02, исправлен 15/01/2014 10:03)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Нужно, чтобы функцию проанализировали другие, чтобы она устоялась как стандарт, а только потом рекомендовать для использования.

Само собой.


Новость не для практических рекомендаций. Просто иллюстрация того, что современным PBKDF ещё есть куда стремиться, указано интересное направление для реализации изменений и ещё раз показано, что Sponge будут всё больше появляться в самых неожиданных областях и конструкциях. Даже если f-Keccak поломают, то сама Sponge — это третье по значимости изобретение в разработке примитивов симметричной криптографии после сети Файстеля и SP-сети.


Грамматика пофиксена, спасибо.

— Гость (15/01/2014 10:50)   <#>
Походу народ к PHC готовится
— unknown (19/01/2014 19:09)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Походу, да.

Функция Lyra основана на конструкции Sponge, что неудивительно, т.к. один из авторов работы является разработчиком алгоритма Keccak (см. «Хэш-функция Keccak и конструкция Sponge как универсальный криптопримитив» и «Перспективные режимы Sponge-шифрования»).


Убрал из новости упоминание о связи с авторством. Paulo S. L. M. Barreto действительно много публиковался с разработчиками Keccak, в т.ч. и в исследованиях по хэш-функциям, но официальным соавтором Keccak он не являлся.
— Гость (19/01/2014 22:08)   <#>
Хм. Скоро выйдут специализированные устройства для майнинга scrypt-криптовалют и потом появятся Lyra-валюты.
— unknown (20/01/2014 00:56)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Если криптовалюты будут создавать на таких новых функциях, то разрабатывать спецжелезо для майнинга будет всё сложнее и малоэффективнее и будет возврат к майнингу на обычных процах.
— Гость (20/01/2014 02:25)   <#>

Это ваши фантазии или реальность? Где об этом почитать?
— Гость (20/01/2014 10:37)   <#>
Это ваши фантазии или реальность? Где об этом почитать?

ASIC как таковой для scrypt выпустить нельзя, но можно просто наставить чипов на плату и сильно оптимизировать энергопотребление. Колоссального разрыва в производительности не будет, как для sha2, но, мне кажется, этим много кто затарится. Эти уже сделали прототип и все их места в предзаказе уже заняли. Обещают примерно через полгода доставить устройства. Самое печальное, что
This device can perform proof-of-work (hashing) for all Scrypt based coins.
а scrypt-форков расплодили немерено, и они сейчас наиболее прибыльны для рядого добытчика с видеокартами. Если вспомнить, что litecoin задумывался именно с упором на невозможность создания специальных железяк, можно предположить, что появится еще-что, например scrypt с подстраивающимся параметром, отвечающим за потребление памяти, или другая функция.

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

Ага, для этого тоже создаются специальные форки. Например, накидать в кучу 6 произвольных хэш-функций, как это сделано в quarkcoin – и до сих пор никто не написал вменяемого майнера для видеокарт. Но у них другая проблема – собрать ферму из ЦП сложнее и дороже, чем из видеокарт, а имея ботнет (или будучи администратором чего-нибудь), можно иметь очень большой % мощности сети. Особенно важно в начале, если нет пулов и все майнят соло – тогда все блоки будет забирать ботнет. И в целом, защищенность сети падает, потому что любой суперкомпьютер из TOP-100 сможет провести атаку 51%.
— Гость (21/01/2014 16:43)   <#>
Эти уже сделали прототип
С прототипом это вы погорячились, там пока только фантазии, впрочем как и здесь
Вот лучше объясните, зачем под пароли городить отдельную хэш-функцию и почему недостаточно, например, обычной SHA-3?
— unknown (21/01/2014 16:59, исправлен 21/01/2014 17:00)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Можно обойтись и SHA-3. Правда, в паре с AES.

— Гость (21/01/2014 17:17)   <#>
Можно обойтись и SHA-3. Правда, в паре с AES.
Тогда надо переформулировать вопрос. Чем в принципе обосновано существование такого класса криптографических преобразований, как "Функции получения ключей из паролей (Password Based Key Derivated Functions)", позволяющих "из произвольной строки пароля получить псевдослучайный ключ с равномерным плоским статистическим распределением". Почему в случае с паролями недостаточно одной-единственной SHA-3, сертифицированной NIST и рассмотренной под микроскопом за много лет?
— unknown (21/01/2014 17:21, исправлен 21/01/2014 17:23)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Подразумевается, что практически никто из пользователей 128-битный (а тем более 256-битный) пароль использовать не будет и это надо как-то компенсировать фиктивной вычислительной энтропией — попыткой замедлить перебор разными методами.

— Гость (21/01/2014 17:22)   <#>
2 unknown: конец рабочего дня
> owerflow как следствие, вопрос снят :)
— unknown (21/01/2014 17:25, исправлен 21/01/2014 17:26)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Побочный эффект этих исследований — замедление возможности создания спецжелеза для майнинга криптовалют и преодоления других протоколов, где используется концепция "proof of work", за счёт внедрения "proof of computational work with memory".

Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3