Привет! Меня зовут Михаил, работаю в компании DataLine сетевым инженером. По специальности я радиофизик, но со школьной скамьи интересуюсь криптографией.
В этом году научная работа в университете помогла совместить два этих интереса. Я посвятил свое исследование применению теории хаоса и задался вопросом: как физические хаотические системы могут помочь в решении задач классической криптографии и спроектировать сильный шифровальный алгоритм.
За основу взял систему дифференциальных уравнений Лоренца и написал новый алгоритм шифрования на njs – на практике это можно применить, например, для шифрования данных на веб-сервере. В посте расскажу, почему Лоренц, почему njs, какие есть варианты реализации и ограничения у выбранного решения.
Немного теории: какие задачи криптозащиты данных мы решали
В чем проблема. Для надежной защиты данных нам необходимы алгоритмы, которые обеспечат конфиденциальность, целостность информации, а также ее доступность для доверенной стороны при дешифровке. В современной классике криптографии для соблюдения этих условий часто используются алгоритмы несимметричного шифрования на основе открытого и закрытого ключа. Их применение регулируется на законодательном уровне: средства шифрования проходят государственную сертификацию, например, в России – ФСТЭК и ФСБ.
Но даже если алгоритм несимметричного шифрования признан криптостойким по всем нормам, вероятность его взлома никогда не равна нулю. Успешность взлома во многом зависит от вычислительных мощностей: если у хакера есть достаточные ресурсы для перебора всех вариантов ключа, он сможет его подобрать. Сейчас на практике этот риск не столь высок, но с распространением квантовых вычислений может стать реальной проблемой. Более подробно об этой трудности уже много писали на Хабре, например, наши коллеги переводили одно из последних исследований вот тут.
Чем поможет хаос. Теория хаоса не раз привлекала исследователей как возможное решение проблемы криптостойкости алгоритма. Этому способствуют отличия хаотических систем от классических криптографических:
Если криптография изучает результат конечного числа итерационных преобразований, то в теории хаоса рассматривается асимптотическое поведение системы, или бесконечное пространство.
Другими словами, количество криптографических состояний ограничено и конечно, а пространство состояний хаоса – это бесконечное множество непрерывных и дискретных значений.
При этом в теории хаоса существуют динамические законы, которые, по известной предыстории, позволяют однозначно определить эволюцию системы во времени.
То есть, в отличие от конечных и линейных вычислений в рамках классической криптографической системы, хаос изменяется постоянно и по более сложным законам. Поэтому несколько принципов теории хаоса можно использовать для защиты информации:
Высокую чувствительность к начальным условиям. Начальное состояние системы в теории хаоса – это практически аналогия открытому тексту в криптографии. Чувствительность хаотической системы к изменениям начальных условий можно сопоставить с чувствительностью криптосистем к открытому тексту и ключу.
Асимптотическую независимость начального и конечного состояния. Это понятие теории хаоса, близкое «запутыванию» в криптографии.
Синхронизацию хаотических ошибок. У двух хаотических систем есть способность синхронизироваться друг с другом. Из этого есть интересное следствие: после синхронизации дальнейшее развитие систем во времени будет происходить одинаково, но лишь при одинаковых начальных условиях. Возможность синхронизации можно использовать в процессе дешифровки.
Стойкость траектории, или асимптотическую устойчивость. Это свойство возникает вследствие синхронизации и проявляется в том, что любые небольшие колебания, которые могут нарушить синхронизацию, быстро затухают. По итогу синхронное колебание остается практически без изменений, то есть устойчивым к небольшим помехам.
Топологическую транзитивность. Она свойственна и динамическим, и криптографическим системам. С точки зрения криптографии, топологическая транзитивность необходима для сохранения состояния криптосистемы в тех пределах, которые допускает носитель информации.
Вот эти аналогии чуть нагляднее:
Криптографические объекты | Состояния хаотической системы |
Открытый текст | Начальное состояние системы и исходное сообщение |
Зашифрованный текст | Заключительное состояние системы |
Ключ | Начальные условия с параметрами |
Запутывание | Асимптотическая независимость начального и конечного состояния |
Исходя из этого я увидел реальные возможности применить хаотическую систему в проектировании криптографической системы.
Что конкретно взял в работу. В первичном эксперименте я хотел проверить теорию, что хаотические системы подходят для использования в алгоритмах шифрования. Для проверки гипотезы остановился на системе дифференциальных уравнений Лоренца – самой простой из многообразия хаотических систем.
Система Лоренца описывается тремя уравнениями:
где x, y, z – безразмерные переменные, а β, ρ и σ – параметры, при определенных значениях которых в системе наблюдается хаотический режим (β=8/3,σ=10 и ρ=28).
Для того чтобы использовать эту систему при создании алгоритма, я выбрал метод хаотической маскировки. Вот его схема:
Отправитель с помощью передающего устройства подмешивает исходное сообщение m(t) к несущему хаотическому сигналу x(t). Плюсом на схеме обозначен сумматор – он создает смесь сигналов CS, которая передается дальше.
Сигнал проходит канал связи и попадает на принимающее устройство получателя, где генератор хаотического сигнала u(t) с помощью пришедшей смеси сигналов CS синхронизируется с генератором отправителя. Минусом на схеме обозначено вычитающее устройство, которое восстанавливает исходное сообщение: оно равно разности принятой смеси CS сигналов и синхронного отклика u(t).
Практика: как реализовали модуль Nginx для шифрования
Изначально метод хаотической маскировки был востребован для создания устройств связи. Глядя на схему, можно представить себе аппаратную реализацию: берем устройство типа роутера и добавляем к нему генератор, который подмешивает шум к основному сигналу. В результате получаем зашифрованные радиоволны, которые для недоверенных устройств выглядят просто как шум.
У аппаратного варианта есть свои нюансы – если на сигнал будут действовать реальные шумы, возможны проблемы с дешифровкой. Но я в своей работе решил сосредоточиться на программной реализации – для шифрования данных при отправке к серверу или от сервера. Таких практических примеров в доступных мне исследованиях не встречалось, а потенциал для применения тут огромный.
Так что на основе предложенной схемы попробуем создать алгоритм для шифрования на стороне веб-сервера. Для начала определимся, какое ПО и язык программирования подойдут для этой задачи.
Почему Nginx. Это довольно популярное решение, которое обслуживает серверы многих высоконагруженных сайтов. Nginx используется для создания HTTP-сервера, обратного прокси-сервера, почтового прокси-сервера и TCP/UDP прокси-сервера общего назначения.
Основные функции веб-сервера в нем ложатся на модули трех типов:
обработчик – обрабатывает запрос и генерирует ответ;
фильтр – обрабатывает результаты обработчика;
балансировщик – выбирают какому бэкенду передать запрос, если бэкендов несколько.
Ядро Nginx берет на себя работу с сетью и реализацию протоколов, а также запускает необходимые для обработки запроса модули. За счет этого у нас есть возможность создавать отдельные компоненты для выполнения конкретных функций и реализовывать децентрализованную архитектуру. При этом обработку запросов в Nginx можно настраивать как угодно – у разработчика есть возможность определить, когда и как должен запускаться нужный модуль. При грамотном использовании это дает гибкость в распределении ресурсов и хороший потенциал для масштабирования.
Для нашей задачи архитектурные особенности Nginx тоже подходят – можем создать отдельный модуль шифрования с использованием нужного алгоритма.
Почему njs. Модуль njs был создан специально под сервер Nginx для написания гибких решений на популярном JavaScript. Модуль очень скоростной благодаря следующим особенностям:
Компиляция кода происходит сразу после старта Nginx, что экономит память и CPU
Для каждого запроса создается копия виртуальной машины: многие объекты можно использовать повторно.
Отсутствует сборка мусора: виртуальные микромашины обрабатывают короткоживущие запросы, поэтому не создают много временных объектов. Опять же, экономим память и CPU.
Как выглядят выбранные алгоритмы шифрования/дешифрования в модуле Nginx. При реализации было важно выбрать конкретный метод решения системы дифференциальных уравнений. Наиболее точный и производительный в рамках компьютерных вычислений – метод Рунге-Кутта.
В цикле преобразования данных с использованием этого метода в качестве параметра интегрирования выступает константа DELTA_TIME_STEP. Она определена в начале кода и равна 100. Где это используется, покажу ниже.
const DELTA_TIME_STEP = 100;
const MAX_CHAR_CODE = 65535;Архитектура алгоритма выглядит следующим образом: сначала задается система дифференциальных уравнений Лоренца с фиксированными параметрами, при которых наблюдается хаотический характер системы.
/**
* Первое уравнение системы Лоренца
*
* @param {Number} t - время
* @param {Number} x – координата по оси X
* @param {Number} y – координата по оси Y
* @param {Number} z – координата по оси Z
* @param {Number} U – сигнал сообщения
* @returns value of function
*/
function fX(t, x, y, z, U) {
return 10 * (U - x);
}
/**
* Второе уравнение системы Лоренца
*
* @param {Number} t - время
* @param {Number} x – координата на оси X
* @param {Number} y – координата на оси Y
* @param {Number} z – координата на оси Z
* @returns value of function
*/
function fY(t, x, y, z) {
return 28 * x - y - x * z;
}
/**
* Третье уравнение системы Лоренца
* @param {Number} t - время
* @param {Number} x – координата на оси X
* @param {Number} y – координата на оси Y
* @param {Number} z – координата на оси Z
* @returns value of function
*/
function fZ(t, x, y, z) {
return -(8/3) * z + x * y;
}Наши алгоритмы шифрования и расшифровывания обрабатывают наборы символов. Поэтому сначала мы объявляем функцию stringToCharCodes(data), которая принимает в качестве аргумента данные типа «строка» и возвращает массив символов.
Для обратного процесса функция charCodesToString(data) принимает символьный массив и возвращает данным исходный вид строки.
/**
* Преобразует формат строки в коды символов
*
* @param {String} data
* @returns array of char codes
*/
function stringToCharCodes(data) {
const outputNumbersArray = [];
for (let i = 0; i < data.length; i++) {
outputNumbersArray.push(data.charCodeAt(i) / MAX_CHAR_CODE);
}
return outputNumbersArray;
}
/**
* Преобразование кодов символов в формат строки
*
* @param {Массив чисел} данные
* @ возвращает строку из массива кодов символов
*/
function charCodesToString(data) {
const outputString = '';
for (let i = 0; i < data.length; i++) {
outputString += String.fromCharCode(data[i] * MAX_CHAR_CODE);
}
return outputString;
}Затем в дело вступает функция encodeMesage(dataString). Она принимает в качестве аргумента данные типа «строка» и выполняет их шифрование. В начале функции вызывается уже упомянутая stringToCharCodes(data) для получения нужного формата данных и определяются переменные, используемые в процессе шифрования.
После этого определяем основной цикл преобразования данных с использованием метода Рунге-Кутта. Здесь нам и пригодится константа DELTA_TIME_STEP в качестве параметра интегрирования.
Цикл будет работать до тех пор, пока не обработает каждый символ поступающих данных. В ходе каждой итерации, согласно выбранному методу интегрирования, пошагово вычисляются все решения системы дифференциальных уравнений Лоренца для четырех начальных условий. На выходе получается массив символов зашифрованных данных.
Для выполнения обратного преобразования используется функция decodeMesage(data)– она принимает в качестве аргумента данные типа «строка». Операции над данными в процессе расшифровки практически идентичны тем, что выполнялись при шифровании. Отличие – в выражениях для шифрованного и расшифрованного символов. Функция возвращает массив символов расшифрованного сообщения, которое можно преобразовать в строку с помощью функции charCodesToString(data).
/**
* Дешифровщик на основе хаотической системы уравнений
* Решение уравнений с использованием метода Рунге-Кутта
*
* @param {String} dataString a message
* @returns string of decoded message
*/
function decodeMessage(dataString) { let t = 0;
let x = 0.1;
let y = 0;
let z = 0;
let S = 0;
const charCodes = stringToCharCodes(dataString);
const output = [];
for (i = 0; i < charCodes.length; i++) {
S = charCodes[i] - y;
k1 = DELTA_TIME_STEP * fX(t, x, y, z, charCodes[i]);
m1 = DELTA_TIME_STEP * fY(t, x, y, z);
r1 = DELTA_TIME_STEP * fZ(t, x, y, z);
k2 = DELTA_TIME_STEP * fX(t + DELTA_TIME_STEP / 2, x + k1 / 2, y + m1
/ 2, z + r1 / 2, charCodes[i]);
m2 = DELTA_TIME_STEP * fY(t + DELTA_TIME_STEP / 2, x + k1 / 2, y +
m1 / 2, z + r1 / 2);
r2 = DELTA_TIME_STEP * fZ(t + DELTA_TIME_STEP / 2, x + k1 / 2, y + m1
/ 2, z + r1 / 2);
k3 = DELTA_TIME_STEP * fX(t + DELTA_TIME_STEP, x + k2 / 2, y + m2 /
2, z + r2 / 2, charCodes[i]);
m3 = DELTA_TIME_STEP * fY(t + DELTA_TIME_STEP, x + k2 / 2, y + m2 / 2, z + r2 / 2);
r3 = DELTA_TIME_STEP * fZ(t + DELTA_TIME_STEP, x + k2 / 2, y + m2 / 2, z + r2 / 2);
k4 = DELTA_TIME_STEP * fX(t + DELTA_TIME_STEP, x + k3, y + m3, z +
r3, charCodes[i]);
m4 = DELTA_TIME_STEP * fY(t + DELTA_TIME_STEP, x + k3, y + m3, z + r3);
r4 = DELTA_TIME_STEP * fZ(t + DELTA_TIME_STEP, x + k3, y + m3, z + r3);
x = x + (k1 + k2 * 2 + k3 * 2 + k4) / 6 ;
y = y + (m1 + m2 * 2 + m3 * 2 + m4) / 6;
z = z + (r1 + r2 * 2 + r3 * 2 + r4) / 6;
output.push(S);
t = t + DELTA_TIME_STEP;
}
return charCodesToString(output);
}
/**
* Шифровщик на основе хаотической системы уравнений
* Решение уравнений с использованием метода Рунге-Кутта
*
* @param {String} dataString a message
* @returns string of encoded message
*/
function encodeMesage(dataString) {
let t = 0;
let x = 0.1;
let y = 0;
let z = 0;
let S = 0;
const charCodes = stringToCharCodes(dataString);
const output = [];
/* Perform calculations */
for (i = 0; i < charCodes.length; i++) {
U = y + charCodes[i];
k1 = DELTA_TIME_STEP * fX(t, x, y, z, U);
m1 = DELTA_TIME_STEP * fY(t, x, y, z);
r1 = DELTA_TIME_STEP * fZ(t, x, y, z);
k2 = DELTA_TIME_STEP * fX(t + DELTA_TIME_STEP / 2, x + k1 / 2, y + m1
/ 2, z + r1 / 2, U);
m2 = DELTA_TIME_STEP * fY(t + DELTA_TIME_STEP / 2, x + k1 / 2, y +
m1 / 2, z + r1 / 2);
r2 = DELTA_TIME_STEP * fZ(t + DELTA_TIME_STEP / 2, x + k1 / 2, y + m1
/ 2, z + r1 / 2);
k3 = DELTA_TIME_STEP * fX(t + DELTA_TIME_STEP, x + k2 / 2, y + m2 / 2, z + r2 / 2, U);
m3 = DELTA_TIME_STEP * fY(t + DELTA_TIME_STEP, x + k2 / 2, y + m2 / 2, z + r2 / 2);
r3 = DELTA_TIME_STEP * fZ(t + DELTA_TIME_STEP, x + k2 / 2, y + m2 / 2, z + r2 / 2);
k4 = DELTA_TIME_STEP * fX(t + DELTA_TIME_STEP, x + k3, y + m3, z + r3, U);
m4 = DELTA_TIME_STEP * fY(t + DELTA_TIME_STEP, x + k3, y + m3, z + r3);
r4 = DELTA_TIME_STEP * fZ(t + DELTA_TIME_STEP, x + k3, y + m3, z + r3);
x = x + (k1 + k2 * 2 + k3 * 2 + k4) / 6;
y = y + (m1 + m2 * 2 + m3 * 2 + m4) / 6;
z = z + (r1 + r2 * 2 + r3 * 2 + r4) / 6;
output.push(U);
t = t + DELTA_TIME_STEP;
}
return charCodesToString(output);
}
В конце кода определены 2 служебных функции, которые используются при создании модулей: receive(r, data, flags), transmit(r, data, flags). Эти функции вызывают sendBuffer – функцию для модуля njs_stream_js_module, который позволяет задавать обработчики на njs.
Затем с помощью модуля export default регулируется область видимости: в случае обращения к скрипту извне будет видна только та часть кода, которая включена в модуль, а все остальное остается скрытым.
function receive(r, data, flags) {
r.sendBuffer(decodeMessage(data), flags);
}
function transmit(r, data, flags) {
r.sendBuffer(encodeMesage(data), flags);
export default {
transmit, receive
};Работу модуля я проверял на «голом» веб-сервере. В дальнейшем хочу проверить программную реализацию алгоритма на производительность и криптостойкость. В рамках этой задачи нужно будет задать конфигурацию серверу, смоделировать реальную ситуацию высоконагруженного сайта и протестировать процесс реального приема и передачи данных в нескольких тест-кейсах. Получается довольно объемная работа, так что об этом расскажу как-нибудь в следующий раз.