СИНХРОНИЗАЦИЯ ДРЕВОВИДНЫХ МАШИН ЧЕТНОСТИ

АННОТАЦИЯ

Статья обсуждает безопасное согласование ключей, необходимое для защищенного канала. Она предлагает использовать для этого древовидную машину четности (ДМЧ), основанную на взаимном обучении нейронных сетей. Протокол ДМЧ включает инициализацию, обмен информацией и синхронизацию весов. Рассматриваются различные подходы к завершению обучения и угрозы безопасности, включая атаки грубой силы и атака "человек посередине".

ABSTRACT

The paper discusses secure key matching required for a secure channel. It proposes the use of a tree parity machine (TPM) based on the mutual learning of neural networks for this purpose. The TPM protocol includes initialization, information exchange and synchronization of weights. Different approaches for training completion and security threats including brute force attacks and man-in-the-middle attack are discussed.

Ключевые слова: Нейрокриптография, Древовидные машины четности, Шифрование, Протоколы передачи данных, Искусственные нейронные сети

Keywords: Neurocryptography, Tree Parity Machines, Encryption, Data Communication Protocols, Artificial Neural Networks

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

Существующие алгоритмы, основанные на открытых ключах, уязвимы к квантовым вычислениям. Извлечение защищенного ключа из передаваемой между абонентами информации, может нарушить безопасность протоколов шифрования ключей. Одним из примеров такого алгоритма является квантовый алгоритм Шора — предназначенный для разложения числа на простые множители, следовательно, способен получить секретный ключ [1]. Однако для этого алгоритма требуется свой квантовый компьютер с достаточным количеством кубитов.

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

Нейронные сети становятся все более популярными и находят широкое применение в области безопасности. Кантер [2] и Розен-Цви [3] представили новый подход к функциям согласования ключей, реализованный с помощью нейронных сетей.

ДМЧ представляет собой структуру искусственных нейронных сетей с двухслойной перцептронной архитектурой, имеющую дискретные веса, двоичные входы и выходы. Входной вектор , где  – натуральные числа, представляют собой последовательность элементов, состоящую из -элементов. Здесь - обозначает количество входов для каждого нейрона в первом слое, а  – количество нейронов в первом слое. Каждый элемент  – входного вектора  может принимать одно из двух значений: -1 или 1. Каждый вход  подключен к -му нейрону и имеет соответствующий вес , который может принимать значения от -L до L, где L – параметр ДМЧ, обозначающий максимальное или минимальное возможное значение веса входных нейронов.

Выход вышеупомянутых нейронов основан на несколько измененной знаковой функции. Она отличается от обычной функции тем, что никогда не возвращает ноль. Значение 0 отображается либо на 1, либо на -1 в зависимости от того, является ли сторона отправителем или получателем сообщения. Стороны получателя и отправителя обозначаются r и s, соответственно. Заранее решается, какая сторона является отправителем, а какая – получателем:

Функция активации нейронов является сумма произведений элементов входного вектора на соответствующий вес:

Конечный результат ДМЧ представляет собой произведение всех выходов скрытых нейронов:

Сторонами, осуществляющими согласование ключей, выполняется протокол, в результате которого получается защищенный общий ключ, известный только участвующим сторонам.

Протокол для двух сторон включает в себя следующие шаги [4]:

1. Оба абонента должны согласовать все параметры своих ДМЧ и инициализировать их.
2. Абоненты публично обмениваются заранее выбранным дискретным случайным входным вектором X.
3. Каждый абонент вычисляет выход своей ДМЧ и передает результат.
4. Если выходы совпадают, оба абонента применяют соответствующее правило обучения для обновления весов ДМЧ.
5. Шаги 2-4 повторяются до полной синхронизации обеих ДМЧ.

Когда ДМЧ достигают полную синхронизацию, их весовые коэффициенты равны между собой соответственно. Обновления весовых коэффициентов проводится таким образом, чтобы процесс синхронизации завершился в конечное время [5].

В процессе обновления весов могут использоваться три различных правила:

1) Правило Хебба:

2) Правило Анти-Хебба:

3) Случайное блуждание:

Здесь Q(a, b) обозначает функцию, возвращающую 1, если a = b, и 0 в противном случае, а t - итерацию в алгоритме согласования ключей. Процесс синхронизации машин четности не является детерминированным и зависит от размеров и параметров ДМЧ. Однако он всегда завершается за конечное время, что можно легко оценить [6]. Время процесса синхронизации увеличивается при увеличении размеров ДМЧ (K и N) и максимального значения веса (L). Количество итераций, необходимых для завершения взаимного обучения двух машин четности, также зависит от начального распределения весов и правила обучения [7].

При рассмотрении процесса обучения двух ДМЧ важно определить критерии синхронизации, для завершения процесса обучения. Рассматриваются различные подходы:

1. Полный перебор: Синхронизация происходит путем перебора все возможных входных векторов до полного совпадения соответствующих выходов ДМЧ. Однако, это не является эффективным и потенциально может увеличить вероятность успеха извлечь защищенный ключ из передаваемой информации.
2. Итеративный подход: Проводится эмпирическая оценка необходимого числа эпох обучения. Но количество итераций может сильно изменяться в зависимости от изначальных параметров ДМЧ абонентов, что может привести к не дообучению или переобучению.
3. Использование хэш-функций: Для сравнения текущих состояний ДМЧ с определенной периодичностью используются хэш-функции. Этот метод требует выбора надежной и быстрой хэш-функции с минимальным риском коллизий. Но в такой ситуации мы полагаемся на алгоритмы, основанные на теории чисел, что возвращает нас к исходной проблеме.

Каждый из этих подходов имеет свои преимущества и недостатки, и выбор конкретного зависит от требований безопасности и эффективности конкретной криптографической системы.

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

1. Атака грубой силы: Поиск точного ключа методом грубой силы на ДМЧ за полиномиальное время невозможен.
2. Генетический алгоритм для предсказания веса: Уязвимы для этого типа атак только ДМЧ с одним нейроном во втором слое.
3. Атака "человек посередине": В среднем 60% весов ДМЧ атакующего синхронизированы с абонентами.

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

Рассмотрим 3-ий вид атак "человек посередине". Допустим, криптоаналитик обладает нейронной сетью того же типа, что и у абонентов, и стремится синхронизировать её с двумя другими нейронными сетями.

Круговая синхронизация, рисунок 1.

Рисунок 1. Круговая синхронизация

Этот метод атаки описывается как процесс нелегальной синхронизации трех ДМЧ, маскируемый под обычную синхронизацию двух ДМЧ. На канал передачи информации встраивается атакующая сторона, воздействующая только в одном направлении.

Алгоритм синхронизации работает следующим образом:

1. ДМЧ-А вычисляет функцию и передает результат на ДМЧ-В;
2. ДМЧ-В корректирует веса, вычисляет функцию и передает результат на ДМЧ-С;
3. ДМЧ-С корректирует веса, вычисляет функцию и передает результат на ДМЧ-А;
4.  ДМЧ-А корректирует веса, вычисляет функцию и передает результат на ДМЧ-В;

Этот процесс повторяется до достижения полной синхронизации всех трех ДМЧ.

Действительно, синхронизация двух ДМЧ может занимать разное количество времени, и точно предсказать необходимое время достижения синхронизации невозможно. Это может быть обусловлено различными факторами, такими как начальные условия ДМЧ, параметры обучения, размеры сети и другие. Поэтому даже если злоумышленник сможет получить данные о процессе обучения и о времени, затраченном на синхронизацию, он не сможет точно определить момент завершения этого процесса.

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

Маятник, рисунок 2.

Рисунок 2. Маятник

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

Шаги алгоритма синхронизации следующие:

1. ДМЧ-А вычисляет функцию и отправляет результат на ДМЧ-С;
2. ДМЧ-С корректирует веса, вычисляет функцию и передает результат на ДМЧ-В;
3. ДМЧ-В корректирует веса, вычисляет функцию и передает результат на ДМЧ-С;
4. ДМЧ-С снова корректирует веса, вычисляет функцию и передает результат на ДМЧ-А;

Этот процесс коррекции и вычисления функции повторяется до полной синхронизации всех трех ДМЧ.

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

Синхронизация суммированием рисунок 3.

Рисунок 3.Синхронизация суммированием

Алгоритм синхронизации следующий:

ДМЧ-А вычисляет функцию и передает результат на ДМЧ-С;

ДМЧ-С корректирует веса, вычисляет функцию, суммирует результаты и передает их на ДМЧ-В;

ДМЧ-В корректирует веса, вычисляет функцию и передает результат на ДМЧ-С;

ДМЧ-С корректирует веса, вычисляет функцию, суммирует результаты и передает их на ДМЧ-А;

Этот процесс повторяется до полной синхронизации всех трех ДМЧ.

Этот метод атаки достаточно быстрый и при этом малозаметный, однако его легко вычислить, когда результаты вычислений проверяются на промежуточном этапе. Его единственным плюсом является скорость. Факт атаки легко обнаружить, проверив результаты вычислений в процессе синхронизации: любые расхождения указывают на атаку, и можно принять меры для обеспечения безопасности данных.

Проведем подобную атаку и сравним количество итераций при обычной синхронизации и при атаке.

При обычной синхронизации цикл завершился после 468 итерации. Посмотрим на график синхронизации от количества итераций, где по оси “Y” будет разность весов Алисы и Боба, а по оси “X” номер итерации, рисунок 4.

Рисунок 4. Итерации синхронизации

Приведем матрицы Алисы и Боба и заметим, что они полностью совпадают рисунок 5:

Рисунок 5. Веса Алисы и Боба

По алгоритму круговой синхронизации, описанному ранее. сымитируем атаку на наш алгоритм. Заметим, что потребовалось в 3 раза больше итераций - 1465. Посмотрим на то, какие значения весовых коэффициентов получились у наших ДМЧ после синхронизации Алисы, Боба и Евы, рисунок 6.

Рисунок 6. Веса трех ДМЧ

Веса всех трех ДМЧ одинаковы, а значит атака прошла успешно. Проверив и передав сообщение, ДМЧ Евы так же смогла его расшифровать.

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

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

Список литературы:

1. Shor P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer // SIAM Rev. — 1999. — Т. 41, №2. — С. 303–332.
2. Kanter I., Kinzel W., Kanter E. Secure exchange of information by synchronization of neural networks // Europhys. Lett. — 2002. — Т. 57, №1. — С. 141–147.
3. Rosen-Zvi M., Kanter I., Kinzel W. Cryptography based on neural networks analytical results // J. Phys. A, Math. Gen. — 2002. — Т. 35, №47. — С. L707–L713. — doi: 10.1088/0305-4470/35/47/104.
4. Volkmer M., Wallner S. Tree parity machine rekeying architectures // IEEE Trans. Comput. — 2005. — Т. 54, №4. — С. 421–427
5. Kinzel W. Theory of Interacting Neural Networks. — NJ, USA: Wiley, 2002. — С. 199–217. — doi: 10.1002/3527602755.
6. Javurek M., Turcanik M. Synchronization of two tree parity machines // Proc. New Trends Signal Process. (NTSP). — Oct. 2016. — С. 1–4.
7. Dolecki M., Kozera R. Distance of the initial weights of tree parity machine drawn from different distributions // Adv. Sci. Technol. Res. J. — 2015. — Т. 9, №26. — С. 137–142. — doi: 10.12913/22998624/2380.