Шифр LEVMTHAN

Шифр разработан сотрудниками Cisco Systems D. А. McGrew и S. R. Fluhrer. Cisco Systems является мировым лидером в области сетевых технологий и ведет разработки в области аппаратного и программного обеспечения, в частности в области защиты данных. Четкая ориентация алгоритма LEVlATHAN именно на сетевые приложения станет ясна ниже. Описание алгоритма LEVlATHAN было опубликовано авторами в сети Интернет в октябре 2000 г.

Шифр разработан специально для обеспечения высокого быстродействия на процессорах общего назначения.

Описание алгоритма

LEVIATHAN- синхронный поточный шифр, в котором шифрование заключается в побитовом сложении соответствующих элементов гаммы (потока ключей) и открытого текста. Шифр имеет два параметра: n – количество битов в выходном элементе (слове) и m – количество байтов в ключе. Хотя шифр определен для всех положительных значений этих параметров, в дальнейшем изложении будем полагать, что n = 32 и либо m = 16 (для режимов с обычным уровнем безопасности (128-битный ключ), либо m = 32 (для режимов с высоким уровнем безопасности (256-битный ключ).

Поток ключей определяется набором структур типа двоичное дерево. Каждое дерево имеет высоту h = 16 и, таким образом, имеет 216листьев. Каждый лист ассоциирован с одним н-разрядным словом потока ключей. Существует 232 таких деревьев, что дает n248 выходных битов.

Каждый узел каждого дерева имеет 3n битов внутреннего состояния, состояние узла представляется переменной s. При необходимости будем использовать представление состояния узла, в котором Зп-разрядная переменная s записывается как г | у | x, т. е. старшие n разрядов переменной s имеют значение z, следующие n разрядов переменной s имеют значение у и младшие n разрядов переменной s имеют значение x. Здесь и далее x, у, z суть /г-разрядные слова. Все переменные рассматриваются как битовые строки или как беззнаковые целые в двоичном представлении с наименее значащим битом в правом разряде.

Выходные элементы последовательности гаммы – это /z-разрядные слова, причем /-e слово вычисляется по следующему алгоритму:

Предварительно необходимо определить номер дерева, к выходной последовательности которого будет принадлежать /-e слово. Номер дерева к можно определить как частное от целочисленного деления номера искомого слова на количество слов в выходной последовательности дерева.

Введем также параметр

Рис. 2.12.7. Схема преобразования с о g

Обоснование проекта

Многие генераторы ПСП поточных шифров имеют следующее ограничение: они не способны эффективно искать произвольные элементы в своей выходной последовательности. В то же время многие приложения требуют этой возможности. В коммуникационных протоколах очень часто не гарантируется, что пакеты данных доставляются в нужном порядке, либо не гарантируется, что они доставляются вообще. Таким образом, там, где возможны потеря и/или неупорядоченная передача, желательно, чтобы поточный шифр позволял бы находить соответствующий элёмент в потоке ключей, основываясь на его порядковом номере. Это свойство легло в основу поточного шифра ESP для протокола IPSecurity. Аналогичным образом при шифровании диска или защите файловой системы может использоваться поточный шифр, если этот шифр поддерживает операцию поиска. В отличие от блочных шифров, где все блоки входных данных одинаково легко вычисляются, поточные требуют возможности поиска в потоке ключей со временем поиска, которое существенно меньше времени, требующегося для генерации самого потока ключей.

Одно из возможных решений – использование линейной функции обратной связи (иначе называемой функцией обновления состояния) при шифровании в режиме Counter.

Другое решение было использовано при разработке шифра SEAL, в котором определена специальная функция поиска, которая псевдослучайно отображает индекс и исходный ключ на внутреннее состояние шифра. Такие поточные шифры позволяют искать некоторые регулярно встречающиеся позиции в своем потоке ключей. Решение, используемое в SEAL, удовлетворяет потребности многих приложений. Однако некоторые из них могут требовать возможности поиска произвольного элемента в потоке ключей. Например, зашифрованная база данных, содержащая много небольших записей, может накладывать это требование. Кроме того, использование функции поиска добавляет требования по безопасности.

Использование древовидной архитектуры в LEVlATHAN реализует возможность поиска без использования линейной функции обновления состояния и без использования специальной функции поиска.

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

Для 32-разрядных процессоров n = 32 – естественный выбор параметра. Для приложений IPSec шифр должен быть способен генерировать 232 сегментов потока ключей длиной по 216 байт. Это определяет выбор параметра h – 16. Количество выходных элементов ограничивается требованиями безопасности.

Быстродействие

Генерация потока ключей выполняется с помощыо рекурсивного прохождения, начиная с кооня дерева. Двоичное дерево высоты h содержит 2;‘ – 1 узлов, листьев играниц (здесь предполагается, что дерево с одним узлом

имеет высоту, равную 1). Каждая граница вычисляется в точности один раз при прохождении дерева. Поэтому скорость, с которой шифр генерирует ключевой поток, приблизительно равна

где– скорость, с которой может быть вычислена функция с, а– средняя скорость, с которой могут быть вычислены функции а и b.

Рекурсивное прохождение вычислительного дерева может быть эффективно реализовано с помощью организации стека из li элементов, /-й элемент которого содержит информацию о состоянии /-ro узла на пути от корня к листу, соответствующему текущему элементу выхода.

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

Каждая из функций /и g может быть вычислена за семь инструкций на процессорах общего назначения, которые способны выполнять две инструкции одновременно, используя 5 регистров (в которых хранятся x, у, г, временная переменная и указатель на таблицу замен). Таким образом, теоретическая скорость шифрования приблизительно равна (2+2×7)/32 =такта на бит ключевого потока (в случае использования двух исполнительных блоков процессора).

 

Источник: Acoсков А. В., Иванов М. A., Мирский А. A., Рузин А. В., Сланин А. В., Тютвин А. Н. Поточные шифры. – M.: КУДИЦ-ОБРАЗ, 2003. – 336 с.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100