ISAAC

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

ISAAC (Indirection, Shift, Accumulate, Add and Count) — генератор псевдослучайных чисел, разработанный в 1996 году Робертом Дж. Дженкинсом младшим, как развитие разработанных им же алгоритмов IA и IBAA. Этот генератор относят к разряду криптостойких генераторов псевдослучайных чисел, хотя полное и строгое доказательство проведено не было.

История создания

[править | править код]

Американский программист Роберт Джон Дженкинс младший в 1993 году поступил в Беркли, чтобы получить там степень доктора в области теоретической информатики, после окончания Университета Карнеги-Меллон в 1989 году и четырёх лет работы в Oracle. Несмотря на то, что учёба в Беркли стала серьёзным испытанием для Дженкинса — ему пришлось бросить её уже через год — именно здесь он начал свою работу по изучению генераторов псевдослучайных чисел в рамках курса Мануэля Блюма по криптографии. В июле 1993 года Дженкинс стал экспериментировать с псевдослучайными числами для процессоров Intel 486 и уже к апрелю 1994 был разработан ISAAC. Правда, статья, описывающая его работу, была опубликована лишь спустя два года, в феврале 1996 года.[1]

Предшественники ISAAC

[править | править код]

Алгоритм шифрования RC4[2][3] состоит из двух этапов: генерации псевдослучайной последовательности битов и побитового суммирования по модулю два этой последовательности с открытым текстом.

На этапе генерации псевдослучайной последовательности важную роль играет n — размер S-блока, массива данных, который фактически определяет внутреннее состояние RC4. Также в RC4 используются следующие переменные: i и j — итераторы, пробегающие значений, массив Key длины length, в котором специальным образом хранится ключ, и массив S (он же S-блок). Выходные данные: массив z — псевдослучайная последовательность.

Рассмотрим алгоритм на примере n = 8. Сначала массив S заполняется числами от 0 до , массив Key — последовательностью n-битовых слов. Если длина ключа меньше длины S, то последовательность повторяется, пока её длина не станет равна . Затем алгоритм работает следующим образом:

i = 0; j = 0;
пока i < 256 //256 = 2^n
j = (j + S[i] + Key[i mod length]) mod 256;
поменять местами S[i] и S[j];
i++;

После этого этапа — этапа инициализации — следует этап собственно генерации псевдослучайной последовательности:

i = 0; j = 0;
пока i < 256 
j = (j + S[i]) mod 256;
поменять местами S[i] и S[j];
z[i] = S[(S[i] + S[j]) mod 256];
i++;

На выходе получается последовательность длины n, с помощью которой шифруется потом открытый текст.

IA (Indirection, Addition) — алгоритм, который был разработан Дженкинсом таким образом, чтобы он мог удовлетворять следующим требованиям[4]:

  • невозможность получения внутреннего состояния по имеющимся выходным результатам;
  • легко запоминающийся код;
  • наибольшая возможная скорость;

Входные данные алгоритма IA: массив S, состоящий из элементов от 0 до , случайным образом распределённых по массиву, итераторы i и j. Массив выходных данных z — результат работы алгоритма. Также значения ячеек в массиве — то есть длины слов — должны быть больше, чем бит, Дженкинс в своих работах берёт K = 32 бит — именно такой длины слова используются во всех описываемых здесь алгоритмах.

IBAA (Indirection, Barrelshift, Accumulate and Add) — алгоритм, созданный Дженкинсом на основе IA. Автор полагает наличие следующих преимуществ у IBAA в дополнение к преимуществам, уже имеющимся у IA[5]:

  • Схематичное описание работы алгоритма IBAA
  • Криптографическая защищённость
  • По всей длине цикла не должны обнаруживаться смещения
  • Короткие циклы должны встречаться невероятно редко

В отличие от RC4 и IA, работа IBAA основана на циклических сдвигах битовых данных влево. В реализации IBAA используется тот же набор переменных, что и в IA, с той лишь разницей, что добавляются аккумуляторы a и b, а также barrelshift function — функция, осуществляющая упомянутый выше циклический сдвиг.

barrel(j) — сдвигает циклически в массиве из 32 бит все биты влево на 19 бит. Также это можно задать формулой , где

 — побитовый XOR

Под операцией >> здесь подразумевается арифметический сдвиг вправо.

ISAAC (Indirection, Shift, Accumulate, Add and Count) — алгоритм псевдослучайных чисел, принцип работы которого труднее запомнить, чем принципы работы IA и IBAA, зато он имеет по сравнению с ними целый ряд преимуществ[6]. При проектировании ISAAC к нему был предъявлен следующий список требований:

  • криптографическая стойкость;
  • невозможность получения внутреннего состояния по имеющимся выходным результатам;
  • отсутствие коротких циклов;
  • отсутствие каких-либо тенденций в распределении бит на всем цикле;
  • упорядоченные состояния должны быстро становиться хаотичными.

В отличие от большинства генераторов псевдослучайных чисел, в основе работы которых лежат потоковые шифры, ISAAC разработан без использования линейных регистров сдвига с обратной связью.

Среднее количество машинных инструкций, требуемых для получения 32-битного значения — 18,75. 64-битная версия ISAAC (ISAAC-64) требует 19 инструкций для получения одного 64-битного значения.

Алгоритм работы

[править | править код]

Так же, как и в предыдущих алгоритмах, в ISAAC есть массив S, определяющий внутреннее состояние системы, так же состоящий из случайно расположенных в массиве элементов от 0 до длины K бит, итератор i и три переменные a, b и c, отвечающие за предыдущие состояния генератора, массив выходных данных z той же длины, что и S. Однако помимо этих переменных здесь вводятся также переменные , которые определяют значение функции, зависящей от обоих итераторов:

.

В своей статье Дженкинс полагает .

Схема работы генератора на произвольном шаге при n = 8, K = 32 выглядит следующим образом:

c = c + 1;
b = b + c;
i = 0;
пока i < 255
x = S[i];
a = f(a, i) + S[i + 128 mod 256];
S[i] = a + b + S[x>>2 mod 256];
z[i] = x + S[S[i]>>10 mod 256];
b = z[i];
i++;

Криптоанализ ISAAC

[править | править код]

На своём персональном сайте автор ISAAC объявил конкурс на взлом генератора — первый, кто сможет указать число, использованное в качестве зерна (англ. seed) для генерации первых 2560 значений, выдаваемых генератором, получит от Дженкинса приз в 1000$. Однако пока с этой задачей никто не смог справиться. Тем не менее, ISAAC был рассмотрен в работах ряда криптоаналитиков.

Атака Пудовкиной

[править | править код]

В 2001 году была опубликована статья[7], в которой Марина Пудовкина описывала атаку, основанную на открытых текстах, с помощью которой можно найти начальное состояние генератора по небольшому сегменту выходных данных, а также давала точную оценку сложности такой атаки. При помощи описанного в статье алгоритма, Пудовкиной удалось снизить сложность взлома до , в то время как сложность полного перебора [8]. По её расчётам, при сложность взлома полным перебором равна , в то время как с помощью алгоритма Пудовкиной это число могло быть уменьшено до . Такая сложность, тем не менее, всё ещё слишком большая, чтобы можно было назвать ISAAC уязвимым генератором псевдослучайных чисел, резюмирует в своей статье криптоаналитик.

Анализ Жана-Филиппа Омассона

[править | править код]

В своей работе[9] 2006 года Омассон описывает четыре множества «слабых» начальных состояний , которые могут пересекаться между собой. Слабыми считаются такие состояния, для которых часть элементов случайны, а остальные элементы равны одному и тому же значению. Если  — начальное состояние, то можно определить с помощью соотношения: , тогда определяется как , множество  — как , в то время как задаётся следующим образом: . Автор рассматривал алгоритм ISAAC при тех же значениях, которые даны выше (то есть n = 8, K = 32) и вычислил для каждого из множеств число слабых состояний. Для это число составило состояний, для  — состояний, для  — , же является подмножеством . Наличие таких состояний ещё не говорит о том, что ISAAC можно легко взломать, однако они — потенциальные слабые места алгоритма, поэтому Омассон предложил модифицированную версию ISAAC — ISAAC+[10].

На вход на некотором шаге подаются те же, что и в ISAAC, числа a, b и c, массив S, составленный из 256 32-битных слов, на выходе — массив z той же размерности, что и S. В описании функции вместо логических битовых сдвигов >> и << используются циклические >>> и <<<, то есть применяется функция

Также поменялся способ инициации S[i] и z[i] на каждом шаге — в обоих случаях используется побитовый XOR. То есть вместо

S[i] = a + b + S[x>>2 mod 256];
z[i] = x + S[S[i]>>10 mod 256];

в ISAAC+ используется:

S[i] = a ⊕ b + S[x>>>2 mod 256];
z[i] = x + a ⊕ S[S[i]>>>10 mod 256];

Атака Пола-Прэнила. Критика

[править | править код]

В том же 2006 году Пол и Прэнил опубликовали статью[11], в которой изучали атаку распознавания (англ. distinguishing attack) на некоторые потоковые RC4-подобные генераторы, в том числе IA и ISAAC. В своей работе они показывают, что сложность взлома ISAAC составляет всего [12]. Омассон не оставил без внимания эту атаку[13] и указал на ошибочность инициации алгоритма Полом и Пренилом, из-за которой и появилась возможность так сильно уменьшить сложность его взлома.

Применение

[править | править код]

Многие реализации ISAAC работают достаточно быстро и надежно, поэтому этот генератор псевдослучайных чисел стал довольно распространённым. ISAAC используется, например, в Unix-утилите shred (Unix)[англ.][14] для зашифровки переписанных данных. Генератор случайных чисел на основе ISAAC реализован в одной из наиболее распространённых математических библиотек Java — Apache Commons Math[15].

Примечания

[править | править код]
  1. Краткая автобиография Роберта Дженкинса. burtleburtle.net. Дата обращения: 25 ноября 2016. Архивировано 9 августа 2016 года.
  2. Шнайер Б., 2002, с. 236.
  3. Пол Г., Сабэмой М., 2001, с. 16—19.
  4. Дженкинс Р. Дж., 1996, с. 41, 42-43.
  5. Дженкинс Р. Дж., 1996, с. 41, 43-45.
  6. Дженкинс Р. Дж., 1996, с. 41, 46-49.
  7. Пудовкина М. А., 2001.
  8. Пудовкина М. А., 2001, с. 9.
  9. Омассон Ж. Ф., 2006.
  10. Омассон Ж. Ф., 2006, с. 5.
  11. Пол С., Прэнил Б., 2006.
  12. Пол С., Прэнил Б., 2006, с. 9—10.
  13. Омассон Ж. Ф., 2006, с. 6.
  14. GNU coreutils git. Дата обращения: 3 декабря 2016. Архивировано 21 сентября 2019 года.
  15. Apache Common Math docs. Дата обращения: 3 декабря 2016. Архивировано 22 апреля 2017 года.

Литература

[править | править код]
  • Шнайер Б. RC4 // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 236. — 816 с. — ISBN 5-89392-055-4.
  • Пол Г., Сабэмой М. Потоковый шифр RC4 // Потоковый шифр RC4 и его варианты = RC4 Stream Cipher and Its Variants. — Бока-Ратон: CRC Press, 2001. — С. 16—19. — 285 с.
  • Дженкинс Р. Дж. ISAAC (англ.) // Lecture Notes in Computer Science. — Fast Software Encryption, 1996. — Vol. 1039. — P. 41—49.
  • Пудовкина М. А. A known plaintext attack on the ISAAC keystream generator (англ.). — IACR ePrint Archive, 2001.
  • Пол С., Прэнил Б. On the (in)security of stream ciphers based on arrays and modular addition (англ.) // Advances in Cryptology – Asiacrypt 2006. — Asiacrypt, 2006.
  • Омассон Ж. Ф. On the pseudo-random generator ISAAC (англ.). — IACR ePrint Archive, 2006.