Нейрокриптография

Нейрокриптография — раздел криптографии, изучающий применение стохастических алгоритмов, в частности, нейронных сетей, для шифрования и криптоанализа.

Определение

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

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

Идеи нейрокриптографии впервые были озвучены Себастьяном Дорленсом (Sebastien Dourlens) в 1995 году, спустя 30 лет после определения основ нейронных сетей.

Применение

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

В 1995 году Себастьян Дорленс применил нейрокриптоанализ, чтобы научить нейронные сети инвертировать S-перестановки в DES. В ходе эксперимента было найдено 50 % битов ключа, то есть ключ целиком может быть найден за короткое время. Аппаратная реализация состоит из множества (64К) простых микроконтроллеров, расположенных на СБИС.

Другой пример — протокол шифрования с открытым ключом Халил Шибаба (Khalil Shihab), в котором процесс расшифрования основан на многоуровневой нейронной сети, обучающейся по алгоритму обратного распространения. В то же время процесс зашифрования и создания закрытого ключа использует обычную двоичную алгебру. Преимущество этого метода в малых затратах времени и памяти. Недостаток — в алгоритме обратного распространения: на больших массивах входных данных нейронная сеть обучается долго. Поэтому данный протокол имеет лишь теоретическое значение.

Протокол обмена ключами

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

TPM

ДМЧ

ДМЧ — это особый вид многоуровневой нейронной сети прямого распространения.

Она состоит из одного выходного нейрона, K скрытых нейронов и K×N входных нейронов. Входные нейроны принимают двоичные значения:

$x_{ij}\in \{-1,+1\}.$

Веса между входными и скрытыми нейронами принимают значения

$w_{ij}\in \{-L,...,0,...,+L\}.$

Значение каждого скрытого нейрона есть сумма произведений входного значения и весового коэффициента:

$\sigma _{i}=\operatorname {sgn} {\Big (}\sum _{j=1}^{N}w_{ij}x_{ij}{\Big )},$

$\operatorname {sgn}(x)={\begin{cases}-1&{\text{if }}x\leq 0,\\1&{\text{if }}x>0.\end{cases}}$

Значение выходного нейрона есть произведение всех скрытых нейронов:

$\tau =\prod _{i=1}^{K}\sigma _{i}.$

Выходное значение также двоичное.

Протокол

У каждого абонента (А или Б) есть своя ДМЧ. Их синхронизация происходит следующим образом:

1. Задаём случайные значения весовых коэффициентов
2. Выполняем следующие шаги, пока не наступит синхронизация
   1. Генерируем случайный входной вектор X
   2. Вычисляем значения скрытых нейронов
   3. Вычисляем значение выходного нейрона
   4. Сравниваем выходы двух ДМЧ:
      1. Выходы разные: переход к п.2.1
      2. Выходы одинаковые: применяем выбранное правило к весовым коэффициентам

После полной синхронизации (веса w_ij обоих ДМЧ одинаковые), А и Б могут использовать веса в качестве ключа.

Этот метод известен как двунаправленное обучение.

Для обновления весовых коэффициентов могут использоваться следующие правила:

• Правило Хебба:

$w_{i}^{+}=w_{i}+\sigma _{i}x_{i}\Theta (\sigma _{i}\tau )\Theta (\tau ^{A}\tau ^{B})$

• Анти-правило Хебба:

$w_{i}^{+}=w_{i}-\sigma _{i}x_{i}\Theta (\sigma _{i}\tau )\Theta (\tau ^{A}\tau ^{B})$

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

$w_{i}^{+}=w_{i}+x_{i}\Theta (\sigma _{i}\tau )\Theta (\tau ^{A}\tau ^{B})$

Виды атак и надёжность

Для каждой атаки предполагается, что криптоаналитик Е может подслушивать сообщения между А и Б, но не может их изменять.

Метод грубой силы

Криптоаналитик должен проверить все возможные варианты ключей, то есть все возможные веса w_ij. Если имеется K скрытых нейронов, K×N входных нейронов и максимальный вес L, то это даёт (2L + 1)^KN вариантов. Например, для K = 3, L = 3, N = 100 ≈ 3·10²⁵³ различных ключей. На сегодняшний день такая атака невозможна.

Обучение собственной ДМЧ

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

1. Output(A) ≠ Output(B): Абоненты не обновляют веса.
2. Output(A) = Output(B) = Output(E): Все трое обновляют веса.
3. Output(A) = Output(B) ≠ Output(E): А и Б обновляют веса, но Е не может этого сделать. Поэтому он обучается медленнее, чем А и Б синхронизируются.

Таким образом, криптоаналитик может определить ключ лишь с очень малой вероятностью.

Другие атаки

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

Алексанр Климов, Антон Митягин и Ади Шамир утверждают, что исходный алгоритм нейросинхронизации может быть сломан по крайней мере тремя видами атак: геометрической, вероятностным анализом и генетическими алгоритмами. Хотя данная реализация небезопасна, идеи случайной синхронизации могут привести к абсолютно безопасной схеме.

Генетическая атака

Атака строится на создании большой популяции нейронных шифровальных устройств (НШУ) — таких же нейросетей с абсолютно идентичной структурой, что А и Б. В процессе обмена информацией между абонентами происходит либо отсеивание ненужных НШУ, либо наоборот — наращивание потенциально благоприятных для взлома. Формализованный алгоритм выглядит так:

• Взломщик инициализует свою машину только с одной НШУ. Веса для него выбираются случайно. Также устанавливается некоторое число М — порог популяции НШУ, которое может себе позволить взломщик.
• Затем при обмене информацией между А и Б могут возникнуть три ситуации:

1. Если выходные значения А и Б не равны между собой: Output(A) ≠ Output(B), обновление весов не происходит. Взломщик не трогает свою популяцию.
2. Если Output(A) = Output(B) и число шифровальных устройств у взломщика не превышает порог М, то все НШУ заменяются на репрезентацию из F новых НШУ, каждая из которых получается альтернативной заменой скрытого нейрона на противоположное значение, собственно для этого подбираются новые веса. Затем происходит обучение по правилам Хеббиана.
3. Если Output(A) = Output(B) и число шифровальных устройств у взломщика превышает порог М, то удаляются все те нейромашины, выходное значение которых Output(E) ≠ Output(A).
Данный алгоритм действует только на маленьких нейросетях (N,K<=3) и становится в тупик даже на очень мощных компьютерах при K>=6. Строго говоря, все атаки, предложенные Александром Климовым и Антоном Митягиным основаны на том, что НШУ имеет небольшой размер. На практике же редко применяются шифровальные нейросети с параметрами N<100, K<100, L<10.

Защита от квантовых компьютеров

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

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

Ссылки

• Neuro-Cryptography 1995 — The first definition of the Neuro-Cryptography (AI Neural-Cryptography) applied to DES cryptanalysis by Sebastien Dourlens, France.
• Neural Cryptography — Description of one kind of neural cryptography at the University of Würzburg, Germany.
• Using synchronized neural networks to achieve public key authentication system — One of the leading papers that introduce the concept.
• A remote password authentication scheme for multiserverarchitecture using neural networks — Possible practical application of Neural Cryptography.
• Analysis of Neural Cryptography (недоступная ссылка) — Analysis of neural cryptography in general and focusing on the weakness and possible attacks of using synchronized neural networks.
• Neural Synchronization and Cryptography — Andreas Ruttor. PhD thesis, Bayerische Julius-Maximilians-Universität Würzburg, 2006.
• Andreas Ruttor, Wolfgang Kinzel, Rivka Naeh, and Ido Kanter. Genetic attack on neural cryptography (англ.) // Physical Review E : journal. — 2006.
• Khalil Shihab. A backpropagation neural network for computer network security (англ.) // Journal of Computer Science 2 : journal. — 2006. — P. 710—715.
• Применение искусственных нейронных сетей и системы остаточных классов в криптографии / [Червяков Н. И. и др.]. — Москва : Физматлит, 2012. — 279 с. : ил., табл.; 24 см; ISBN 978-5-9221-1386-1 (в пер.)