Содержание к диссертации
Введение
Глава 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. Алгоритм LOMD 90
3.2.3. Выбор логических операций для алгоритма LOMD 95
3.2.4. Порядок применения логических операций 102
3.2.5. Оптимизация хэша LOMD 105
3.2.6. Свойства хэша LOMD 105
3.2.7. Программные воплощения алгоритма LOMD 109
3.3. Хэширование с использованием псевдослучайной строки 109
3.3.1. Назначение хэш-функции PRBSH 110
3.3.2. Хэширование с помощью псевдослучайной строки 110
3.3.3. Анализ алгоритма PRBSH 111
3.3.4. Графическая иллюстрация к PRBSH 114
3.3.5. Алгоритм вычисления PRBSH-хэша 115
3.3.6. Алгоритм PRBSH для конкатенации строк хэшей 117
3.4. Характеристики LOMD и PRBSH 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
- Контроль целостности информации с помощью хэширования
- Проверка записей на самосогласованность
- Свойства хэша LOMD
- Применение метода АН при тестировании программных решений
Введение к работе
Актуальность темы
Объективный контроль целостности информации чрезвычайно важен для национальной безопасности, работы гражданских институтов, связи и управления, сохранности научной и технической информации.
Более 90% компаний сталкивается с внутренними вторжениями, 78% инсайдерских нарушений целостности данных держатели скрывают, а пользователи не имеют возможности доказать факты таких нарушений.
Контроль целостности данных в условиях возможности злонамеренных действий (искажения, удаления, замены информации), особенно действий лиц с санкционированным доступом к базам данных и каналам связи, остается, к сожалению, нерешенной задачей.
Развитию технологий контроля целостности информации посвящена данная работа.
Объектом исследований в диссертационной работе являются конфиденциальные данные, выраженные в символьной форме, целостность которых требуется контролировать.
Предметом исследования являются алгоритмы и технология регистрации информации, обеспечивающие надежный контроль целостности.
Целью диссертационной работы является развитие математического обеспечения, методов и алгоритмов общедоступного, надежного и объективного контроля целостности информации.
Для достижения указанной цели поставлены следующие задачи:
-
развитие метода контроля целостности информации, основанного на формировании структуры связанных хэшей, и разработка алгоритмов контроля и восстановления этой структуры с использованием распределенного хранения;
-
разработка и исследование алгоритмов хэширования для оптимизации контроля целостности информации при хранении и передаче.
К поставленным задачам относятся также обеспечение:
-
конфиденциальности зарегистрированной информации;
-
регистрации данных без их сохранения;
-
свободного доступа к средствам контроля целостности информации.
Методы исследования, использованные в диссертационной работе -
это методы теории информации, дискретной алгебры, теории криптографии, статистического и эвристического анализа.
Научная новизна работы заключается в следующем:
-
-
Разработан и исследован метод (метод AH - Associated Hashes) контроля целостности зарегистрированной информации, основанный:
на формировании системы регистрирующих записей любой конфиденциальности на базе структуры взаимосвязанных хэшей данных;
на выделении из связанной системы регистрирующих записей части, названной в работе контрольным ядром;
на распространении контрольного ядра в информационной среде;
на обнаружении по контрольному ядру нарушений целостности любого из его компонентов при любом происхождении этих нарушений.
Введены понятия: «релевантность коллизий», «условная плотности коллизий», «самосогласованность» фрагментов контрольного ядра, «цепочка записей», - и с их использованием сформулирован и доказан ряд существенных свойств контрольных ядер (приведены далее), на основе которых разработаны способы частичного или полного восстановления их копий, распределенных в информационной среде.
Введено понятие симметричных таблиц логических функций и на их основе разработан алгоритм последовательного хэширования LOMD (Logical Operation Message Digest), позволяющий распараллеливать вычисление хэша.
Доказаны свойства алгоритма LOMD, позволяющие ускорить формирование контрольного ядра.
Разработан и исследован алгоритм хэширования с использованием псевдослучайной строки PRBSH (PseudoRandom Binary String Hashing), оптимизирующий формирование контрольных ядер.
Предложено оптоэлектронное устройство для хэширования.
Практическая значимость.
Разработан совместимый с существующими СУБД метод контроля целостности информации, которая может храниться у произвольного держателя, на произвольном носителе и быть конфиденциальной. Метод AH создает возможности контроля целостности зарегистрированной информации без обращения к регистратору данных и позволяет практически исключить бесследное ее изменение.
Предложенные в работе алгоритмы хэширования
обеспечивают эффективность метода AH;
позволяют легко управлять свойствами хэш-функций;
имеют самостоятельное значение в качестве инструментальных средств для других применений (не связанных с методом AH).
Метод AH создает новые возможности для документирования юридической, финансовой, технической и любой иной информации.
Внедрение результатов работы.
Развитый в работе метод AH использован: в ЗАО «Синимэкс- Информатика» (для оптимизации тестирования интеграционных банковских решений); в ЗАО «КБ Технотроник» (для организации безбумажного документооборота в системе менеджмента качества (СМК), а также для повышения доверия партнеров путем передачи им контрольного ядра СМК); при разработке эталонного дальномера (для уменьшения погрешностей и документирования эталонных измерений).
Основные научные положения и результаты, выносимые на защиту:
Метод и алгоритмы контроля целостности информации путем формирования структуры взаимосвязанных данных и хэшей, выделения из них контрольного ядра и множественного произвольного размещения его в информационном пространстве с возможностью автономного полного или частичного его восстановления.
Математическое обоснование, разработка и исследование свойств функций хэширования на логических операциях и на псевдослучайной строке.
Апробация работы
Результаты, полученные в ходе выполнения диссертации, докладывались на семинаре кафедры № 36 МИФИ («Кафедра информационных систем и технологий»), на семинаре ЗАО «Зеленоградский нанотехнологический центр», на научных сессиях МИФИ в секциях «Информационные технологии» и «Кибернетика и безопасность». По результатам диссертационной работы опубликованы: 4 статьи [1-4] в рецензируемом издании из списка ВАК, тезисы двух докладов на научных сессиях МИФИ [5; 6], две заявки на получение патентов РФ на изобретения [7; 8], две международные заявки [10; 11], по которым получены положительные заключения по тем же изобретениям, - а также зарегистрирована программа для ЭВМ [9] и получен патент РФ на изобретение [12].
Личный вклад автора
Все научные и практические результаты диссертации получены автором лично.
Структура и объем работы
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Основное содержание работы изложено на 145 страницах и включает 29 рисунков и 12 таблиц. Список использованных источников содержит 137 наименований.
Контроль целостности информации с помощью хэширования
Более надежными, чем упомянутые выше методы «четности», «контрольных сумм», «циклического контрольного кода» и «турбо-кода», могут быть методы, построенные на использовании однонаправленных криптографических функций хэширования [44, с. 321-384].
Анализ целостности отдельного объекта (текста, файла) может быть основан на вычислении хэша этого объекта по согласованному алгоритму [55] и на последующем сравнении его с исходным хэшем проверяемого объекта, в верности которого нет сомнений. Подобный анализ используют при синхронизации данных [56, п. 3.1.3 и др.], при архивировании [57], при резервировании [58] при осуществлении цифровой подписи [59], а также при других процедурах.
Однако этот метод уязвим, т.к. при преднамеренном нарушении целостности информации, особенно если нарушение производится лицом с санкционированным доступом, может быть заменен и ее контрольный хэш.
Отдельным сформировавшимся направлением контроля целостности данных является регистрация времени поступления данных, использующая средства для обнаружения нарушения их целостности задним числом - TSP (Time-Stamp Protocol). Этому направлению уделено внимание во многих работах: от ранних ([60] и [61]) до одной из последних [62]. Принцип регистрации данных в этих работах основан на формировании цепочки связанных хэшей (hash-chain based protocols for time-stamping and secure logging) по схеме, приведенной на рисунке 3, и на закреплении регистрации путем публикаций, что позволяет обнаруживать нарушения целостности данных, произведенных задним числом.
Метод заключается в том, что регистрируемую информацию подвергают хэшированию (получают ее хэш h), затем вычисляют связывающий хэш Н, учитывающий h и значение предыдущего связывающего хэша. Каждый N-ый связывающий хэш публикуют.
Средствам закрепления регистрации средств хранения и обработки во внешней информационной среде посвящен ряд работ, например [63], в которой предложено проводить регистрацию с использованиям п серверов, из которых в каждом акте регистрации участвует к выбранных случайным образом серверов, результаты работы которых анализируются по заданному алгоритму. Такой способ повышает устойчивость, например, к DDoS-атакам.
Для регистрации данных оператору TSP - в соответствии со схемой на рисунке 4 - направляют хэш этих данных и получают в ответ заверенную электронными средствами посылку, включающую регистрируемый хэш (хэш регистрируемых данных), время его регистрации и криптографическую метку, например соответствующий связывающий хэш (Н на рисунке 3).
Описанный выше способ TSP обладает значительным потенциалом, частично использованным в данной работе. Недостатком способа TSP является то, что контроль целостности зарегистрированной в специальной базе данных информации, может осуществлять только держатель этой БД по хранящейся у него системе хэшей, а публикуемые отдельные хэши (каждый N-ый, например) не дают пользователю возможностей для самостоятельного контроля целостности информации - ими непосредственно может воспользоваться лишь держатель БД, если пожелает. Если же не пожелает, то контроль целостности оказывается недоступен для пользователя - т.е. контроль целостности информации зависит от воли ограниченного круга лиц, т.е. необъективен и уязвим.
Исследование литературных источников показало, что задача обеспечения контроля целостности информации, устойчивого к воздействию любой группы лиц и доступного для осуществления любым пользователем без обращения к держателю зарегистрированных данных не ставилась и не решалась.
Алгоритмы хэширования
Функции хэширования должны обеспечивать сжатие данных (получение хэша), должны просто вычисляться (не выше, чем с полиноминальной сложностью) и могут быть бесключевыми (зависящими только от сообщения) или с секретным ключом (зависящие от сообщения и от секретного ключа) [44; 65; 66]. К бесключевым хэш-функциям относятся коды обнаружения изменений (modification detection codes, MDC-коды), к которым предъявляются требования необратимости (вычислительная невозможность восстановления данных по их хэшу, однонаправленность), стойкости к коллизиям первого рода (вычислительная невозможность нахождения второго сообщения с хэшем, как у данного), стойкость к коллизиям второго рода (вычислительная невозможность нахождения пары сообщений с совпадающими хэшами). Такие хэш-функции называются криптографическими. Они оцениваются по отсутствию корреляций между входными и выходными битами, по стойкости к близким коллизиям (вычислительная невозможность коллизий, отличающихся малым количеством бит), по стойкости к частичной однонаправленности (вычислительно невозможно восстановить часть исходного сообщения), по возможности растягивания (возможность хэширования коротких сообщений) и др. [67]. При этом n-битная хэш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для неё близка к 2" , т.е. к среднему числу атак «дней рождения» для хэша длиной в п разрядов. Атаки, не зависящие от алгоритма: атака "грубой силой", атака методом "дня рождения", полный перебор ключей. При таких атаках уязвимы все алгоритмы, единственная возможность противостоять им — увеличить длину хэш-значения [68, с. 29-30].
Список распространенных алгоритмов хэширования включает: Adler-32, CRC, SHA-1, SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512), HAVAL, MD2, MD4, MD5, N-Hash, RIPEMD-160, Snefru, Tiger (TTH), Whirlpool, ГОСТ P34.11-94 (ГОСТ 34.311-95), IP Internet Checksum (RFC 1071).
Схема алгоритма вычисления значения хэш-функции по российскому стандарту [69] приведена на рисунке 5.
Обозначения:
- Hj - i-oe приближение хэш-функции в виде строки длиной 256 бит (Hj - произвольное);
- nij - i-ый блок длиной 256 бит, на которые разбита хэшируемая строка (дополняется при необходимости нулями);
- f - шаговая функция хэширования, которая отображает два блока длиной 256 бит в один блок длиной 256 бит;
Шаговая функция хэширования f состоит из трех частей:
генерирования ключей Кь К2, К3, К}, каждый из которых представляет собой 256-битную строку, получаемую путем побитового сложения Н; и Ш, многократного перемешивания блоков различной длины, на которые эти строки разбиваются, и побитового сложения с заданными тремя константами;
шифрующего преобразования — шифрования с использованием ключей Кь К2, К3, Кд по стандарту криптографического преобразования [70], основанного на сети Фейстеля [71];
перемешивающее преобразование результата шифрования.
После применения функции f ко всем блокам nij и соответствующим промежуточным значениям НІ ее применяют к длине входного сообщения по модулю 2256 с Hn+i и к контрольной сумме mi+m2+...+mn с Н„+2. В результате получают хэш входного сообщения.
Схема алгоритма хэширования по российскому стандарту является вариантом итерационной цепочки Меркле-Дамгарда [72; 73], изображенной на рисунке 6.
Проверка записей на самосогласованность
Проверкой на самосогласованность, в соответствии с приведенным в п. 2.2 определением, назовем проверку целостности контрольного ядра путем вычисления одних его элементов через другие и сравнения результатов вычислений с соответствующими хранящимися значениями.
В случае несовпадения вычисленного значения связанного хэша записи с хранящимся проверяемым значением делается вывод о нарушении целостности данной записи: либо нарушена целостность одного связанного хэша данной записи, либо и локального тоже, - об этом делается в установленном порядке соответствующая пометка в служебной строке. Присвоим этой нарушенной записи номер к. Следующей подвергаем проверке не запись под № (к + 1), а запись под № (к + 2), т.к. не располагаем верным значением Нк, необходимым для вычисления Нк+1. Если проверка строки № (к + 2) покажет, что вычисленное значение связанного хэша для нее совпадает с проверяемым Нк+2, то делаем вывод, что целостность строки № (к + 2) не нарушена условно. Кроме того, можно сделать и вывод, что не нарушен условно и связанный хэш Hk+i строки № (к + 1).
Для завершения проверки пропущенной записи № (к + 1) в описываемом случае недостаточно информации, но если будут представлены значение локального хэша этой строки и связанного хэша предыдущей строки, при учете которых будет получено верное значение связанного хэша Hk+i, то этих данных, учитывая описанную выше проверку, будет достаточно для вывода об условной целостности представленной информации и для восстановления значения связанного хэша Нк.
«Условно не нарушена» или «условно целостна» означает выше и далее согласованность с окружающими записями, т.е. локальную самосогласованность ядра.
Определение 8. Самосогласованный ряд (п. 2.2) последовательных записей (двух и более) контрольного ядра назовем условно целостным, если нет доказательств целостности (безусловной целостности) этого ряда.
Определение 9. Самосогласованный ряд последовательных записей контрольного ядра назовем целостным, если все составляющие его неполные записи целостны.
Соглашение 2. Далее под словом «доказательство», когда оно опирается на вычислительную невозможность нахождения релевантных коллизий при использовании криптографических хэш-функций, условно предполагается тождественность «невозможности» и «вычислительной невозможности», т.е. предполагается доказательство утверждения, справедливого не в меньшей степени, чем упомянутая вычислительная невозможность. Использование при изложении такой условности обусловлено тем, что зависимость трудоемкости получения конкретных примеров нарушения доказываемых ниже свойств от трудоемкости получения коллизий для используемых хэш-функций легко вычисляется для каждого конкретного случая, а формулировки с детальным учетом вероятностей неоправданно громоздки.
Свойство 1. Если целостна какая-либо запись, входящая в условно целостный ряд записей контрольного ядра, то целостны и все предшествующие ей записи этого ряда.
Доказательство. Пусть доказана целостность неполной записи № і непрерывной последовательности условно не нарушенных записей. Тогда, по определению условной ненарушенности ряда, связанный хэш этой записи НІ является хэшем конкатенации относящейся к записи № (і - 1) (в случае, если неполная запись № і - не первая в рассматриваемой последовательности) строки связанного хэша Ни и строки локального хэша h;. При целостном НІ это возможно (с учетом соглашения 2) только при целостности связанного хэша Ни. Если связанный хэш Ни целостен, то, благодаря самосогласованности ряда, целостен и локальный хэш Ьи строка которого входит в конкатенацию строк, для которой вычислен Ни (в предположении исчезающе малой вероятности коллизий) Далее, по индукции, целостными являются все предыдущие неполные записи до начала данного условно ненарушенного участка контрольного ядра.
О целостности записей условно целостного ряда, следующих за целостной записью № і, нельзя сказать определенно, целостны они или только условно целостны, т.к. самосогласованности ряда можно было добиться и подменой всех записей с номерами больше і. Свойство 2. Связанный хэш нецелостной записи условно целостного ряда не целостен (нарушен).
Доказательство. Пусть запись № і условно целостного ряда не целостна. Это значит, что не целостен ее локальный хэш hi, либо не целостен ее связанный хэш Нь либо не целостны оба этих хэша. Вариант целостности связанного хэша НІ при не целостном локальном хэше hj считаем (соглашение 2) невозможным из-за вычислительной невозможности нахождения релевантных коллизий при используемой хэш-функции, т.к. НІ является, в соответствии с условной целостью ряда, хэшем строки, в которую входит и строка локального хэша hj. Следовательно, у нецелостной записи условно целостного ряда связанный хэш обязательно нарушен.
Свойство 3. Если не целостна (нарушена) хотя бы одна из входящих в условно целостный ряд неполных записей, то нецелостными являются и все последующие неполные записи этого ряда.
Доказательство. Пусть доказана нецелостность неполной записи № і. Тогда из свойства 2 следует, что не целостен ее связанный хэш Hj. Это означает, что в контрольное ядро, по меньшей мере в связанный хэш НІ, задним числом были внесены изменения. Из условной целостности ряда следует, что связанный хэш Ні+1 следующей записи получен для конкатенации строк, содержащей нарушенную строку хэша Н;, поэтому он не мог (это вычислительно невозможно) сохранить исходное (целостное) значение, которое имел до внесения изменений в контрольное ядро. Далее, по индукции, следует, что все неполные записи этого ряда не целостны.
Подобная ситуация возникает при нарушении целостности, например при целенаправленной замене, всех записей, начиная с записи № і с целью локальной маскировки подмены нужной записи. Свойство 4. Если целостен связанный хэш неполной записи, входящей в условно целостный ряд, то целостен и локальный ее хэш, т.е. целостна данная неполная запись.
Доказательство. Предположив, что локальный хэш неполной записи, не целостен, придем к противоречию, т.к. запись принадлежит условно целостному ряду, в котором эти хэши согласованы.
Сформулируем и докажем более сильное свойство, чем свойство 1.
Свойство 5. Если целостен связанный хэш одной из неполных записей, входящих в условно целостный ряд, то целостны и все предыдущие неполные записи этого ряда.
Доказательство. Пусть доказана целостность связанного хэша Hj условно целостной записи № і, входящей в условно целостный ряд. Тогда из свойства 4 следует, что целостна вся данная неполная запись. Целостность данной входящей в условно целостный ряд записи влечет за собой, благодаря свойству 1, целостность и всех предыдущих неполных записей этого ряда.
Подобное утверждение в отношение целостного локального хэша, неверно, т.к. он не связан с предыдущей частью контрольного ядра, поэтому связанный хэш предыдущей записи может быть взят произвольным, а последующий вычислен с учетом этого.
Методика проверки контрольного ядра на самосогласованность включает: - (1) последовательное, начиная с корневого хэша Н0, вычисление связанных хэшей каждой последующей записи по описанной выше процедуре и сравнение полученного значения с хранящимся в контрольном ядре в этой записи - до первого несовпадения вычисленного и хранящегося связанного хэша записи (поврежденная запись)
Свойства хэша LOMD
Алгоритм LOMD обладает, в частности, очень полезным для применения в методе АН свойством: он совмещает процедуры объединения (конкатенации) строк и вычисления хэша от полученной строки. Покажем это.
Пусть L(ho;m) - оператор хэширования, преобразующий по рационализированному алгоритму LOMD начальную строку хэша h в соответствии со значениями разрядов хэшируемой строки т.
Тогда хэш-функцией строки m будет строка h(m) = L(h0; m).
Утверждение 7. Если: m3 = mi х m2 (віз является конкатенацией строк mi и т2), начальное значение строки хэша равно h0, a hj = h(mi) = L(ho; ті), то L(h0;m3) = L(hi;m2).
Доказательство. По определению оператора L(h;m), хэш строки т3 равен h3=L(ho;m3).
Т.к. процедура хэширования предполагает последовательную обработку значений разрядов хэшируемой строки (т3 = тг х т2), можно рассмотреть промежуточное значение хэша при завершении обработки первой составляющей (itij) конкатенации строк (тз): hi = L(ho;m!).
Тогда, по определению оператора L(h;m), h3 = L(hi;m2) и, следовательно, L(h0;m3) = L(hi;m2).
Т.е., хэш строки можно вычислить по хэшу начальной ее части и по содержанию остальной части строки. Кроме того, хэш от конкатенации строк равен хэшу от конкатенации хэша одной составляющей строки с другой составляющей.
Из последнего утверждения (утверждение 7) следует также, что рационализованный алгоритм LOMD предусматривает наличие прогнозируемых коллизий, которые легко выделить из коллизий, не являющихся продуктом алгоритма.
Утвериедение 8. Рационализованный алгоритм LOMD позволяет для строки длиной т3, большей, чем длина хэша (h), подобрать (т3 - h - 1) коллизий с длиной строки mCj m3.
Доказательство. Это следствие того, что Ь(шз) = L(hj х т2): строки тз и (hi х т2) — это разные строки, а хэши их совпадают. Первые Н разрядов строки т3 являются хэшем нулевого порядка (исходным для вычисления L(m3), а остальные (т3 - Н) разряда подлежат обработке. После обработки разряда с номером (Н + 1) получим хэш первого порядка прежней длины, общая длина строки сократится на один разряд, а не подвергнутыми хэшированию останутся (m3 - Н - 1) разрядов. По рационализованному алгоритму LOMD первые Н разрядов каждой конкатенации являются хэшем нулевого порядка для этой конкатенации. Всего имеется (тз - Н) строк с длиной больше Н и не больше т3, имеющих одинаковый хэш LOMD. Исключая из этого числа случай полной строки тз, получаем число (т3 - Н -1) коллизий, т.е. сама строка тз и еще (т3 - Н - 1) строк, каждая из которых является конкатенацией очередного приближения хэша и необработанного остатка строки тз, имеют одинаковый хэш.
Если две строки, имеющие одинаковый LOMD-хэш (коллизия), имеют одинаковое окончание любой длины, а начала строк отличаются тем, что одно из них является LOMD-хэшем другого, то коллизия относится к контролируемым и не может считаться коллизией в полном смысле этого слова (релевантной коллизией). Это свойство рационализованного алгоритма LOMD может быть использовано для анализа данных, для обеспечения конфиденциальности части данных, для быстрого хэширования открытых для записи строк и т.д. Оно может быть использовано и для реализации электронной подписи, т.к. позволяет формировать множество различных строк с одинаковыми значениями хэша (контролируемыми коллизиями): например, получатель знает только хэш, а отправитель знает достаточно длинную строку т3 и использует в первый раз строку длиной Н + 1, состоящую из предпоследнего приближения хэша и последнего разряда строки т3, в следующий раз - строку длиной Н + 2, состоящую из предшествующего упомянутому приближения хэша и последних двух разрядов строки т3, и т.д. — а получатель хэширует полученную строку и сравнивает с имеющимся хэшем, а строку сохраняет в качестве запрещенной для дальнейшего применения подписи.
Последовательный характер обработки разрядов при использовании алгоритма LOMD дает новую возможность для распознавания данных и синхронизации баз данных. При вычислении хэша от проверяемой строки совпадение его значения на каком-либо этапе вычисления с хэшем хранящейся строки будет означать, что проверяемая строка является продолжением этой хранящейся строки. Преимущество перед поиском непосредственно по строке начальных разрядов в том, что можно использовать хэш длиной значительно меньше строки начальных разрядов и, кроме того, использование хэша позволяет сохранить определенную степень конфиденциальности. В таблицах хэшей, используемых для обозначения файлов в базах данных, может быть при этом использовано обозначение одного и того же файла не одним, а двумя или несколькими значениями хэшей, соответствующих разному числу обработанных разрядов.
Другими полезными качествами алгоритма LOMD являются неограниченность длины хэшируемой строки и возможность распараллеливания операций при вычислении хэша.
Неограниченность длины хэшируемой строки обеспечена тем, что количество одновременной обрабатываемой информации при использовании алгоритма LOMD и используемый набор логических операций не зависят от длины строки.
Возможность распараллеливания операций связана с тем, что при применении алгоритма LOMD разряды строки хэша, обработанные очередным разрядом хэшируемой строки, могут сразу же затем обрабатываться следующим разрядом хэшируемой строки, и нет необходимости ждать, пока с помощью одного из разрядов хэшируемой строки будут обработаны все разряды строки хэша. В рационализованном LOMD можно одновременно обрабатывать каждый четвертый разряд строки хэша, и скорость обработки при этом может, в зависимости от вычислительных возможностей, возрасти в Н/4 раз при побитовой обработке. Поблоковая обработка еще более значительно ускоряет процесс.
Применение метода АН при тестировании программных решений
Существование множества автоматизированных систем, построенных зачастую на различных технологических платформах, обуславливает появление такой важной задачи, как создание среды, обеспечивающей интеграцию приложений и данных [24]. При этом вопрос о проведении тестирования подобных решений необходимо решать особо, т.к. многочисленные чрезвычайно развитые и сложно структурированные системы требуют специализированных программных средств для автоматического осуществления такого внедрения [121—123]. Существенной частью внедрения приложения является тестирование всех компонентов взаимодействия системы и приложения [124].
Опыт показывает, что при проведении тестирования интеграционных решений возникают проблемы, связанные:
с большим количеством связанных систем;
с задержками при проведении тестирования из-за «неготовности» одной из систем;
со сложностями с локализацией дефекта;
с большим объемом данных;
с «белыми пятнами» аналитики, связанными с интеграцией; с человеческим фактором при сверке данных. С учетом сетевой специфики предложенного метода АН было решено разработать систему, обеспечивающую:
возможность взаимодействия с несколькими внешними системами одновременно;
возможность параллельного запуска тестовых сценариев;
удобный анализ результатов тестирования;
возможность мониторинга изменений в БД;
возможность создания собственных адаптеров к внешней системе;
возможность взаимодействия по WebSphere MQ и WebService Soap/HTTP и др. в одном продукте;
минимизацию трудоемкости создания тестов.
Для системы автоматизированного тестирования была разработана архитектура, представленная на рисунке 27.
Согласно разработанной архитектуре система состоит из 6 модулей.
Модуль настроек используется для управления настройками проекта такими как, например, описание тестового окружения (очереди WebSphere MQ, точки подключения к WebSphere через soap/http), загрузка файлов мнемоник для xpath-выражений и регулярных выражений, настройка параметров журнала выполнения тестов и пакетов тестов, создание переменных в контексте пакета тестов и местонахождение файлов мнемоник.
Под результатами тестирования понимаются различные xml-документы, которые формируются в рамках функционирования системы.
При проведении тестирования интеграционных решений огромную роль играет регрессионное тестирование, необходимость которого обусловлена постоянным динамическим развитием/изменением тестируемых систем. В рамках регрессионного тестирования серьезной проблемой становится сравнение результатов тестирования на одних и тех же тестовых примерах. Сложность состоит в необходимости локализации расхождения в выходных данных при условии их большого объема.
Подсистема логирования разработанной системы автоматизированного тестирования использует метод связанных хэшей, что позволяет решить проблему обработки больших объемов выходных данных:
При первичном тестировании выходные данные регистрируются в хранилище результатов тестирования, представляющем собой БД с реализованным механизмом формирования связанных хэшей.
Для данной базы генерируется контрольное ядро, где локальным хэшем является хэш одного выходного набора данных представляющего собой одну запись в БД.
При каждом последующем тестировании отпадает необходимость в полном сравнении данных и достаточно сравнения значений связанных хэшей. Сравнение локальных хэшей осуществляется только в случае несоответствия связанных.
Возможно использование двух подходов по сравнению выходных данных:
Связанные хэши сравниваются по мере их расчета, что дает возможность остановить испытания сразу при обнаружения несоответствия.
Связанные хэши сравнивают, начиная с записей с максимальными номерами. Если связанные хэши не совпали, то сравнивают связанные хэши с меньшими номерами (последовательно или по иному выбранному алгоритму). Если хеши с каким-либо номером совпали, то все записи с меньшими номерами можно считать совпавшими, благодаря свойству контрольного ядра, - это значительно ускоряет сравнение результатов тестирования.
Результаты каждого последующего тестирования так же сохраняются в базе, причем расширение набора выходных данных по каждому из примеров не является помехой: для нового, более полного, набора выходных данных создается параллельное контрольное ядро.
Использование данного метода, помимо упрощения сравнения результатов тестирования, избавляет от необходимости хранить старые результаты или каждый раз прибегать к перегенерации данных.
В настоящее время система находится в промышленной эксплуатации и параллельно, по мере необходимости, осуществляется ее развитие.
Похожие диссертации на Метод и алгоритмы контроля целостности конфиденциальных данных на основе функций хэширования
-
