Криптопрограммирование
Криптопрограммирование посредством использования инкрементальных алгоритмов
Одним из основных инструментов методологии криптопрограммирования являются инкрементальные алгоритмы. Цель инкрементальной криптографии заключается в разработке криптографических алгоритмов обработки электронных данных, обладающих следующим принципиальным свойством. Если алгоритм применяется к электронным данным D для достижения каких-либо их защитных свойств, то применение инкрементального алгоритма к данным D, подвергнувшихся модификации - D`, должно осуществляться быстрее, чем необходимость заново обработать данный документ. В тех приложениях, когда указанные алгоритмы являются, например, алгоритмами шифрования электронных документов или их цифровой подписи, требование повышения эффективности инкрементальных алгоритмов является крайне желательным. Один из основных методов применения инкрементальных алгоритмов заключается в использовании их аутентификационных признаков для антивирусной защиты.
При обработке электронных документов инкрементальными алгоритмами рассматриваются такие операции обработки данных как "вставка" и "стирание" для символьных строк или "cut" - "вырезание и помещение в буфер" и "paste" - "извлечение из буфера и вставка" для текста. Основная задача здесь заключается в разработке эффективных инкрементальных алгоритмов для схем цифровой подписи и схем аутентификации сообщений, поддерживающих вышеупомянутые операции по модификации электронных данных. Такие алгоритмы должны обладать основным качественным свойством, а именно свойством "защиты от вмешательства", что, таким образом, и делает их применимыми для защиты программ от вирусов и других разрушающих программных средств. Основные криптографические примитивы, такие как шифрование и цифровая подпись имеют фундаментальную теоретическую базу. Во многих работах (см., например, обзор в работе []) были даны базовые определения их криптографической стойкости, основанные на обобщенных теоретико-сложностных и теоретико-информационных предположениях.
Главная проблема, которая остается и затрудняет использование на практике многих доказуемо стойких теоретических криптоконструкций, заключается в их пространственно-временной неэффективности. Инкрементальность, в этом смысле, является новой мерой эффективности, которая является вполне приемлемой во многих алгоритмических приложениях.
Пусть далее рассматривается процессор, защищенный от физического вмешательства, который имеет ограниченное количество безопасной локальной памяти. Необходимо получить доступ к файлам, находящихся на удаленных (возможно небезопасных) носителях, например, хост-станциях или www-серверах. Компьютерный вирус может атаковать удаленную станцию, и исследовать и изменять содержание удаленной информационной среды (но при этом он не имеет доступа к безопасной локальной памяти процессора). Для защиты файлов от таких вирусов, процессор вычисляет для каждого файла аутентификационный признак, как функцию от самого файла и ключа, который хранится в безопасной локальной памяти.
Внедрение вируса в файл не позволяет ему заново вычислять признак, и при реализации процесса верификации признака, таким образом, обнаружится вторжение вируса. Следует обратить внимание на то, что для корректной верификации аутентификационного признака защищенный процессор должен заново подтвердить подлинность файлов. Ясно, что наиболее привлекательным способом является модернизация аутентификационного признака быстрее, чем необходимость его вычисления заново. Эта проблема особенно сложна в том случае, когда локальная память не достаточно большая для того, чтобы хранить (даже временно) фрагмент файла или когда "слишком дорого" ввести в локальную память полный файл.
Идея инкрементальных алгоритмов, состоит в том, чтобы воспользоваться какими-либо имеющимися преимуществами такой организации программно-аппаратного взаимодействия и найти способы криптографических преобразований над электронными данными D не заново, а, скорее, как получение быстродействующей функции от значений криптографических преобразований над данными из которых D был получен.
Когда "изменения" не велики, инкрементальные методы могут дать большие преимущества по эффективности.
Основные элементы инкрементальной криптографии
Примитивы. Инкрементальность можно рассматривать для любого криптографического примитива. В данном случае рассматриваются два из них - цифровая подпись и шифрование. Инкрементальность далее рассматривается, как правило, для "прямых" преобразованиях, а именно для генерации подписи и шифровании, но все рассуждения будут верны и для "сопряженных" преобразований, а именно для верификации подписи и дешифрования.
Операторы модификации. Рассмотрим проблему модификации защищаемого файла в терминах применения фиксированного набора основных операций по модификации электронного документа. Например: замена блока в документе другим; вставка нового блока; удаление старого блока. Операции должны быть достаточно "мощны" для демонстрации реальных модификаций таких как: замена, вставка и удаление. Соответственно также рассматриваются операции "cut" и "paste", например, операции разбиения отдельного документа на два, а затем, вставка двух документов в один.
Инкрементальные алгоритмы. Зафиксируем базовое криптографическое преобразование T (например, цифровая подпись документа с некоторым ключом). Каждой элементарной операции модификации текста (например, вставки) будет соответствовать инкрементальный алгоритм I. На вход этого алгоритма подаются: исходный файл; значения преобразования T на нем; описание модификаций; и возможно соответствующие ключи или другие параметры. Это позволит вычислить значение T для результирующего файла. Основная проблема здесь заключается в проектировании схем обработки файлов, обладающих эффективными инкрементальными алгоритмами. Предположим, что имеется подпись ?old для файла Dold и файл D'old, измененный посредством вставки в файл Dold некоторых данных. Необходимо получить подпись путем подписывания строки, состоящей из ?old и описания модификаций над документом Dold.
Это схема называется схемой, зависящей от истории. Могут иметься приложения, когда такие действия являются приемлемыми. В большинстве же случаев это не желательно, так как делается большое количество изменений и затраты на верификацию подписи пропорциональны числу изменений. В связи с этим размеры подписи растут со временем. Чтобы избежать таких затрат необходимо использовать схемы, свободные от истории или HF-схемы. Все нижеприведенные схемы являются схемами, свободными от истории.
Безопасность. Свойство инкрементальности вводит новые проблемы безопасности и вызывает необходимость новых определений. Рассмотрим случай схем подписи и аутентификации. Разумно предположить, что противник не только имеет доступ к предыдущим подписанным версиям фалов, но также способен выдавать команды на модификацию текста в существующих файлах и получать инкрементальные подписи для измененных файлов. Такая атака на основе выбранного сообщения для инкрементальных алгоритмов подписи может вести к "взлому" используемой схемы подписи, которая не может быть взломана при проведении противником других атак, в тех случаях, когда не используются инкрементальные алгоритмы. Кроме того, в некоторых сценариях, например, при вирусных атаках можно предположить, что противник вмешивается в содержание существующих документов и аутентификационных признаков, полученных посредством схем подписи/аутентификации. Соответственно рассматриваются два определения безопасности: базовое и более сильное понятие безопасности, когда доказывается стойкость защиты от вмешательств.
Секретность инкрементальных схем. Исходя из вышесказанного, появляется новая проблема, которая проявляется в инкрементальном сценарии, а именно - проблема секретности различных версий файлов. Предположим ? - подпись кода М и ?' является подписью слегка измененного кода M'. Тогда, наилучшим вариантом было бы получить такую подпись ?', которая давала бы как можно меньше информации, об оригинальном коде М.
Метод защиты файлов программ посредством инкрементального алгоритма маркирования
Основные определения. Пусть АУТ(m) - обычный алгоритм аутентификации сообщений и АУТa(m)- функция маркирования сообщения m, индуцированная схемой АУТ с ключом аутентификации a. Пусть ВЕРa(m,?) - соответствующий алгоритм верификации, где ?={true, false} - предикат корректности проверки.
Далее будут использоваться деревья поиска и, следовательно, необходимо напомнить, что 2-3-дерево имеет все концевые узлы (листья) на одном и том же самом уровне/высоте (как и в случае сбалансированных двоичных деревьев) и каждая внутренняя вершина имеет или 2, или З дочерних узла []. В данном случае 2-3-дерево подобно двоичному дереву является упорядоченным деревом и, таким образом, концевые узлы являются упорядоченными. Пусть Vh - определяет множество всех строк длины не больше h, ассоциированных очевидным способом с вершинами сбалансированного 2-3-дерева высоты h. Маркированное дерево может рассматриваться как функция Т: Vh - >{0,1}*, которая приписывает аутентификационный признак (АП) каждой вершине.
Пусть совокупный аутентификационный признак файла F получен посредством использования 2-З-дерева аутентификационных признаков каждого из блоков файла F=F[1],...,F[l] (далее такое дерево будет называться маркированным деревом). Каждая вершина w ассоциирована с меткой, которая состоит из АП (аутентифицирующих дочерние узлы) и счетчика, представляющего число узлов в поддереве с корнем w.
Алгоритм маркирования. Алгоритм создания 2-3-дерева аутентификационных признаков (алгоритм маркирования) работает следующим образом:
для каждого i, пусть T(w)=АУТ?(F[i]), где w - i-тый концевой узел;
для каждого не - концевого узла w, пусть Т(w)=АУТ?((L1,L2,L3),рзм), где Li - метка i-того дочернего узла w (в случае, если w имеет только два дочерних узла, то L3=?) и рзм - число узлов в поддереве с корнем w);
для корня дерева Т(?)=АУТ?((L1,L2,L3),Id,счт), где Id - название документа и счт - соответствующее показание счетчика (связанное с этим документом).
Инкрементальный алгоритм маркирования.
Предположим, что файл F, аутентифицированный маркированным деревом, подвергается операции замены, то есть j-тый блок файла F заменен блоком F(?). Сначала необходимо проверить, что путь от требуемого текущего значения до корня дерева корректен. Для этого необходимо выполнить следующий алгоритм.
Пусть u0,...uh - путь из корня u0=? к j-тому концевому узлу обозначается как uh. Тогда:
проверить, что ВЕР? принимает Т(?) как корректный АП строки Т(?)=АУТa((L1,L2,L3),Id,счт), где Id - название документа и счт - текущее значение счетчика (связанного с этим документом);
для i=1,...,h-1 проверить, что ВЕР? принимает Т(ui) как корректный АП строки ((L1,L2,L3),рзм), где Li - метка i-того дочернего узла w (в случае, если w имеет только два дочерних узла, то L3=?) и рзм - число узлов в поддереве с корнем w));
проверить, что ВЕР? принимает Т(uh) как корректный АП блока F[j] .
Если все эти проверки успешны, тогда совокупный АП файла F получается следующим образом:
установить Т(uh):=АУТ(F(?));
для i=h-1,...,1 установить Т(ui):=АУТ(Т(ui1),Т(ui2),Т(ui3));
установить Т(?):=АУТ((Т(ui0),Т(ui1),Т(ui1)),Id,счт+1).
Следует подчеркнуть, что значения Т на всех других вершинах (то есть, не стоящих на пути u0,...,uh) остаются неизменяемыми.
Следует отметить, что предлагаемая инкрементальная схема маркирования имеет дополнительное свойство, заключающееся в том, что она безопасна даже для противника который может "видеть" как отдельные аутентификационные признаки, так и все маркированное дерево и может даже "вмешиваться" в эти признаки. Для каждого файла, пользователь должен хранить в локальной безопасной памяти ключ x схемы подписи, имя файла и текущее значение счетчика. Всякий раз, когда пользователь хочет проверить целостность файла, он проверяет корректность маркированного дерева открытым образом.
Наиболее эффективным является использование инкрементального алгоритма маркирования для защиты программ, использующих постоянно обновляющие структуры данных, например, файл с исходными данными или итерационно изменяемыми переменными.
