Алгоритм Ярроу

Разработан алгоритм Ярроу, семейство генераторов криптографических псевдослучайных чисел (CPRNG) Авторы Джон Келси, Брюс Шнайер и Нильс Фергюсон, опубликовано в 1999 году. Алгоритм Ярроу явно не запатентован, не требует лицензионных отчислений и имеет открытый исходный код; для его использования не требуется лицензии. Ярроу включен в iOS и macOS для их устройств / dev / random и был в FreeBSD (где он заменен на Fortuna ).

Усовершенствованный дизайн от Фергюсона и Шнайера, Fortuna, описан в их книге «Практическая криптография», и FreeBSD теперь использует его.

• 1 Имя
• 2 Принципа
• 3 Дизайн
  • 3.1 Компоненты
  • 3.2 Философия дизайна
  • 3.3 Тысячелистник-160
    • 3.3.1 Поколение
    • 3.3.2 Reseed
    • 3.3.3 Реализация тысячелистника -160
• 4 Плюсы и минусы тысячелистника
  • 4.1 Плюсы
  • 4.2 Минусы
• 5 Ссылки
• 6 Внешние ссылки

Имя тысячелистник намекает на использование тысячелистник в случайном процессе генерации гадания И Цзин. Начиная с династии Ся (ок. 2070 - ок. 1600 г. до н.э.), китайцы использовали тысячелистник стебли для гадания. Гадалки делят набор из 50 стеблей тысячелистника на стопки и рекурсивно используют модульную арифметику для генерации двух битов случайной информации. которые имеют не- равномерное распределение.

Основными принципами дизайна Ярроу являются: устойчивость к атакам, простота использования программистами, не имеющими опыта криптографии, и возможность повторного использования существующих строительных блоков. Первые широко используемые конструкции, такие как и, имеют лазейки, которые дают возможность атаковать при определенных обстоятельствах. Некоторые из них не предназначены для реальных атак. Yarrow также стремится обеспечить легкую интеграцию, чтобы позволить разработчикам систем с небольшим знанием функциональности ГПСЧ.

Компоненты

Конструкция Ярроу состоит из четырех основных компонентов: энтропийного аккумулятора, механизма повторной засечки, механизм генерации и контроль повторного заполнения.

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

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

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

Философия проектирования

Ярроу предполагает, что может быть накоплено достаточно энтропии, чтобы гарантировать, что ГПСЧ находится в непредсказуемом состоянии. Разработчики накапливают энтропию, чтобы сохранить возможность восстановления ГПСЧ, даже если ключ скомпрометирован. Аналогичная философия проектирования используется в PRNG RSAREF, DSA и ANSI X9.17.

Ярроу-160

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

Генерация

Ярроу-160 использует трехклавишный Triple DES в режиме счетчика для генерации выходных данных. C - n-битное значение счетчика; K - это ключ. Чтобы сгенерировать следующий выходной блок, Ярроу следует функциям, показанным здесь.

Тысячелистник ведет счет выходного блока, потому что, как только ключ будет скомпрометирован, утечка старого выхода до взломанного может быть немедленно остановлена. Как только достигается некоторый системный параметр безопасности P g, алгоритм генерирует k битов вывода PRNG и использует их в качестве нового ключа. В Yarrow-160 для параметра безопасности системы установлено значение 10, что означает P g = 10. Параметр намеренно установлен на низкий уровень, чтобы минимизировать количество выходов, для которых может быть выполнено обратное отслеживание.

Reseed

Механизм повторной загрузки Yarrow-160 использует SHA-1 и Triple DES в качестве хэш-функции и блочного шифра. Подробные инструкции приведены в исходном документе.

Реализация Yarrow-160

Yarrow-160 была реализована в Java и для FreeBSD. Примеры можно найти в «Реализации Yarrow PRNG для FreeBSD» Марка Р. В. Мюррея.

Плюсы

• Тысячелистник повторно использует существующие строительные блоки.
• По сравнению с предыдущими ГПСЧ, тысячелистник достаточно эффективен.
• Тысячелистник. может использоваться программистами без опыта криптографии достаточно безопасным способом. Тысячелистник портативен и точно определяется. Интерфейс простой и понятный. Эти функции несколько снижают вероятность ошибок реализации.
• Ярроу был создан с использованием процесса проектирования, ориентированного на атаку.
• Оценка энтропии Ярроу очень консервативна, что предотвращает исчерпывающие поисковые атаки. Очень часто ГПСЧ терпят неудачу в реальных приложениях из-за завышенной оценки энтропии и угадываемых начальных точек.
• Процесс повторного заполнения Yarrow является относительно дорогостоящим с точки зрения вычислений, поэтому стоимость попытки угадать ключ ГПСЧ выше.
• Yarrow использует функции для упрощения управления исходными файлами, поэтому файлы постоянно обновляются.
• Для обработки криптоаналитических атак, Yarrow разработан на основе блока шифр, который защищен. уровень безопасности механизма генерации зависит от блочного шифра.
• Ярроу пытается избежать зависимых от данных путей выполнения. Это сделано для предотвращения атак по побочным каналам, таких как атаки по времени и анализ мощности. Это улучшение по сравнению с более ранними ГПСЧ, например RSAREF 2.0 PRNG, которые полностью развалятся, как только дополнительная информация о внутренних операциях перестанет защищаться.
• Ярроу использует криптографические хеш-функции для обработки входных выборок, а затем использует функцию безопасного обновления для объединения образцов с существующим ключом. Это гарантирует, что злоумышленник не сможет легко манипулировать входными выборками. ГПСЧ, такие как ГПСЧ RSAREF 2.0, не способны противостоять такого рода атакам с выбранным входом.
• В отличие от ГПСЧ ANSI X9.17, Ярроу может восстанавливаться после взлома ключа. Это означает, что даже если ключ скомпрометирован, злоумышленник не сможет навсегда предсказать будущие результаты. Это связано с механизмом повторного заполнения Yarrow.
• Yarrow имеет пул выборок энтропии, отделенный от ключа, и повторно устанавливает ключ только тогда, когда содержимое пула энтропии полностью непредсказуемо. Такая конструкция предотвращает атаки с итеративным угадыванием, когда злоумышленник с ключом угадывает следующий образец и проверяет результат, наблюдая за следующим выходом.

Минусы

• Поскольку выходные данные Yarrow получены криптографически, системы, использующие эти выходные данные, могут быть настолько безопасным, насколько безопасен сам механизм генерации. Это означает, что злоумышленник, который может сломать механизм генерации, легко взломает систему, которая зависит от выходных данных Yarrow. Эта проблема не может быть решена путем увеличения накопления энтропии.
• Ярроу требует оценки энтропии, что является очень большой проблемой для реализации. Трудно быть уверенным, сколько энтропии нужно собрать, прежде чем использовать ее для повторной загрузки ГПСЧ. Эта проблема решена с помощью Fortuna (PRNG), усовершенствованного Yarrow. Фортуна имеет 32 пула для сбора энтропии и полностью удалил оценщик энтропии.
• Сила Ярроу ограничена размером ключа. Например, Yarrow-160 имеет эффективный размер ключа 160 бит. Если для защиты требуется 256 бит, Ярроу-160 не сможет выполнить эту работу.
• Ярроу-160 использует SHA-1, который многие считали устаревшим из-за его первого публичного конфликта.

• Страница алгоритма Ярроу
• Ярроу-160: Заметки о конструкции и анализе генератора криптографических псевдослучайных чисел Ярроу, Дж. Келси, Б. Шнайер и Н. Фергюсон
• " Реализация Yarrow в Java "
• " Реализация Yarrow в FreeBSD "
• " Реализация PRNG Yarrow для FreeBSD "