РАЗРАБОТКА МЕТОДОВ ИССЛЕДОВАНИЯ СТАТИСТИЧЕСКИХ ХАРАКТЕРИСТИК ПРОМЕЖУТОЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ БЛОЧНОГО ШИФРА ГОСТ 28147-89

Н.А. Семенова


Московский государственный институт электроники и математики (технический университет), Россия
электроники и математики (технический университет), Россияя


В работе описана методика испытаний промежуточных последовательностей блочного шифра ГОСТ 28147-89, позволяющая проверить их на предмет отклонения от случайной равновероятной последовательности, а также представлены программные модули, позволяющие автоматизировать тестирование. Методика тестирования основана на применении набора статистических тестов NIST STS (NIST Statistical Test Suite).

Введение

В ходе криптографического анализа алгоритмов шифрования повышенное внимание уделяется так называемым криптографическим свойствам узлов и блоков криптосхем – свойствам, которые в значительной мере влияют на возможность построения эффективных методов взлома. Разработчики алгоритмов шифрования стремятся обеспечить ситуацию, когда выходная последовательность по своим вероятностным характеристикам неотличима от последовательности, полученной по равновероятной полиномиальной схеме. То есть множество выходных последовательностей по своим вероятностно-статистическим характеристикам не отличается от реализации соответствующей равновероятной полиномиальной схемы. Обнаруженные отличия шифртекста от равновероятной последовательности могут служить сигналом того, что криптосхема имеет определенные криптографические слабости [2].

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

Наиболее известными наборами статистических тестов являются: тесты, предложенные Кнутом в его классической работе «Искусство программирования для ЭВМ. Том 2» [4], пакет Diehard и NIST-STS [1].

В данной статье описывается методика испытаний промежуточных последовательностей блочного шифра ГОСТ 28147-89, основанная на пакете NIST-STS.

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

1.Генерация множества входных последовательностей (открытого текста) и множества ключей.

2. Шифрование.

3. Проверка близости выходной последовательности (шифртекста) к РРСП.

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

В самом общем виде критерий согласия состоит в разбиении множества X наблюдений (возможных анализируемых последовательностей) на два класса X0() и X1() [3]. Множества строятся таким образом, чтобы для РРСП (гипотеза H0) вероятность того, что реализация принадлежит X1(), равнялась достаточно близкой к 0 величине , называемой уровнем значимости критерия. Если в ходе эксперимента выясняется, что наблюдаемая последовательность x принадлежит множеству X0(), делается вывод, что результаты эксперимента согласуются (не противоречат) гипотезе H0 о том, что наблюдаемая последовательность есть реализация РРСП. В противном случае делается вывод, что результаты эксперимента противоречат этой гипотезе.

При использовании статистических критериев из того или иного пакета мы можем воспользоваться рассчитанным множеством X0(), для задания которого строится некоторая статистика st(x) – действительная функция от наблюдения x – случайная величина с функцией распределения F(z)=P{st(x)z}.

P{p(x)z}=P{F(st(x))z}=P{st(x)F-1(z)}=FF-1(z)=z, где p(x) - квантиль распределения F(z), p(x)=F(st(x)). Распределение случайной величины p(x) равномерно на отрезке [0,1]. Поэтому P{xX0()}=P{p(x)R0()}=1-. Достаточно вычислить значение p(x) и проверить его на принадлежность множеству R0().

Множество R0() строится таким образом, чтобы критерий выявлял наиболее ожидаемые отклонения в последовательности от РРСП.

Выше отмечалось, что гипотеза РРСП принимается, если p(x)R0() и отвергается в противном случае. В пакете NIST STS по результатам эксперимента делаются более «мягкие» выводы. А именно:

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

Методика тестирования

С учетом того, что каждый из критериев пакета NIST STS предъявляет собственные требования к объему входных данных, методика тестирования должна иметь следующий вид:

  1. Расчет параметров для проведения тестирования (объем входных данных и входные параметры для каждого из критериев)

  2. Расчет параметров для интерпретации результатов тестов (пороговое значение для признания результатов теста «удовлетворительными»)

  3. Подготовка тестовых данных в объемах, рассчитанных на шаге 1 (генерация ключей и открытых текстов)

  4. Проведение тестов

  5. Интерпретация результатов

Математическая модель исследуемого шифра.

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

Рассмотрим уравнение блочного шифра ГОСТ 28147-89:

c=f(k,m), где с — шифрованный текст (блок), m — открытый текст (блок), k — ключ, f — функция блочного шифрования.

Будем использовать обозначения:

М — множество всех открытых текстов,;

К — множество всех ключей,;

— множество возможных шифрованных текстов.

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

Пусть ключевое множество разбито на непересекающиеся подмножества,

(данное разбиение задается, например, фиксацией части координат ключевого вектора), θ - заданное отображение множества С в множество R, |R|<<|C|.

Тогда через рj(r) обозначим вероятность того, что θ(f(k,m))=r при случайном выборе k из множества Kj и m из множества Мо (при этом k и m выбираются независимо друг от друга).

Набор вероятностей задает распределение Рj на элементах множества R. Если при этом распределения Рj различны для разных j, то возникает принципиальная возможность определения подмножества Кj, которому принадлежит неизвестный ключ блочного шифра, по частотам встречаемости величин rj=θ(ci), где ci=f(k,mi), , i=1,2,...,N. Именно на различии распределений Рj основаны линейный и дифференциальный анализ блочных шифров.

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

Для оценки соответствия частот встречаемости величин rj=θ(ci), где ci =f(k, mi),

, i=1,2,...,N, выборке из равновероятного распределения на множестве R можно использовать, например, статистический критерий хи-квадрат с |R|-1 степенями свободы.

Один из наиболее простых способов выбора параметров Mo, R, θ, Кj, (j=1,2,...,t),

заключается в фиксации значений некоторых координат векторов с,k,m.

Пусть, например, фиксируется один байт (для определенности — первый) в каждом из указанных векторов. Тем самым, задаются множества Mo, R, θ, Кj (j=1,2,...,t). Далее случайным образом фиксируется ключ и для случайных , i= l 2,...,N,

вычисляются частоты значений первого байта в множестве векторов ci =f(k, mi), (i=1,2,...,N}, которые затем проверяются по критерию хи-квадрат с 255 степенями свободы.

Для фиксированного ключа и множества Мо необходимый объем шифртекста составит N~216 . Различных множеств Кj, которые определяются значением первого байта ключевого вектора, равно 256. Следовательно, для экспериментальной оценки степени различимости ключевых множеств Кj по частотам встречаемости значений первого байта в блоке шифртекста необходимо реализовать ~224 тактов шифрования.

Необходимый объем шифртекста для проверки шифра ГОСТ с сокращенным числом раундов n составит N~216 (определяется минимальными требованиями длины входной последовательности батареи статистических тестов NIST).

Проведенные тесты

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

1. Шифрование множества случайных открытых текстов на одном ключе

2. Шифрование одного открытого текста на множестве различных ключей с фиксированным первым битом

3. Шифрование одного открытого текста на инкрементальном множестве ключей

Разработанные программные модули.

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

В рамках данной работы были созданы 3 программных модуля:

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

2. GOST – программная реализация шифра ГОСТ 28147-89, модернизированная для возможности съема промежуточных последовательностей и выбора числа раундов шифрования (от 1 до 32).

3. NIST2 – автоматически запускает тесты из пакета NIST на выходных данных модуля GOST.

Результаты тестирования

В результате проведенных тестов выяснилось, что не все критерии из пакета NIST обнаруживают отклонения промежуточных последовательностей с одинаковой эффективностью. Так, критерий «Линейной сложности» перестает обнаруживать отклонения уже после 2 раундов шифрования, в то время как критерии «Тест дискретного преобразования Фурье» и «Совпадение с апериодическим шаблоном» выявляют отклонения вплоть до 27 раунда.

Начиная с 28 раунда, ни один из критериев не обнаруживал отклонения от равновероятности.

Заключение

При выполнении данной работы были решены следующие задачи:

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

- Разработано ПО, позволяющее автоматизировать тестирование по разработанной методологии.

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

Литература:

  1. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST Special Publication 800-22 (with revisions dated May 15, 2001)

  2. Security requirements for Cryptographic Modules. FIPS 140-1. – U.S. Department of Commerse. 1994

  3. Ивченко Г.И., Медведев Ю.И. Математическая статистика: Учебное пособие для ВТУЗов. – М.: Высш. шк. – 248 с

  4. Д. Э. Кнут. Искусство программирования, том 2. Получисленные алгоритмы, 3-е изд.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 832 с

  5. ГОСТ 28147-89: Государственный Стандарт Российской Федерации. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования.