Биокриптография как шанс спастись от криптоапокалипсиса

в 8:39, , рубрики: Блог компании «Лаборатория Касперского», генетические алгоритмы, информационная безопасность, квантовая криптография, криптография, машинное обучение

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

Так вот, он был неправ (хотя без слепого пятна можно было бы и обойтись). Сейчас наука то и дело подсматривает у живых организмов отдельные принципы и приемы. Да, они не всегда энергетически эффективны, часто область их применения узка, зато проверены миллионами лет выживания. И вот что интересно – даже в такой безжизненной области, как криптография, находится применение тому, что придумала когда-то жизнь. Конечно, животные не шифруют передаваемую информацию, так что напрямую тут ничего не украсть. We need to go deeper, как выразился известный оскароносец.

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

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

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

Любая биологическая система решает какие-то свои задачи, будь то поиск пищи, приспособление к изменяющимся условиям внешней среды, противодействие агрессии и так далее. Это можно представить в виде вычислительной модели – относительно грубой, в силу того, что человечество изучило жизнь не слишком глубоко. И есть ряд задач, в том числе криптографических и криптоаналитических, для решения которых эти модели оказываются чрезвычайно эффективны. Да-да, речь о нейронных сетях, я уверен, все их узнали. Но не только о них.

Нейронные сети

Биокриптография как шанс спастись от криптоапокалипсиса - 2Если сформулировать кратко, искусственная нейронная сеть – очень-очень грубая и в корне неверная модель мозга. Состоит из множества взаимосвязанных нейронов, каждый может получать несколько сигналов от других нейронов и передавать один выходной сигнал. Каждая межнейронная связь имеет свой вес, который может изменяться в процессе обучения сети. Видов нейросетей, начиная с перцептрона 1957 года, придумано множество, различаются они передаточной функцией нейрона, топологией соединений нейронов и способами обучения – определения весов связей.

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

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

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

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

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

Генетические алгоритмы

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

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

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

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

Искусственные иммунные системы

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

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

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

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

Disclaimer: Данная колонка отражает лишь частное мнение ее автора. Оно может совпадать с позицией компании «Лаборатория Касперского», а может и не совпадать. Тут уж как повезет.

Автор: «Лаборатория Касперского»

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js