Алгоритм Ярроу: Криптографический генератор псевдослучайных чисел.

Введение

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

Ярроу использовался в FreeBSD, но теперь заменен на Fortuna. Ярроу также был интегрирован в iOS и macOS для их устройств /dev/random, но Apple перешла на Fortuna начиная с первого квартала 2020 года.

Имя

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

Принципы

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

Компоненты

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

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

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

Поколение

Yarrow 160 использует три ключа Triple DES в режиме счетчика для генерации выходных данных. C – это n-битное значение счетчика, K – ключ. Для генерации следующего выходного блока Yarrow выполняет функции, представленные здесь. Yarrow ведет подсчет выходных блоков, поскольку, как только ключ будет скомпрометирован, утечка старых выходных данных, предшествующих скомпрометированному, может быть немедленно остановлена. Как только системный параметр безопасности Pg достигнет определенного значения, алгоритм генерирует k бит псевдослучайной последовательности (PRNG) и использует их в качестве нового ключа. В Yarrow 160 системный параметр безопасности установлен равным 10, что означает, что параметр намеренно установлен на низкое значение, чтобы минимизировать количество выходных данных, которые можно восстановить.

Пересев

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

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

Yarrow 160 был реализован на Java и для FreeBSD. Примеры можно найти в статье "Реализация ГСЧ Yarrow для FreeBSD" Марка Р. В. Мюррея.

Плюсы

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

Yarrow reuses existing building blocks. Compared to previous PRNGs, Yarrow is reasonably efficient. Yarrow can be used by programmers with no cryptography background in a reasonably secure way. Yarrow is portable and precisely defined. The interface is simple and clear. These features somewhat decrease the chances of implementation errors. Yarrow was created using an attack oriented design process. The entropy estimation of Yarrow is very conservative, thus preventing exhaustive search attacks. It is very common that PRNGs fail in real world applications due to entropy overestimation and guessable starting points. The reseeding process of Yarrow is relatively computationally expensive, thus the cost of attempting to guess the PRNG's key is higher. Yarrow uses functions to simplify the management of seed files, thus the files are constantly updated. To handle cryptanalytic attacks, Yarrow is designed to be based on a block cipher that is secured. The level of security of the generation mechanism depends on the block cipher. Yarrow tries to avoid data dependent execution paths. This is done to prevent side channel attacks such as timing attacks and power analysis. This is an improvement compared to earlier PRNGs, for example RSAREF 2.0 PRNG, that will completely fall apart once additional information about the internal operations are no longer secured. Yarrow uses cryptographic hash functions to process input samples, and then uses a secure update function to combine the samples with the existing key. This makes sure that the attacker cannot easily manipulate the input samples. PRNGs such as RSAREF 2.0 PRNG do not have the ability to resist this kind of chosen input attack. Unlike ANSI X9.17 PRNG, Yarrow has the ability to recover from a key compromise. This means that even when the key is compromised, the attacker will not be able to predict future outputs forever. This is due to the reseeding mechanism of Yarrow. However, there is no published attack that uses SHA 1 collisions to undermine Yarrow's randomness. Since the outputs of Yarrow are cryptographically derived, the systems that use those outputs can only be as secure as the generation mechanism itself. That means the attacker who can break the generation mechanism will easily break a system that depends on Yarrow's outputs. This problem cannot be solved by increasing entropy accumulation. Yarrow requires entropy estimation, which is a very big challenge for implementations. It is hard to be sure how much entropy to collect before using it to reseed the PRNG. This problem is solved by Fortuna, an improvement of Yarrow. Fortuna has 32 pools to collect entropy and removed the entropy estimator completely. Yarrow's strength is limited by the size of the key. For example, Yarrow 160 has an effective key size of 160 bits. If the security requires 256 bits, Yarrow 160 is not capable of doing the job.