ISAAC

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

История созданияПравить

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

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

RC4Править

Основная статья: RC4

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

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

Рассмотрим алгоритм на примере n = 8. Сначала массив S заполняется числами от 0 до $2^n-<!--\; -\; -->1$$2^{n}-1$ , массив Key — последовательностью n-битовых слов. Если длина ключа меньше длины S, то последовательность повторяется, пока её длина не станет равна $2^n$$2^{n}$ . Затем алгоритм работает следующим образом:

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) — алгоритм, который был разработан Дженкинсом таким образом, чтобы он мог удовлетворять следующим требованиям:

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

Входные данные алгоритма IA: массив S, состоящий из $2^n$$2^{n}$  элементов от 0 до $2^n-<!--\; -\; -->1$$2^{n}-1$ , случайным образом распределённых по массиву, итераторы i и j. Массив выходных данных z — результат работы алгоритма. Также значения ячеек в массиве — то есть длины слов — должны быть больше, чем $2\ast <!--\; \ast \; -->n$$2*n$  бит, Дженкинс в своих работах берёт K = 32 бит — именно такой длины слова используются во всех описываемых здесь алгоритмах.

IBAAПравить

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

•  

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

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

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

$\oplus <!--\; \oplus \; -->$$\oplus$  — побитовый XOR

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

ISAACПравить

ОписаниеПравить

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

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

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

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

Алгоритм работыПравить

Так же, как и в предыдущих алгоритмах, в ISAAC есть массив S, определяющий внутреннее состояние системы, так же состоящий из случайно расположенных в массиве $2^n$$2^{n}$  элементов от 0 до $2^n-<!--\; -\; -->1$$2^{n}-1$  длины K бит, итератор i и три переменные a, b и c, отвечающие за предыдущие состояния генератора, массив выходных данных z той же длины, что и S. Однако помимо этих переменных здесь вводятся также переменные $p_0,p_1,p_2,p_3$$p_{0},p_{1},p_{2},p_{3}$ , которые определяют значение функции, зависящей от обоих итераторов:

$f(a,i)={\begin{cases}a<<p_{0},&{\text{if }}i\equiv 0{\text{ mod 4}}\\a>>p_{1},&{\text{if }}i\equiv 1{\text{ mod 4}}\\a<<p_{2},&{\text{if }}i\equiv 2{\text{ mod 4}}\\a>>p_{3},&{\text{if }}i\equiv 3{\text{ mod 4}}\end{cases}}$ .

В своей статье Дженкинс полагает $p_0=13,p_1=6,p_2=2,p_3=16$$p_{0}=13,p_{1}=6,p_{2}=2,p_{3}=16$ .

Схема работы генератора на произвольном шаге при 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 году была опубликована статья, в которой Марина Пудовкина описывала атаку, основанную на открытых текстах, с помощью которой можно найти начальное состояние генератора по небольшому сегменту выходных данных, а также давала точную оценку сложности такой атаки. При помощи описанного в статье алгоритма, Пудовкиной удалось снизить сложность взлома до $T_{met}=2^{(2n+{\mathrm{\theta <!--\; \theta \; -->}}_2)(m-<!--\; -\; -->1)}(K-<!--\; -\; -->2n-<!--\; -\; -->{\mathrm{\theta <!--\; \theta \; -->}}_2)\frac{2}{3}m$$T_{met}=2^{(2n+\theta _{2})(m-1)}(K-2n-\theta _{2}){\frac {2}{3}}m$ , в то время как сложность полного перебора $T_{br}=2^{Km-<!--\; -\; -->1}$$T_{br}=2^{Km-1}$ . По её расчётам, при $m=256,n=8,K=32,p_{\mathrm{\theta <!--\; \theta \; -->}}=13,p_1=6,p_2=2,p_3=16,{\mathrm{\theta <!--\; \theta \; -->}}_1={\mathrm{\theta <!--\; \theta \; -->}}_2=2$$m=256,n=8,K=32,p_{\theta }=13,p_{1}=6,p_{2}=2,p_{3}=16,\theta _{1}=\theta _{2}=2$ сложность взлома полным перебором равна $T_{br}=5.91\ast <!--\; \ast \; -->{10}^{2446}$$T_{br}=5.91*10^{2446}$ , в то время как с помощью алгоритма Пудовкиной это число могло быть уменьшено до $T_{met}=4.67\ast <!--\; \ast \; -->{10}^{1240}$$T_{met}=4.67*10^{1240}$  . Такая сложность, тем не менее, всё ещё слишком большая, чтобы можно было назвать ISAAC уязвимым генератором псевдослучайных чисел, резюмирует в своей статье криптоаналитик.

Анализ Жана-Филиппа ОмассонаПравить

В своей работе 2006 года Омассон описывает четыре множества «слабых» начальных состояний $W_1,W_2,W_3,W_4$$W_{1},W_{2},W_{3},W_{4}$ , которые могут пересекаться между собой. Слабыми считаются такие состояния, для которых часть элементов случайны, а остальные элементы равны одному и тому же значению. Если $\mathrm{\alpha <!--\; \alpha \; -->}$$\alpha$  — начальное состояние, то $W_1$$W_{1}$  можно определить с помощью соотношения: $\mathrm{\alpha <!--\; \alpha \; -->}\in <!--\; \in \; -->W_1⟺<!--\; ⟺\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_0={\mathrm{\alpha <!--\; \alpha \; -->}}_1$$\alpha \in W_{1}\Longleftrightarrow \alpha _{0}=\alpha _{1}$ , тогда $W_2$$W_2$  определяется как $\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$ , множество $W_3$$W_{3}$  — как $\mathrm{\alpha <!--\; \alpha \; -->}\in <!--\; \in \; -->W_3⟺<!--\; ⟺\; -->\mathrm{\exists <!--\; \exists \; -->}N\in <!--\; \in \; -->\{2,...,256\},\mathrm{\exists <!--\; \exists \; -->}X\in <!--\; \in \; -->\{0,...,2^{32}-<!--\; -\; -->1\},\mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->\{0,...,N-<!--\; -\; -->1\},{\mathrm{\alpha <!--\; \alpha \; -->}}_i=X$$\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$ , в то время как $W_4$$W_{4}$  задаётся следующим образом: $\mathrm{\alpha <!--\; \alpha \; -->}\in <!--\; \in \; -->W_4⟺<!--\; ⟺\; -->\mathrm{\exists <!--\; \exists \; -->}X\in <!--\; \in \; -->\{0,...,2^{32}-<!--\; -\; -->1\},\mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->\{0,...,255\},{\mathrm{\alpha <!--\; \alpha \; -->}}_i=X$$\alpha \in W_{4}\Longleftrightarrow \exists X\in \{0,...,2^{32}-1\},\forall i\in \{0,...,255\},\alpha _{i}=X$ . Автор рассматривал алгоритм ISAAC при тех же значениях, которые даны выше (то есть n = 8, K = 32) и вычислил для каждого из множеств число слабых состояний. Для $W_1$$W_{1}$  это число составило $2^{8160}$$2^{8160}$ состояний, для $W_2$$W_2$  — $2^{8167,99}$$2^{8167,99}$  состояний, для $W_4$$W_{4}$  — $2^{32}$$2^{32}$ , $W_3$$W_{3}$  же является подмножеством $W_2$$W_2$ . Наличие таких состояний ещё не говорит о том, что ISAAC можно легко взломать, однако они — потенциальные слабые места алгоритма, поэтому Омассон предложил модифицированную версию ISAAC — ISAAC+.

ISAAC+Править

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

$f'(a,i)={\begin{cases}a<<<p_{0},&{\text{if }}i\equiv 0{\text{ mod 4}}\\a>>>p_{1},&{\text{if }}i\equiv 1{\text{ mod 4}}\\a<<<p_{2},&{\text{if }}i\equiv 2{\text{ mod 4}}\\a>>>p_{3},&{\text{if }}i\equiv 3{\text{ mod 4}}\end{cases}}$ 

Также поменялся способ инициации 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 году Пол и Прэнил опубликовали статью, в которой изучали атаку распознавания (англ. distinguishing attack) на некоторые потоковые RC4-подобные генераторы, в том числе IA и ISAAC. В своей работе они показывают, что сложность взлома ISAAC составляет всего $T\approx <!--\; \approx \; -->2^{17}$$T\approx 2^{17}$ . Омассон не оставил без внимания эту атаку и указал на ошибочность инициации алгоритма Полом и Пренилом, из-за которой и появилась возможность так сильно уменьшить сложность его взлома.

ПрименениеПравить

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

ЛитератураПравить

• Шнайер Б. 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.

СсылкиПравить

• Официальный веб-сайт проекта ISAAC
• Math::Random::ISAAC — реализация алгоритма на языке Перл
• http://guilload.com/pyisaac/ - реализация алгоритма на языке Питон
• https://rosettacode.org/wiki/The_ISAAC_Cipher - реализация алгоритма на 19 разных языках программирования