Иванов М.А. КМЗИ сети. Криптографические методы защиты информации
 Скачать 3.04 Mb.
|
|
ГЛАВА 8. ПРИНЦИПЫ ПОСТРОЕНИЯ ГЕНЕРАТОРОВ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ Cфера применения генераторов генераторов псевдослучай- ных чисел (ПСЧ) чрезвычайно широка. Качественные псевдо- случайные последовательности (ПСП), являясь по своей сути детерминированными, обладают, тем не менее, практически всеми свойствами реализаций истинно случайных процессов и успешно их заменяют во многих приложениях, так как случай- ные последовательности чрезвычайно сложно формировать. Часть 2 данного пособия посвящена в первую очередь гене- раторам ПСЧ, ориентированным на использование в системах защиты информации от случайных и умышленных деструктив- ных воздействий, иначе говоря, генераторам, к которым предъ- являются наиболее жесткие требования. В главе 8 дается классификация генераторов ПСЧ, рассмат- риваются общие принципы проектирования непредсказуемых генераторов ПСЧ, требования к таким устройствам, описыва- ются основные строительные блоки, используемые при их соз- дании. Уделяется внимание перспективным типам генераторов: генераторам на регистрах сдвига с линейными обратными свя- зями, генераторам ПСЧ на основе стохастических сумматоров или R-блоков. Криптографические блочные и поточные генера- торы ПСЧ, а также генераторы ПСЧ на основе односторонних функций были рассмотрены в предыдущих главах. Конгруэнт- ные генераторы ПСЧ не рассматриваются в связи с их неудовле- творительным качеством. В главе 9 приведены примеры использования стохастических методов при обеспечении безопасности электронных платежных систем, а в главе 10 – информация по методам оценки качества генераторов ПСЧ. Результаты исследований генераторов ПСЧ различных типов представлены в [16]. 231 8.1. Стохастические методы защиты информации Стохастическими методами защиты в широком смысле при- нято называть методы защиты компьютерных систем, прямо или косвенно основанные на использовании генераторов ПСЧ или хеш-генераторов, если учесть, что результат работы и тех, и дру- гих непредсказуем. При этом эффективность защиты в значи- тельной степени определяется качеством используемых алго- ритмов соответственно генерации ПСЧ или хеширования. Крип- то- и стеганографические методы защиты, таким образом, явля- ются лишь частным случаем стохастических методов. Генераторы ПСЧ и хеш-генераторы успешно решают практи- чески все задачи, стоящие перед разработчиками систем обеспе- чения безопасности информации (ОБИ). При реализации боль- шинства методов защиты информации используются генераторы ПСЧ или хеш-генераторы. Иначе говоря, эти методы – стохасти- ческие. Более того, наиболее перспективный метод защиты, су- тью которого является внесение неопределенности в работу компьютерных систем (реализация которого в принципе невоз- можна без использования генераторов ПСЧ), универсален. Он может использоваться совместно с любым другим методом за- щиты, автоматически повышая его качество. Функции генераторов ПСЧ в системах ОБИ: формирование тестовых воздействий на входы проверя- емых компонентов системы при автономном или встроен- ном диагностировании; реализация счетчиков команд или адреса (в том числе само- проверяемых) компьютерных систем; определение соответствия между адресом порта ввода- вывода и запрашиваемой функцией при реализации пла- вающих протоколов взаимодействия ПО и устройств ввода- вывода (УВВ), механизма скрытых функций УВВ; формирование элементов вероятностного пространства при внесении неопределенности в результат работы алгоритмов защиты информации (вероятностное шифрования, техноло- гия OAEP); 232 задание последовательности выполнения при внесении не- определенности в последовательность выполнения отдель- ных шагов алгоритма; задание длительности выполнения при внесении неопреде- ленности в длительность выполнения отдельных шагов ал- горитма для защиты от утечки по побочным каналам; формирование элементов вероятностного пространства при внесении неопределенности в механизм работы программ- ных средств (полиморфизм, метаморфизм, запутывание про- грамм (obfuscating)); формирование гаммы при шифровании информации в ре- жимах гаммирования и гаммирования с обратной связью; формирование ключей и паролей пользователей; формирование случайных запросов при аутентификации удаленных абонентов по принципу «запрос–ответ»; формирование долей секрета в протоколах разделения секрета; формирование затемняющих множителей при слепом шиф- ровании (например, для скрытия содержимого электронного документа при формировании слепой подписи); формирование прекурсоров для защиты прав собствен- ников информации (протокол слепой подписи). Функции хеш-генераторов в системах ОБИ: формирование контрольных кодов целостности информации или правильности выполнения шагов алгоритма; необратимое преобразование паролей для защиты пароль- ных систем разграничения доступа; необратимое сжатие информации перед формированием электронной цифровой подписи (ЭЦП) для повышения про- изводительности схемы ЭЦП; необратимое преобразование случайных запросов при аутен- тификации по принципу запрос–ответ; необратимое преобразование информации для защиты от утечки (например, в схеме двойной электронной подписи); необратимое преобразование информации (прекурсора) с целью защиты прав ее владельца (например, при формиро- вании серийного номера цифровой купюры); необратимое преобразование информации при реализации метода внесения неопределенности в результат работы 233 криптоалгоритмов (например, при создании несепарабель- ных режимов шифрования, предназначенных для повыше- ния стойкости симметричных криптоалгоритмов с неболь- шой разрядностью ключа или реализации технологии OAEP для асимметричных криптоалгоритмов). Таким образом, можно сделать обоснованный вывод об уни- версальности стохастических методов (необходимо только пом- нить, что они являются методами двойного назначения, так как используются как при атаках, так и организации защиты компь- ютерных систем) и определяющей роли качественных быст- родействующих генераторов ПСЧ. В случае их наличия можно эффективно строить все другие криптографические примитивы симметричной криптографии. После обоснования утверждения о решающей роли генерато- ров ПСЧ при построении системы ОБИ, появляется возможность подойти к решению задач защиты компьютерных систем с еди- ных исходных позиций. Ранее научные дисциплины, в той или иной степени связанные с решением задач ОБИ, развивались обособленно друг друга. Речь в первую очередь идет о техниче- ской диагностике, теории помехоустойчивого кодирования, криптографии и криптоанализе, стеганографии и стегоанализе, информационной безопасности, технологии безопасного про- граммирования. 8.2. Требования к генераторам ПСЧ Эффективность стохастических методов ОБИ определяется в первую очередь качеством используемых генераторов ПСЧ. Сформулируем, что входит в понятие «качественный генератор ПСЧ». Качественныйгенератор ПСЧ, ориентированный на исполь- зование в задачах защиты информации, должен удовлетворять следующим требованиям: непредсказуемость (по сути, криптографическая стой- кость); хорошие статистические свойства, ПСП по своим статисти- ческим свойствам не должна отличаться от истинно случай- ной последовательности; 234 большой период формируемой последовательности, учи- тывая, что при преобразовании больших массивов данных каждому элементу входной последовательности необходимо ставить в соответствие свой элемент псевдослучайной по- следовательности; эффективная программная и аппаратная реализация. При использовании непредсказуемого генератора ПСЧ три следующие задачи для противника, не знающего ключевой ин- формации, вычислительно неразрешимы: 1) определение предыдущего (i – 1)-го элемента i–1 после- довательности на основе известного фрагмента последо- вательности i i + 1 i + 2 i + b – 1 конечной длины b (не- предсказуемость влево); 2) определение последующего (i + b)-го элемента i+b после- довательности на основе известного фрагмента гаммы i i + 1 i + 2 i + b – 1 конечной длины b (непредсказуемость вправо); 3) определение ключевой информации по известному фраг- менту последовательности конечной длины. Справедливо следующее утверждение [3, 4]: непредсказуемый влево генератор ПСЧ является криптостойким. Криптоаналитик, знающий принцип работы такого генерато- ра, имеющий возможность анализировать фрагмент выходной последовательности конечной длины, но не знающий исполь- зуемой ключевой информации, для определения предыдущего выработанного элемента последовательности не может предло- жить лучшего способа, чем подбрасывание жребия. Непредсказуемость генератора ПСЧ чрезвычайно сложно оценить количественно. Чаще всего обоснования стойкости не- линейной функции F k генератора ПСЧ сводятся к недоказуемым предположениям о том, что у аналитика не хватит ресурсов (вы- числительных, временных или стоимостных) для того, чтобы при неизвестном k обратить (инвертировать) эту функцию. Тео- рия сложности вычислений, к сожалению, не может дать стро- гую нижнюю границу трудоемкости решения подобных задач. В рамках другого подхода к построению качественного гене- ратора ПСЧ предлагается свести задачу построения криптогра- 235 фически сильного генератора к задаче построения статистиче- ски безопасного генератора. Статистически безопасный генератор ПСЧ должен удовле- творять следующим требованиям: ни один статистический тест не обнаруживает в ПСП каких- либо закономерностей (иными словами, не отличает эту по- следовательность от истинно случайной); нелинейное преобразование F k , зависящее от секретной ин- формации (ключа k), используемое для построения генера- тора, обладает свойством «размножения» искажений – все выходные (преобразованные) вектора e возможны и равно- вероятны независимо от исходного вектора e (рис. 8.3); при инициализации случайными значениями генератор по- рождает статистически независимые ПСП. 8.3. Классификация генераторов ПСЧ Классификация генераторов ПСЧ показана на рис. 8.1. В ка- честве параметров выбраны: тип используемого нелинейного преобразования; структура генератора; наличие или отсутствие внешних источников случайности. Тип функции. По этому параметру генераторы ПСЧ можно разделить на некриптографические и криптографические. К не- криптографическим относятся конгруэнтные генераторы, гене- раторы, функционирующие в конечных полях, и генераторы на регистрах сдвига с нелинейными обратными связями. К крипто- графическим – блочные и поточные генераторы (см. соответст- венно разделы 2.4 и 2.8), генераторы на основе односторонних функций (см. раздел 5.8). Достоинство некриптографических генераторов – эффектив- ная программная и аппаратная реализация. Недостаток – пред- сказуемость. Аддитивные генераторы Галуа и Фибоначчи, функ- ционирующие в конечных полях, генераторы на регистрах сдви- га с нелинейными обратными связями можно использовать лишь в качестве строительных блоков при разработке качественных генераторов ПСЧ. 236 Тип функции Классификация генераторов ПСЧ Криптографические Внешние источники случайности Некриптографические На регистрах сдвига с нелинейными обратными связями Конгруэнтные Функционирующие в конечных полях Блочные На основе односторонних функций Поточные Архитектура «Сеть Фейстеля» Архитектура «Квадрат» Управление по принципу stop-and-go Без использования Способ управления синхронизацией Тип используемых S- или R-блоков Комбинирование нескольких ПСЧ Без комбинирования Механизм получения последовательности Секретное табличное преобразование, зависящее от ключа, содержимое таблицы изменяется в процессе работы Без управления Фиксированная таблица замен Секретное фиксированное табличное преобразование, зависящее от ключа Один каскад Наличие каскадов Несколько каскадов Режим OFB – использование нелинейной функции обратной связи Режим Counter – использование нелинейной функции выхода Структура Использование физических источников случайности Использование информации с системного таймера, мыши, клавиатуры, дисковой подсистемы ПК и пр. Без использования Рис. 8.1. Классификация генераторов ПСЧ 237 В криптографических генераторах ПСЧ в качестве нелинейно- го преобразования F k используется функция зашифрования либо симметричной (блочные и поточные генераторы ПСЧ), либо асимметричной криптосистемы (генераторы ПСЧ на основе одно- сторонних функций с секретом). При использовании в качестве нелинейной функции F k функции зашифрования E k одноключевой или двухключевой криптосистемы применение криптостойких функций E k автоматически придает аналогичное по сути свойство непредсказуемости и генератору ПСЧ. При построении блочных криптографических генераторов в первую очередь уделяется внимание их непредсказуемости. Не- линейное преобразование, определяющее свойство непредска- зуемости, суть многократное повторение одной и той же раундо- вой операции. Основной целью построения поточных генераторов является высокая скорость работы при приемлемой для большинства при- ложений непредсказуемости. В отличие от блочных генераторов ПСЧ здесь нет единого принципа построения. Можно выделить лишь следующие перспективные тенденции: применение в качестве строительных блоков генераторов, функционирующих в конечных полях (генераторы SOBER, PANAMA, SNOW и др.) [24]; использование при построении нелинейных функций блоков пространственного сжатия (space compression) информации для необратимости результирующего преобразования [29]; применение таблиц замен или стохастического преоб- разования, непрерывно изменяющихся в процессе работы (RC4, SQ1-R и др.) [24, 34]. Наиболее обоснованными математически следует признать генераторы с использованием односторонних функций. Непред- сказуемость данных генераторов основывается на сложности решения ряда математических задач (например, задачи дискрет- ного логарифмирования (в том числе на эллиптических кривых) или задачи разложения больших чисел на простые множители). Существенный недостаток генераторов этого класса – низкая производительность. Анализ криптографических генераторов позволяет сделать два основных вывода: 238 1) существует трудноразрешимое противоречие между ка- чеством формируемых ПСЧ, с одной стороны, и эффек- тивностью программной и аппаратной реализации гене- раторов, с другой; 2) непредсказуемость криптографических генераторов ос- новывается на недоказуемых предположениях о том, что у аналитика не хватит ресурсов (вычислительных, вре- менных или стоимостных) для того, чтобы обратить (ин- вертировать) нелинейную функцию обратной связи или нелинейную функцию выхода генератора ПСЧ. Структура генератора. Можно выделить два подхода при использовании в составе генераторов ПСЧ нелинейных функций: 1) применение нелинейной функции непосредственно в це- пи обратной связи (рис. 8.2,а) 2) двухступенчатая структура (рис. 8.2,б), в которой задача первой ступени (по сути счетчика) заключается всего лишь в обеспечении максимально большого периода при данном количестве N элементов памяти генератора. Первая схема носит название OFB (Output FeedBack – обратная связь по выходу), вторая – Counter. а S 0 F k F k Q k i S 0 F fb Q i k F out S 0 F fb Q i б в Рис. 8.2. Варианты построения генератора ПСЧ: а – с нелинейной внутренней логикой (режим OFB); б – с нелинейной внешней логикой (режим Counter); в – общая схема. Q – элементы памяти генератора; S 0 – начальное состояние генератора; F fb – линейная или нелинейная функция обратной связи; F k – нелинейная функция, результат работы которой зависит от секретного параметра k (ключа);, i – элемент выходной последовательности; F out – линейная или нелинейная функция выхода генератора 239 Уравнения работы генераторов, функционирующих в режи- мах OFB и Counter, имеют соответственно вид , , 1 t fb t t t Q F Q Q γ (8.1) , , 1 t fb t t out t Q F Q Q F γ (8.2) где 0 Q = S 0 ; t Q и 1 t Q – состояние генератора в моменты време- ни t и (t + 1) соответственно; t – значение выхода в момент вре- мени t, Необходимые свойства используемой нелинейной функции иллюстрирует рис. 8.3, где e – входной вектор изменений (оши- бок), содержащий 1 в разрядах, соответствующих измененным (искаженным) битам, е – преобразованный (выходной) вектор изменений. При случайном выборе ключа k при любых измене- ниях на входе значения преобразованных векторов е равномер- но распределены на интервале [1; 2 n – 1], где n – разрядность выходного слова (рис. 8.3,а). Аналогично, при случайном выбо- ре входного слова x при любых изменениях ключа значения пре- образованных векторов е ошибок также равномерно распреде- лены на интервале [1; 2 n – 1] (рис. 8.3,б). Такие свойства автома- тически имеют место при использовании в роли F k функции за- шифрования качественного блочного криптоалгоритма, обеспе- чивающей рассеивание и перемешивание информации. F k y = F k (x) k F k k x F k y' = F k (x') k x' = x e e = x' x e' = y' y F k y = F k (x) k F k x F k y' = F k' (x) x k' = k e e = k' k e' = y' y x а б Рис. 8.3 |