Американский программист Роберт Джон Дженкинс младший в 1993 году поступил в Беркли, чтобы получить там степень доктора в области теоретической информатики, после окончания Университета Карнеги-Меллон в 1989 году и четырёх лет работы в Oracle. Несмотря на то, что учёба в Беркли стала серьёзным испытанием для Дженкинса — ему пришлось бросить её уже через год — именно здесь он начал свою работу по изучению генераторов псевдослучайных чисел в рамках курса Мануэля Блюма по криптографии. В июле 1993 года Дженкинс стал экспериментировать с псевдослучайными числами для процессоров Intel 486 и уже к апрелю 1994 был разработан ISAAC. Правда, статья, описывающая его работу, была опубликована лишь спустя два года, в феврале 1996 года.[1]
Предшественники ISAAC
RC4
Шаблон:CatmainАлгоритм шифрования RC4Шаблон:SfnШаблон:Sfn состоит из двух этапов: генерации псевдослучайной последовательности битов и побитового суммирования по модулю два этой последовательности с открытым текстом.
На этапе генерации псевдослучайной последовательности важную роль играет n — размер S-блока, массива данных, который фактически определяет внутреннее состояние RC4. Также в RC4 используются следующие переменные: i и j — итераторы, пробегающие <math>2^n</math>значений, массив Key длины length, в котором специальным образом хранится ключ, и массив S (он же S-блок). Выходные данные: массив z — псевдослучайная последовательность.
Рассмотрим алгоритм на примере n = 8. Сначала массив S заполняется числами от 0 до <math>2^n-1</math>, массив Key — последовательностью n-битовых слов. Если длина ключа меньше длины S, то последовательность повторяется, пока её длина не станет равна <math>2^n</math>. Затем алгоритм работает следующим образом:
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
IA (Indirection, Addition) — алгоритм, который был разработан Дженкинсом таким образом, чтобы он мог удовлетворять следующим требованиямШаблон:Sfn:
невозможность получения внутреннего состояния по имеющимся выходным результатам;
легко запоминающийся код;
наибольшая возможная скорость;
Входные данные алгоритма IA: массив S, состоящий из <math>2^n</math> элементов от 0 до <math>2^n-1</math>, случайным образом распределённых по массиву, итераторы i и j. Массив выходных данных z — результат работы алгоритма. Также значения ячеек в массиве — то есть длины слов — должны быть больше, чем <math>2*n</math> бит, Дженкинс в своих работах берёт K = 32 бит — именно такой длины слова используются во всех описываемых здесь алгоритмах.
IBAA
IBAA (Indirection, Barrelshift, Accumulate and Add) — алгоритм, созданный Дженкинсом на основе IA. Автор полагает наличие следующих преимуществ у IBAA в дополнение к преимуществам, уже имеющимся у IAШаблон:Sfn:
По всей длине цикла не должны обнаруживаться смещения
Короткие циклы должны встречаться невероятно редко
В отличие от RC4 и IA, работа IBAA основана на циклических сдвигах битовых данных влево. В реализации IBAA используется тот же набор переменных, что и в IA, с той лишь разницей, что добавляются аккумуляторы a и b, а также barrelshift function — функция, осуществляющая упомянутый выше циклический сдвиг.
barrel(j) — сдвигает циклически в массиве из 32 бит все биты влево на 19 бит. Также это можно задать формулой <math>(j<<19)\oplus(j>>13)</math> , где
ISAAC (Indirection, Shift, Accumulate, Add and Count) — алгоритм псевдослучайных чисел, принцип работы которого труднее запомнить, чем принципы работы IA и IBAA, зато он имеет по сравнению с ними целый ряд преимуществШаблон:Sfn. При проектировании ISAAC к нему был предъявлен следующий список требований:
невозможность получения внутреннего состояния по имеющимся выходным результатам;
отсутствие коротких циклов;
отсутствие каких-либо тенденций в распределении бит на всем цикле;
упорядоченные состояния должны быстро становиться хаотичными.
В отличие от большинства генераторов псевдослучайных чисел, в основе работы которых лежат потоковые шифры, ISAAC разработан без использования линейных регистров сдвига с обратной связью.
Среднее количество машинных инструкций, требуемых для получения 32-битного значения — 18,75. 64-битная версия ISAAC (ISAAC-64) требует 19 инструкций для получения одного 64-битного значения.
Алгоритм работы
Так же, как и в предыдущих алгоритмах, в ISAAC есть массив S, определяющий внутреннее состояние системы, так же состоящий из случайно расположенных в массиве <math>2^n</math> элементов от 0 до <math>2^n-1</math> длины K бит, итератор i и три переменные a, b и c, отвечающие за предыдущие состояния генератора, массив выходных данных z той же длины, что и S. Однако помимо этих переменных здесь вводятся также переменные <math>p_0, p_1, p_2, p_3</math>, которые определяют значение функции, зависящей от обоих итераторов:
<math>f(a, i) = \begin{cases} a<<p_0, & \text{if }i\equiv0\text{ mod 4} \\ a>>p_1, & \text{if }i\equiv1\text{ mod 4} \\ a<<p_2, & \text{if }i\equiv2\text{ mod 4} \\ a>>p_3, & \text{if }i\equiv3\text{ mod 4} \end{cases}</math>.
В своей статье Дженкинс полагает <math>p_0 = 13, p_1 = 6, p_2 = 2, p_3 = 16</math>.
Схема работы генератора на произвольном шаге при 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 году была опубликована статьяШаблон:Sfn, в которой Марина Пудовкина описывала атаку, основанную на открытых текстах, с помощью которой можно найти начальное состояние генератора по небольшому сегменту выходных данных, а также давала точную оценку сложности такой атаки. При помощи описанного в статье алгоритма, Пудовкиной удалось снизить сложность взлома до <math>T_{met} = 2^{(2n+\theta_2)(m-1)}(K-2n-\theta_2)\frac{2}{3}m</math>, в то время как сложность полного перебора <math>T_{br} = 2^{Km-1}</math>Шаблон:Sfn. По её расчётам, при <math>m=256, n=8, K=32, p_\theta=13, p_1=6, p_2=2, p_3=16, \theta_1=\theta_2=2</math>сложность взлома полным перебором равна <math>T_{br} = 5.91*10^{2446}</math>, в то время как с помощью алгоритма Пудовкиной это число могло быть уменьшено до <math>T_{met} = 4.67*10^{1240}</math> . Такая сложность, тем не менее, всё ещё слишком большая, чтобы можно было назвать ISAAC уязвимым генератором псевдослучайных чисел, резюмирует в своей статье криптоаналитик.
Анализ Жана-Филиппа Омассона
В своей работеШаблон:Sfn 2006 года Омассон описывает четыре множества «слабых» начальных состояний <math>W_1, W_2, W_3, W_4</math>, которые могут пересекаться между собой. Слабыми считаются такие состояния, для которых часть элементов случайны, а остальные элементы равны одному и тому же значению. Если <math>\alpha</math> — начальное состояние, то <math>W_1</math> можно определить с помощью соотношения: <math>\alpha \in W_1 \Longleftrightarrow \alpha_0 = \alpha_1</math>, тогда <math>W_2</math> определяется как <math>\alpha \in W_2 \Longleftrightarrow \exists N \in \{2,...,256\}, \exists X \in \{0,...,2^{32} - 1\}, \alpha_0 = X, \{0 < i < 256, \alpha_i = X\} = N - 1</math>, множество <math>W_3</math> — как <math>\alpha \in W_3 \Longleftrightarrow \exists N \in \{2,...,256\}, \exists X \in \{0,...,2^{32} - 1\},\forall i \in \{0,...,N - 1\}, \alpha_i = X</math>, в то время как <math>W_4</math> задаётся следующим образом: <math>\alpha \in W_4 \Longleftrightarrow \exists X \in \{0,...,2^{32} - 1\}, \forall i \in \{0,...,255\}, \alpha_i = X</math>. Автор рассматривал алгоритм ISAAC при тех же значениях, которые даны выше (то есть n = 8, K = 32) и вычислил для каждого из множеств число слабых состояний. Для <math>W_1</math> это число составило <math>2^{8160}</math>состояний, для <math>W_2</math> — <math>2^{8167,99}</math> состояний, для <math>W_4</math> — <math>2^{32}</math>, <math>W_3</math> же является подмножеством <math>W_2</math>. Наличие таких состояний ещё не говорит о том, что ISAAC можно легко взломать, однако они — потенциальные слабые места алгоритма, поэтому Омассон предложил модифицированную версию ISAAC — ISAAC+Шаблон:Sfn.
ISAAC+
На вход на некотором шаге подаются те же, что и в ISAAC, числа a, b и c, массив S, составленный из 256 32-битных слов, на выходе — массив z той же размерности, что и S. В описании функции <math>f(a, i)</math> вместо логических битовых сдвигов >> и << используются циклические >>> и <<<, то есть применяется функция
<math>f'(a, i) = \begin{cases} a<<<p_0, & \text{if }i\equiv0\text{ mod 4} \\ a>>>p_1, & \text{if }i\equiv1\text{ mod 4} \\ a<<<p_2, & \text{if }i\equiv2\text{ mod 4} \\ a>>>p_3, & \text{if }i\equiv3\text{ mod 4} \end{cases}</math>
Также поменялся способ инициации 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 году Пол и Прэнил опубликовали статьюШаблон:Sfn, в которой изучали атаку распознавания (англ.distinguishing attack) на некоторые потоковые RC4-подобные генераторы, в том числе IA и ISAAC. В своей работе они показывают, что сложность взлома ISAAC составляет всего <math>T \approx 2^{17}</math>Шаблон:Sfn. Омассон не оставил без внимания эту атакуШаблон:Sfn и указал на ошибочность инициации алгоритма Полом и Пренилом, из-за которой и появилась возможность так сильно уменьшить сложность его взлома.
Применение
Многие реализации ISAAC работают достаточно быстро и надежно, поэтому этот генератор псевдослучайных чисел стал довольно распространённым. ISAAC используется, например, в Unix-утилите Шаблон:Iw[2] для зашифровки переписанных данных. Генератор случайных чисел на основе ISAAC реализован в одной из наиболее распространённых математических библиотек Java — Apache Commons Math[3].
