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

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

Определение

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

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

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

Применение

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

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

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

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

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

TPM

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

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

<math>x_{ij} \in \{-1, +1\}.</math>

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

<math>w_{ij} \in \{-L,...,0,...,+L\}.</math>

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

<math>\sigma_i = \sgn\Big(\sum_{j=1}^N w_{ij} x_{ij}\Big),</math>

<math>\sgn (x) = \begin{cases}

-1 & \text{if } x \le 0, \\ 1 & \text{if } x > 0. \end{cases}</math>

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

<math>\tau = \prod_{i=1}^K \sigma_i.</math>

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

Протокол

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

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

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

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

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

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

<math>w_i^+=w_i+\sigma_ix_i\Theta(\sigma_i\tau)\Theta(\tau^A\tau^B)</math>

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

<math>w_i^+=w_i-\sigma_ix_i\Theta(\sigma_i\tau)\Theta(\tau^A\tau^B)</math>

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

<math>w_i^+=w_i+x_i\Theta(\sigma_i\tau)\Theta(\tau^A\tau^B)</math>

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

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

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

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

Обучение собственной TPM

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

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.

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

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

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

Ссылки

• [translate.google.com/translate?u=http%3A%2F%2Fs.dourlens.free.fr%2Fmaitrise%2Fmaitrise.htm Neuro-Cryptography] 1995 — The first definition of the Neuro-Cryptography (AI Neural-Cryptography) applied to DES cryptanalysis by Sebastien Dourlens, France.
• [theorie.physik.uni-wuerzburg.de/~ruttor/neurocrypt.html Neural Cryptography] — Description of one kind of neural cryptography at the University of Würzburg, Germany.
• [ieeexplore.ieee.org/Xplore/defdeny.jsp?url=/iel5/8534/27062/01202841.pdf?tp=&tp=x&arnumber=1202841&isnumber=27062&code=4 Using synchronized neural networks to achieve public key authentication system] — One of the leading papers that introduce the concept.
• [ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=963786 A remote password authentication scheme for multiserverarchitecture using neural networks] — Possible practical application of Neural Cryptography.
• [www.springerlink.com/content/kbpxkbnkgtk4ymhh/ Analysis of Neural Cryptography] — Analysis of neural cryptography in general and focusing on the weakness and possible attacks of using synchronized neural networks.
• [www.opus-bayern.de/uni-wuerzburg/volltexte/2007/2361/ 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 (2006). «[link.aps.org/abstract/PRE/v73/e036121 Genetic attack on neural cryptography]». Physical Review E.
• Khalil Shihab (2006). «[www.scipub.org/fulltext/jcs/jcs29710-715.pdf A backpropagation neural network for computer network security]». Journal of Computer Science 2: 710–715.
• Червяков Н.И., Евдокимов А.А., Галушкин А.И., Лавриненко И.Н. и др.,[www.fml.ru/webapp/book/list?page=1 Применение искусственных нейронных сетей и системы остаточных классов в криптографии],- М.: ФИЗМАТЛИТ, 2012.- 280 c. - ISBN 978-5-9221-1386-1.

Отрывок, характеризующий Нейрокриптография

Из передней Берг плывущим, нетерпеливым шагом вбежал в гостиную и обнял графа, поцеловал ручки у Наташи и Сони и поспешно спросил о здоровье мамаши.
– Какое теперь здоровье? Ну, рассказывай же, – сказал граф, – что войска? Отступают или будет еще сраженье?
– Один предвечный бог, папаша, – сказал Берг, – может решить судьбы отечества. Армия горит духом геройства, и теперь вожди, так сказать, собрались на совещание. Что будет, неизвестно. Но я вам скажу вообще, папаша, такого геройского духа, истинно древнего мужества российских войск, которое они – оно, – поправился он, – показали или выказали в этой битве 26 числа, нет никаких слов достойных, чтоб их описать… Я вам скажу, папаша (он ударил себя в грудь так же, как ударял себя один рассказывавший при нем генерал, хотя несколько поздно, потому что ударить себя в грудь надо было при слове «российское войско»), – я вам скажу откровенно, что мы, начальники, не только не должны были подгонять солдат или что нибудь такое, но мы насилу могли удерживать эти, эти… да, мужественные и древние подвиги, – сказал он скороговоркой. – Генерал Барклай до Толли жертвовал жизнью своей везде впереди войска, я вам скажу. Наш же корпус был поставлен на скате горы. Можете себе представить! – И тут Берг рассказал все, что он запомнил, из разных слышанных за это время рассказов. Наташа, не спуская взгляда, который смущал Берга, как будто отыскивая на его лице решения какого то вопроса, смотрела на него.
– Такое геройство вообще, каковое выказали российские воины, нельзя представить и достойно восхвалить! – сказал Берг, оглядываясь на Наташу и как бы желая ее задобрить, улыбаясь ей в ответ на ее упорный взгляд… – «Россия не в Москве, она в сердцах се сынов!» Так, папаша? – сказал Берг.
В это время из диванной, с усталым и недовольным видом, вышла графиня. Берг поспешно вскочил, поцеловал ручку графини, осведомился о ее здоровье и, выражая свое сочувствие покачиваньем головы, остановился подле нее.
– Да, мамаша, я вам истинно скажу, тяжелые и грустные времена для всякого русского. Но зачем же так беспокоиться? Вы еще успеете уехать…
– Я не понимаю, что делают люди, – сказала графиня, обращаясь к мужу, – мне сейчас сказали, что еще ничего не готово. Ведь надо же кому нибудь распорядиться. Вот и пожалеешь о Митеньке. Это конца не будет?
Граф хотел что то сказать, но, видимо, воздержался. Он встал с своего стула и пошел к двери.
Берг в это время, как бы для того, чтобы высморкаться, достал платок и, глядя на узелок, задумался, грустно и значительно покачивая головой.
– А у меня к вам, папаша, большая просьба, – сказал он.
– Гм?.. – сказал граф, останавливаясь.
– Еду я сейчас мимо Юсупова дома, – смеясь, сказал Берг. – Управляющий мне знакомый, выбежал и просит, не купите ли что нибудь. Я зашел, знаете, из любопытства, и там одна шифоньерочка и туалет. Вы знаете, как Верушка этого желала и как мы спорили об этом. (Берг невольно перешел в тон радости о своей благоустроенности, когда он начал говорить про шифоньерку и туалет.) И такая прелесть! выдвигается и с аглицким секретом, знаете? А Верочке давно хотелось. Так мне хочется ей сюрприз сделать. Я видел у вас так много этих мужиков на дворе. Дайте мне одного, пожалуйста, я ему хорошенько заплачу и…
Граф сморщился и заперхал.
– У графини просите, а я не распоряжаюсь.
– Ежели затруднительно, пожалуйста, не надо, – сказал Берг. – Мне для Верушки только очень бы хотелось.
– Ах, убирайтесь вы все к черту, к черту, к черту и к черту!.. – закричал старый граф. – Голова кругом идет. – И он вышел из комнаты.
Графиня заплакала.
– Да, да, маменька, очень тяжелые времена! – сказал Берг.
Наташа вышла вместе с отцом и, как будто с трудом соображая что то, сначала пошла за ним, а потом побежала вниз.
На крыльце стоял Петя, занимавшийся вооружением людей, которые ехали из Москвы. На дворе все так же стояли заложенные подводы. Две из них были развязаны, и на одну из них влезал офицер, поддерживаемый денщиком.
– Ты знаешь за что? – спросил Петя Наташу (Наташа поняла, что Петя разумел: за что поссорились отец с матерью). Она не отвечала.
– За то, что папенька хотел отдать все подводы под ранепых, – сказал Петя. – Мне Васильич сказал. По моему…
– По моему, – вдруг закричала почти Наташа, обращая свое озлобленное лицо к Пете, – по моему, это такая гадость, такая мерзость, такая… я не знаю! Разве мы немцы какие нибудь?.. – Горло ее задрожало от судорожных рыданий, и она, боясь ослабеть и выпустить даром заряд своей злобы, повернулась и стремительно бросилась по лестнице. Берг сидел подле графини и родственно почтительно утешал ее. Граф с трубкой в руках ходил по комнате, когда Наташа, с изуродованным злобой лицом, как буря ворвалась в комнату и быстрыми шагами подошла к матери.
– Это гадость! Это мерзость! – закричала она. – Это не может быть, чтобы вы приказали.
Берг и графиня недоумевающе и испуганно смотрели на нее. Граф остановился у окна, прислушиваясь.
– Маменька, это нельзя; посмотрите, что на дворе! – закричала она. – Они остаются!..
– Что с тобой? Кто они? Что тебе надо?
– Раненые, вот кто! Это нельзя, маменька; это ни на что не похоже… Нет, маменька, голубушка, это не то, простите, пожалуйста, голубушка… Маменька, ну что нам то, что мы увезем, вы посмотрите только, что на дворе… Маменька!.. Это не может быть!..
Граф стоял у окна и, не поворачивая лица, слушал слова Наташи. Вдруг он засопел носом и приблизил свое лицо к окну.
Графиня взглянула на дочь, увидала ее пристыженное за мать лицо, увидала ее волнение, поняла, отчего муж теперь не оглядывался на нее, и с растерянным видом оглянулась вокруг себя.
– Ах, да делайте, как хотите! Разве я мешаю кому нибудь! – сказала она, еще не вдруг сдаваясь.
– Маменька, голубушка, простите меня!
Но графиня оттолкнула дочь и подошла к графу.
– Mon cher, ты распорядись, как надо… Я ведь не знаю этого, – сказала она, виновато опуская глаза.
– Яйца… яйца курицу учат… – сквозь счастливые слезы проговорил граф и обнял жену, которая рада была скрыть на его груди свое пристыженное лицо.
– Папенька, маменька! Можно распорядиться? Можно?.. – спрашивала Наташа. – Мы все таки возьмем все самое нужное… – говорила Наташа.
Граф утвердительно кивнул ей головой, и Наташа тем быстрым бегом, которым она бегивала в горелки, побежала по зале в переднюю и по лестнице на двор.
Люди собрались около Наташи и до тех пор не могли поверить тому странному приказанию, которое она передавала, пока сам граф именем своей жены не подтвердил приказания о том, чтобы отдавать все подводы под раненых, а сундуки сносить в кладовые. Поняв приказание, люди с радостью и хлопотливостью принялись за новое дело. Прислуге теперь это не только не казалось странным, но, напротив, казалось, что это не могло быть иначе, точно так же, как за четверть часа перед этим никому не только не казалось странным, что оставляют раненых, а берут вещи, но казалось, что не могло быть иначе.
Все домашние, как бы выплачивая за то, что они раньше не взялись за это, принялись с хлопотливостью за новое дело размещения раненых. Раненые повыползли из своих комнат и с радостными бледными лицами окружили подводы. В соседних домах тоже разнесся слух, что есть подводы, и на двор к Ростовым стали приходить раненые из других домов. Многие из раненых просили не снимать вещей и только посадить их сверху. Но раз начавшееся дело свалки вещей уже не могло остановиться. Было все равно, оставлять все или половину. На дворе лежали неубранные сундуки с посудой, с бронзой, с картинами, зеркалами, которые так старательно укладывали в прошлую ночь, и всё искали и находили возможность сложить то и то и отдать еще и еще подводы.
– Четверых еще можно взять, – говорил управляющий, – я свою повозку отдаю, а то куда же их?
– Да отдайте мою гардеробную, – говорила графиня. – Дуняша со мной сядет в карету.
Отдали еще и гардеробную повозку и отправили ее за ранеными через два дома. Все домашние и прислуга были весело оживлены. Наташа находилась в восторженно счастливом оживлении, которого она давно не испытывала.
– Куда же его привязать? – говорили люди, прилаживая сундук к узкой запятке кареты, – надо хоть одну подводу оставить.
– Да с чем он? – спрашивала Наташа.
– С книгами графскими.
– Оставьте. Васильич уберет. Это не нужно.
В бричке все было полно людей; сомневались о том, куда сядет Петр Ильич.
– Он на козлы. Ведь ты на козлы, Петя? – кричала Наташа.
Соня не переставая хлопотала тоже; но цель хлопот ее была противоположна цели Наташи. Она убирала те вещи, которые должны были остаться; записывала их, по желанию графини, и старалась захватить с собой как можно больше.