Lyra2

Lyra2 – это функция формирования ключа, также называемая схемой хэширования паролей, которая получила особое признание во время конкурса хэширования паролей в июле 2015 года. Алгоритм Lyra2 был разработан Маркосом Симплисио младшим, Леонардо К. Алмейда, Эвертоном Р. Андраде, Паулу К. Ф. Сантушем и Паулу С. Л. М. Баррето из Политехнической школы Университета Сан-Паулу.

Содержание

Обзор алгоритма Lyra2

Lyra2 является улучшением первой версии алгоритма Lyra, который был предложен ранее теми же авторами. Lyra2 сохраняет безопасность, эффективность и гибкость своего предшественника, в том числе: возможность настроить желаемый объем памяти, время обработки и параллелизм, которые будут использоваться алгоритмом, а также способность обеспечить высокое использование памяти со временем обработки, аналогичным полученному в алгоритме Scrypt. Кроме того, Лира2 приносит значительные улучшения по сравнению с предшественником:

  • Lyra2 повышает уровень безопасности в точках нападения;
  • позволяет законным пользователям более эффективно использовать возможности параллелизма для своих собственных платформ;
  • Лира2 включает в себя настройки для увеличения затрат, связанных с построением выделенного оборудования (пр. FPGA) для атаки на алгоритм;
  • поддерживает сопротивление против угроз и нападений сторон-канала полагаясь на более дешевых (и, следовательно, более медленных) запоминающих устройствах.

Lyra2 выпущен под общественным владением и предоставляет два основных расширения:

  • Lyra2-δ, дает потребителю более лучшее управление над использованием ширины полосы частот алгоритма;
  • Lyra2 «p», использует возможности параллелизма на платформе пользователя.

Этот алгоритм позволяет параметризировать:

  • время выполнения (затраты времени T);
  • требуемую память (количество строк R и количество столбцов C);
  • степень параллелизма (количество потоков p);
  • основная функция перестановки (может рассматриваться как основной криптографический примитив);
  • число блоков, используемых базовой функцией перестановки (bitrate));
  • количество раундов, выполненных для базовой функции перестановки (rho);
  • количество бит, используемых при вращении (omega);
  • выходная длина (kappa).

Алгоритм Lyra2 на сегодняшний день используется в майнинге лишь как составляющая других современных алгоритмов, таких как Lyra2Rev2. Также, существуют майнинг пулы и монеты, которые работают на современных версиях Lyra2.

Устойчивость Lyra2

  • Высокая устойчивость к пересчетам памяти: оценочные затраты на обработку атак с низким использованием памяти включают фактор, который растет экспоненциально с затратами времени из-за пересчетов;
  • Затраты памяти и времени в Lyra2 могут быть разделены, что позволяет точно настроить использование ресурсов;
  • Быстрое использование сокращенной круглой sponge-функции в ядре алгоритма;
  • Дизайн Лира2 сочетает в себе устойчивость к атакам боковых каналов (на протяжении всего этапа настройки) и атакам с использованием дешевых (следовательно, низкоскоростных) устройств памяти, балансируя эти противоречивые требования;
  • Lyra2 рассматривает более широкий диапазон конфигураций для защиты от атакующих платформ при оптимизации выполнения на легитимной платформе, таких как:
    • Поддержка параллелизма для многоядерных платформ, не давая много преимуществ для GPU-атак;
    • Возможность использования различных базовых sponge-функций в зависимости от целевой платформы (например, Blake2b для реализаций программного обеспечения; Keccak для аппаратных реализаций; BlaMka для дополнительного сопротивления аппаратным платформам и т.д.);
    • Возможность увеличить использование пропускной способности памяти алгоритма.

Дизайн

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

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

Строительство и визуализация матрицы осуществляется с помощью комбинации состояния поглощающего, сжимая и дублирование операций, лежащих в основе губки (то есть, его внутреннее состояние не сбрасывается в ноль), обеспечивающие последовательный характер всего процесса.

Кроме того, количество раз, когда ячейки матрицы пересматриваются после инициализации, определяется пользователем, что позволяет точно настраивать время выполнения Lyra2 в соответствии с ресурсами целевой платформы. Подробные код на языке Python по реализации алгоритма Lyra2 можно найти на английской версии данной статьи по ссылке: https://en.bitcoinwiki.org/wiki/Lyra2.

Производительность

Lyra2 майнер – Лира2

На рисунке показано время обработки, полученное с помощью одноядерной реализации SSE Lyra2.

Эта цифра была извлечена и очень похожа на результаты сторонних тестов.

Результаты изображены соответствуют среднему времени выполнения Lyra2, настроенного по параметрам C=256, rho=1, b=768 бит (т. е. внутреннее состояние имеет 256 бит), и различных параметров T и R, дающие общее представление о возможных сочетаниях параметров и соответствующее использование ресурсов.

Как показано на рисунке, Lyra2 способен выполнить за менее 1 секунду при использовании до 400 МБ (при R = 2^{14} и T=5) или до 1 ГБ памяти (при R approx 4.2cdot10^{4} and T=1); или менее чем за 5 секунд до 1,6 ГБ (с R = 2^{16} и T=6).

Все тесты проводились на Intel Xeon E5-2430 (2,20 ГГц с 12 ядрами, 64 бита), оснащенном 48 ГБ DRAM, под управлением Ubuntu 14.04 LTS 64 бит, а исходный код был скомпилирован с использованием gcc (GNU Compiler Collection) 4.9.2.

См. также на BitcoinWiki