Математические основы криптологии и криптографические методы и средс

о том, что разработчики ГОСТа учли как положительные, так и от­ рицательные стороны DESa, а также более реально оценили текущие

иперспективные возможности криптоанализа.

9.Требования к качеству ключевой информации и источ­ ники ключей

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

Исчерпывающий ответ на вопрос о критериях качества ключей и таблиц замен ГОСТа если и можно вообще где-либо получить, то только у разработчиков алгоритма. Соответствующие данные не бы­ ли опубликованы в открытой печати. Однако согласно установлен­ ному порядку для шифрования информации, имеющей гриф, должны быть использованы ключевые данные, полученные от уполномочен­ ной организации. Косвенным образом это может свидетельствовать о наличии методик проверки ключевых данных на «вшивость». Сам факт существования слабых ключевых данных в Российском стан­ дарте шифрования не вызывает сомнения.

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

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

вырабатываются с помощью генератора псевдослучайных чисел, то используемый генератор должен обеспечивать указанные выше ста­ тистические характеристики и, кроме того, обладать высокой крип­ тостойкостью, не меньшей, чем у самого ГОСТа. Иными словами, задача определения отсутствующих членов вырабатываемой генера­ тором последовательности элементов не должна быть проще, чем задача вскрытия шифра. Кроме того, для отбраковки ключей с пло­ хими статистическими характеристиками могут быть использованы различные статистические критерии. На практике обычно хватает двух критериев - для проверки равновероятного распределения би­ тов ключа между значениями 0 и 1 обычно используется критерий

Пирсона х2 >а для проверки независимости битов ключа - критерий

серий.

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

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

Необходимо отметить еще один интересный факт относительно таблицы замен. Для обратимости циклов шифрования 32 - 3 и 32 - Р не требуется, чтобы узлы замен были перестановками чисел от 0 до 15. Все работает даже в том случае, если в узле замен есть повто­ ряющиеся элементы, и замена, определяемая таким узлом, необрати­ ма, однако в этом случае снижается стойкость шифра.

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

Вопросы использования стандарта

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

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

Вариации на тему ГОСТа Очень часто для использования в системе криптографической

защиты данных требуется алгоритм с большим, чем у ГОСТа, быст­ родействием реализации, и при этом не требуется такая же высокая, как у ГОСТа, криптостойкость. Типичным примером подобных задач являются различного рода биржевые торговые системы, управляю­ щие торговыми сессиями в реальном времени. Здесь от использован­ ных алгоритмов шифрования требуется, чтобы было невозможно дешифровать оперативные данные системы в течение сессии (данные о выставленных заявках, о заключенных сделках и т.п.), по ее исте­ чении же эти данные, как правило, уже бесполезны для злоумыш­ ленников. Другими словами, требуется гарантированная стойкость всего на несколько часов (такова типичная продолжительность тор­ говой сессии). Ясно, что использование полновесного ГОСТа в этой ситуации было бы «стрельбой из пушки по воробьям».

К счастью, из этой ситуации есть достаточно легкий выходиспользовать модификацию алгоритма ГОСТ с меньшим количест­ вом основных шагов в базовых циклах. Этого можно достигнуть двумя путями - уменьшением длины ключа и уменьшением числа циклов использования элементов ключа - вспомните, что число ос­ новных шагов в базовых циклах шифрования равно N = n-m, где п - число 32-битных элементов в ключе, т - число циклов использо­ вания ключевых элементов, в стандарте п = 8, т = 4. Во сколько раз уменьшается число основных шагов в циклах, примерно во столько же раз увеличивается быстродействие кода.

К несчастью, нет никаких сведений о том, как изменяется крип­ тостойкость подобного ослабленного варианта ГОСТа. Что касается криптоанализа по статистической линии (перебор всех возможных значений ключа), то здесь все достаточно ясно, так как эта величина

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

При выборе размера «редуцированного цикла» надо принимать во внимание, что ГОСТ проектировался с учетом возможного про­ гресса вычислительной техники на несколько десятилетий вперед и в нем заложен огромный запас криптостойкости. В большинстве практических случаев представляется разумным использование ре­ дуцированных вариантов ГОСТа без изменения схемы использова­ ния ключа (/и = 4 = 3 + 1), но с уменьшенным вчетверо размером ключа (л = 2) —это позволит увеличить скорость шифрования при­ мерно вчетверо. По стойкости к статистическим методам криптоана­ лиза данная модификация с ее 64-битным ключом будет надежнее, чем DES с размером ключа в 56 бит.

Необычная работа криптографической гаммы Конечно, основное назначение криптоалгоритмов ГОСТа-это

шифрование и имитозащита данных. Однако у криптографической гаммы есть еще одно важное применение - выработка ключевой ин­ формации. Выработка массива ключевой или парольной информации большого объема является типовой задачей администратора безопас­ ности системы. Как уже было отмечено выше, ключ может быть сге­ нерирован как массив нужного размера статистически независимых и равновероятно распределенных между значениями 0 и 1 битов, для этого можно использовать программу, вырабатывающую ключ по принципу «электронной рулетки». Но такой подход совершенно не годится, когда объем необходимой ключевой информации велик. В этом случае идеально использование аппаратных датчиков случай­ ных чисел, что, однако, не всегда возможно по экономическим или техническим соображениям. В этом случае в качестве источника по­ тока случайных битов может быть использован генератор гаммы на основе любого блочного шифра, в том числе и ГОСТ 28147-89, так как, по определению, криптографическая гамма обладает необходи­ мыми статистическими характеристиками и криптостойкостью. Та­

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

32байта.

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

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

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

2.1.8. Выбор группы шифра

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

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

1. Выбор параметров ПСП и функции усложнения

Общей особенностью указанных режимов является использова­ ние генератора псевдослучайных последовательностей (ПСП), в ка­ честве функции обратной связи (OFB, CFB) или функции выхода {Counter) которого используется функция зашифрования блочного шифра (рис. 46). В двухступенчатой структуре Counter задача первой ступени заключается всего лишь в обеспечении максимально воз­ можного числа состояний, что, естественно, приводит к получению ПСП такой же длины. Иначе говоря, большим достоинством струк­ туры Counter является то, что она позволяет гарантировать заданное значение периода формируемой ПСП.

Поточные режимы блочного

и Counter результат шиф­ рования конкретного бло­ ка зависит от его позиции

в исходном тексте;

♦в режимах OFB и Counter каждый блок исходного текста шифруется на своем блоке гаммы (эле­ менте ПСП);

♦ в режиме CFB результат шифрования г-го блока

зависит от всех блоков с первого по /-й включительно; ♦ режимы OFB и Counter являются синхронными;

♦ режим CFB является самосинхронизирующимся.

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

Лучшим на сегодняшний день, безусловно, является блочный криптоалгоритм RIJNDAEL, принятый в 2002 году в качестве амери­ канского стандарта криптографической защиты AES {Advanced En­ cryption Standard). AES заменил морально устаревший алгоритм DES {Data Encryption Standard), с 70-х годов являвшийся де-факто миро­ вым стандартом блочного шифрования.

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

♦ Криптографическое сообщество окончательно приняло (и даже пошло дальше) правило Кирхгофа, согласно которо­ му надежность криптоалгоритма должна определяться только секретностью ключа. AES был принят в результате открыто­ го международного конкурса, при этом в конкурсе на звание американского стандарта победила разработка бельгийских криптографов. На конкурс были представлены исчерпываю­ щие описания сути алгоритмов. В процессе проведения кон­ курса открыто публиковались исследования стойкости шиф- ров-участников. Среди 5 финалистов конкурса (MARS, RC6, RIJNDAEL, SERPENT, TWOFISH), приблизительно равно­ ценных по совокупности основных параметров, победил наи­ более простой, красивый и логичный алгоритм. Сами авторы

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

♦ Принцип построения блочного шифра, впервые предложен­ ный К. Шенноном и названный SP-сетью (S - substitution, Р - permutation), доказал свою жизнестойкость. Использую­ щую этот принцип новую архитектуру «Квадрат», впервые предложенную в прототипе RIJNDAEL алгоритме SQUARE, следует признать более эффективной, чем классическую сеть Фейстеля. В RIJNDAEL в одном раунде изменению подвер­ гается весь блок, при этом преобразования выполняются

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

♦Все операции в RIJNDAEL (в том числе логику работы бло­ ков замены) можно описать с использованием математиче­ ского аппарата теории полей Галуа. Достоинство операций

вконечных полях - эффективная программная и аппаратная реализация на 8- (смарт-карты) и 32-разрядной платформах.

♦При проведении конкурса AES для исследования шифровкандидатов использовался анализ их статистической безо­ пасности, иначе говоря, проводилось исследование на слу­ чайность результатов зашифрования, а также исследование статистической безопасности псевдослучайных последова­ тельностей, формируемых в режимах гаммирования. НИСТ США опубликовал многостраничный труд с описанием ста­ тистических тестов, методикой их использования и оценкой результатов при анализе криптографических генераторов псевдослучайных последовательностей.

2. Тенденции проектирования поточных шифров

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

♦Активное использование устройств, функционирующих не только в двоичных (LFSR) (шифр А5), но и недвоичных ко­ нечных полях (шифры PANAMA, SOBER, SNOW и др.). При этом операции в конечных полях используются как при по­ строении функции обратной связи, так и при построении функции выхода.

♦Активное использование блоков замен (S-блоков) с динами­

чески изменяющейся в процессе работы таблицей замен (шифры RC4, SAPPHIRE, SQ1-R и др.).

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

3. Стохастические криптоалгоритмы

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

Особенностью обработки информации с использованием Л-блоков является наличие двух операндов в операции стохастиче­ ского преобразования

у = т о ,

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