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

Алгоритм Ярроу (англ. Yarrow algorithm) — криптографически стойкий генератор псевдослучайных чисел. В качестве названия выбран тысячелистник, засушенные стебли которого служат источником энтропии при гадании^[1].

Алгоритм разработан в августе

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

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

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

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

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

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

Алгоритм Ярроу состоит из 4 независимых частей^[7]:

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

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

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

Чтобы сгенерировать новый

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

Механизм генерации дает на выходе последовательность псевдослучайных чисел. Она должна быть такой, чтобы злоумышленник, не знающий ключа генератора, не смог отличить её от случайной последовательности бит^{[англ.][14]}.

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

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

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

По мере поступления выборок в каждый пул^[англ.] сохраняются оценки энтропии для каждого источника. Как только эта оценка для любого источника достигает предельного значения, происходит усложнение из быстрого пула. В подавляющей части систем это случается множество раз в час. Усложнение из медленного пула происходит, когда оценки для любых ${\displaystyle k}$ из ${\displaystyle n}$ источников в медленном пуле превышают пороговую отметку^[17].

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

Одной из возможных реализаций алгоритма Ярроу является Ярроу-160. Основная идея этого алгоритма — использование односторонней хеш-функции ${\displaystyle h()}$ и блочного шифра ${\displaystyle E_{K}()}$

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

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

В Ярроу-160 используется алгоритм SHA-1 в качестве ${\displaystyle h()}$^[19].

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

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

В Ярроу-160 используется алгоритм 3-KEY Triple DES в качестве ${\displaystyle E_{K}()}$^[19].

Генератор основан на использовании блочного шифра в режиме счётчика (см. рис. 2)^[23].

Имеется n-битное значение счётчика ${\displaystyle C}$. Для генерации следующих ${\displaystyle n}$-бит

${\displaystyle C}$

${\displaystyle K}$

${\displaystyle C\leftarrow (C+1){\bmod {2}}^{n}}$

${\displaystyle R\leftarrow E_{K}(C)}$

где ${\displaystyle R}$ — выход

${\displaystyle K}$

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

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

В Ярроу-160 ${\displaystyle P_{g}}$ равняется 10. Данный параметр специально задается низким значением, чтобы минимизировать количество выходов, которые можно узнать при помощи атаки перебора с возвратом (англ. Backtracking)^[25].

Время выполнения механизма усложнения зависит от параметра ${\displaystyle P_{t}\geq 0}$. Этот параметр может быть зафиксирован или изменяться динамически^[26].

Данный механизм состоит из следующих шагов^[26]:

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

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

${\displaystyle s_{0}:=m}$

${\displaystyle s_{i}:=h(s_{0}|\ldots |s_{i-1}),\ \ {\text{где}}\ \ i=1,\ldots }$

${\displaystyle h^{'}(m,k):={\text{первые}}\ \ k\ \ {\text{бит}}\;(s_{0}|s_{1}|\ldots )}$

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

Установка нового значения в счётчик ${\displaystyle C}$ выполняется не из соображений безопасности, а для обеспечения большей гибкости реализации и поддержки совместимости между различными реализациями^[26].

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

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

В планах на будущее у создателей использование нового

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

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

• Щербаков, Л. Ю., Домашев, А. В. Прикладная криптография. Использование и синтез криптографических интерфейсов. — Русская Редакция, 2003. — 416 с. — ISBN 5-7502-0215-1.
• Фергюсон, Н., Шнайер, Б. Практическая криптография. — Издательский дом “Вильямс”, 2004. — 432 с. — ISBN 5–8459–0733–0.

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

• Shneier, B. Applied Cryptography. — John Wiley & Sons, 1996. — 784 с. — ISBN 978-1-119-09672-6.
• Agnew G. Random Sources for Cryptographic Systems (англ.) // Advances in Cryptology — EUROCRYPT '87: Workshop on the Theory and Application of Cryptographic Techniques Amsterdam, The Netherlands, April 13–15, 1987 Proceedings / D. Chaum, W. L. Price — Springer Science+Business Media, 1988. — P. 77—81. — 316 p. — ISBN 978-3-540-19102-5 — doi:10.1007/3-540-39118-5_8
• Kelsey J., Schneier B., Wagner D. A., Hall C. Cryptanalytic Attacks on Pseudorandom Number Generators (англ.) // Fast Software Encryption: 5th International Workshop, FSE’ 98 Paris, France, March 23–25, 1998 Proceedings / S. Vaudenay — Berlin, Heidelberg, New York City, London: Springer Berlin Heidelberg, 1998. — P. 168—188. — (Lecture Notes in Computer Science; Vol. 1372) — ISBN 978-3-540-64265-7 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-69710-1_12
• Kelsey J., Schneier B., Ferguson N. Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator (англ.) // Selected Areas in Cryptography: 6th Annual International Workshop, SAC’99 Kingston, Ontario, Canada, August 9–10, 1999 Proceedings / H. M. Heys, C. Adams — Berlin, Heidelberg, New York City, London: Springer Berlin Heidelberg, 2000. — P. 13—33. — (Lecture Notes in Computer Science; Vol. 1758) — ISBN 978-3-540-67185-5 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-46513-8_2
• Murray, Mark R. V. An Implementation of the Yarrow PRNG for FreeBSD // BSDC'02 Proceedings of the BSD Conference 2002 on BSD Conference. — USENIX, 2002. — С. 47—53. — ISBN 1-880446-02-2.
• Viega J. Practical Random Number Generation in Software (англ.) // 19th Annual Computer Security Applications Conference (ACSAC) 2003, 8-12 December 2003, Las Vegas, NV, (USA) — IEEE Computer Society, 2003. — P. 129—140. — ISBN 978-0-7695-2041-4 — doi:10.1109/CSAC.2003.1254318

• Yarrow — страница алгоритма на сайте Б. Шнайера (англ.)

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