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

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Алгоритм тысячелистника»  – Новости  · газеты  · книги  · ученый  · JSTOR (Ноябрь 2015) (Узнайте, как и когда удалить этот шаблон сообщения)

В Алгоритм тысячелистника это семья криптографические генераторы псевдослучайных чисел (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 использует трехклавишный Тройной DES в режиме счетчика для генерации выходных данных. C является п-значение счетчика битов; K это ключ. Чтобы сгенерировать следующий выходной блок, Ярроу следует функциям, показанным здесь.

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

Пересесть

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

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

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

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

Эта секция в список формат, но может читаться лучше как проза. Вы можете помочь преобразование этого раздела, при необходимости. Помощь при редактировании доступен. (Ноябрь 2015)

Плюсы

• Тысячелистник повторно использует существующие строительные блоки.
• По сравнению с предыдущими ГПСЧ 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]

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

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

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