Алгоритм тысячелистника - Yarrow algorithm

В Алгоритм тысячелистника это семья криптографические генераторы псевдослучайных чисел (CPRNG) разработан Джон Келси, Брюс Шнайер, и Нильс Фергюсон и опубликован в 1999 г. Алгоритм Ярроу явно не запатентован, не требует лицензионных отчислений и имеет открытый исходный код; для его использования не требуется лицензии. Улучшенный дизайн от Фергюсона и Шнайера, Фортуна, описано в их книге, Практическая криптография

Тысячелистник использовался в FreeBSD, но теперь его заменяет Фортуна.[1]. Тысячелистник также был включен в iOS[2] и macOS для них / dev / случайный устройств, но Apple перешла на Fortuna с первого квартала 2020 года.[3].

Имя

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

Принципы

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

Дизайн

Составные части

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

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

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

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

Философия дизайна

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

Тысячелистник-160

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

АлгоритмыХарактеристикиЧто использует тысячелистник-160
Хеш-функция h (x)
  • В одну сторону
  • m-битный размер вывода
  • столкновение неразрешимый

Данный M входные значения, | M | выборки выходных значений равномерно распределены по м-битовые значения.

SHA-1 хэш-функция
Блочный шифр E ()
  • Устойчивость к атакам с использованием известного и выбранного открытого текста

Высокая статистическая производительность выходных данных при наличии сильно структурированных входных данных.

Трехклавишный Тройной DES

Поколение

Функции для механизма генерации

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

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

Пересесть

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

Реализация тысячелистника-160

Тысячелистник-160 реализован в г. Ява, и для FreeBSD. Примеры можно найти в "Реализация ГПСЧ Yarrow для FreeBSD"[5] Марк Р. В. Мюррей.

Плюсы и минусы тысячелистника

Плюсы

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

Минусы

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

Рекомендации

  1. ^ "[базовая] Ревизия 284959". Svnweb.freebsd.org. Получено 18 октября 2016.
  2. ^ «Безопасность iOS» (PDF). Apple.com. Октябрь 2012 г.. Получено 2016-10-21.
  3. ^ «Генерация случайных чисел». Служба поддержки Apple. Получено 2020-10-26.
  4. ^ Шнайер, Брюс. "Вопросы и ответы о тысячелистнике". Шнайер о безопасности. Получено 2016-02-15. Гадалка делит набор из 50 стеблей на стопки, а затем многократно использует модульную арифметику для генерации двух случайных битов.
  5. ^ "Реализация ГПСЧ Yarrow для FreeBSD". Получено 18 октября 2016.
  6. ^ "Fortuna Cryptographically Secure PRNG: AN0806 - Application Note Note" (PDF). Silabs.com. Получено 2016-10-21.
  7. ^ цитадель. "Fortuna - криптографически безопасный генератор псевдослучайных чисел - CodeProject". Получено 18 октября 2016.
  8. ^ Стивенс, Марк; Бурштейн, Эли; Карпман, Пьер; Альбертини, Анж; Марков, Ярик (23.02.2017). "SHAttered". SHAttered. Получено 2017-04-27.

внешняя ссылка