ISAAC

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

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

История создания[править | править вики-текст]

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

Предшественники ISAAC[править | править вики-текст]

RC4[править | править вики-текст]

Алгоритм шифрования 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;
пока 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 (Inderection, Addition) - алгоритм[4], который был разработан Дженкинсом таким образом, чтобы он мог удовлетворять следующим требованиям:

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

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

Для n = 8 схема работы алгоритма такова:

j = 0;
i = 0;
пока i < 256 // 256 = 2^n
x = S[i];
y = S[x mod 256] + j;
S[i] = y;
j = S[y>>8 mod 256] + x; 
z[i] = j;
i++;

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

IBAA[править | править вики-текст]

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

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

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

Для случая n = 8 реализация алгоритма показана ниже:

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

- побитовый XOR

i = 0;
пока i < 256 // 256 = 2^n
x = S[i];
j = barrel(j) + S[(i + 128) mod 256];
y = S[x mod 256] + j + b;
S[i] = y;
b = S[(y>>8) mod 256] + x;
z[i] = b;
i++;

ISAAC[править | править вики-текст]

Описание[править | править вики-текст]

ISAAC (Inderection, 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 объявил конкурс[7] на взлом генератора - первый, кто сможет указать число, использованное в качестве зерна (англ. seed) для генерации первых 2560 значений, выдаваемых генератором, получит от Дженкинса приз в 1000$. Однако пока с этой задачей никто не смог справиться. Тем не менее, ISAAC был рассмотрен в работах ряда криптоаналитиков.

Атака Пудовкиной[править | править вики-текст]

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

Анализ Жана-Филиппа Омассона[править | править вики-текст]

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

ISAAC+[править | править вики-текст]

На вход на некотором шаге подаются те же, что и в 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 году Пол и Прэнил опубликовали статью[10], в которой изучали атаку распознавания (англ. distinguishing attack) на некоторые потоковые RC4-подобные генераторы, в том числе IA и ISAAC. В своей работе они показывают, что сложность взлома ISAAC составляет всего . Омассон не оставил без внимания эту атаку[9] и указал на ошибочность инициации алгоритма Полом и Пренилом, из-за которой и появилась возможность так сильно уменьшить сложность его взлома.

Применение[править | править вики-текст]

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

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

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