автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Метод и алгоритмы контроля целостности конфиденциальных данных на основе функций хэширования

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

Ж"

Нураев Имангазали Юнусович

МЕТОД И АЛГОРИТМЫ КОНТРОЛЯ ЦЕЛОСТНОСТИ КОНФИДЕНЦИАЛЬНЫХ ДАННЫХ НА ОСНОВЕ ФУНКЦИЙ ХЭШИРОВАНИЯ

Специальность: 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей.

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

005531722

Москва-2013

005531722

Работа выполнена в Закрытом акционерном обществе «Зеленоградский нанотехнологический центр» (ЗНТЦ)

Научный Кудрявцев Константин Яковлевич,

руководитель: кандидат технических наук, доцент кафедры

«Информационные системы и технологии» (№36) федерального государственного автономного образовательного учреждения высшего

профессионального образования «Национальный исследовательский ядерный университет «МИФИ»

Официальные Царев Олег Валерьевич,

оппоненты: доктор технических наук, начальник управления

федерального государственного казенного учреждения "46 Центральный научно-исследовательский институт" Министерства обороны Российской Федерации

Скрипник Александр Борисович, кандидат технических наук, генеральный директор закрытого акционерного общества

«Радиотехкомплект»

Ведущая Открытое акционерное общество

организация: «Концерн «Системпром»

Защита состоится «19» июня 2013 г. в 15-00 на заседании диссертационного совета Д 212.131.05 при МГТУ МИРЭА по адресу: Москва, 119454, пр-т Вернадского, д. 78, ауд. Д-412.

С диссертацией можно ознакомиться в библиотеке МГТУ МИРЭА.

Автореферат разослан «14» мая 2013 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу 119454, г.Москва, пр-т Вернадского,78, диссертационный совет Д 212.131.05.

Ученый секретарь

диссертационного совета „ _ .

7_______Е.Г. Андрианова

к.т.н., доцент ^ ^

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

Более 90% компаний сталкивается с внутренними вторжениями, 78% инсайдерских нарушений целостности данных держатели скрывают, а пользователи не имеют возможности доказать факты таких нарушений.

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

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

Объектом исследований в диссертационной работе являются конфиденциальные данные, выраженные в символьной форме, целостность которых требуется контролировать.

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

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

Для достижения указанной цели поставлены следующие задачи:

- развитие метода контроля целостности информации, основанного на формировании структуры связанных хэшей, и разработка алгоритмов контроля и восстановления этой структуры с использованием распределенного хранения;

- разработка и исследование алгоритмов хэширования для оптимизации контроля целостности информации при хранении и передаче.

К поставленным задачам относятся также обеспечение:

- конфиденциальности зарегистрированной информации;

- регистрации данных без их сохранения;

- свободного доступа к средствам контроля целостности информации.

Методы исследования, использованные в диссертационной работе —

это методы теории информации, дискретной алгебры, теории криптографии, статистического и эвристического анализа.

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

1. Разработан и исследован метод (метод АН - Associated Hashes) контроля целостности зарегистрированной информации, основанный:

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

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

- на распространении контрольного ядра в информационной среде;

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

2. Введены понятия: «релевантность коллизий», «условная плотности коллизий», «самосогласованность» фрагментов контрольного ядра, «цепочка записей», - и с их использованием сформулирован и доказан ряд существенных свойств контрольных ядер (приведены далее), на основе которых разработаны способы частичного или полного восстановления их копий, распределенных в информационной среде.

3. Введено понятие симметричных таблиц логических функций и на их основе разработан алгоритм последовательного хэширования LOMD (Logical Operation Message Digest), позволяющий распараллеливать вычисление хэша.

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

5. Разработан и исследован алгоритм хэширования с использованием псевдослучайной строки PRBSH (PseudoRandom Binary String Hashing), оптимизирующий формирование контрольных ядер.

6. Предложено оптоэлектронное устройство для хэширования.

Практическая значимость.

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

2. Предложенные в работе алгоритмы хэширования

- обеспечивают эффективность метода АН;

- позволяют легко управлять свойствами хэш-функций;

- имеют самостоятельное значение в качестве инструментальных средств для других применений (не связанных с методом АН).

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

Внедрение результатов работы.

Развитый в работе метод АН использован: в ЗАО «Синимэкс-Информатика» (для оптимизации тестирования интеграционных банковских решений); в ЗАО «КБ Технотроник» (для организации безбумажного документооборота в системе менеджмента качества (СМК), а также для повышения доверия партнеров путем передачи им контрольного ядра СМК); при разработке эталонного дальномера (для уменьшения погрешностей и документирования эталонных измерений).

Основные научные положения и результаты, выносимые на защиту:

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

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

Апробация работы

Результаты, полученные в ходе выполнения диссертации, докладывались на семинаре кафедры № 36 МИФИ («Кафедра информационных систем и технологий»), на семинаре ЗАО «Зеленоградский нанотехнологический центр», на научных сессиях МИФИ в секциях «Информационные технологии» и «Кибернетика и безопасность». По результатам диссертационной работы опубликованы: 4 статьи [1-4] в рецензируемом издании из списка ВАК, тезисы двух докладов на научных сессиях МИФИ [5; 6], две заявки на получение патентов РФ на изобретения [7; 8], две международные заявки [10; 11], по которым получены положительные заключения по тем же изобретениям, - а также зарегистрирована программа для ЭВМ [9] и получен патент РФ на изобретение [12].

Личный вклад автора

Все научные и практические результаты диссертации получены автором лично.

Структура и объем работы

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

изложено на 145 страницах и включает 29 рисунков и 12 таблиц. Список использованных источников содержит 137 наименований.

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

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

Первая глава посвящена анализу методов контроля целостности информации.

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

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

Сделаны следующие выводы:

- в настоящее время не решена задача обеспечения контроля целостности информации, устойчивого к влиянию любого круга лиц;

- существует необходимость разработки метода контроля целостности информации, который не зависел бы от воли любых лиц;

- основанные на формировании структур связанных хэшей способы контроля целостности информации, сходные с TSP (Time-Stamp Protocol), не позволяют сделать вывод о целостности данных без участия (или против воли) держателя соответствующей БД, то есть узкого круга лиц.

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

Вторая глава посвящена описанию разработанного метода АН (Associated Hashes), основанного:

на регистрации информации путем ее хэширования, создании структуры связанных хэшей и выделении из нее контрольного ядра;

- на распространении копий контрольного ядра, его фрагментов и специально разработанных реперов в информационном пространстве;

- на создании алгоритмов полного или частичного восстановления контрольного ядра путем сравнения его копий или копий его фрагментов.

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

Блок-схема, отражающая порядок формирования контрольного ядра по методу АН, приведена на рисунке 1 и включает:

- формирование исходной строки;

- вычисление локального хэша hm исходной строки;

- вычисление связанного хэша Нш, как хэша от конкатенации строк локального хэша Ьш и связанного хэша Нт.! предыдущей записи (Нх - по заданному Н0, названному корневым хэшем контрольного ядра).

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

Строгое задание структуры строки данных является дополнительным препятствием при поиске коллизий для ее связанного хэша.

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

9

Рис. 1. Блок-схема алгоритма формирования контрольного ядра

Рис. 2. Схема вычисления связанного хэша ¡-ой записи

Схема с рисунка 1 принимает при этом вид, приведенный на рисунке 3. При нарушении целостности какого-либо элемента записи:

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

- изменения в локальном хэше будут обнаружены по его несоответствию связанному хэшу (даже при одновременной подмене исходной строки);

10 II 1з 14 ••• Исходные строки

^ ^ ^ ^ ^

Ьо' " 112* Ьз* 114' •••* 111 Конкатенация локальных хэшей до ¡-го

И] Связанный хэш ¡-он записи

л

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

10 II Ь Ь 14 ... Ь 11+1 1м 1м 1оЬ-4 ••• Исходныые строки I ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

-------------------------— — — ^

Ьо* 1ц * 112' 113- 1и* 1ч * 11|+1* Ькз* Им * Локальныезэши

ГШ"!......П""Г""Г"Т"]'

Но Ш Нз Нз Н4 ... Н| Нь-1 Нь-2 Нм Нь-4<... Связанныехэши (1о (Ь (12 (Ъ ... {1| с1ь-1 (11+2 (1кЗ 1 Служебные строки

¡^Контрольное ядро |

Рис. 3. Схема формирования контрольного ядра с использованием алгоритма ЮМБ или РИББИ

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

Проверкой на самосогласованность названа в работе проверка соблюдения логики, проиллюстрированной на рисунке 1.

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

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

• Связанный хэш нецелостной записи самосогласованного ряда не целостен (нарушен).

• Если не целостна хотя бы одна из входящих в самосогласованный ряд неполных записей, то нецелостными являются и все последующие неполные записи этого ряда.

• Если целостен связанный хэш неполной записи, входящей в самосогласованный ряд, то целостен и локальный ее хэш.

• Если целостен связанный хэш самосогласованного ряда, то целостны и все предыдущие неполные записи этого ряда.

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

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

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

• Совпадение целостных связанных хэшей записей сравниваемых ядер или их фрагментов означает, что записи относятся к записям с одинаковыми порядковыми номерами в своих контрольных ядрах.

На рисунке 4 приведен пример такого «ремонта»: а) и б) — имеющиеся копии цепочек контрольного ядра, в) - результат рассмотрения и «ремонта» (при следующих обозначениях: С - запись с целостным связанным хэшем, У - запись с неустановленной целостностью связанного хэша, Z - запись с нарушенным связанным хэшем).

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

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

Запись

№ 1 2 к-1 к к+1 т т+1 ~ гъ1 п п+1 п+2 М * 1+1 Г+4 1+5 и

а) С-С-.. .-с г у-у-... -У У. ..угу У-У-... -у-угууу У-У-У...-^ {...

б) С-С-. ..-с г у у... У-У- ...-У-У-У-УУ ... У-У-У-У-У-У-С-У-... У...

в) С-С-. •"С 2 С"С"ш -С-С- • * ■С"С"љљС"љљУ"• • У...

Рис. 4. Ремонт фрагментов контрольного ядра по цепочке

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

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

В третьей главе сформулированы особенности требований к алгоритмам хэширования, используемым в методе АН, которые связаны:

- с необходимостью хэширования конкатенаций строк;

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

- с желательностью управления свойствами хэш-функций.

Предложено два алгоритма, соответствующих этим требованиям.

Первый — алгоритм хэширования на логических операциях — ЬОМЭ.

На рисунке 5 приведен вариант алгоритма ЬОМО, где исходная строка

хэша длиной в Н разрядов (нулевое приближение хэша) состоит из первых Н разрядов хэшируемой строки, а обработка начинается с ее (Н + 1)-го разряда.

Виртуальное логическое исполнительное устройство Ь считывает очередные обрабатываемые разряды строки хэша и хэшируемой строки, определяет номер очередной применяемой логической функции по заданной таблице логических функций по формуле 1е5 = (|ЬЧ' Ь2]' + е + |Ье;|)тос18, где - номер логической функции для обработки разряда № е приближения № ] строки хэша, вычисляет значение логической функции от двух переменных |1Ц|| и записывает новое значение |Ье]-ц[ разряда № е строки хэша

вместо прежнего, обеспечивает осуществление внутреннего (перебор значений Ьц) и внешнего (перебор значений циклов.

Рис. 5. Схема алгоритма ЬОМО

Криптостойкость алгоритма ЬОМЭ определяется, в частности, тем, что результат последовательного применения логических функций зависит, в общем случае, от порядка их применения.

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

Свойства симметричных таблиц сформулированы в виде доказанных утверждений, приведенных ниже:

• Симметричная таблица может сдержать только четное количество логических операций (четное количество строк).

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

• Таблица из симметричных таблиц также симметрична.

Использование в ЬОМБ симметричных таблиц логических функций

препятствует деградации строки хэша по мере вычисления.

Рассмотрены также приемы оптимизации алгоритма ЬОМБ. Например, вместо отдельных битов строки хэша и хэшируемой строки единицами (элементами), подвергающимися логической обработке, могут быть байты, 32- или 64-разрядные блоки, что может значительно ускорить обработку.

Далее принято, что Ь(Ь;т) - оператор хэширования ЬОМБ, преобразующий по предложенному способу строку хэша Ь в соответствии со значениями разрядов хэшируемой строки т. Доказаны следующие свойства алгоритма хэширования ЬОМБ:

• Если т3 = Ш! ' т2 (т3-конкатенация строк п^ и ш2), начальное значение строки хэша равно Ь0, а Ь] = Ь(Ь0;ш1), то Ь(Ь0;т3) = ЦЬ^Шг).

• Рационализованный алгоритм ЬОМБ позволяет для строки длиной ш3, большей, чем длина хэша (Ь), подобрать (ш3 - Ь -1) коллизий с длиной строки тС| < т3.

Благодаря первому из этих двух свойств, можно не вычислять хэш от всей строки, к которой добавились новые разряды, а продолжать вычисление с хэша прежней части строки. Это свойство означает также, что рационализованный алгоритм ЬОМБ приводит к наличию прогнозируемых (М - Н - 1) коллизий, которые легко выделить из коллизий, не являющихся продуктом алгоритма (где М — число разрядов хэшируемой строки, а Н -число разрядов хэша).

Это свойство рационализованного алгоритма ЬОМБ может быть использовано для анализа данных, для быстрого хэширования строк с

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

Второй алгоритм - это алгоритм хэширования с использованием псевдослучайной строки - PRBSH (PseudoRandom Binary Sequence Hash). Он разработан с целью: повысить криптостойкость, ускорить хэширование конкатенаций строк и обеспечить простоту смены кодирования.

На рисунке 6 приведена схема разбиения хэшируемой строки для вычисления хэша по одному из вариантов алгоритма PRBSH, а на рисунке 7 показана процедура его вычисления: m -хэшируемая бинарная строка, |т| -ее модуль (например, 110011=9), I - число разрядов в строке m, p¡- блоки по г разрядов, на которые разбита строка m, |p¡| - модули блоков p¡, к — число разрядов хэша, d, - отрезки псевдослучайной бинарной строки одинаковой длины (по к разрядов), H¡ - приближение хэша после учета очередного смещения по псевдослучайной бинарной строке.

Отрезки ллиной г исходной бинарной строки т.

Pi

Р2

Рз

Р4

Pi

т

Число разрядов

Рис. 6. Разбиение хэшируемой строки

От начала ПБС (рисунок 7) отсчитывают |ш| + 1 (как вариант) разрядов, затем отсчитываем еще к разрядов, которые и будут нулевым приближением (Н0) к-разрядного хэша. Отсчитывают далее число разрядов |после которых отсчитывают следующие к разрядов, образующих двоичную строку сЁ1. Первое приближение хэша равно Нх = Н0 © (II, где © - знак побитового сложения (ХОЯ). Для ¡-го приближения хэша Получим: Н1= Нм ф d¡.

Исследованы и другие варианты, в т.ч. с использованием сложения по модулю 2к (вместо побитового), и тогда Н; = (Ны + d¡)mod2k.

Показано, что алгоритм хэширования РИВБИ обеспечивает «лавинный эффект», позволяет легко регулировать характеристики, дает возможность

введения короткого и объективного идентификатора строк, хорошо приспособлен для модификаций.

Псевдослучайная бинарная строка (ПБС):

Бинарные отрезки строки Но ¿1 ¿2 ¿3 С1| ПБС

Число разрядов |т|+1 к ы к 1 Р21 к |Рз| к М 1Р,1 к №№ разрядов

N=1 Ц, = |т|+[ и^Мо.гИр.Мр,!

Приближения хэша: Но Н^Но©^ Нг=Н,&6г Н, =Н2 ®с1, Н,=Ни1®(1,

Рис. 7. Схема вычисления хэша по алгоритму НРКВБН. Сплошная линия - ПБС

Для формирования контрольного ядра по схеме, изображенной на рисунке 2, достаточно, чтобы для алгоритма хэширования РЛВ8Н выполнялось равенство Нщ = Ь(Н; • Это условие выполняется при

следующем порядке вычислений: для вычисления Н!+1 по схеме, приведенной на рисунке 7, первый отступ производят на число разрядов, равное |Щ (вместо суммы |ш|+1), а остальные отступы от р] до р, выполняют, разбивая строку Ь|+1 так, что = р!. р2..... р^ а длины строк р1—ре заданы, -остальные действия прежние.

В четвертой главе приведены способы использования предложенного в данной работе метода АН и предложенных алгоритмов хэширования.

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

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

Подсистема логирования (регистрации и обработки результатов) разработанной системы автоматизированного тестирования использует метод АН, что позволяет решить проблему обработки больших объемов выходных данных:

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

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

Рис. 8. Архитектура системы автоматизированного тестирования

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

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

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

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

Описано два разработанных при выполнении данного исследования изобретения: в одном способ АН использован для документирования данных, а алгоритм РНВБН - для повышения точности при передаче данных, другое предназначено для обработки данных, в частности, для хэширования.

В заключении отражены основные результаты, полученные в данной диссертационной работе:

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

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

3. Введено понятие симметричности таблиц логических функций и разработан алгоритм хэширования (ЬОМЭ) на основе таких таблиц.

4. Доказан ряд свойств алгоритма ЬОМБ, позволяющих: повысить эффективность метода АН, ускорить хэширование открытых строк, ускорить синхронизацию данных, распараллеливать вычисление хэша.

5. Доказана возможность получения заданного количества коллизий для ЬОМО-хэша.

6. Разработан и исследован алгоритм хэширования (РЯВЗН) с использованием псевдослучайной строки для оптимизации метода АН.

7. Показаны различные применения результатов данной работы.

Таким образом, в диссертационной работе разработан метод решения

актуальной задачи обеспечения объективного и доступного контроля целостности зарегистрированной конфиденциальной информации.

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

В изданиях по перечню ВАК:

1. Нураев И. Ю. Криптографическая хэш-функция на логических операциях / И. Ю. Нураев // «Военная электроника и электротехника» (Научно-технический сборник). - Мытищи, ФГУ «22 ЦНИИ Минобороны России». Выпуск 61.- 2009г.- С. 242-247.

2. Нураев И. Ю. Система хранения и обработки конфиденциальной информации, предоставляемой во временное пользование / И. Ю. Нураев, А. В. Штейнмарк // Военная электроника и электротехника (Научно-технический сборник). - Мытищи, ФГУ «22 ЦНИИ Минобороны России». Выпуск 61.-2009. С. 248-253

3. Нураев И. Ю. Разработка системы автоматизированного функционального тестирования интеграционных решений / И. Ю. Нураев // «Военная электроника и электротехника» (Научно-технический сборник). -Мытищи, ФГУ «22 ЦНИИ Минобороны России». Выпуск 62. - 2010. -С.267-273.

4. Нураев И. Ю. Схема защиты записей в системах хранения данных / И. Ю. Нураев // «Военная электроника и электротехника» (Научно-технический сборник). - Мытищи, ФГУ «22 ЦНИИ Минобороны России». Вып. 63, ч. 2. - 2011. - С. 76-86.

В прочих изданиях:

5. Нураев И. Ю. Автоматизация распределенного процесса разработки и сопровождения программного обеспечения / И. Ю. Нураев // Научная сессия МИФИ-2009. Секция: Информационные технологии. ISBN 978-5-7262-1042-1. - Москва: Московский инженерно-физический институт (государственный университет). — 2009. - Т.З. - С. 133.

6. Нураев И. Ю. Обработка результатов регрессионного тестирования по методам связанных хэшей / И. Ю. Нураев, К. Я. Кудрявцев // Научная сессия МИФИ-2013. Секция: Кибернетика и безопасность. ISBN

978-5-7262-11787-1. - Москва: Национальный исследовательский ядерный университет «МИФИ», 2013, т. 2. - С. 228.

Свидетельства о регистрации ПрЭВМ и патенты:

7. Способ измерения расстояния и устройство для этого (варианты): заявка на изобретение RU2008141062 / А. X. Абдуев., М. X. Абдуев, И. Ю. Нураев // Изобретения и полезные модели. Официальный бюллетень Федеральной службы по интеллектуальной собственности РФ № 20. — Москва: Роспатент. - 2009.

8. Экран и оптический коммутатор: заявка на изобретение RU2009112030 / А. X. Абдуев., М. X. Абдуев, И. Ю. Нураев // Изобретения, полезные модели. Официальный бюллетень федеральной службы по интеллектуальной собственности РФ №20. — Москва: Роспатент. — 2009.

9. Модуль вычисления хэша на логических операциях с бинарной строкой (Logical Operation Message Digest): свидетельство на программу для ЭВМ RU2011615029 / И. Ю. Нураев // Реестр программ для ЭВМ Российской Федерации. -Москва: Роспатент. -2011.

10. Distance Measuring Method and a Device for Carring out Said Method: Pub .No. W02010/044699 [Электронный ресурс] / A. Abduev, M. Abduev, I. Nuraev. - Режим доступа: http://patentscope.wipo.int/search/en/ W02010114417.-2010.

11. Display, "Electronic Paper" and an Optical Switch: Pub.No.W02010114417 [Электронный ресурс] / A. Abduev, M. Abduev, I. Nuraev. — Режим доступа: http://patentscope.wipo.int/search/en/ W02010044699.-2010.

12. Экран и оптический коммутатор: патент РФ на изобретение №2473936 / А. X. Абдуев., М. X. Абдуев, И. Ю. Нураев // Изобретения, полезные модели. - Москва: Роспатент Официальный бюллетень федеральной службы по интеллектуальной собственности РФ №3. — 2013.

Формат 60x90/16. Заказ 1678. Тираж 100 экз. Усл.-печ. л. 1,0. Печать офсетная. Бумага для множительных аппаратов. Отпечатано в ООО "ФЭД+", Москва, Ленинский пр. 42, тел. (495)774-26-96

ЗАКРЫТОЕ АКЦИОНЕРНОЕ ОБЩЕСТВО «ЗЕЛЕНОГРАДСКИЙ НАНОТЕХНОЛОГИЧЕСКИЙ ЦЕНТР»

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

04201357615

Нураев Имангазали Юнусович

МЕТОД И АЛГОРИТМЫ КОНТРОЛЯ ЦЕЛОСТНОСТИ КОНФИДЕНЦИАЛЬНЫХ ДАННЫХ НА ОСНОВЕ ФУНКЦИЙ

ХЭШИРОВАНИЯ

Специальность 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»

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

Москва 2013

Оглавление

Введение...............................................................................................................4

Глава 1. Анализ методов контроля целостности информации..............16

1.1. Целостность информации.....................................................................16

1.2. Существующие методы контроля целостности информации.......17

1.3. Контроль целостности информации с помощью хэширования ... 23

1.4. Патентный анализ..................................................................................31

1.5. Выводы по первой главе.......................................................................35

Глава 2. Метод контроля целостности информации................................37

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

2.2. Метод связанных хэшей........................................................................39

2.3. Контрольное ядро...................................................................................44

2.4. Алгоритм формирования контрольного ядра..................................49

2.5. Алгоритм контроля целостности компонентов записи..................53

2.5.1. Контроль целостности исходной строки.....................................53

2.5.2. Контроль целостности локального хэша....................................54

2.5.3. Контроль целостности связанного хэша.....................................54

2.5.4. Контроль целостности неполной записи.....................................55

2.5.5. Проверка записей на самосогласованность................................56

2.5.6. Проверка по эталону........................................................................64

2.5.7. Проверка по реперам.......................................................................65

2.5.8. Проверка по копиям........................................................................68

2.6. Обеспечение сохранности контрольного ядра.................................74

2.6.1. Программные способы восстановления контрольного ядра..76

2.6.2. Технические способы защиты контрольного ядра...................78

2.6.3. Организационные меры защиты контрольного ядра..............80

2.6.4. Юридическая поддержка метода связанных хэшей.................80

2.7. Разветвленное контрольное ядро........................................................81

2.8. Особенности метода АН........................................................................84

2.9. Выводы по второй главе.......................................................................87

Глава 3. Разработка и исследование алгоритмов хэширования............88

3.1. Хэш-функции в методе АН...................................................................88

3.2. Последовательное хэширование с использованием логических операций.............................................................................................................88

3.2.1. Принцип последовательного хэширования................................88

3.2.2. Алгоритм ЬОМБ..............................................................................90

3.2.3. Выбор логических операций для алгоритма ЬОМБ................95

3.2.4. Порядок применения логических операций.............................102

3.2.5. Оптимизация хэша ЬОМБ...........................................................105

3.2.6. Свойства хэша ЬОМ1>...................................................................105

3.2.7. Программные воплощения алгоритма ЬОМО........................109

3.3. Хэширование с использованием псевдослучайной строки..........109

3.3.1. Назначение хэш-функции РИВвН..............................................110

3.3.2. Хэширование с помощью псевдослучайной строки...............110

3.3.3. Анализ алгоритма РКВвН............................................................111

3.3.4. Графическая иллюстрация к РЯВБН........................................114

3.3.5. Алгоритм вычисления РИВвН-хэша.........................................115

3.3.6. Алгоритм РКВвН для конкатенаций строк хэшей.................117

3.4. Характеристики ЬОМБ и РБШБН.....................................................118

3.5. Выводы по третьей главе....................................................................119

Глава 4. Применения метода АН................................................................120

4.1. Сопряжение метода АН с СУБД......................................................120

4.2. Применение метода АН при тестировании программных решений............................................................................................................120

4.3. Метод АН для документирования безбумажного документооборота..........................................................................................124

4.4. Метод АН как инструмент доказательства в юриспруденции ... 124

4.5. Депонирование информации и метод АН.......................................125

4.6. Использование метода АН в банковских операциях....................125

4.7. Использование метода АН в корпоративном учете......................128

4.8. Использование метода АН в гридах и облаках..............................130

4.9. Техника: использование и обеспечение метода АН......................131

4.10. Выводы по четвертой главе...............................................................133

Заключение......................................................................................................134

Список источников........................................................................................135

Приложение А. Акты о внедрениях.........................................................146

Введение

Актуальность темы

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

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

По существующим оценкам более 90% компаний сталкивались с внутренними вторжениями, более половины сталкиваются с ними постоянно, а потери компаний только в США приближаются к 1 трлн. долл. США [2; 3, с. 3]. Большая часть потерь связана с действиями сотрудников самих этих компаний, так как существующие методы контроля целостности данных контролируются самими держателями БД. Причинами сознательного корпоративного или личного нарушения целостности информации [4, с. 29] -удаления, искажения, подмены - могут быть: месть, корысть, страх, принуждение, вандализм, любопытство, тщеславие, самоутверждение, карьерные идеи, конкуренция, диверсия, саботаж и другие. О части нарушений целостности данных держатель не сообщает, скрывая их, по разным причинам: из-за ответственности юридической и коммерческой, заботы о репутации, выгоды от произведенного нарушения, безответственности, низкой квалификации и т.п. О сокрытии держателями

БД известных им инсайдерских нарушений целостности данных сообщает 78% респондентов целевого опроса [5; 19] и порядка 90% процентов опрошенных при этом считают, что такое положение связано с нехваткой ресурсов для управления. Из последнего следует вывод, что использование существующих систем контроля целостности данных требует слишком больших усилий для обеспечения этого контроля и допускает сокрытие нарушений целостности данных.

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

В работе [3], посвященной предупреждению внутренних вторжений путем анализа действий персонала, приведены данные, что «более 30% времени работы отделов 1Т безопасности уходит на обнаружение следов уже случившихся внутренних вторжений», поэтому важно создание инструмента для постоянного, удобного, быстрого и надежного контроля целостности информации при ее хранении и передаче, чему посвящена данная работа.

Ниже отмечено значение контроля целостности информации в разных областях деятельности человека.

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

Национальная безопасность - значение контроля целостности информации для национальной безопасности иллюстрируется, например, тем, какие структуры созданы в США в соответствии с принятым «Национальным планом защиты информационных систем» [6, с. 12]:

- Совет по безопасности национальной инфраструктуры (№АС) и специальные центры компьютерной и информационной безопасности:

- в Пентагоне - Объединенный центр защиты сетей (ДТР-СМЭ),

- в ФБР - Национальный центр защиты инфраструктуры (№РС),

Национальный и Федеральный центры реагирования на компьютерные происшествия (N8111(1!, РеёСШС).

Эти структуры - с помощью специальной федеральной сети обнаружения вторжения (РГО№1;) - оповещают заинтересованные организации об угрозах информационной безопасности. Одним из приемов обнаружения вторжений является контроль целостности информации.

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

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

и принимаются необходимые законы, и при исполнении некоторых из них [8] контроль целостности информации является ключевым вопросом.

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

Юридическая область - это область, для которой достоверность сведений, свидетельств и документов является существенным моментом. Особое значение в нашей стране доказательство достоверности приобрело после закрепления в Конституции Российской Федерации принципа состязательности [9, ч. 3 ст. 123], когда доказывание в суде обстоятельств, на которые лицо, участвующее в деле, ссылается как на основание своих требований и возражений, возлагается на самих этих лиц. Надежный метод контроля целостности информации способен значительно облегчить всем сторонам судебных разбирательств оценку доводов и доказательств и поднять судопроизводство на качественно более высокий уровень.

На повышение доверия к представляемым документам, т.е. на подтверждение их целостности, направлена деятельность таких специально созданных организаций, как Intellectual Property Rights Management (IPRM), Intellectual Property Management (IPM), Digital Rights Management (DRM), Rights Management (RM), Electronic Copyright Management (ECM). Этому же служит множество исследований, разработок и патентов, таких, например, как патент США №6931545 [10].

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

созданных на основе принятых законов (в т.ч. части 4 ГК РФ) и международных договоров под эгидой Всемирной организации интеллектуальной собственности (ВОИС). Значение контроля целостности данных об интеллектуальной собственности чрезвычайно велико, как для частных лиц и компаний, так и для целых государств: например, «...самый большой доход от американского экспорта приходится на продажу за границу как раз интеллектуальной собственности» [11].

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

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

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

глобального позиционирования. Передача эталонных значений допустима только с точностью настолько близкой к 100%, что не обеспечивается простыми средствами. Для решения подобных задач применяются алгоритмы контроля информации на основе использования хэш-функций [12; 13]. Например, для синхронизации и восстановления справочной информации в сети баз данных Федерального агентства по техническому регулированию и метрологии, а также для предотвращения распространения ошибок по сети баз данных специально создана программа реализации алгоритма синхронизации на основе использования хэш-функций [14].

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

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

- это далеко не полный перечень приложений способов идентификации.

Для решения подобных задач НАТО подписало в 2012 году с итальянской компанией Finmeccanica и американской Northrop Grumman контракт на 67 млн. долларов на разработку, внедрение и обслуживание программы киберзащиты NCIRC (NATO Computer Incident Response Capability), что должно обеспечить цифровую безопасность примерно 50 объектов и штаб-квартир НАТО в 28 странах мира. Одна из функций NCIRC

- распознание угроз, т.е. их идентификация [15; 16]. Проект планируется расширить до 2,7 миллиарда долларов в следующие 3-5 лет.

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

Существуют многочисленные программные комплексы для защиты баз данных, Web-серверов и файловых серверов, обеспечивающие защиту от несанкционированного доступа к ним [18].

К широко известным и применяемым системам управления базами данных можно отнести: Microsoft Access, Microsoft Visual FoxPro, Microsoft SQL Server, Oracle, IBM DB2, и PostgreSQL . Известны и продолжают совершенствоваться ср�