Гайд Шифрование строк на основе конечных автоматов

SapDragon · 9 Июл 2024

Более читабельная версия с рабочими картинками:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Всем привет, снова врайтап, который прочтёт два с половиной человека. Сегодня я страдая последствиями сломанного режима решился написать компил тайм шифрование строк на основе DFA. Не забывайте, что это всё Proof Of Concept, и для использования в реальном проекте нужно улучшать…

Часть 1: Теория автоматов для чайников ( и кофейников )
Что такое конечный автомат?
Представьте, что вы робот, который заменил людей в кодинге, и вы работаете в гугле. У вас есть несколько состояний:

Каждое событие (входной символ) переводит вас в новое состояние. Например, "Мозг кипит" переводит из "Анализ" в "Кофе". Вот это, друзья, и есть конечный автомат!

Математически это выглядит как A = (Q, Σ, δ, q0, F), где:

Q: множество состояний (Анализ, Отладка, Патч, Кофе)
Σ: алфавит входных символов (события, которые вызывают переходы)
δ: функция перехода (стрелки на диаграмме)
q0: начальное состояние (допустим анализ)
F: множество конечных состояний (в нашем случае их нет, работа никогда не заканчивается, увы это ж гугл )

От теории к практике
Теперь додумывая, что каждое состояние не просто название, а какое-то число. И при переходе из одного состояния в другое, мы не просто переходим, а еще и выдаем какой-то символ, вот и вся логика

На языке псевдо-кода:

Python:

state = initial_state

for char in input_text:
    output = output_table[state][char]
    state = transition_table[state][char]
    encrypted_text += output

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

Как это работает:

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

В нашей структуре DFA это отражено следующим образом:

C++:

struct DFA {
    std::array<std::array<std::array<uint8_t, ALPHABET_SIZE>, NUM_STATES>, NUM_LAYERS> transitions;
    std::array<std::array<uint8_t, NUM_STATES>, NUM_LAYERS> output;
    std::array<uint8_t, NUM_LAYERS> initial_state;
};

transitions: трехмерный массив, где первое измерение - это слой, второе - текущее состояние, третье - входной символ. Значение - это новое состояние.
output: двумерный массив, определяющий выходной символ для каждого состояния в каждом слое.
initial_state: начальное состояние для каждого слоя.

Нудный алгоритм:
Ну с учётом кучки автоматов, выходит такой процесс шифрования:

Инициализация: Каждый автомат устанавливается в свое начальное состояние.
Обработка символа:
- Первый автомат получает символ из входного текста.
- На основе текущего состояния и входного символа, автомат: a) Генерирует выходной символ. b) Переходит в новое состояние.
Последовательное преобразование:
- Выходной символ первого автомата становится входным для второго.
- Процесс повторяется через все автоматы в цепочке.
Формирование результата:
- Символ, выданный последним автоматом, становится результатом шифрования.
Итерация:
- Процесс повторяется для каждого символа входного текста.

Часть 2: Реализация многослойного автомата
Структура автомата

Начнём с простого, помните я вам показал выше код нашего автомата? Если забыли, то вот еще раз:

C++:

struct ComplexDFA {
    std::array<std::array<std::array<uint8_t, ALPHABET_SIZE>, NUM_STATES>, NUM_LAYERS> transitions;
    std::array<std::array<uint8_t, NUM_STATES>, NUM_LAYERS> output;
    std::array<uint8_t, NUM_LAYERS> initial_state;
};

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

Очередные MBA примитивы
В основном по приколу нам нужно добавить несколько примитивных функций, первая:

C++:

__forceinline constexpr uint8_t complex_ROL8(uint8_t x, unsigned int n) {
    n &= 7;
    uint8_t result = (x << n) | (x >> (8 - n));
    return result ^ (result >> 4) ^ (result << 3);
}

Эта функция не только выполняет циклический сдвиг, но и добавляет нелинейность с помощью XOR операций, ну типа прикольно, сложно все дела??

А еще у нас есть смешная нелинейная подстановка ( s-box )

C++:

__forceinline constexpr uint8_t enhanced_magic_hash(uint8_t x) {
    x ^= 0xAA;
    x = complex_ROL8(x, 3);
    x *= 0x13;
    x ^= 0x55;
    x = complex_ROL8(x, 5);
    x += 0x42;
    x ^= (x >> 3);
    x *= 0x2D;
    return x;
}

По факту функция тупо комбинируя различные операции пытается достичь высокой нелинейности, типа в случае внешнего анализа…

Генерация автомата
Теперь самое интересное - создание нашего автомата:

C++:

__forceinline constexpr ComplexDFA generate_complex_dfa(const char* key) {
    ComplexDFA dfa;
    std::array<uint8_t, NUM_LAYERS> key_hash;
    for (size_t i = 0; i < NUM_LAYERS; ++i) {
        key_hash[i] = 0x42 + i;
    }

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

Дальше мы с помощью итерации создаём хеш ключ для каждого слоя, чтобы позже использовать этот хеш для заполнения таблиц переходов и выходов:

C++:

   for (int i = 0; key[i] != '\\\\0'; ++i) {
        for (size_t layer = 0; layer < NUM_LAYERS; ++layer) {
            key_hash[layer] = enhanced_magic_hash(complex_ROL8(key_hash[layer], 1) ^ static_cast<uint8_t>(key[i]) ^ layer);
        }
    }

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

C++:

   for (size_t layer = 0; layer < NUM_LAYERS; ++layer) {
        for (uint8_t state = 0; state < NUM_STATES; ++state) {
            for (uint16_t symbol = 0; symbol < ALPHABET_SIZE; ++symbol) {
                uint8_t combined = complex_ROL8(state, 2) ^ complex_ROL8(static_cast<uint8_t>(symbol), 3) ^ key_hash[layer];
                combined = enhanced_magic_hash(combined);
                dfa.transitions[layer][state][symbol] = combined % NUM_STATES;
            }
            dfa.output[layer][state] = advanced_bit_scramble(enhanced_magic_hash(complex_ROL8(key_hash[layer], state)));
        }
        dfa.initial_state[layer] = key_hash[layer] % NUM_STATES;
    }
    return dfa;
}

Визуализация слоя:

Часть 3: Шифровать, шифровать, ьтаворфиш

Само шифрование
Теперь, когда у нас есть наш крутой многослойный автомат, давайте сделаем шифрование с помощью его кусочками

C++:

__forceinline constexpr EncryptedData encrypt_string(const char* input) {
    EncryptedData result{};
    std::array<uint8_t, NUM_LAYERS> state;
    for (size_t i = 0; i < NUM_LAYERS; ++i) {
        state[i] = ENCRYPTION_DFA.initial_state[i];
    }
    uint32_t counter = 0;

Здесь ничего интересного, просто подготавливаем всё

result - сюда будем ложить зашифрованное
state - начальные позиции для каждого слоя нашего автомата
counter - сам счётчик автомата

Теперь начинается самое интересное:

C++:

   size_t i;
    for (i = 0; input[i] != '\\\\0' && i < MAX_STRING_LENGTH; ++i) {
        uint8_t symbol = static_cast<uint8_t>(input[i]);
        symbol ^= advanced_bit_scramble(counter & 0xFF);

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

C++:

        for (size_t layer = 0; layer < NUM_LAYERS; ++layer) {
            symbol ^= ENCRYPTION_DFA.output[layer][state[layer]];
            state[layer] = ENCRYPTION_DFA.transitions[layer][state[layer]][symbol];
        }

Затем каждый символ проходит через все слои автомата:

Символ смешивается с выходом текущего состояния (symbol ^= ENCRYPTION_DFA.output[layer][state[layer]]).
Затем мы переходим в новое состояние на основе текущего символа (state[layer] = ENCRYPTION_DFA.transitions[layer][state[layer]][symbol]).

Визуализация прохождения через слои:

C++:

       result.data[i] = symbol;
        counter = some_mna(counter) + 17;
    }

    result.length = i;

    return result;
}

После прохождения через все слои, зашифрованный символ сохраняется, а счетчик обновляется с помощью MBA ( простите, я не хотел, меня заставили… )

Расшифровать то как…
Так, зашифровали… круто, а что дальше?

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

Выходит полностью обратная ситуация ( можете сравнить картинки даже ):

Часть 4: Заключение
Мы условно завершили смешной аналог ксора, давайте взглянем полностью, что же мы сделали:

Больше, чем просто XOR
Наш смешной шифр по моему выглядит интереснее чем просто ксор через 128 битные регистры

Многослойность: Использование нескольких слоев автомата выглядит страшно
Зависимость от состояния: Каждый символ шифруется по-разному в зависимости от текущего состояния автомата.
Уникальность для каждого ключа: Генерация уникального автомата под каждый ключ
Необычно: Это не две инструкции…
Нелинейность: Сложно найти все места по паттерну, при правильном полиморфе невозможно

Увы, через эмуляцию как и любое шифрование легко вытянуть ведь строка лежит на стеке

Заключительные мысли
Сегодня я вас познакомил с концепцией автоматов, чуток рассказал математики, заставил робота из гугла страдать, и наконец показал как делать базовое шифрование не через xorps! Мне эта тема показалась довольно интересной, ведь я её нигде не видел.

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

Блог:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Кривая, сырая, не вкусная реализация на гитхабе:

Пожалуйста, авторизуйтесь для просмотра ссылки.

найс форум, сьело все пикчи...

ne_latviankult · 10 Июл 2024

SapDragon написал(а):
Более читабельная версия с рабочими картинками:
Пожалуйста, авторизуйтесь для просмотра ссылки.

Всем привет, снова врайтап, который прочтёт два с половиной человека. Сегодня я страдая последствиями сломанного режима решился написать компил тайм шифрование строк на основе DFA. Не забывайте, что это всё Proof Of Concept, и для использования в реальном проекте нужно улучшать…

Часть 1: Теория автоматов для чайников ( и кофейников )
Что такое конечный автомат?
Представьте, что вы робот, который заменил людей в кодинге, и вы работаете в гугле. У вас есть несколько состояний:

Каждое событие (входной символ) переводит вас в новое состояние. Например, "Мозг кипит" переводит из "Анализ" в "Кофе". Вот это, друзья, и есть конечный автомат!

Математически это выглядит как A = (Q, Σ, δ, q0, F), где:

Q: множество состояний (Анализ, Отладка, Патч, Кофе)

Σ: алфавит входных символов (события, которые вызывают переходы)

δ: функция перехода (стрелки на диаграмме)

q0: начальное состояние (допустим анализ)

F: множество конечных состояний (в нашем случае их нет, работа никогда не заканчивается, увы это ж гугл )

От теории к практике
Теперь додумывая, что каждое состояние не просто название, а какое-то число. И при переходе из одного состояния в другое, мы не просто переходим, а еще и выдаем какой-то символ, вот и вся логика

На языке псевдо-кода:

Python:

state = initial_state for char in input_text: output = output_table[state][char] state = transition_table[state][char] encrypted_text += output

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

Как это работает:

Последовательное прохождение: Входной символ проходит через все слои по очереди. Выход одного слоя становится входом для следующего.

Независимые состояния: Каждый слой имеет свое собственное текущее состояние, которое меняется независимо от других слоев.

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

В нашей структуре DFA это отражено следующим образом:

C++:

struct DFA { std::array<std::array<std::array<uint8_t, ALPHABET_SIZE>, NUM_STATES>, NUM_LAYERS> transitions; std::array<std::array<uint8_t, NUM_STATES>, NUM_LAYERS> output; std::array<uint8_t, NUM_LAYERS> initial_state; };

transitions: трехмерный массив, где первое измерение - это слой, второе - текущее состояние, третье - входной символ. Значение - это новое состояние.

output: двумерный массив, определяющий выходной символ для каждого состояния в каждом слое.

initial_state: начальное состояние для каждого слоя.

Нудный алгоритм:
Ну с учётом кучки автоматов, выходит такой процесс шифрования:

Инициализация: Каждый автомат устанавливается в свое начальное состояние.

Обработка символа:

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

На основе текущего состояния и входного символа, автомат: a) Генерирует выходной символ. b) Переходит в новое состояние.

Последовательное преобразование:

Выходной символ первого автомата становится входным для второго.

Процесс повторяется через все автоматы в цепочке.

Формирование результата:

Символ, выданный последним автоматом, становится результатом шифрования.

Итерация:

Процесс повторяется для каждого символа входного текста.

Часть 2: Реализация многослойного автомата
Структура автомата

Начнём с простого, помните я вам показал выше код нашего автомата? Если забыли, то вот еще раз:

C++:

struct ComplexDFA { std::array<std::array<std::array<uint8_t, ALPHABET_SIZE>, NUM_STATES>, NUM_LAYERS> transitions; std::array<std::array<uint8_t, NUM_STATES>, NUM_LAYERS> output; std::array<uint8_t, NUM_LAYERS> initial_state; };

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

Очередные MBA примитивы
В основном по приколу нам нужно добавить несколько примитивных функций, первая:

C++:

__forceinline constexpr uint8_t complex_ROL8(uint8_t x, unsigned int n) { n &= 7; uint8_t result = (x << n) | (x >> (8 - n)); return result ^ (result >> 4) ^ (result << 3); }

Эта функция не только выполняет циклический сдвиг, но и добавляет нелинейность с помощью XOR операций, ну типа прикольно, сложно все дела??

А еще у нас есть смешная нелинейная подстановка ( s-box )

C++:

__forceinline constexpr uint8_t enhanced_magic_hash(uint8_t x) { x ^= 0xAA; x = complex_ROL8(x, 3); x *= 0x13; x ^= 0x55; x = complex_ROL8(x, 5); x += 0x42; x ^= (x >> 3); x *= 0x2D; return x; }

По факту функция тупо комбинируя различные операции пытается достичь высокой нелинейности, типа в случае внешнего анализа…

Генерация автомата
Теперь самое интересное - создание нашего автомата:

C++:

__forceinline constexpr ComplexDFA generate_complex_dfa(const char* key) { ComplexDFA dfa; std::array<uint8_t, NUM_LAYERS> key_hash; for (size_t i = 0; i < NUM_LAYERS; ++i) { key_hash[i] = 0x42 + i; }

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

Дальше мы с помощью итерации создаём хеш ключ для каждого слоя, чтобы позже использовать этот хеш для заполнения таблиц переходов и выходов:

C++:

for (int i = 0; key[i] != '\\\\0'; ++i) { for (size_t layer = 0; layer < NUM_LAYERS; ++layer) { key_hash[layer] = enhanced_magic_hash(complex_ROL8(key_hash[layer], 1) ^ static_cast<uint8_t>(key[i]) ^ layer); } }

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

C++:

for (size_t layer = 0; layer < NUM_LAYERS; ++layer) { for (uint8_t state = 0; state < NUM_STATES; ++state) { for (uint16_t symbol = 0; symbol < ALPHABET_SIZE; ++symbol) { uint8_t combined = complex_ROL8(state, 2) ^ complex_ROL8(static_cast<uint8_t>(symbol), 3) ^ key_hash[layer]; combined = enhanced_magic_hash(combined); dfa.transitions[layer][state][symbol] = combined % NUM_STATES; } dfa.output[layer][state] = advanced_bit_scramble(enhanced_magic_hash(complex_ROL8(key_hash[layer], state))); } dfa.initial_state[layer] = key_hash[layer] % NUM_STATES; } return dfa; }

Визуализация слоя:

Часть 3: Шифровать, шифровать, ьтаворфиш

Само шифрование
Теперь, когда у нас есть наш крутой многослойный автомат, давайте сделаем шифрование с помощью его кусочками

C++:

__forceinline constexpr EncryptedData encrypt_string(const char* input) { EncryptedData result{}; std::array<uint8_t, NUM_LAYERS> state; for (size_t i = 0; i < NUM_LAYERS; ++i) { state[i] = ENCRYPTION_DFA.initial_state[i]; } uint32_t counter = 0;

Здесь ничего интересного, просто подготавливаем всё

result - сюда будем ложить зашифрованное

state - начальные позиции для каждого слоя нашего автомата

counter - сам счётчик автомата

Теперь начинается самое интересное:

C++:

size_t i; for (i = 0; input[i] != '\\\\0' && i < MAX_STRING_LENGTH; ++i) { uint8_t symbol = static_cast<uint8_t>(input[i]); symbol ^= advanced_bit_scramble(counter & 0xFF);

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

C++:

for (size_t layer = 0; layer < NUM_LAYERS; ++layer) { symbol ^= ENCRYPTION_DFA.output[layer][state[layer]]; state[layer] = ENCRYPTION_DFA.transitions[layer][state[layer]][symbol]; }

Затем каждый символ проходит через все слои автомата:

Символ смешивается с выходом текущего состояния (symbol ^= ENCRYPTION_DFA.output[layer][state[layer]]).

Затем мы переходим в новое состояние на основе текущего символа (state[layer] = ENCRYPTION_DFA.transitions[layer][state[layer]][symbol]).

Визуализация прохождения через слои:

C++:

result.data[i] = symbol; counter = some_mna(counter) + 17; } result.length = i; return result; }

После прохождения через все слои, зашифрованный символ сохраняется, а счетчик обновляется с помощью MBA ( простите, я не хотел, меня заставили… )

Расшифровать то как…
Так, зашифровали… круто, а что дальше?

Инициализация: Мы начинаем с тех же начальных состояний и счетчика, что и при шифровании.

Обратный проход по слоям: Мы проходим слои в обратном порядке (от последнего к первому).

Восстановление состояний: Для каждого символа мы сначала определяем, в какое состояние перешел автомат, а затем используем это для расшифровки.

XOR с выходом предыдущего состояния: Мы выполняем XOR с выходом предыдущего состояния, а не текущего.

Обработка счетчика: После прохождения всех слоев, мы выполняем XOR с тем же значением счетчика, что и при шифровании.

Выходит полностью обратная ситуация ( можете сравнить картинки даже ):

Часть 4: Заключение
Мы условно завершили смешной аналог ксора, давайте взглянем полностью, что же мы сделали:

Больше, чем просто XOR
Наш смешной шифр по моему выглядит интереснее чем просто ксор через 128 битные регистры

Многослойность: Использование нескольких слоев автомата выглядит страшно

Зависимость от состояния: Каждый символ шифруется по-разному в зависимости от текущего состояния автомата.

Уникальность для каждого ключа: Генерация уникального автомата под каждый ключ

Необычно: Это не две инструкции…

Нелинейность: Сложно найти все места по паттерну, при правильном полиморфе невозможно

Увы, через эмуляцию как и любое шифрование легко вытянуть ведь строка лежит на стеке

Заключительные мысли
Сегодня я вас познакомил с концепцией автоматов, чуток рассказал математики, заставил робота из гугла страдать, и наконец показал как делать базовое шифрование не через xorps! Мне эта тема показалась довольно интересной, ведь я её нигде не видел.

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

Блог:
Пожалуйста, авторизуйтесь для просмотра ссылки.

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

найс форум, сьело все пикчи...

Интересно, какой компилятор вы юзаете, раз ни msvc ни шланг с latest плюсами не хочет компилировать ваше чудо

SapDragon · 10 Июл 2024

ne_latviankult написал(а):
Интересно, какой компилятор вы юзаете, раз ни msvc ни шланг с latest плюсами не хочет компилировать ваше чудо

На MSVC 14.40 с С++ latest всё отлично компилируется

ne_latviankult · 10 Июл 2024

SapDragon написал(а):
Посмотреть вложение 280841
На MSVC 14.40 с С++ latest всё отлично компилируется

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

W4tev3n · 10 Июл 2024

~~Мат логика и теория алгоритмов 2 курс моей прикладной матеши, сука, я хотел это забыть как страшный сон.~~

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

SapDragon · 10 Июл 2024

ne_latviankult написал(а):
А, просто в дебаге компил еррор. На самом деле сомнительные вещи делаете, ведь такими приватными методами шифрования обычных строк вы убиваете оптимайз

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

constexpr size_t kNumStates = 32;
constexpr size_t kAlphabetSize = 256;
constexpr size_t kMaxStringLength = 1024;
constexpr size_t kNumLayers = 3;

W4tev3n · 10 Июл 2024

SapDragon написал(а):
там PoC чуть поломанный, в идаале по скорости это чуть дольше чем ксор выходит. Ну и всегда можно регулировать эти константы напрямую меняя сложность автомата, и его производительность

constexpr size_t kNumStates = 32;
constexpr size_t kAlphabetSize = 256;
constexpr size_t kMaxStringLength = 1024;
constexpr size_t kNumLayers = 3;

А что по времени компиляции? Если пару сотен литералов так зашифровать бинарик собирать час не будет?

SapDragon · 10 Июл 2024

W4tev3n написал(а):
А что по времени компиляции? Если пару сотен литералов так зашифровать бинарик собирать час не будет?

не особо проверял, но во время тестов на 30-40 строках длинной 20-60 символов компил занимал меньше секунды ( на i7 14700hx )

Zodiak · 10 Июл 2024

SapDragon пикчи битые. Можешь конвертировать из svg в png/jp(e)g и тогда должны отображаться. Пингани если не сработает.

e0d1706 · 11 Июл 2024

SapDragon написал(а):
Более читабельная версия с рабочими картинками:
Пожалуйста, авторизуйтесь для просмотра ссылки.

Всем привет, снова врайтап, который прочтёт два с половиной человека. Сегодня я страдая последствиями сломанного режима решился написать компил тайм шифрование строк на основе DFA. Не забывайте, что это всё Proof Of Concept, и для использования в реальном проекте нужно улучшать…

Часть 1: Теория автоматов для чайников ( и кофейников )
Что такое конечный автомат?
Представьте, что вы робот, который заменил людей в кодинге, и вы работаете в гугле. У вас есть несколько состояний:

Каждое событие (входной символ) переводит вас в новое состояние. Например, "Мозг кипит" переводит из "Анализ" в "Кофе". Вот это, друзья, и есть конечный автомат!

Математически это выглядит как A = (Q, Σ, δ, q0, F), где:

Q: множество состояний (Анализ, Отладка, Патч, Кофе)

Σ: алфавит входных символов (события, которые вызывают переходы)

δ: функция перехода (стрелки на диаграмме)

q0: начальное состояние (допустим анализ)

F: множество конечных состояний (в нашем случае их нет, работа никогда не заканчивается, увы это ж гугл )

От теории к практике
Теперь додумывая, что каждое состояние не просто название, а какое-то число. И при переходе из одного состояния в другое, мы не просто переходим, а еще и выдаем какой-то символ, вот и вся логика

На языке псевдо-кода:

Python:

state = initial_state for char in input_text: output = output_table[state][char] state = transition_table[state][char] encrypted_text += output

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

Как это работает:

Последовательное прохождение: Входной символ проходит через все слои по очереди. Выход одного слоя становится входом для следующего.

Независимые состояния: Каждый слой имеет свое собственное текущее состояние, которое меняется независимо от других слоев.

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

В нашей структуре DFA это отражено следующим образом:

C++:

struct DFA { std::array<std::array<std::array<uint8_t, ALPHABET_SIZE>, NUM_STATES>, NUM_LAYERS> transitions; std::array<std::array<uint8_t, NUM_STATES>, NUM_LAYERS> output; std::array<uint8_t, NUM_LAYERS> initial_state; };

transitions: трехмерный массив, где первое измерение - это слой, второе - текущее состояние, третье - входной символ. Значение - это новое состояние.

output: двумерный массив, определяющий выходной символ для каждого состояния в каждом слое.

initial_state: начальное состояние для каждого слоя.

Нудный алгоритм:
Ну с учётом кучки автоматов, выходит такой процесс шифрования:

Инициализация: Каждый автомат устанавливается в свое начальное состояние.

Обработка символа:

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

На основе текущего состояния и входного символа, автомат: a) Генерирует выходной символ. b) Переходит в новое состояние.

Последовательное преобразование:

Выходной символ первого автомата становится входным для второго.

Процесс повторяется через все автоматы в цепочке.

Формирование результата:

Символ, выданный последним автоматом, становится результатом шифрования.

Итерация:

Процесс повторяется для каждого символа входного текста.

Часть 2: Реализация многослойного автомата
Структура автомата

Начнём с простого, помните я вам показал выше код нашего автомата? Если забыли, то вот еще раз:

C++:

struct ComplexDFA { std::array<std::array<std::array<uint8_t, ALPHABET_SIZE>, NUM_STATES>, NUM_LAYERS> transitions; std::array<std::array<uint8_t, NUM_STATES>, NUM_LAYERS> output; std::array<uint8_t, NUM_LAYERS> initial_state; };

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

Очередные MBA примитивы
В основном по приколу нам нужно добавить несколько примитивных функций, первая:

C++:

__forceinline constexpr uint8_t complex_ROL8(uint8_t x, unsigned int n) { n &= 7; uint8_t result = (x << n) | (x >> (8 - n)); return result ^ (result >> 4) ^ (result << 3); }

Эта функция не только выполняет циклический сдвиг, но и добавляет нелинейность с помощью XOR операций, ну типа прикольно, сложно все дела??

А еще у нас есть смешная нелинейная подстановка ( s-box )

C++:

__forceinline constexpr uint8_t enhanced_magic_hash(uint8_t x) { x ^= 0xAA; x = complex_ROL8(x, 3); x *= 0x13; x ^= 0x55; x = complex_ROL8(x, 5); x += 0x42; x ^= (x >> 3); x *= 0x2D; return x; }

По факту функция тупо комбинируя различные операции пытается достичь высокой нелинейности, типа в случае внешнего анализа…

Генерация автомата
Теперь самое интересное - создание нашего автомата:

C++:

__forceinline constexpr ComplexDFA generate_complex_dfa(const char* key) { ComplexDFA dfa; std::array<uint8_t, NUM_LAYERS> key_hash; for (size_t i = 0; i < NUM_LAYERS; ++i) { key_hash[i] = 0x42 + i; }

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

Дальше мы с помощью итерации создаём хеш ключ для каждого слоя, чтобы позже использовать этот хеш для заполнения таблиц переходов и выходов:

C++:

for (int i = 0; key[i] != '\\\\0'; ++i) { for (size_t layer = 0; layer < NUM_LAYERS; ++layer) { key_hash[layer] = enhanced_magic_hash(complex_ROL8(key_hash[layer], 1) ^ static_cast<uint8_t>(key[i]) ^ layer); } }

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

C++:

for (size_t layer = 0; layer < NUM_LAYERS; ++layer) { for (uint8_t state = 0; state < NUM_STATES; ++state) { for (uint16_t symbol = 0; symbol < ALPHABET_SIZE; ++symbol) { uint8_t combined = complex_ROL8(state, 2) ^ complex_ROL8(static_cast<uint8_t>(symbol), 3) ^ key_hash[layer]; combined = enhanced_magic_hash(combined); dfa.transitions[layer][state][symbol] = combined % NUM_STATES; } dfa.output[layer][state] = advanced_bit_scramble(enhanced_magic_hash(complex_ROL8(key_hash[layer], state))); } dfa.initial_state[layer] = key_hash[layer] % NUM_STATES; } return dfa; }

Визуализация слоя:

Часть 3: Шифровать, шифровать, ьтаворфиш

Само шифрование
Теперь, когда у нас есть наш крутой многослойный автомат, давайте сделаем шифрование с помощью его кусочками

C++:

__forceinline constexpr EncryptedData encrypt_string(const char* input) { EncryptedData result{}; std::array<uint8_t, NUM_LAYERS> state; for (size_t i = 0; i < NUM_LAYERS; ++i) { state[i] = ENCRYPTION_DFA.initial_state[i]; } uint32_t counter = 0;

Здесь ничего интересного, просто подготавливаем всё

result - сюда будем ложить зашифрованное

state - начальные позиции для каждого слоя нашего автомата

counter - сам счётчик автомата

Теперь начинается самое интересное:

C++:

size_t i; for (i = 0; input[i] != '\\\\0' && i < MAX_STRING_LENGTH; ++i) { uint8_t symbol = static_cast<uint8_t>(input[i]); symbol ^= advanced_bit_scramble(counter & 0xFF);

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

C++:

for (size_t layer = 0; layer < NUM_LAYERS; ++layer) { symbol ^= ENCRYPTION_DFA.output[layer][state[layer]]; state[layer] = ENCRYPTION_DFA.transitions[layer][state[layer]][symbol]; }

Затем каждый символ проходит через все слои автомата:

Символ смешивается с выходом текущего состояния (symbol ^= ENCRYPTION_DFA.output[layer][state[layer]]).

Затем мы переходим в новое состояние на основе текущего символа (state[layer] = ENCRYPTION_DFA.transitions[layer][state[layer]][symbol]).

Визуализация прохождения через слои:

C++:

result.data[i] = symbol; counter = some_mna(counter) + 17; } result.length = i; return result; }

После прохождения через все слои, зашифрованный символ сохраняется, а счетчик обновляется с помощью MBA ( простите, я не хотел, меня заставили… )

Расшифровать то как…
Так, зашифровали… круто, а что дальше?

Инициализация: Мы начинаем с тех же начальных состояний и счетчика, что и при шифровании.

Обратный проход по слоям: Мы проходим слои в обратном порядке (от последнего к первому).

Восстановление состояний: Для каждого символа мы сначала определяем, в какое состояние перешел автомат, а затем используем это для расшифровки.

XOR с выходом предыдущего состояния: Мы выполняем XOR с выходом предыдущего состояния, а не текущего.

Обработка счетчика: После прохождения всех слоев, мы выполняем XOR с тем же значением счетчика, что и при шифровании.

Выходит полностью обратная ситуация ( можете сравнить картинки даже ):

Часть 4: Заключение
Мы условно завершили смешной аналог ксора, давайте взглянем полностью, что же мы сделали:

Больше, чем просто XOR
Наш смешной шифр по моему выглядит интереснее чем просто ксор через 128 битные регистры

Многослойность: Использование нескольких слоев автомата выглядит страшно

Зависимость от состояния: Каждый символ шифруется по-разному в зависимости от текущего состояния автомата.

Уникальность для каждого ключа: Генерация уникального автомата под каждый ключ

Необычно: Это не две инструкции…

Нелинейность: Сложно найти все места по паттерну, при правильном полиморфе невозможно

Увы, через эмуляцию как и любое шифрование легко вытянуть ведь строка лежит на стеке

Заключительные мысли
Сегодня я вас познакомил с концепцией автоматов, чуток рассказал математики, заставил робота из гугла страдать, и наконец показал как делать базовое шифрование не через xorps! Мне эта тема показалась довольно интересной, ведь я её нигде не видел.

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

Блог:
Пожалуйста, авторизуйтесь для просмотра ссылки.

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

найс форум, сьело все пикчи...

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