В рубрику "Криптография" | К списку рубрик | К списку авторов | К списку публикаций
Часть работ, как это порой бывает с направлениями, ставшими вдруг "модными", оказалась просто элементарно безграмотной и содержала грубейшие ошибки, поскольку работы зачастую писались не профессиональными криптографами, а людьми, имевшими о криптографии самое поверхностное представление. Все это не могло не сказаться на "авторитете" этой тематики.
Однако в последнее время вновь наблюдается рост интереса криптографического сообщества к использованию в криптографии клеточно-автоматных моделей. Количество работ, посвященных приложению КлА к криптографии, за последние годы вновь резко выросло. Все это объясняется самой природой КлА и прежде всего свойствами параллельности и локальности. Они позволяют организовать параллельную обработку существенных порций информации с помощью достаточно скромных вычислительных ресурсов. Это соответствует современной тенденции в развитии информационных технологий, когда мы имеем дело с огромным потоком сáмой разнообразной информации из самых разных источников. Эта информация порой требует обработки в условиях весьма ограниченных вычислительных ресурсов (как то, например, смарт-карты или радиочастотные метки, имеющие выход в Интернет), что образует сферу так называемого Интернета вещей. И здесь клеточные автоматы могут найти самое широкое применение в качестве высокоскоростных и не требовательных к ресурсам шифровальных средств, если удастся в полной мере реализовать их возможности, связанные с присущим им "природным" параллелизмом вычислений.
Первые исследования в области клеточных автоматов, их свойств и возможностей их применения как генераторов псевдослучайных последовательностей (ГПСП) принадлежат С. Вольфраму и относятся к одномерным клеточным автоматам [Wol85]. Вольфрамом и рядом других авторов была рассмотрена возможность применения подобных одномерных КлА в качестве генераторов гаммы поточного шифрования.
Рассмотрим предложенный Вольфрамом ГПСП подробнее. Одномерный клеточный автомат представляет собой массив из N циклически соединенных ячеек памяти s=[m0, m1,...,mn-1], каждая из которых может принимать значения из множества Ω={0,1}. В процессе функционирования КлА все ячейки меняют свои значение синхронно и одновременно. Значение i-й ячейки на t-м такте работы будем обозначать mi(t). Тогда значение i-й ячейки на (?+1)-м такте работы определяется локальной функцией связи
где вычисление индексов осуществляются по модулю N (т.к. массив ячеек памяти "закольцован"). Вектором инициализации генератора является набор s(0) = [m0(0), m1(0),...,mn-1(0)], образованный начальным заполнением ячеек памяти.
Для формирования выходной последовательности {y(t)} генератора используется съем с одной зафиксированной ячейки: y(t) = mk(t),t = 1,2... .
Таким образом, генератор вырабатывает выходную последовательность со скоростью 1 бит за 1 такт работы.
Вольфрам рассматривал клеточные автоматы с различным числом ячеек памяти и, основываясь на эмпирических данных, пришел к выводу, что при больших значениях N большинство состояний такого автомата лежит на одном цикле длины ~2N.
Через некоторое время Мейер (Meier W.) и Стаффельбах (Staffel-bach O.) представили атаку на этот шифр [Mei91]. Для значений N<500 эта атака может быть реализована на обычном ПК в реальное время. Кроме того, Бардел (Bardell P.H.) [Bar90] доказал, что линейная сложность выходной последовательности такого генератора совпадает с числом его ячеек памяти, что также не позволяет считать данный генератор криптографически безопасным.
В последующем различными авторами было предложено много схем поточного шифрования с генератором ключевого потока на базе классического одномерного клеточного автомата. Как правило, такие генераторы демонстрируют достаточно хорошие статистические свойства и эффективную аппаратную реализацию. Тем не менее они обладают и рядом существенных недостатков, таких как:
Отметим, что практически все генераторы на базе одномерного клеточного автомата, привлекшие внимание криптоаналитиков, через некоторое время оказались взломанными (например, [Koc97], [Bla97] [Bao04]). Невзломанными, по всей видимости, остались лишь схемы, анализом которых никто, кроме самих авторов, не занимался.
В настоящее время одномерные клеточные автоматы используются в составе генератора псевдослучайных последовательностей в математическом пакете Wolfram Mathematica, разработанном компанией Wolfram Research [Ran], однако в остальном они не получили широкого распространения.
Возможность применения двумерных клеточных автоматов в качестве генераторов гаммы поточного шифрования рассматривалась в зарубежной литературе достаточно редко, в качестве примера можно привести лишь работы [Tom00], [Moh09]. Наиболее существенный вклад в развитие этого направления содержится в работах Б.М. Сухинина [Сух10а], [Сух10б], [Сух10в], [Сух10г], [Сух10д], [Сух11].
Для характеристики криптографических свойств двумерного клеточного автомата Б. Сухининым было применено понятие лавинного эффекта, введенное в 1973 г. Х. Фейстелем (Feistel H.) [Fei73] для блочных шифров. С неформальной точки зрения – это свойство преобразований, при котором небольшие изменения входных данных влекут за собой значительные изменения выходных данных. Оно играет важнейшую роль в криптографии при изучении свойств блочных шифров и хэш-функций.
В нашем случае для измерения лавинного эффекта рассматриваются два тождественных клеточных автомата A и Â. Пусть s(t) = (m1(t), m2(t), ..., mN(t)) и - внутренние состояния этих автоматов в момент времени t, где - соответствующие заполнения ячеек памяти в момент времени t, а N - число ячеек памяти в автоматах A и Â. Локальные функции связи, разумеется, также совпадают. Пусть начальные состояния s(0) и $(0) различаются в заполнении только одной ячейки, т.е. удовлетворяют условию:
В работе [Сух10в] для количественного описания лавинного эффекта в классических КлА были введены понятия интегральной и пространственной характеристик лавинного эффекта.
Интегральная характеристика лавинного эффекта η(t) [Сух11] равна отношению числа различающихся в данный момент времени одноименных ячеек к общему числу ячеек клеточного автомата:
где ∑- обычное арифметическое сложение, а ? - сложение по модулю 2.
Согласно [Сух11] интегральная характеристика лавинного эффекта ограничена сверху:
где |v| - мощность окрестности каждой ячейки (для классических КлА данные мощности равны для любой из ячеек).
В свою очередь, пространственная характеристика µ(t) показывает скорость, с которой изменения распространяются по решетке клеточного автомата.
Кроме того, в [Сух11] было введено понятие оптимального лавинного эффекта: оптимальным лавинным эффектом называется лавинный эффект, при котором изменения распространяются по решетке КлА равномерно во всех направлениях с максимально возможной скоростью, и при этом значение каждой ячейки изменяется с вероятностью 1/2.
Далее в работе [Сух11] было произведено исследование характеристик лавинного эффекта для двумерных КлА в зависимости от размера и типа выбранной окрестности (рис. 1).
Результаты этого исследования приведены на рис. 2 и 3.
В итоге для двумерных клеточных автоматов в работах [Сух10а], [Сух10б], [Сух10в], [Сух10г], [Сух10д], [Сух11] было:
Нами уже было отмечено, что клеточные автоматы имеют приложения во многих отраслях науки, таких как физика, химия, биология, информатика и т.д. В получаемых моделях удается достаточно точно воспроизводить многие природные явления, моделируя механизмы, лежащие в их основе. Однако если для большинства приложений важна регулярная структура решетки ячеек памяти, для криптографических приложений любая регулярность, как правило, ведет к снижению криптостойкости. По-видимому, это главная причина, по которой классические КлА, несмотря на многочисленные попытки, широкого применения в криптографии не нашли. Отказ от регулярной структуры для массива ячеек памяти лишает КлА некоторых преимуществ, но больше подходит для криптографических приложений, где регулярность оказывается вредной.
Как уже упоминалось выше, "… клеточные автоматы изобретались много раз под разными названиями…" [Tof87]. Обобщенный клеточный автомат впервые появился в 1969 г. в работах Стюарта Кауффмана (Kauffman S.A.) под именем "булевой сети" (Boolean Network) и предназначался для моделирования генетических процессов в биологии [Kau69], а затем был предложен в работе [Сух10а], где был назван "неоднородным клеточным автоматом" (в данной работе термин "неоднородный клеточный автомат" будет использоваться в другом смысле).
Математически обобщенный КлА можно описать следующим образом.
Пусть задан ориентированный граф G = (V,E), где V = {v1, ... vN} - множество вершин графа, E– множество дуг. Пусть δi– полустепень захода для вершины vi, при этом входящие в вершину дуги пронумерованы числами 1,…, δi. Будем считать, что с каждой вершиной vi связана ячейка памяти, содержащая булеву переменную mi, и булева функция fi (x1,...,x δi) - локальная функция связи i-й вершины.
Обобщенный клеточный автомат - это автономный автомат, его внутренним состоянием в момент времени t называется заполнение массива ячеек (m1 (t), m2(t),..., mN(t)). Функция переходов является отображением множества состояний в себя и определяет следующее состояние автомата как функцию от текущего состояния. При этом заполнение ячеек памяти обобщенного КлА описывается уравнением:
где mi(t) - состояние i-й ячейки памяти в момент времени t, n(i,j) – номер вершины, из которой исходит дуга, входящая в вершину i и имеющая номер j2.
Однородный обобщенный клеточный автомат – это обобщенный клеточный автомат, граф которого является регулярным по входу (т.е. число дуг, заходящих в вершину, – одно и то же для всех вершин) и при этом локальная функция связи для всех ячеек одинакова. В противном случае обобщенный клеточный автомат будет называться неоднородным.
Выходом однородного обобщенного КлА на шаге с номером t будем считать значения r фиксированных ячеек памяти в этот момент времени: y(t) = (mi1(t), mi2(t), ... , mir(t)). Последовательность: y(t0), y(t0 + 1), y(t0 + 2) ... образует выходную последовательностью клеточного автомата.
Переход к обобщенному клеточному автомату позволяет не только сохранить все преимущества классического КлА, но и улучшить многие его характеристики. Для обобщенного КлА выполняются следующие свойства:
При моделировании с помощью КлА природных процессов (например, в биологии) наибольший интерес представляют аттракторы – устойчивые в том или ином смысле конфигурации заполнений ячеек памяти. Основные направления исследований в этом случае сводились к поиску условий, вызывающих их появление. Так было и при изучении булевых сетей (первоначальное название обобщенных клеточных автоматов) – [Ger04], [Kau70], [Kau84], [Luc91], [Lyn93], [Lyn95], [Lyn02]. В то же время для криптографии наличие аттракторов – ситуация катастрофическая. Криптографическим идеалом является случайное равновероятное заполнение всех ячеек памяти, и основные усилия исследователей направлены на поиск условий, обеспечивающих такое предельное распределение.
Важнейшим фактором, определяющим поведение однородного обобщенного клеточного автомата, является его структура, которая полностью определяется структурой соответствующего графа. Соответственно, и криптографические свойства обобщенного клеточного автомата как преобразования, реализующего некоторую однонаправленную функцию, и свойство быть "удобно и эффективно реализуемым" так же напрямую зависят от структуры графа и свойств локальной функции связи.
Так введенные в [Сух10в] для классических клеточных автоматов интегральная и пространственная характеристики лавинного эффекта были в [Сух10д], [Клю11] перенесены на случай обобщенных клеточных автоматов. Как и в случае двумерного клеточного автомата, для определения интегральной и пространственной характеристик рассматриваются два идентичных клеточных автомата, работающих на паре начальных заполнений, различающихся в заполнении только одной ячейки. Пусть эта ячейка соответствует вершине v1 графа G, задающего наш автомат.
Интегральной характеристикой [Сух10д] называется зависящая от номера такта величина*), равная отношению числа несовпадающих значений одноименных ячеек в этих двух автоматах к числу ячеек клеточного автомата.
Пространственной характеристикой лавинного эффекта [Клю11] для обобщенного клеточного автомата называется зависимость отношения расстояния от вершины до самой дальней вершины, для которой значения соответствующих ячеек в двух автоматах не совпадают, к эксцентриситету вершины v1:
где Δ(i, j) - длина минимального пути из вершины i в вершину j, а e(i) - эксцентриситет вершины vi3.
Для обеспечения должного уровня лавинного эффекта, а также для обеспечения хороших статистических характеристик выходной последовательности необходимо, чтобы с ростом t характеристики η(t) → 1/2, а µ(t) → 1, причем желательно, чтобы приближение к указанным пределам происходило максимально быстро. Чтобы уменьшить время, необходимое для этого, следует использовать клеточный автомат, граф которого имеет как можно меньший диаметр (при заданных значениях N и δ) [Сух11].
В работе [Сух11] наряду с ГПСП на основе классических клеточных автоматов были рассмотрены ГПСП на основе обобщенных однородных клеточных автоматов. Было продемонстрировано заметное преимущество ГПСП на основе обобщенных клеточных автоматов по сравнению с классическими в быстродействии и особенно в эффективности аппаратной реализации на ПЛИС (FPGA).
Предложенный в [Сух11] ГПСЧ представляет собой два параллельно работающих обобщенных однородных клеточных автомата A1 и A2, дополненных регистром сдвига с линейной обратной связью. На каждом такте работы клеточные автоматы A1 и A2 вырабатывают по 256 бит двоичных последовательностей, которые складываются побитно, а результат сложения подается на выход генератора. Поскольку последовательности, вырабатываемые клеточными автоматами, могут рассматриваться как независимые, сложение позволяет улучшить статистические свойства выходной последовательности генератора [Сух11].
Для исследования статистических свойств генераторов был использован набор специализированных тестов, разработанный Национальным институтом стандартов и технологий США [NIST]. Набор включает в себя 15 статистических тестов и предназначен для тестирования выходных последовательностей криптографических генераторов с предъявлением наиболее жестких требований. В результате исследований, проведенных в [Сух11], были определены конкретные графы и локальные функции связи, при которых разработанные генераторы успешно проходят весь набор статистических тестов.
В ходе работы над [Сух11] были разработаны прототипы аппаратной реализации генератора псевдослучайных последовательностей на основе классических клеточных автоматов (в терминологии автора [Сух11] – ККлА) и генератора псевдослучайных последовательностей на основе обобщенных однородных клеточных автоматов (в терминологии автора [Сух11] – НКлА). Для практической реализации предложенных ГПСП была выбрана микросхема FPGA Cyclone II (EP2C35F672C6) корпорации Altera, относящаяся к семейству недорогих ПЛИС начального уровня. Основные характеристики микросхемы приведены в табл. 1.
В терминологии Altera ячейки ПЛИС называются логическими элементами (Logic Elements, LE). Каждый логический элемент микросхемы Cyclone II включает следующие основные компоненты (см. рис. 4):
Для генераторов ККлА и генераторов НКлА автором [Сух11] были построены прототипы аппаратной реализации на указанной микросхеме. Номинальное быстродействие прототипов составило 23,8 Гбит/с на тактовой частоте 100 МГц.
При этом оно может быть увеличено до 33,4 Гбит/с для генераторов ККлА и до 35,5 Гбит/с для генераторов НКлА за счет увеличения тактовой частоты работы схемы без изменения самой реализации. Основные характеристики разработанных прототипов приведены в табл. 2.
Было проведено сравнение полученных реализаций разработанных алгоритмов генерации псевдослучайных последовательностей (ККлА и НКлА) с аппаратными реализациями поточных шифров, представленных на европейский конкурс eSTREAM (как генераторов псевдослучайных последовательностей, к которым предъявляются наиболее строгие требования как по быстродействию, так и по статистическим свойствам выходных последовательностей). В число рассмотренных алгоритмов вошли как победители конкурса eSTREAM в категории "поточные шифры, ориентированные на аппаратную реализацию" (Grain, MICKEY, Trivium), так и алгоритмы, включенные в международные криптографические стандарты (все тот же Trivium) [ISO-3]. Данные о производительности и эффективности аппаратных реализаций алгоритмов взяты из работ [Rog07] и [Gur06]. Сравнение проводилось по двум показателям: абсолютному быстродействию, отражающему скорость выработки выходной последовательности на максимальной тактовой частоте, и приведенному быстродействию, показывающему скорость выработки выходной последовательности на частоте 100 МГц. Сравнение показало, что оба прототипа существенно (в несколько раз) превосходят аналоги по скорости выработки выходной последовательности (рис. 5).
Помимо быстродействия важную роль играет эффективность аппаратной реализации, которая выражается в быстродействии на единицу аппаратных ресурсов (для FPGA корпорации Altera такой единицей является логический элемент – LE). Сравнение эффективности аппаратной реализации представлено на рис. 6.
Из приведенных диаграмм видно, что по сравнению с другими алгоритмами аппаратная реализация генераторов НКлА является намного более эффективной и требует меньших аппаратных ресурсов FPGA. Эти показатели были достигнуты за счет использования обобщенных клеточных автоматов с локальной функцией связи от четырех переменных. В этом случае для реализации одной ячейки клеточного автомата потребуется всего 1 LE. Тем самым достигается оптимум по затрате логических элементов (LE) для данной микросхемы FPGA. Использование других моделей ПЛИС позволит с такой же эффективностью реализовывать обобщенные клеточные автоматы с локальной функцией связи от бóльшего числа переменных (что ведет к улучшению их криптографических свойств). Общий же вывод таков, что матрица LE является одной из наиболее удачных платформ для реализации алгоритмов на основе обобщенных клеточных автоматов.
В то же время следует отметить, что указанные конструкции предлагались исключительно в качестве генераторов псевдослучайных последовательностей и серьезный криптографический анализ предложенных ГПСП не проводился.
Литература
Опубликовано: Журнал "Information Security/ Информационная безопасность" #3, 2017