автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Оптимизация алгоритмов преобразования данных в автоматизированных системах управления информационными процессами

РОССИЙСКОЕ АГЕНТСТВО ПО СИСТЕМАМ УПРАВЛЕНИЯ Государственное унитарное предприятие Специализированный центр программных систем «Спектр»

АЛЕКСЕЕВ Леонид Евгеньевич

На правах рукописи

РГБ ОД

1 о АПР 2303

ОПТИМИЗАЦИЯ АЛГОРИТМОВ ПРЕОБРАЗОВАНИЯ ДАННЫХ В АВТОМАТИЗИРОВАННЫХ СИСТЕМАХ УПРАВЛЕНИЯ ИНФОРМАЦИОННЫМИ ПРО!ЦХСАМИ

Специальность 05.13.06 - Автоматизированные

системы управления

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата

технических наук.

Санкт-Петербург - 2000

РОССИЙСКОЕ АГЕНТСТВО ПО СИСТЕМАМ УПРАВЛЕНИЯ Государственное унитарное предприятие Специализированный центр программных систем «Спектр»

На правах рукописи

АЛЕКСЕЕВ Леонид Евгеньевич

ОПТИМИЗАЦИЯ АЛГОРИТМОВ ПРЕОБРАЗОВАНИЯ ДАННЫХ В АВТОМАТИЗИРОВАННЫХ СИСТЕМАХ УПРАВЛЕНИЯ ИНФОРМАЦИОННЫМИ ПРОЦЕССАМИ

Специальность 05.13.06 - Автоматизированные

системы управления

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата

технических наук.

Санкт-Петербург - 2000

Работа выполнена в государственном унитарном предприятии Специализированный центр программных систем «Спектр»

Научный руководитель:

кандидат физико-математических наук Молдовян H.A.

Официальные оппоненты:

Доктор технических наук профессор Сахаров В. В. Кандидат технических наук Ямалов A.B.

Ведущая организация - Государственное унитарное предприятие

Научно-исследовательский институт «Рубин»

Защита состоится <с27 »«и», /.о 2000 г. в Т-/ часов на заседании диссертационного совета Д г 116.01.03 при Санкт-Петербургском Государственном Университете водных коммуникаций по адресу: 198035, Сшпсг-Петербург, ул. Двинская д.7, к.5.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан «2? » и

2000 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

Ю. М. Кулибанов

ВВЕДЕНИЕ

Актуальность темы исследования. Ни одна сфера жизни современного общества не может функционировать без развитой информационной инфраструктуры. Национальный информационный ресурс является сегодня одним из главных источников экономической и военной мощи государства, основной предпосылкой его социально-экономического развития. В настоящее время информационная безопасность приобретает первостепенное значение во всех сферах общественной жизни - и государственной деятельности. В политической сфере можно наблюдать все большее смещение центра тяжести от силовых факторов к более скрытым и тонким, базирующимся на информационном воздействии. В экономической сфере все большее влияние оказывает уровень развития информационной инфраструктуры. Одновременно растет потенциальная уязвимость экономики по отношению к информационным воздействиям. В военном деле наметилась тенденция перехода от оружия массового уничтожения к высокоточному оружию и «информационному оружию». В области науки, техники, экологии целый ряд систем управления (транспортом, связью, атомной энергетикой экологически опасными производствами) относятся к критическим. Очевидно, недооценка вопросов информационной безопасности этих систем может привести к непредсказуемым последствиям, огромным материальным потерям и человеческим жертвам.

Широкое применение компьютерных технологий в автоматизированных системах обработки информации и управления, используемых в АСУ реального времени, а также в оборонных и коммерческой областях, привело к обострению проблемы защиты информации от несанкционированного доступа, обусловленной тем, что электронная форма представления данных обладает рядом специфических особенностей, связанных с тем, что информация не является жестко связанной с носителем, может легко и быстро копироваться и передаваться по каналам связи. Одним из важных механизмов поддержания защищенного функционирования автоматизированных систем является преобразование информации. В случае высокопроизводительных АСУ возникает проблема разработки надежных скоростных алгоритмов преобразования информации.

Вопросы оптимизации алгоритмов защиты информации приобретают все более возрастающее значение в связи со стабильными тенденциями развития современных средств вычислительной техники, характеризующихся быстрым ростом объема устройств памяти и производительности процессоров, что приводит к увеличению информационных потоков в АСУ. Важнейшими параметрами алгоритмов преобразования является стойкость и скорость преобразования. При обеспечении данного уровня стойкости увеличение скорости алгоритмов защиты информации позволяет существенно повысить производительность АСУ. Таким образом, актуальной является проблема создания скоростных алгоритмов преобразования данных

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

Известно очень большое число угроз информации, которые могут быть реализованы как со стороны внешних нарушителей, так и со стороны внутренних нарушителей. Отметим некоторые современные направления, где требуется обеспечить защиту информации циркулирующей в АСУ:

• Защита от несанкционированного чтения информации.

• Защита от навязывания ложных сообщений (умышленных и непреднамеренных).

• Идентификация законных пользователей.

• Контроль целостности информации.

• Аутентификация информации.

• Электронная цифровая подпись.

• Системы тайного электронного голосования.

• Электронная жеребьевка.

• Защита от отказа факта приема сообщения.

• Одновременное подписание контракта.

• Защита документов и ценных бумаг от подделки.

Вопросы оптимизации алгоритмов защиты информации приобретают , первостепенное значение. Широкое применение скоростных алгоритмов |. преобразования информации требует проведения оценок их стойкости. При \ этом стойкость оценивается по отношению к конкретным видам нападений.

Обоснование надежности используемых систем осуществляется I ' экспериментально путем моделирования различных видов нападений. При этом, как правило, при анализе стойкости предоставляются более благоприятные, чем на практике условия. Если в этих условиях алгоритм оказывается стойким, то он рекомендуется для данного конкретного применения.

Радикальное решение проблем защиты электронной информации может быть получено на базе использования специальных преобразований информации, которые позволяют решать важнейшие проблемы защищенной автоматизированной обработки и передачи данных. При этом современные скоростные методы преобразования данных позволяют в основном сохранить исходную производительность автоматизированных систем. Подобные преобразования данных являются наиболее эффективным средством обеспечения конфиденциальности данных, их целостности и подлинности. Только их использование в совокупности с необходимыми техническими и организационными мероприятиями могут обеспечить защиту от широкого спектра потенциальных угроз и тем самым сделать работу АСУ стабильной, не смотря на внешние воздействия.

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

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

В соответствии с поставленной целью в работе решаются следующие основпые задачи

• Разработка принципов построения скоростных и стойких алгоритмов преобразования информации в АСУ.

• Разработка методов анализа процедур преобразований информации, циркулирующей в АСУ.

• Применение разработанных методов анализа к предлагаемым алгоритмам преобразования информации.

Предмет исследования диссертации составляют скоростные алгоритмы преобразования информации, циркулирующей в АСУ.

Методы исследования. В работе использованы методы алгебры, теории чисел, дискретной математики, теории вероятностей, математической статистики, теории сложности и структурного программирования.

Научная новизна полученных в диссертации результатов заключается в следующем:

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

2. Предложены подходы к повышению скорости программных алгоритмов преобразования информации.

3. Построены скоростные алгоритмы, обладающие хорошей стойкостью.

4. Дано обоснование применения новой операции микропроцессора -управляемой перестановки, использование которой позволит резко повысить производительность про1раммных алгоритмов защиты информации в АСУ.

5. Разработан новый статистический тест для оценки цикловой структуры алгоритмов.

6. Проверены статистические свойства исследуемых алгоритмов

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

Реализация работы. Разработанные в работе методы анализа и статистические тесты были использованы при выборе алгоритмов преобразования данных в широко применяемой системе защиты информации «СПЕКТР-2». Построенные алгоритмы реализованы в виде программных модулей. Написаны программные модули, с помощью которых были проанализированы исследуемые алгоритмы преобразования данных.

Положения, выносимые на защиту.

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

2. Для повышения стойкости скоростных псевдовероятностных алгоритмов к атакам на основе подобранных текстов может быть применен "сокращенный" раунд.

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

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

5': Разработан метод оценки статистических свойств преобразованных текстов, позволяющий дать необходимую оценку стойкости алгоритмов преобразования информации циркулирующей в АСУ.

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

1. V Санкт-Петербургская международная конференция «Региональная информатика-96» Санкт-Петербург, 13-16 мая 1996 г.

2. Конференция, посвященная 100-летию Санкт-Петербургского политехнического института: «Методы и технические средства обеспечения безопасности информации». Санкт-Петербург, 28-30 октября 1997 г.

3. Научно-практическая конференция «Безопасность и экология Санкт-Петербурга». Санкт-Петербург, 11-13 марта 1999 г.

4. Межрегиональная конференция «Информационная безопасность регионов России ИБРР-99» Санкт-Петербург, 13-15 октября 1999 г.

5. Первая Международная конференция «РусКрипто 1999». Москва, Непецино, 22 - 24 декабря 1999 г..

6. Вторая Международная конференция «РусКрипто 2000». Москва, Непецино, 3-5 февраля 2000 г.

Публикации. Основные положения диссертации изложены в 9 публикациях.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

В первой главе диссертационной работы дан краткий обзор основных понятий связанных с вопросами стойкости алгоритмов преобразования информации циркулирующей в АСУ.

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

Анализ различных подходов к построению эффективной системы защиты информации, циркулирующей в АСУ и ориентированной на массовое применение показал, что принципиальной проблемой является необходимость использования скоростных программных модулей преобразования информации, обеспечивающих высокую стойкость к различным видам нападений. Попытки разработать программные модули на основе аппаратао-ориентированных алгоритмов защиты информации не могут привести к желаемому результату, поскольку наиболее известные и апробированные алгоритмы такого типа, например, DES и ГОСТ 28147-89 не позволяют осуществить скоростное преобразование программными средствами. Учитывая интенсивный характер информационных потоков в АСУ, высокую скорость считывания и записи, обеспечиваемую современными устройствами внешней памяти и необходимость предусмотреть возможность установки режима глобального преобразования данных, требуется высокая скорость преобразования данных.

Под алгоритмом преобразования информации с секретным ключом будем понимать некоторое семейство преобразований информации где параметр Z — ключ преобразования, необязательный параметр R -случайная величина, X - преобразуемая информация, Y - преобразованная информация. Для того чтобы можно было давать оценки стойкости алгоритмов защиты информации, прежде всего, необходимо сформулировать основные понятия и дать критерии стойкости. Тогда появится возможность качественного и количественного описания стойкости.

Исторически первым кто рассмотрел теоретические основы стойкости, был Шеннон. Под рабочей характеристикой W{ri) Шеннон определил среднее количество работы, необходимое для нахождения ключа на основе п знаков преобразованного текста. Наибольший интерес представляет предельное значение Ща>) которое можно рассматривать как среднюю работу, необходимую для раскрытия алгоритма при неограниченном объеме преобразованных данных. Однако практические алгоритмы обычно оцениваются с помощью величины, которую можно назвать достигнутой оценкой рабочей характеристики, W„(оо). Она определяется как среднее

7

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

При современном подходе к оценке стойкости рассматриваются следующие виды нападений

• Анализ на основе преобразованного текста.

• Анализ на основе открытого текста.

• Анализ на основе подобранного открытого текста.

• Анализ на основе подобранного преобразованного текста.

• Анализ на основе аппаратных ошибок.

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

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

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

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

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

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

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

выделенных Шенноном: рассеивание и перемешивание. Рассеиванием он назвал распространение влияния одного знака открытого текста на много знаков преобразованного текста, что позволяет скрыть статистические свойства открытого текста. Развитием этого принципа является распространение влияния одного знака ключа на много знаков преобразованного текста, что предотвращает восстановление ключа по частям. Перемешиванием Шеннон назвал использование таких преобразований, которые усложняют восстановление взаимосвязи статистических свойств открытого и преобразованного текста. Однако алгоритм преобразований должен не только затруднять раскрытие, но и обеспечивать легкость преобразований (при известном ключе). Так распространенный способ достижения рассеивания и перемешивания состоит в использовании составного алгоритма преобразований, т.е. алгоритма, который может быть реализован в виде некоторой последовательности простых процедур, каждая из которых вносит небольшой вклад в значительное суммарное рассеивание и перемешивание.

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

При создании скоростных программных алгоритмов защиты информации рекомендуется использовать следующие конструктивные принципы:

1. Высокая скорость преобразования при программной реализации.

2. Компактность. Алгоритм не должен требовать большого объема оперативной памяти для своего размещения.

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

4. Возможность использования секретного ключа произвольной длины.

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

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

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

Для построения скоростных программных алгоритмов преобразования информации была предложена идея использования псевдослучайных выборок из ключа преобразования. Алгоритмы с подобной недетерминированной выборкой, подключей характеризуются тем, что элементы ключа, используемые при преобразовании входного блока данных, выбираются в зависимости от структуры преобразуемого блока и от структуры ключа. Для алгоритмов, основанных на подобной схеме, расписание выборки подключей не является предопределенным, что является I существенным фактором повышения стойкости преобразования. За счет | этого количество раундов может быть уменьшено и тем самым повышена ■ скорость преобразований. Алгоритмы с выборкой подключей в зависимости от преобразуемых данных можно назвать псевдовероятностными по ; характеру .выборки подключей. .

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

Блок анализа

управляющего параметра -__-

Блок предварительных преобразований

Л

\—/

Алгоритм преобразования

Исходный массив данных

С

1 Параметр,

управляющий

преобразованием

V

Преобразованный массив данных

Рис. 1. Блок-схема преобразования информации в АСУ

Ниже приводятся конкретные используемые раундовые процедуры. На первой и третьей процедуре нумерация преобразуемых символов идет справа налево, на второй и четвертой процедурах нумерация символов идет слева на право. Размер преобразуемого блока данных составляет 512 байт. Fm[ui\, ад, Fm\yi\, Fc[ui\ - значения слов подключей с адресами (указателями) и„ у,\ Щ, yt ~ 8-ми битовые переменные; щ, у0, К, С\ - константы, вычисляемые на этапе предвычислений. Clh С1\, Chb СИ',— младшие и старшие байты соответствующих переменных; Tit С, - 16-ти битовые слова исходного и преобразованного массива данных. "+", ("-") - операции сложения (вычитания) по модулям 28 и 216, в зависимости от разрядности операндов, "©" — операция поразрядного сложения по модулю два.

Алгоритм первой процедуры

1. Установить значение счетчика г':=1 и вычислить начальные значения щ, уо, К, в зависимости от параметра преобразования.

2. Осуществить преобразование i-ой пары символов: С'г:= (Ti-K)@Fm[Ui.i mod 256];

и,:= (м,ч mod 256) Ф Fc\yiA mod 256]; yt:= (yiA mod 256) + CI',; С,:=С', + м,;

3.Прирастить г':=г'+1. Если /<256, то перейти к п.2, иначе СТОП.

Алгоритм второй процедуры

1. Установить значение счетчика ¿:=1 и вычислить начальные значения н0, уо в зависимости от параметра преобразования.

2. Осуществить преобразование С',:— Ъ Ф Fc[iij.\ mod 256];

и,:= (и,л mod 256) © Fm[yl4 mod 256]; yt:= О,. 1 mod 256) + С/г',-; C,-:= C'i +u,.

3. Прирастить г:=/+1. Если i<256, то перейти к п.2, иначе СТОП.

Алгоритм третьей процедуры

1. Установить значение счетчика /:=1 и вьгаислить начальные значения щ, у0, С о в зависимости от параметра преобразования.

2. Осуществить преобразование С,-:= (Ti + С',.,) ® Fm[uiA mod 256]; у,~уи + С/',,,;

м,:= ((ы,ч mod 256) © Fc\y, mod 256]) + Ch\A C,:= C'i +щ.

3. Прирастить /:=/+1. Если /<256, то перейти к п.2, иначе СТОП.

Алгоритм четвертой процедуры

1. Установить значение счетчика i:=l и вычислить начальные значения

«о, Уо, С'о в зависимости от параметра преобразования.

2. Осуществить преобразование . С',:= (Г, + С\л ) © Fc[ut., mod 256];

У1~У1Л + СК-ь

м," ((цч mod 256) © Fm\y, mod 256]) + С/',.,;

С,:= + щ.

3. Установить i:=i+1. Если i<256, то перейти к п.2, иначе СТОП.

В зависимости от параметров преобразования конкретный алгоритм может содержать одну, две, три или четыре указанные процедуры (важным является, чтобы от раунда к раунду направление преобразования менялось на противоположное). Например, алгоритм преобразования может состоять из трех раундов и использовать следующие процедуры 1, 2,1.

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

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

W =256х4хЖ„ +257хРРс, где Wa - сложность арифметических операций по модулю 216, a Wc -сложность операций шифрования. Для двухраундового преобразования имеем следующую оценку сложности вычисления ключа W= Lx(MxWc +IVJ,

здесь Wc - сложность операций шифрования, М — среднее количество уравнений в системе необходимое для определения неременных (предполагаем, что часть битов остается неопределенной), Ws сложность решения системы из М уравнений, L - среднее количество систем уравнений необходимое для вычисления ключа с учетом того, что некоторые биты нельзя однозначно определить, решая только одну систему уравнений. Минимальное значение для М равно 5 (так как имеется пять неизвестных). Эднако лучше взять больше, чтобы отбраковать липшие решения и довести IX в среднем до 8192. В качестве М можно взять, скажем, 256. Коэффициент г> зависит от N и можно взять порядка 1000, чтобы найти ключ с достаточно шеокой вероятностью. Тогда оценка сложности примет вид: W = 1000 х (256 x.Wc+Ws).

В случае если нарушитель не может вводить специально подобранные •ексты, но знает несколько преобразованных и соответствующих им ггкрытых блоков данных однораундовый алгоритм преобразований щформации не является стойким. Данная модель нарушителя является ипичной для АСУ, так как предполагается, что в таких системах имеется [екоторая служебная информация, которая с одной стороны является бщеизвестной, а с другой подвергается преобразованию.

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

Описанные выше алгоритмы преобразований оперировали 16-ти битовыми словами. Однако современные массовые процессоры ориентированы также и на работу с 32-х разрядными словами. Ясно, что обработать одно 32-х битовое можно не менее быстро, чем обработать два 16-ти битовых. Кроме того, при обработке 32-битовых слов будет лучшее сцепление слов блока, чем при обработке 16-ти битовых, решать уравнения относительно 32-х битовых слов сложнее, чем решать аналогичные уравнения относительно 16-ти битовых слов. Вероятности того, что два различных 32-х битовых слова преобразуются с использованием одних и тех же переменных при прочих равных условиях на порядок ниже вероятности преобразования двух различных слов с использованием одних и тех же 16-ти битовых переменных. При этом для получения той же стойкости потребуется I меньшее количество раундов преобразования. Поэтому естественен переход | от процедур обрабатывающих 16-ти битовые слова к процедурам | обрабатывающим 32-х битовые слова.

: , Для усиления стойкости введем дополнительные требования. Во-

< первых, потребуем, чтобы даже незначительные изменения преобразуемых данных (например, изменение всего лишь одного бита) приводили к изменению выборки подюпочей алгоритма преобразования и, во-вторых, потребуем, чтобы подключи не применялись бы непосредственно в уравнении, связывающем преобразованный и исходный блок данных. При таких условиях возникает необходимость либо увеличить количество выборок подключей, либо увеличить размер ключа. В предложенных выше алгоритмах размер ключа составлял 385 байтов. Если оставить неизменным порядок размера ключа, то потребуется использовать четыре выборки подключей. Это может замедлить алгоритм преобразования. С другой стороны, если использовать две выборки подключей, то потребуется ключ размером в 64 Кбайта, что в некоторых приложениях может оказаться неприемлемым. Определенным компромиссом между скоростью преобразования и размером ключа может служить увеличение размера ключа до 2П байт. При этом возникают две возможности построения скоростных алгоритмов преобразования данных.

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

гарантированного влияния любых изменений преобразуемого блока на расписание выборки подключей требуется использование трех выборок подюпочей. Такой подход применен в широко применяемой в настоящее время системе защиты информации «СПЕКТР-Z». Алгоритм системы защиты информации от НСД «СПЕКТР-Z» преобразует информацию блоками по 512 байт и состоит из двух полных и одного неполного раундов преобразований. Как и в случае с алгоритмами, рассмотренными выше, ключ преобразований системы «СПЕКТР-Z» генерируется на этапе предвычислений который не является критичным по времени. Поэтому в данной работе не проводится анализа процедур построения ключа. По сравнению с представленными выше алгоритмами алгоритм преобразований системы «СПЕКТР-Z» обладает дополнительным механизмом защиты, значительно повышающим его стойкость к различным видам атак. Поскольку подключи используются для вычисления вспомогательных переменных и непосредственно не участвуют в уравнении, связывающем преобразованный блок данных с исходным блоком данных, то для нахождения ключа требуется решать уравнения не для отдельных слов, а для пар соседних слов. При этом естественно вероятность использования для различных слов преобразуемого блока одинаковых промежуточных переменных значительно ниже. Хотя для одного раунда алгоритма мы и можем зафиксировать используемые для преобразования одного 32-х разрядного слова подключи, но для двух соседних слов в общем случае (предполагается, что ключ представляет случайную равномерно распределенную последовательность байтов) промежуточные переменные нельзя зафиксировать (даже зная ключ). Таким образом, техника, используемая для нахождения ключа для описанных выше процедур преобразования в принципе не подходит для решения аналогичных уравнений алгоритма преобразования данных используемого в системе «СПЕКТР-Z».

При втором подходе также используется ключ размером порядка 211 байт (хотя здесь размер ключа можно гибко изменять, не внося существенных изменений в структуру алгоритма). В качестве используемых операций предлагается использовать операцию умножения, которая имеет хорошие рассеивающие характеристики (т.е. изменение небольшого количества битов одного из операндов со значительной вероятностью приводит к существенным изменения произведения). В результате применения операции умножения можно уменьшить количество выборок (и, следовательно, обращений к памяти) с трех до двух и даже одной. Соответственно уменьшается количество используемых переменных и общее количество операции. В таблице 1 приводятся сравнения скорости алгоритма системы «СПЕКТР-Z» и алгоритмов использующих операцию умножения по модулю 232 и одну, две выборки подключей (для процессора Pentium-IT 266). Время и скорость преобразований измерялись для случая многократного (107 раз) преобразований одного 512-ти байтового блока данных.

Таблица 1.

Алгоритм системы «спектра» Алгоритм с одной выборкой Алгоритм с двумя выборками

Время преобразования 280 с 208 с 303 с

Скорость преобразования 18 Мбайт/с 25 Мбайт/с 17 Мбайт/с

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

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

Использование алгоритмов преобразований данных в программных системах защиты ЭВМ предопределяет то, что все процедуры преобразований должны быть записаны на магнитном носителе компьютера, если мы не хотим обременять пользователя постоянной необходимостью многократно выполнять дополнительные действия. Таким образом, в удобной для пользователя системе. компьютерной безопасности алгоритм преобразования информации принципиально доступен злоумышленнику. Очевидно, что отсутствие информации или ее части об используемых процедурах преобразований значительно затрудняет потенциальному противнику задачу взлома системы защиты.

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

16

алгоритму который необходимо предполагать известным нападающему. Множество возможных алгоритмов преобразования конечно, а закон его описания (порождающий алгоритм) известен нарушителю. Однако последний не знает, какая конкретная модификация алгоритма будет реализована, поскольку ее выбор задается ключом. Такой подход к построению является логическим продолжением рассмотренных в предыдущей главе подходов к построению алгоритмов преобразования данных в АСУ. Теперь не только расписание выбора иодключей не является заранее определенным, но и сами процедуры преобразования являются неопределенными. При этом, поскольку, настройка алгоритма происходит на этапе предвычислений скорость второго этапа преобразований в общем случае остается неизменной.

Если число реализуемых модификаций будет достаточно большим, то задание неопределенности процедур преобразования может оказаться эффективным средством противодействия атакам. Более того, сведение задачи анализа к перебору возможных вариантов вряд ли реально. Построение же общего алгоритма анализа, видимо, является гораздо более трудной задачей, чем разработка метода анализа алгоритмов преобразований информации с фиксированным алгоритмом. В работе был исследован недетерминированный 64-битовый алгоритм преобразований. Алгоритм представляет собой реализацию недетерминированных процедур преобразований, основанных на механизме выборки подключей в зависимости от входных данных. Входной блок представляется в виде конкатенации двух 32-битных подблоков. В качестве зарезервированных бинарных операций *р подлежащих настройке на этапе инициализации, используются простые арифметические операции: поразрядное сложение по модулю 2 (©), сложение и вычитание по модулю 232 (+ и - соответственно). Кроме этих бинарных операций, зарезервированы также унарные операции циклического сдвига вправо Х"с> слова X на число битов равное с; = 0, 1, 2,...31. Значения р= 1, 2,...,8г и 1=1, 2,...,12г являются порядковыми номерами бинарных и унарных операций, соответственно.

При записи алгоритма преобразований использованы следующие обозначения: X, У - 32-битовые переменные; (Ш={60)} ~ ключ преобразования, представленный в виде последовательности 256 32-битовых подключей 0{}) 0=0, 1, 2,..., 255); АЧс^хзИхь и Т^ЬзЫУь где х, и у\ - 8-битовые подблоки. Ниже приводится недетерминированные процедуры преобразования 64-битовых блоков данных

ВХОД: 64-битовый блок данных, представленный как конкатенация 8-битовых слов /,: Г=/81^1гбИ^Ыь^ь

1. Установить значения: /?=3, г=Т, и У-иЩ^Ь.

2. Преобразовать:

- = уГ1""';* = = = .

3. Преобразовать:

4. Преобразовать:

* Я*];

5. Преобразовать:

6. Преобразовать:

7. Преобразовать:

Г = (Г*8г еМГ'"'-

8. Если г<Д, то прирастить г=г+1 и перейти к шагу 2.

СТОП.

ВЫХОД: 64-битовый блок С=Х\У.

Данный алгоритм преобразования инициализируется на этапе предвычислений, задающего число зарезервированных операций в зависимости от установленного числа раундов преобразований Я. Допустимое число раундов преобразования равно К>3.

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

IV = ^ (5 X 232 X + 57696 х ),'

где 1¥с сложность процедуры преобразования, а Жа - сложность арифметических операций над 32-х разрядными словами.

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

Во всех рассмотренных выше алгоритмах в качестве базовых были использованы аппаратно реализованные операции, используемые в современных микропроцессорах общего назначения. Однако если в качестве базовых операций допустить операции управляемых перестановок, то возникает возможность создания алгоритмов преобразования данных, скорость которых при программной реализации превысит достижимые на данный момент скорости преобразования на 200% и более. При этом можно так подобрать структуру блока управляемых перестановок, что будут

18

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

В четвертой главе приводятся результаты исследования статистических свойств алгоритмов преобразования информации в АСУ, описанных во второй и третьей главах. Процедуры преобразования данных можно рассматривать как некоторое семейство подстановок на множестве {О, 1,..., п}, где п -некоторое натуральное число (для рассматриваемых преобразований п является степенью двойки). Данное семейство подстановок можно параметризовать. Естественным параметром является ключ' преобразования. Одним из наиболее важных свойств, влияющих на стойкость алгоритма преобразования данных, является равномерность распределения семейства подстановок. В случае если подстановка (алгоритм преобразования) задает случайное преобразование, потенциальный нарушитель не сможет применить статистические методы обработки информации с целью НСД.

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

В работе используются такие известные тесты, основанные на критерии х2, как

• Проверка равномерности. Последовательность должна быть равномерной, т.е. вероятность нуля должна совпадать с вероятностью единицы.

• Проверка серий. Проверяется равномерность и независимость следующих друг за другом битов.

• Покер тест. Проверяется, соответствуют ли частоты комбинаций вероятностям.

• Тест интервалов. Проверяется длины интервалов межу появлением значений последовательности принадлежащих некоторому

фиксированному интервалу.

• Проверка независимости по таблице сопряженности признаков. Проверяется независимость битов преобразованного и исходного текстов.

Кроме тестов основанных на критерии для анализа вероятностных характеристик алгоритмов преобразования применяются следующие тесты

• Тест последовательной корреляции. Применяется для проверки независимости соседних битов преобразованного текста.

• Тест корреляции преобразованного и исходного блоков информации. Применяется для проверки независимости преобразованного и исходного блока данных. При малых значениях коэффициента корреляции преобразованный и исходный блоки являются независимыми. При значениях коэффициента корреляции ±1 блоки являются линейно зависимыми.

В дополнение к указанным выше тестам в работе разрабатывается тест для статистического анализа цикловой структуры подстановки. Известно, что каждая подстановка может быть представлена в виде произведения попарно непересекающихся циклов. Все множество подстановок разбивается на цикловые классы в зависимости от цикловой структуры {ги г2>..г„}, где г, -обозначает количество циклов длины г. Предполагаем, что вероятность отдельно взятой подстановки составляет 1/и! В этом случае, вероятность любого циклового класса равняется

_1_

Г' 2Г' ...п" г1,.г2,....гп1'

и при достаточно больших п составляет близкую к нулю величину. Поэтому для анализа цикловой структуры такое разбиение на классы не годится. Для п имеющих порядок приблизительно 2 2 предлагается способ объединения цикловых классов в большие группы. Про подстановку будем говорить, что она обладает к большими циклами, если у подстановки имеется к циклов имеющих длины а|>а2>- • >йк и при этом суммарная оставшихся циклов т<ак. Можно Дать аналогичное определение, где все неравенства нестрогие, однако, при строгих неравенствах анализ упрощается. В случае ¿=1, имеем

а>т. При этом очевидно т<, п ~1

. В зависимости от т все цикловые классы

2 ]

разбиваются на группы. Для вероятности ' каждой 1руппы получена следующая формула

р(п, т„ тм) = р(п, т, <т<тм)= 2, —-« I-= 1и(-),

™ п-т > п-т п-т,и

для 0<т1<тм<

щ " " '".+1

И-Г

Для получения численных оценок качества

подстановок к полученным данным применяется метод х2-

На рис. 2 показана блок-схема алгоритма нахождения длины большого цикла для подстановки, в случае если такой цикл существует. Если большого цикла не существует, то возвращается значение 0.

/ Начальные значения ; в1=0

значен \Т0:=0;)

Зис. 2. Блок-схема алгоритма нахождения длины большого цикла подстановки

С помощью программного обеспечения указанные тесты (кроме анализа цикловой структуры) были применены к алгоритмам защиты информации, базирующимся на выборке подключей в зависимости от преобразуемых данных. К 64-битовому недетерминированному алгоритму были применены все рассмотренные тесты, включая анализ цикловой структуры. По результатам тестов можно сделать вывод о том, что исследуемые алгоритмы обладают хорошими вероятностными свойствами. И, следовательно, потенциальный нарушитель не имеет возможности применить анализ статистических закономерностей для получения НСД к информации циркулирующей в АСУ.

Основные результаты работы

При выполнении работы получены следующие результаты.

1. Обоснованы границы применимости семейства скоростных алгоритмов защиты информации в АСУ, базирующихся на выборке подключей в зависимости от преобразуемых данных. Даны оценки стойкости в зависимости от модели потенциального нарушителя.

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

3. Исследован скоростной алгоритм преобразования информации, используемый в широко применяемой системе защиты информации «СПЕКТРА», даны оценки его стойкости и рекомендации по его оптимизации по скорости и стойкости.

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

5. Показана перспективность применения механизмов увеличения рассеивания на базе целочисленного умножения в алгоритмах преобразования, используемых в специальных загрузчиках операционной системы.

6. Предложены методы анализа недетерминированного 64-битового алгоритма при одном и двух раундах преобразования на основе подобранных текстов и даны рекомендации по выбору числа раундов в зависимости от модели • нарушителя и варианта алгоритма инициализации.

7. Обосновано расширение системы команд микропроцессоров широкого назначения командой управляемой перестановки, что позволит увеличить скорость программных алгоритмов преобразования на 200 % и более по сравнению с лучшими алгоритмами известными в настоящее время.

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

Публикации по теме диссертации

1. Алексеев JT. Е., Ростовцев А. Г. Свойства семейства криптографических модулей защиты ЭВМ. // «Региональная информатика - 96». Тезисы докладов, часть 1. - СПб, Издание СПОИСУ, 1996. 211 с. Стр. 99.

2. Алексеев JI. Е. О 4-х битных подстановках с максимальной нелинейностью. // «Методы и технические средства обеспечения безопасности информации». Тезисы конференции. СПб, издательство СПбГТУ, 1997. 198 стр. Стр. 8-10.

3. Алексеев JI. Е. Статистический анализ на основе информации о цикловой структуре. // «Безопасность и экология Санкт-Петербурга.» Материалы научно-практической конференции 11-13 марта 1999. СПб. 1999. Стр. 109110.

4. Алексеев JI. Е. О стойкости псевдовероятностного 512-байтового блочного шифра. // Межрегиональная конференция «Информационная безопасность регионов России ИБРР-99» Санкт-Петербург, 13-15 октября 1999 года. Тезисы конференции, часть 1. Стр.29.

5. Молдовян Н. А., Алексеев JI. Е. Преобразование информации в системе «СПЕКТР-Z». // Первая Международная конференция «РусКрипто 1999». Москва, Непецино, 22 - 24 декабря 1999 года. Тезисы конференции. //www.lancrypto.com.

6. Алексеев JI. Е., Заболотный А. II., Молдовян А. А. Алгоритм файлового шифрования и криптоалгоритм загрузчика системы «СПЕКТР-Z». // Вторая Международная конференция «РусКрипто 2000». Москва, Непецино, 3-5 февраля 2000. Тезисы докладов, //www.lancrypto.com.

7. Алексеев JI. Е., Молдовян Н. А. Повышение скорости шифрования программных криптоалгоритмов. // Вторая Международная конференция «РусКрипто 2000». Москва, Непецино, 3-5 февраля 2000. Тезисы докладов, //www.lancrypto.com.

1. Алексеев Л.Е., Белкин Т.Г., Молдовян A.A., Молдовян H.A. Способ итеративного шифрования блоков данных. // Патент РФ N 2140714, С1 6 Н 04 L 9/20. Опубл. 27.10.99. Бюл. N 30.

). Молдовян Н. А., Молдовян А. А., Алексеев JI. Б. Перспективы разработки скоростных шифров на основе управляемых перестановок. // «Вопросы защиты информации». Научно практический журнал. Москва, №1 (44) 1999 стр. 41-47.

ВВЕДЕНИЕ.

ГЛАВА I. ФАКТОРИЗАЦИЯ ПРЕДМЕТНОЙ ОБЛАСТИ.

§1. Общие вопросы и понятия связанные с защитой информации.

§2. Блочные алгоритмы преобразования информации.

§3. Примеры блочных алгоритмов преобразования информации в АСУ.

§4. Скоростные программные алгоритмы преобразования информации в

Постановка задачи.

Основные результаты.

ГЛАВА II. АНАЛИЗ АЛГЕБРАИЧЕСКИХ СВОЙСТВ ПСЕВДОВЕРОЯТНОСТНЫХ АЛГОРИТМОВ ПРЕОБРАЗОВАНИЯ ИНФОРМАЦИИ В АСУ.

§ 1 .Алгоритм преобразований базирующийся на выборке подключей в зависимости от преобразуемых данных.

§2. Методы вычисления подключей при реализации повторов.

§3. Способы повышения скорости и стойкости алгоритмов преобразования данных в АСУ.

Основные результаты.

ГЛАВА III. АНАЛИЗ АЛГЕБРАИЧЕСКИХ СВОЙСТВ НЕДЕТЕРМИНИРОВАННЫХ АЛГОРИТМОВ ПРЕОБРАЗОВАНИЯ ИНФОРМАЦИИ В АСУ.

§ 1. Построение скоростных программных алгоритмов преобразования данных с недетерминированными процедурами.

§2. Анализ алгебраических свойств преобразования.

§3. Выявление особенностей ключей - слабые и сомнительные ключи.

§4 Построение алгоритмов преобразования на основе управляемых блоков перестановок.

Основные результаты.

ГЛАВА IV. ОЦЕНИВАНИЕ СТАТИСТИЧЕСКИХ СВОЙСТВ АЛГОРИТМОВ ПРЕОБРАЗОВАНИЙ ДАННЫХ В АСУ.

§ 1. Описание основных критериев и тестов используемых для анализа статистических свойств алгоритмов преобразований.

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

§3. Применение статистического анализа к исследуемым алгоритмам преобразования данных.

Основные результаты.

Ни одна сфера жизни современного общества не может функционировать без развитой информационной инфраструктуры. Национальный информационный ресурс является сегодня одним из главных источников экономической и военной мощи государства, основной предпосылкой его социально-экономического развития. В настоящее время информационная безопасность приобретает первостепенное значение во всех сферах общественной жизни и государственной деятельности. В политической сфере можно наблюдать все большее смещение центра тяжести от силовых факторов к более скрытым и тонким, базирующимся на информационном воздействии. В экономической сфере все большее влияние оказывает уровень развития информационной инфраструктуры. Одновременно растет потенциальная уязвимость экономики по отношению к информационным воздействиям. В военном деле наметилась тенденция перехода от оружия массового уничтожения к высокоточному оружию и «информационному оружию». В области науки техники экологии целый ряд систем управления (транспортом, связью, атомной энергетикой экологически опасными производствами) относятся к критическим. Очевидно, недооценка вопросов информационной безопасности этих систем может привести к непредсказуемым последствиям, огромным материальным потерям и человеческим жертвам [1].

Широкое применение компьютерных технологий в автоматизированных системах обработки информации и управления, используемых в АСУ реального времени, а также в оборонных и коммерческой областях, привело к обострению проблемы защиты информации от несанкционированного доступа, обусловленной тем, что электронная форма представления данных обладает рядом специфических особенностей, связанных с тем, что информация не является жестко связанной с носителем, может легко и быстро копироваться и передаваться по каналам связи [2]. Одним из важных механизмов поддержания защищенного функционирования автоматизированных систем является преобразование информации. В случае высокопроизводительных АСУ возникает проблема разработки надежных скоростных алгоритмов преобразования информации.

Вопросы оптимизации алгоритмов защиты информации приобретают все более возрастающее значение в связи со стабильными тенденциями развития современных средств вычислительной техники, характеризующихся быстрым ростом объема устройств памяти и производительности процессоров, что приводит к увеличению информационных потоков в АСУ. Важнейшими параметрами алгоритмов преобразования является стойкость и скорость преобразования. При обеспечении данного уровня стойкости увеличение скорости алгоритмов защиты информации позволяет существенно повысить производительность АСУ. Таким образом, актуальной является проблема создания скоростных алгоритмов преобразования данных с учетом конкретных условий применения, определяющих потенциальные угрозы информационной защищенности.

Известно очень большое число угроз информации, которые могут быть реализованы как со стороны внешних нарушителей, так и со стороны внутренних нарушителей [3]. Отметим некоторые современные направления, где требуется обеспечить защиту информации циркулирующей в АСУ [2]:

• Защита от несанкционированного чтения информации.

• Защита от навязывания ложных сообщений (умышленных и непреднамеренных).

• Идентификация законных пользователей.

• Контроль целостности информации.

• Аутентификация информации.

• Электронная цифровая подпись.

• Системы тайного электронного голосования.

• Электронная жеребьевка.

• Защита от отказа факта приема сообщения.

• Одновременное подписание контракта.

• Защита документов и ценных бумаг от подделки.

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

Радикальное решение проблем защиты электронной информации может быть получено на базе использования специальных преобразований информации, которые позволяют решать важнейшие проблемы защищенной автоматизированной обработки и передачи данных. При этом современные скоростные методы преобразования данных позволяют в основном сохранить исходную производительность автоматизированных систем. Подобные преобразования данных являются наиболее эффективным средством обеспечения конфиденциальности данных, их целостности и подлинности. Только их использование в совокупности с необходимыми техническими и организационными мероприятиями могут обеспечить защиту от широкого спектра потенциальных угроз и тем самым сделать работу АСУ стабильной, не смотря на внешние воздействия.

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

В первой главе приводятся общие сведения, связанные с вопросами защиты информации. Приводятся примеры известных алгоритмов преобразования данных. Даются общие критерии для создания стойких к различным видам нападения алгоритмов.

Во второй главе приводится описание системы основанной на псевдослучайной выборке подключей. Предлагаются методы нахождения ключей для неполных вариантов алгоритмов преобразования информации и даются оценки сложности этих методов. Приводятся алгоритмы преобразования информации, используемые в системе «СПЕКТРА», дается оценка их стойкости и скорости. Предлагаются пути повышения скорости алгоритмов преобразования информации, основанных на псевдовероятностной выборке подключей.

В третьей главе приводится описание 64-битового недетерминированного алгоритма преобразования информации. Для однораундовой и двухраундововой модификаций алгоритма предлагаются методы нахождения ключей и даются оценки сложности этих методов. Рассматривается вопрос повышения скорости алгоритмов за счет использования управляемых перестановок.

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

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

2. Для повышения стойкости скоростных псевдовероятностных алгоритмов к атакам на основе подобранных текстов может быть применен «сокращенный» раунд.

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

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

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

Основные результаты

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

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

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

4. На уменьшенной в два раза модели проведен анализ цикловой структуры семейства подстановок реализующих недетерминированный 64-битный алгоритм преобразования информации и показано, что указанное семейство носит случайный характер с точки зрения цикловой структурой.

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

142

АСУ обладают хорошими статистическими свойствами, что является одним из показателей стойкости указанных алгоритмов к различным видам атак.

Заключение.

В результате выполненного диссертационного исследования получены следующие результаты:

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

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

3. Исследован скоростной алгоритм преобразования информации, используемый в широко применяемой защищенной автоматизированной системе «СПЕКТРА», и даны оценки его стойкости и рекомендации по его оптимизации по скорости и стойкости.

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

5. Показана перспективность применения механизмов увеличения рассеивания на базе целочисленного умножения в алгоритмах преобразования, используемых в специальных загрузчиках операционной системы.

6. Предложены методы анализа недетерминированного 64-битового алгоритма при одном и двух раундах преобразования на основе подобранных текстов и даны рекомендации по выбору числа раундов в зависимости от модели нарушителя и варианта алгоритма инициализации.

7. Обосновано расширение системы команд микропроцессоров широкого назначения командой управляемой перестановки, что позволит увеличить скорость программных алгоритмов преобразования на 200% и более по сравнению с лучшими алгоритмами известными в настоящее время.

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

1. Яшин Ю. А. Основные направления совершенствования государственной системы защиты информации в Российской Федерации. // «Безопасность информации» Сборник материалов международной конференции. Москва 14-18 апреля 1997 г.

2. Молдовян Н. А. Проблематика и методы криптографии. // СПб, Издательство СпбГУ, 1998. - 212с.

3. Герасименко В. А. Защита информации в автоматизированных системах обработки данных. // В 2-х кн. М.: Энергоатомиздат, 1994. -576 с.

4. Молдовян Н. А. Скоростные блочные шифры. // СПб, Издательство СпбГУ, 1998.-230с.

5. Месси Дж. JI. Введение в современную криптологию. // ТИИЭР, 1988, т. 76. N5. Стр. 24-42.

6. Шеннон К. Э. Работы по теории информации и кибернентике. // М.: ИЛ, 1963. С. 333-402.

7. Молдовян А. А., Молдовян Н. А., Советов Б. Я. Скоростные программные шифры и средства защиты информации в компьютерных системах. // СПб, ВАС, 1997. 136с. Под общей редакцией д.т.н., профессора Советова Б. Я.

8. Сэвидж Д. Э. Сложность вычислений. // М.: Издательство «Факториал». 1998. 368 с.

9. Seberry J., Zhang Х.-М., Zheng Y. Nonlinearly Balanced Boolean Functions and Their Propagation Characteristics. //Advances in Cryptology Crypto'93. Springer-Verlag, Berlin, Geidelberg, New York

10. Ю.Алексеев Л. E. О 4-х битных подстановках с максимальной нелинейностью. // «Методы и технические средства обеспечения безопасности информации». Тезисы конференции. СПб, издательство СПбГТУ, 1997. 198 стр. Стр. 8-10.

11. Nyberg К. On the construction of highly nonlinear permutations. // Workshop on the Theory and Applications of Cryptographic Techniques. EUROCRYPT"92. Hanguary, May 24-28, Procceeding 1992. Pp. 89-94.

12. Диффи У., Хеллман M. Э. Защищенность и имитостойкость: Введение в криптографию. // ТИИЭР. 1979. Т. 67. № 3. Стр. 71-109.

13. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. // М. Госстандарт.

14. Schneir В. Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish) // "Fast Software Encryption", Cambridge Security Workshop Proc., LNCS 809, Springer-Verlag, 1994, pp. 191-204.

15. Rivest R. L. The RC5 Encryption Algorithm // "Fast Software Encryption", Second International Workshop Proc., LNCS 1008, Springer-Verlag, 1995 pp. 86-96.

16. Молдовян А. А. Комбинированные криптосхемы на базе библиотеки процедур шифрования. // "Региональная информатика 96". Тезисы докладов, часть 1. - СПб, Издание СПОИСУ, 1996. 211 с. Стр.110-111.

17. Риордан Дж. Введение в комбинаторный анализ. // М. Издательство иностранной литературы, 1962. 288с.

18. Алексеев JI. Е., Ростовцев А. Г. Свойства семейства криптографических модулей защиты ЭВМ. // "Региональная информатика 96". Тезисы докладов, часть 1. - СПб, Издание СПОИСУ, 1996. 211 с. Стр. 99.

19. Moldovyan A. A., Moldovyan N. A. Software encryption algorithms for transparent protection technology // Cryptologia, January 1998, Volume XXII № 1. P. 56-68.

20. Алексеев JI. E. О стойкости псевдовероятностного 512-байтового блочного шифра. // Межрегиональная конференция «Информационная безопасность регионов России ИБРР-99» Санкт-Петербург, 13-15 октября 1999 года. Тезисы конференции, часть 1. Стр.29.

21. Молдовян Н. А., Алексеев Л. Е. Преобразование информации в системе «СПЕКТР-Z». // Первая Международная конференция «РусКрипто1999». Москва, Непецино, 22 24 декабря 1999 года. Тезисы конференции. www.lancrypto.com

22. Biham Е., Shamir A. Differential Fault Analysis of Secret Key Cryptosystems // 17th Annual International Conference "Advances in Cryptology -CRYPTO'97". Santa Barbara, USA, August 17-21, 1997. Procedings SpringerVerlag LNCS. 1997. V. 1294. P. 513-525.

23. Алексеев Л. E., Молдовян H. А. Повышение скорости шифрования программных криптоалгоритмов. // Вторая Международная конференция «РусКрипто 2000». Москва, Непецино, 3-5 февраля 2000. Тезисы докладов, www.lancrypto.com.

24. Rivest L. R., Robshaw М. J. В., Sidney R., Yin Y. L. The RC6™ Block Cipher // The First Advanced Encription Standard Candidate Conference. Ventura, California, August 20-22 1998.

25. X. Lai and J. Massey, A proposal for a New Block Encription Standard. // Advances in Cryptology EUROCRYPT'90 Proceedings, Springer-Verlag, 1991, pp. 389-404.

26. Алексеев Л. E., Заболотный А. П., Молдовян А. А. Алгоритм файлового шифрования и криптоалгоритм загрузчика системы «СПЕКТР-Z». //Вторая Международная конференция «РусКрипто 2000». Москва, Непецино, 3-5 февраля 2000. Тезисы докладов, www.lancrypto.com.

27. Moldovyan A. A., Moldovyan N. A. Flexible Block cipher with provably inequivalent cryptalgorithm modifications // Cryptologia, April 1998, Volume XXII №2. P. 134-140.

28. Молдовян H. А., Молдовян А. А., Алексеев Л. E. Перспективы разработки скоростных шифров на основе управляемых перестановок. // Научно-практический журнал «Вопросы защиты информации». Москва, №1 (44) 1999 г.148

29. Каргополов М. И., Мерзляков Ю. И. Основы теории групп. // М. Наука физматлит. 1996. 288с.

30. Алексеев JI.E., Белкин Т.Г., Молдовян A.A., Молдовян H.A. Способ итеративного шифрования блоков данных. // Патент РФ N 2140714, С1 6 Н 04 L 9/20. Опубл. 27.10.99. Бюл. N 30.

31. Кнут Д. Искусство программирования для ЭВМ. // T.-l. М., 1976. 728с

32. Джонсон Н., Лион Ф. Статистика и планирование эксперимента в технике и науке. // М., Издательство "Мир", 1980. 612с.

33. Кофман А. Введение в прикладную комбинаторику. // М., Издательство «Наука», 1975. -480с.

34. Алексеев JI. Е. Статистический анализ на основе информации о цикловой структуре. // Безопасность и экология Санкт-Петербурга. Материалы научно-практической конференции 11-13 марта 1999. СПб. 1999. Стр. 109110.ш ш и т ш1. Ш;1?,1. НА ИЗОБРЕТЕНИЕ2140714

35. На основании Патентного закона Российской Федерации, введенного в действие 14 октября 1992 года, Российским агентством по патентам и товарным знакам выдан настоящий патент на изобретение

36. СПОСОБ ИТЕРАТИВНОГО ШИФРОВАНИЯ БЛОКОВ ДАННЫХ1. Патентообл адатель(л и):см. ш 'о&фотно заявке № 99100950, дата поступления: 18,01.99 Приоритет от 18.01.99 Авгор(ы) изобретения:

37. Алексеев Леонид Шткип Шнмур Щ>торъеМ1,с/Ьекшнф сЛпд^евМ,, Молдовян 91нкола4 Шт^тШ

38. Патент действует на всей территории Российской Федерации в течение 20 лет с 18 января 1999 г. при условии своевременной уплаты пошлины за поддержание патента в силе

39. Зарегистрирован в Государственном реестре изобретений Российской Федерацииг Москва, 27 октября 1999 г.