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

Алгоритм Ярроу (Шаблон:Lang-en) — криптографически стойкий генератор псевдослучайных чисел. В качестве названия выбран тысячелистник, засушенные стебли которого служат источником энтропии при гаданииШаблон:Sfn.

Алгоритм разработан в августе 1999 года Брюсом Шнайером, Джоном Келси и Нильсом Фергюсоном из компании Шаблон:Нп3Шаблон:Sfn. Алгоритм не запатентован и свободен от лицензионных отчислений, для его использования не требуется получение лицензии. Ярроу включен в феврале 2002 года в поставку FreeBSD, OpenBSD, и Mac OS X в качестве реализации устройства /dev/randomШаблон:Sfn.

Дальнейшим развитием Ярроу стало создание Фергусом и Шнайером алгоритма Fortuna, описанного в их книге «Практическая криптография»Шаблон:Sfn.

Необходимость алгоритма

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

В 1998 году создатели Ярроу провели исследования других ГПСЧ и выявили в них ряд уязвимостей. Последовательности случайных чисел, которые они давали на выходе, были небезопасными для криптографических приложений.

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

Принципы проектирования

Во время разработки алгоритма создатели заострили внимание на следующих аспектахШаблон:Sfn:

1. Быстрота и эффективность. Никто из разработчиков не будет использовать алгоритм, сильно замедляющий приложение.
2. Простота. Любой программист без особых знаний в криптографии должен суметь его безопасно использовать.
3. Оптимизация. Там, где это возможно, алгоритм должен использовать уже существующие блоки команд.

Структура алгоритма

Компоненты

Рис. 1. Общая блок-схема алгоритма Ярроу

Алгоритм Ярроу состоит из 4 независимых частейШаблон:Sfn:

1. Накопитель энтропии. Собирает выборки из источников энтропии и помещает их в два Шаблон:Нп3.
2. Механизм усложнения. Периодически усложняет ключ генератора, используя энтропию из пулов.
3. Механизм генерации. Генерирует выходные сигналы ГПСЧ из ключа.
4. Механизм управления усложнением. Определяет время выполнения усложнения.

Накопитель энтропии

Накопление энтропии (Шаблон:Lang-en) — это процесс, при котором ГПСЧ получает новое неугадываемое внутреннее состояниеШаблон:Sfn. В данном алгоритме энтропия накапливается в двух Шаблон:Нп3: быстром и медленномШаблон:Sfn. В данном контексте под пулом понимается хранилище инициализированных и готовых к использованию битов. Быстрый пул обеспечивает частые усложнения ключа. Это гарантирует, что компрометация ключа имеет невысокую продолжительность. Медленный пул обеспечивает редкие, но существенные усложнения ключа. Это необходимо для того, чтобы гарантировать получение безопасного усложнения даже в тех случаях, когда оценки энтропии сильно завышены. Входные выборки попеременно посылаются в быстрый и медленный пулыШаблон:Sfn.

Механизм усложнения

Механизм усложнения соединяет накопитель энтропии с механизмом генерации. Когда механизм управления усложнением определяет, что усложнение необходимо, то механизм усложнения, используя информацию из одного или сразу двух Шаблон:Нп3, обновляет ключ, который используется механизмом генерации. Таким образом, если злоумышленник не знает текущий ключ или пулы, то ключ будет ему неизвестен после усложнения. Также, возможно, усложнению потребуется большое количество ресурсов, чтобы минимизировать успех атаки на основе угадывания входных значенийШаблон:Sfn.

Чтобы сгенерировать новый ключ, усложнение из быстрого пула использует текущий ключ и хеши всех входов быстрого пула с момента последнего усложнения ключа. Как только это будет выполнено, Шаблон:Нп3 для быстрого пула обнулятсяШаблон:SfnШаблон:Sfn.

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

Механизм генерации

Механизм генерации дает на выходе последовательность псевдослучайных чисел. Она должна быть такой, чтобы злоумышленник, не знающий ключа генератора, не смог отличить её от Шаблон:Нп3Шаблон:Sfn.

Механизм генерации должен обладать следующими свойствамиШаблон:Sfn:

• стойкостью к криптографическим атакам;
• производительностью (Шаблон:Lang-en);
• способностью генерировать очень длинную последовательность сигналов без усложнения;
• стойкостью к атакам перебором с возвратом (Шаблон:Lang-en) после компрометации ключа.

Механизм управления усложнением

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

По мере поступления выборок в каждый Шаблон:Нп3 сохраняются оценки энтропии для каждого источника. Как только эта оценка для любого источника достигает предельного значения, происходит усложнение из быстрого пула. В подавляющей части систем это случается множество раз в час. Усложнение из медленного пула происходит, когда оценки для любых $k$ из $n$ источников в медленном пуле превышают пороговую отметкуШаблон:Sfn.

В Ярроу-160 у быстрого пула этот предел составляет 100 бит, у медленного — 160 бит. По умолчанию как минимум два различных источника в медленном пуле должны быть больше 160 бит, чтобы произошло усложнение из медленного пулаШаблон:Sfn.

Ярроу-160

Одной из возможных реализаций алгоритма Ярроу является Ярроу-160. Основная идея этого алгоритма — использование односторонней хеш-функции $h()$ и блочного шифра $E_K()$Шаблон:Sfn. Если оба алгоритма безопасны и ГПСЧ получает достаточное количество начальной энтропии, то в результате получится сильная последовательность псевдослучайных чиселШаблон:Sfn.

Хеш-функция должна обладать следующими свойствамиШаблон:Sfn:

• быть необратимой, то есть стойкой к восстановлению прообраза;
• быть стойкой к коллизиям;
• давать на выходе $m$-бит.

В Ярроу-160 используется алгоритм SHA-1 в качестве $h()$Шаблон:Sfn.

Блочный шифр должен обладать следующими свойствамиШаблон:Sfn:

• иметь ключ длиной $k$-бит и блок данных размером $n$-бит;
• быть устойчивым к открытому тексту и атакам по выбранному тексту;
• иметь хорошие статистические свойства выходных сигналов, даже при высокошаблонных входных сигналах.

В Ярроу-160 используется алгоритм 3-KEY Triple DES в качестве $E_K()$Шаблон:Sfn.

Генерация

Рис. 2. Механизм генерации

Генератор основан на использовании блочного шифра в режиме счётчика (см. рис. 2)Шаблон:Sfn.

Имеется n-битное значение счётчика $C$. Для генерации следующих $n$-бит псевдослучайной последовательности счётчик $C$ увеличивается на 1 и зашифровывается блочным шифром с использованием ключа $K$Шаблон:Sfn:

$C\leftarrow (C+1){mod2}^n$

$R\leftarrow E_K(C)$

где $R$ — выход ГПСЧ, а $K$ — текущее значение ключа.

Если в какой-то момент времени ключ оказался скомпрометирован, то необходимо предотвратить утечку предыдущих выходных значений, которые злоумышленник может получить. Данный механизм генерации не имеет защиты от атак такого рода, поэтому дополнительно подсчитывается количество выходных блоков ГПСЧ. Как только будет достигнут некоторый предел $P_g$ (Шаблон:Нп3, $1\le P_g\le 2^{n/3}$), то генерируется $k$-битовый выход ГПСЧ, который затем используется как новый ключШаблон:Sfn.

$K\leftarrow \text{следующие k бит выхода ГПСЧ}$

В Ярроу-160 $P_g$ равняется 10. Данный параметр специально задается низким значением, чтобы минимизировать количество выходов, которые можно узнать при помощи атаки перебора с возвратом (Шаблон:Lang-en)Шаблон:Sfn.

Усложнение

Время выполнения механизма усложнения зависит от параметра $P_t\ge 0$. Этот параметр может быть зафиксирован или изменяться динамическиШаблон:Sfn.

Данный механизм состоит из следующих шаговШаблон:Sfn:

1. Накопитель энтропии вычисляет хеш всех входов в быстрый Шаблон:Нп3. Результат этого вычисления обозначим $v_0$.
2. Положим $v_i:=h(v_{i-1}|v_0|i)\text{ для }i=1,\dots ,t$.
3. $K\leftarrow h^{\text{'}}(h(v_{P_t}|K),k)$.
4. $C\leftarrow E_K(0)$.
5. Сбросим все счётчики энтропии в пулах в 0.
6. Очистим память, в которой хранятся промежуточные значения.
7. Если файл прототипа (Шаблон:Lang-en) используется, то перезапишем содержимое этого файла следующими $2k$ битами выхода псевдослучайной последовательности.

Функция $h^{\text{'}}$ определяется в терминах функции $h$ следующим образомШаблон:Sfn:

$s_0:=m$

$s_i:=h(s_0|\dots |s_{i-1}),\text{где}i=1,\dots$

$h^{\text{'}}(m,k):=\text{первые}k\text{бит}(s_0|s_1|\dots )$

Фактически это функция адаптации размера, то есть она преобразует вход любой длины к выходу указанной длины. Если на вход пришло больше данных, чем ожидалось, то функция принимает ведущие биты. Если размеры входа и выхода совпадают, то функция является функцией тождественности. Если же размер данных на входе меньше ожидаемого, то дополнительные биты генерируются с помощью данной хеш-функции. Это довольно дорогой в плане вычислений алгоритм ГПСЧ, но для небольших размеров может использоваться без проблемШаблон:Sfn.

Установка нового значения в счётчик $C$ выполняется не из соображений безопасности, а для обеспечения большей гибкости реализации и поддержки совместимости между различными реализациямиШаблон:Sfn.

Нерешенные вопросы и планы

В сегодняшней реализации алгоритма Ярроу-160 размер Шаблон:Нп3 накопления энтропии ограничивается 160 битами. На алгоритм 3-KEY Triple DES известны атаки эффективнее полного перебора. Однако даже для атак перебором с возвратом ключи изменяются довольно часто, и 160 бит хватает для обеспечения безопасности на практикеШаблон:Sfn.

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

В планах на будущее у создателей использование нового стандарта блочного шифра AES. Новый блочный шифр легко сможет разместиться в базовой конструкции алгоритма Ярроу. Однако, как подчеркивают разработчики, будет необходимо или изменить хеш-функцию усложнения, или придумать новую хеш-функцию, чтобы обеспечить заполнение пула энтропии более чем 160 битами. Для AES со 128 битами это не будет проблемой, а для AES со 192 или 256 битами эту проблему придется разрешить. Следует отметить, что основная структура алгоритма Ярроу — это соединение блочного шифра AES и 256-битной хеш-функцииШаблон:Sfn.

Набор правил для механизма управления усложнением по-прежнему остается временным, тем не менее, дальнейшее изучение может улучшить его. По этой причине это является предметом постоянных исследованийШаблон:Sfn.

Литература

на русском языке

• Шаблон:Книга
• Шаблон:Книга

на английском языке

• Шаблон:Книга
• Шаблон:Source
• Шаблон:Source
• Шаблон:Source
• Шаблон:Статья
• Шаблон:Source

Ссылки

• Yarrow — страница алгоритма на сайте Б. ШнайераШаблон:Ref-en