Сравнение статистических свойств ключей асимметричных шифров

В настоящее время наблюдается кризис развития криптографии в области надежных поточных шифров, следствием которого является отсутствие современных стандартов поточного шифрования в США, России, Европе. В 2009 году провалом был завершен конкурс по выбору стандарта, поточного шифрования для Европейского Союза. - E-Stream. Несмотря на. отсутствие результата, в процессе организации и проведения упомянутого конкурса, были сформулированы и апробированы требования к поточным шифрам, приведенные в работе Шамира. [1]:

• •    малое потребление ресурсов в аппаратной реализации (меньше, чем у Advanced Encryption Standard);

• е    высокая скорость шифрования в программной реализации (быстрее, чем Advanced Encryption Standard);

е стойкость шифра к атакам.

Учитывая эти требования и существующее положение со стандартами шифрования, особый интерес представляет исследование свойств открытых ключей асимметричных шифров в качестве источника, энтропии ключа, поточных шифров. Необходимо учесть, что

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

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

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

Исходя из этих предпосылок, следует рассмотреть следующие области применения, которые в свою очередь не являются исчерпывающими:

• •    телекоммуникационное оборудование;

• •    спутниковое оборудование;

• •    mesh-сети.

2.    Описание рассматриваемых шифров

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

За период своего существования система ГПТ-1 [4] неоднократно менялась [5]. Эти изменения были связаны с необходимостью уменьшения размера ключа, ускорения процедуры шифрования и необходимостью защиты от новых атак на криптосистему. Вариант криптосистемы ГПТ-1, использованный в данной работе, приведен ниже:

G_pub = S [X\G] Р.

Численные параметры криптосистемы:

• •    степень расширения поля Галуа: GF(q^N ) = GF (2^N ),q = 2;

е п,к,ж - параметры, определяемые ниже.

Секретный ключ состоит из 4-х частей:

• •    G - порождающая матрица раивового МРГ-кода. размера (к х п):

• •    S - строковый скремблер - случайная обратимая (к х к)-матрица над расширенным полем GF(q);

• •    X - случайна.я шумовая (к х п)-матрнпа над расширенным полем GF(q^N ) с рангами: столбцевым рангом (X\т) = ж над основным полем GF(q) рангом т(Х\qN ) = тж над расширенным полем GF(q^N );

• •    Р - случайный столбцевой скремблер обратимая (п +ж х п +ж)-матрица над основным полем GF(q).

Псевдослучайным источником энтропии служит матрица G_pub, элементы которой используются для суммирования 0 с открытым текстом посимвольно. Открытый текст m представлен в виде m = mi... m^ ,miGF(q^N ). Для реализации шифра были выбраны следующие параметры:

• •    N = 65547, 0, 0, 0, 0, 0, 0, 0,1, 0;

• •    п = 8;

• •    к = 7;

• •    ж = 4.

Для криптосистемы ГПТ-2 использованы условия, изложенные ниже. Для реализации была использована следующая схема кодирования: Ключ G_pub = SGP. Шифрование С = М * G_pub + е. Отличия системы ГПТ-1 от ГПТ-2 заключаются в том, что система ГПТ-1 содержит матрицы X и P, которые выбираются из поля GF(q) В то же время система ГПТ-2 не содержит матрицы X, и матрица P выбирается из расширенного поля GF(q^m). Параметры криптосистемы ГПТ-2:

• •    N = 65547, 0, 0, 0, 0, 0, 0, 0,1, 0;

• •    п = 8;

• •    к = 7;

• •    ж = 4.

3.    Сравнительная оценка скорости работы

Система. ГПТ-1:

е генерация 26 250 кб = 210 000 000 бит = 136 кбит/с (RC4 около 154 Мбит/с);

• •    время вычислений 25 минут 34 секунды;

• •    вычислительная платформа: Intel Core 13 2,27 GHz;3 Гб.

Система. ГПТ-2:

е генерация 26 250 кб = 210 000 000 бит = 136 кбит/с (RC4 около 154 Мбит/с);

• •    время 1 час 32 секунды;

• •    вычислительная платформа: Intel Core 13 2,27 GHz;3 Гб.

4.    Тесты псевдослучайных последовательностей DIEHARD

Тесты псевдослучайных последовательностей Diehard были созданы Джорджем Марсальей в 1995 году и предназначены для тестирования создаваемых генераторов псевдослучайных чисел на. предмет их стойкости.

Первый тест называется пространство дней рождений (Birthday Spacings) — выбираются случайные точки на большом интервале. Расстояния между точками должны быть асимптотически близки к распределению Пуассона. Название этот тест получил на основе парадокса дней рождения. В этом тесте выбираются m дней рождения из п дней года. Рассчитываются расстояния между датами дней рождения. Пусть j - количество чисел, которые встречаются в последовательности неоднократно, тогда j ассимптотически близко распределению Пуассона со значением р(к) = m3/(4n). Опыт показывет, что п должно быть достаточно большим, п > 218, чтобы можно было проводить сравнение с распределением Пуассона. В этом тесте используются значения п = 224 и т = 29, чтобы основное распределение Пуассона использовало А = 227/(226) = 2. Каждый 500-й J проверяется на соответствие распределению у2. Первый тест использует 1-24 бит (считаются справа налево) от целых чисел в задаваемом файле последовательности. После чего файл закрывается и открывается снова. Затем считываются значения с порядковыми номерами 2-25 и проверяются на совпадения дней рождения так же, как значения с порядковыми номерами 3-26 для последовательности значений с порядковыми номерами 9-32. Для каждого набора вычисляется значение вероятности р, и девять значений этих тестов используются в тесте KSTEST.

Пересекающиеся перестановки (Overlapping Permutations) — анализируются последовательности пяти последовательных случайных чисел. 120 возможных перестановок должны получаться со статистически эквивалентной вероятностью. В ходе этого теста рассматриваются последовательности из одного миллиона 32битных случайных целых чисел. Каждый из наборов пяти последовательно взятых чисел может быть в 120 состояниях (5!). Таким образом, каждые 5,6,7... чисел образуют коалиции. Так как рассматриваются несколько тысяч различных состояний, то обнаруживаются несколько совпадений. Эта версия использует 1 000 000 целых чисел дважды.

Ранги матриц (Ranks of matrices) — выбирается некоторое количество бит из некоторого количества случайных чисел для формирования матрицы над 0,1, затем определяется ранг матрицы. Считаются ранги. В этом тесте проверяются матрицы размера 31 х 31. Крайние 31-е левые биты 31-го случайного целого числа испытываемой последовательности используются для формирования двоичной матрицы размера 31 х 31 из поля 1, 0. Ранг определен. Ранг может быть от 0 до 31, но ранг < 28 редкий, и их счетчики объединены со счетчиком 28-го ранга. Ранги определяются для 40 000 случайных матриц, тест у² выполняется для рангов 31, 30, 29 и 28.

В этом тесте проверяются матрицы размера 32 х 32. Каждая строка - это случайное 32-битное число. Ранг определен. Ранг может быть от 0 до 32. но jмиг < 29 редкий, и их счетчики объединены с счетчиком 29-го ранга. Ранги определяются для 40 000 случайных матриц, тест у2 выполняете я для рангов 32, 31, 30 и 29. В этом тесте проверяются матрицы размера 6х8. От каждого из шести случайных 32-битных целых чисел генератора при тесте выбирается байт, в результате формируется матрица 6 х 8. Ранг определен. Ранг может быть от 0 до 6, но ранг < 4 редкий, и их счетчики объединены со счетчиком 4-го ранга. Ранги определяются для 100 000 случайных матриц, тест распределения у2 выполняется для рангов 6, 5 и 4.

Обезьяньи тести (Monkey Tests) — последовательности некоторого количества бит интерпретируются как слова. Считаются пересекающиеся слова в потоке. Количество «слов», которые не появляются, должно удовлетворять известному распределению. В этом тесте файл рассматривается как поток битов. Предполагается, что алфавит двоичный, биты потока нумеруются, после чего поток разделяется на 20-битные слова так, чтобы они накладывались. Тест подсчитывает пропавшие слова в последовательности длиной 221 бит, в которой существуют 220 комбинаций 20-ти битных слов. Для действительно случайной последовательности в 221 + 19 символов число недостающих j слов должно быть близко к нормальному распределению 141, 909 и сигмой 428. Таким образом, вероятность определяется из диапазона [0,1). Тест повторяется двадцать раз.

Подсчёт единичек (Count the l’s) — считаются единичные биты в каждом из последующих или выбранных байт. Эти счётчики преобразуется в «буквы», и считаются случаи пятибуквенных «слов».

Тест OPSO рассматривает двухбуквенные слова из алфавита, состоящего из 1024 букв. Каждая буква определяется специальными 10-ю битами из 32-битного целого числа, которое подвергается проверке. В тесте генерируется 221 двухбуквенное слово из потока в

221 + 1 символов, в распределение должно быть близко к среднему с 141, 909. сигмой 290. Таким образом, (missingumds = 141909)/290 должно быть нормально распределенной переменной.

Teem OQSO проверяет четырехбуквенные слова, получаемые из алфавита в 32 бита, где каждое слово задается 5-го последовательно идущими битами из файла, элементами которого считаются 32-битные случайные целые числа. В тесте предполагается 221 потерянное четырехбуквенное слово, из последовательности в 221 + 3 слова с сигмой = 295.

Тест ДНК (DNA) рассматривает четыре записи С, G, А, Т, каждая из которых определяется двумя битами из случайных целых чисел. Тест рассматривает 10-буквенные слова, чтобы, как и в OPSO, в OQSO, где возможно, сформировать 220 слов из последовательности, это означает, что в последовательности 221 десятибуквенное слово из последовательности 221 + 9 возможно 141 909 потерянных слов. Стандартное отклонение sigma = 339 определено для OQSO.

Тест на парковку (Parking Lot Test) — единичные окружности случайно размещаются в квадрате 100 х 100. Если окружность пересекает уже существующую, попытаться ещё. После 12 000 попыток количество успешно «припаркованных» окружностей должно быть нормально распределено.

Тест на минимальное расстояние (Minimum Distance Test) — 8000 точек случайно размещаются в квадрате 10 000 х 10 000, затем находится минимальное расстояние между любыми парами. Квадрат этого расстояния должен быть экспоненциально распределён с некоторой медианой. В данном тесте рассматривается квадрат с ребром в 100 единиц. В заданном квадрате нужно расположить п чисел так, чтобы они не пересекались: радиус одного числа принят за единицу. Проверяется п = 12 000 попыток, после чего считается отношение удачных попыток к неудачным. Количество удачных попыток к должно составить в среднем 3523 с сигмой 21.9, что близко к нормальному распределению. Таким образом, (к — 3523)/21.9 должно быть стандартной нормальной переменной, которая после преобразованния в однородную переменную проходит KSTEST на 10-ти образцах.

Тест случайных сфер (Random Spheres Test) — случайно выбираются 4000 точек в кубе с ребром 1000. В каждой точке помещается сфера, чей радиус является минимальным расстоянием до другой точки. Минимальный объём сферы должен быть экспоненциально распределён с некоторой медианой.

Тест сжатия (The Squeeze Test) — число 231 умножается на случайные вещественные числа в диапазоне [0,1) до тех пор, пока не получится 1. Повторяется 100 000 раз. Количество вещественных чисел, необходимых для достижения 1, должно быть распределено определённым образом.

Тест пересекающихся сумм (Overlapping Sums Test) — генерируется длинная последовательность вещественных чисел из интервала [0,1). В ней суммируются каждые 100 последовательных чисел. Суммы должны быть нормально распределены с характерными средним и дисперсией.

Тест последовательностей (Runs Test) — генерируется длинная последовательность на [0,1). Подсчитываются восходящие и нисходящие последовательности. Числа должны удовлетворять некоторому распределению.

Тест игры в кости (The Craps Test) — играется 200 000 игр в кости, подсчитываются победы и количество бросков в каждой игре. Каждое число должно удовлетворять некоторому распределению.

5.    Результаты тестирования последовательности ключа шифров ГПТ-1 и ГПТ-2

Результаты тестирования шифров ГПТ-1 и ГПТ-2 тестами DIEHARD в основной своей массе свидетельствовали о том, что правила формирования ключей в шифрах ГПТ-1 и ГПТ-2 вносят в ключ закономерности и шифры не являются статистически безопасными. Сами результаты тестов в статье не приводятся из-за своей объемности. Стоит отметить тесты, в которых возникали отклонения от равномерного распределения. В тесте с 5-то перестановками шифры ГПТ-1 и ГПТ-2 не прошли 1-е и 4-е испытание. В бинарном ранговом тесте оба шифра имели отклонения в 1, 2 и 4 тестах. Тест битового потока - в 1, 4 и 5 тестах. Тест OPSO - в 1 и 4 тестах. Обезьяний тест, тест подсчета единиц, тест сжатия, тест игры в кости - в 1 и 4 тестах. Тестирование выполнялось на пяти различных последовательностях. Отличия в результатах небольшие, что позволяет утверждать их репрезентативность и корректность. При их рассмотрении также учитывался тот фактор, о котором было заявлено разработчиками теста: как правило, даже самый хороший генератор псевдослучайных чисел имеет ряд отклонений от нормально распределения вероятностей. Тест считается пройденным в случае, если результат вычисления распределения вероятностей лежит в диапазоне [0,1) - тогда последовательность чисел является полностью независимой. Если получено более шести вероятностей, равных 0 или 1, тогда тест считается полностью не пройденным.

6.    Заключение

Беспроводные сети получили широкое распространение в повседневной жизни, и динамика процесса распространения такова, что количество беспроводных сетей будет только возрастать. Ценность информации, передаваемой по беспроводным сетям, растет вместе с количеством информации и сетей. Используемые криптографические алгоритмы и протоколы не обеспечивают необходимого уровня защиты передаваемой, хранимой и обрабатываемой информации. Причины этого заключатся в недостаточной криптографической стойкости алгоритмов шифрования к атакам, в том числе к атаке «грубой силы». В случае, если не реализованы надежные протоколы смены и генерации ключей, а так же при отсутствии аутентификации узлов и информационных пакетов, использование системы ГПТ-2 в беспроводных сетях позволит серьезно улучшить их защищенность, так как, работая в режиме асимметричного шифра, возможно быстро и безопасно проводить замену ключей, в случае передаче большого объема информации шифр можно перевести в режим поточного шифрования. С использованием текущей архитектуры шифр ГПТ-2 проходит большую часть тестов DIEHARD, что по аналогии с семейством шифров А5 позволяет его применять для защиты беспроводных сетей и сетей связи. Для повышения надежности шифра следует уточнить регламент его использования и частоту смены ключей. Несмотря на статистическое несовершенство, шифр ГПТ-1 является устойчивым ко всем существующим видам криптоанализа поточных шифров [6], но может оказаться неустойчивым к криптоаналитическим атакам, характерным для самого ГПТ-1 и ГПТ-2, что должно стать темой отдельного исследования.