Привет! Сегодня мы продолжаем реализовывать шифрование. В этой статье мы рассмотрим алгоритм шифра "Магма", который был разработан и использовался в СССР.

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

Шифр "Магма" имеет несколько идентификаторов:

• ГОСТ 28147-89 использовался в СССР и это была первая публикация шифра.

• ГОСТ Р 34.12-2015 использовался с 2015 года. Под этим идентификатором скрывалось два шифра: "Магма" и "Кузнечик".

• ГОСТ 34.12-2018 используется с 2018 года и представляет уже межгосударственный стандарт.

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

Характеристики и подробности

Шифр "Магма" — криптосистема, созданная на основе итерационной схемы сети Фейстеля.

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

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

Википедия — Сеть Фейстеля.

В "Магме" используется:

• Длина блока — 64 бита (8 байт).

• Длина ключа — 256 бит (32 байта).

• Количество итераций — 32 итерации.

Соответственно, сеть Фейстеля шифра "Магма" состоит из 32 ячеек, каждой на вход которой подаются данные (8 байт) и итерационный ключ (4 байта).

Алгоритм

Для того, чтобы реализовать шифр "Магма" понадобятся следующие функции и преобразования:

1. Формирование итерационных ключей.

2. Преобразование t.

3. Преобразование g.

4. Функция шифрования.

5. Функция расшифровывания.

Сам по себе алгоритм, как и его отдельные преобразования, довольно прост.

Зададим сразу несколько необходимых констант:

/// Длина блока: 64 бита
const BLOCK_SIZE: usize = 8;
/// Длина ключа: 256 бит
const KEY_SIZE: usize = 32;
/// Количество раундов шифрования: 32
const ROUNDS: usize = 32;

И создадим структуру шифра:

/// # Шифр "Магма"
///
/// - Длина блока: 64 бита
/// - Длина ключа: 256 бит
/// - Количество раундов шифрования: 32
#[derive(Debug, Clone)]
pub struct Magma {
    round_keys: [u32; ROUNDS],
    matrix_pi: [[u8; 16]; 8],
}

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

1. Формирование итерационных ключей

Начнем с того, что мы уже знаем:

• Длина ключа — 256 бит (32 байта).

• Количество итераций — 32 итерации.

И дополним новой информацией:

• Длина итерационного ключа — 32 бита (4 байта).

Получается, что из 32 байт ключа шифрования нам нужно получить 128 байт итерационных ключей, то есть в 4 раза больше.

Алгоритм формирования итерационных ключей максимально прост:

• Первые 24 ключа мы получаем просто разделяя ключ шифрования на части по 4 байта — получится 8 частей (ключей). Эти 8 частей мы просто повторим 3 раза и получим 24 ключа.

• Последние 8 ключей получаются почти таким же образом. Мы должны разделить ключ шифрования на 8 частей, а потом взять их в обратном порядке, то есть первым ключом будет часть, под порядковым номером 8, вторым — 7 и так далее.

Таким образом формируются 32 итерационных ключа.

// Первые 24 раундовых ключа
// с порядком следования 0, 1, 2, 3, 4, 5, 6, 7
let mut round_keys = [0u32; ROUNDS];
for i in 0..3 {
    for (j, chunk) in key.chunks_exact(4).enumerate() {
        let key = u32::from_be_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]);
        round_keys[j + 8 * i] = key;
    }
}

// Последние 8 раундовых ключа
// с порядком следования 7, 6, 5, 4, 3, 2, 1, 0
for (j, chunk) in key.chunks_exact(4).rev().enumerate() {
    let key = u32::from_be_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]);
    round_keys[j + 24] = key;
}

2. Преобразование t

Сложнее этого преобразования уже не будет, хотя само по себе оно довольно простое. Преобразование t принимает и возвращает 32-битную последовательность.

Это нелинейное преобразование разделяет 32-битную последовательность на части по 4 бита, далее по таблице \pi производит подмену и собирает обратно в 32-битную последовательность.

Начнем с разбиения 32-битной последовательности на части по 4 бита.

Для удобства восприятия я перевел значения в десятичное представление.

/// # Таблица подстановок RFC 7836
pub const ID_TC26_GOST_28147_PARAM_Z: [[u8; 16]; 8] = [
    [0x0c, 0x04, 0x06, 0x02, 0x0a, 0x05, 0x0b, 0x09, 0x0e, 0x08, 0x0d, 0x07, 0x00, 0x03, 0x0f, 0x01],
    [0x06, 0x08, 0x02, 0x03, 0x09, 0x0a, 0x05, 0x0c, 0x01, 0x0e, 0x04, 0x07, 0x0b, 0x0d, 0x00, 0x0f],
    [0x0b, 0x03, 0x05, 0x08, 0x02, 0x0f, 0x0a, 0x0d, 0x0e, 0x01, 0x07, 0x04, 0x0c, 0x09, 0x06, 0x00],
    [0x0c, 0x08, 0x02, 0x01, 0x0d, 0x04, 0x0f, 0x06, 0x07, 0x00, 0x0a, 0x05, 0x03, 0x0e, 0x09, 0x0b],
    [0x07, 0x0f, 0x05, 0x0a, 0x08, 0x01, 0x06, 0x0d, 0x00, 0x09, 0x03, 0x0e, 0x0b, 0x04, 0x02, 0x0c],
    [0x05, 0x0d, 0x0f, 0x06, 0x09, 0x02, 0x0c, 0x0a, 0x0b, 0x07, 0x08, 0x01, 0x04, 0x03, 0x0e, 0x00],
    [0x08, 0x0e, 0x02, 0x05, 0x06, 0x09, 0x01, 0x0c, 0x0f, 0x04, 0x0b, 0x00, 0x0d, 0x0a, 0x03, 0x07],
    [0x01, 0x07, 0x0e, 0x0d, 0x00, 0x05, 0x08, 0x03, 0x04, 0x0f, 0x0a, 0x06, 0x09, 0x0c, 0x0b, 0x02],
];

Далее нам понадобится матрица Pi. С помощью нее мы будем совершать подмену. Разделяя 32-битную последовательность на части по 4 бита мы получим 8 частей. Для каждой из частей мы будем использовать свою строку.

Интересно, что узлы замены могут варьироваться. В тексте стандарта ГОСТ 28147-89 указывается, что поставка заполнения узлов замены производится в установленном порядке, то есть разработчиком алгоритма.

Например, на Википедии содержатся 6 узлов замены: 4 для CryptoPro, 1 из RFC 7836 и 1 использовавшийся на территории Украины.

Википедия — Узлы замены шифра "Магма".

Поскольку значения 4-х битные, то и за пределы 16 значений в строке мы точно не выйдем.

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

Примерно таким образом это должно выглядеть.

После подмены, необходимо обратно собрать 32-битную последовательность не забывая о порядке.

Таким образом мы определили преобразование t.

fn transform_t(&self, value: u32) -> u32 {
    let mut result: u32 = 0;

    for (i, row) in self.matrix_pi.iter().enumerate() {
        let part = (value >> (4 * i)) & 0x0f;

        let substituted = row[part as usize] as u32;

        result |= substituted << (4 * i);
    }

    result
}

Здесь я использую обычные сдвиги и маску 0x0f, чтобы выбрать только 4 бита. Далее использую полученное значение как индекс для получения элемента в строке и на месте дополняю результирующее значение.

3. Преобразование g

Преобразование g работает с двумя 32-битными числами a и k, а в качестве результата возвращает только одно 32-битное число.

Это преобразование еще проще и состоит оно всего из 3-х действий:

1. Необходимо сложить числа a и k, отбрасывая переполнение (сложение по модулю 2 в степени 32).

2. Результат сложения необходимо передать преобразованию t.

3. Результат преобразования t необходимо циклически сдвинуть влево на 11 позиций.

fn transform_g(&self, a: u32, k: u32) -> u32 {
    let temp = a.wrapping_add(k);
    let substituted = self.transform_t(temp);
    substituted.rotate_left(11)
}

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

4. Функция шифрования

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

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

let mut a0 = u32::from_be_bytes([block[0], block[1], block[2], block[3]]);
let mut a1 = u32::from_be_bytes([block[4], block[5], block[6], block[7]]);

Мы будем чередовать работу над каждой частью. Это как раз будут ячейки сети Фейстеля. Мы будем каждый раз подавать данные (2 части по 4 байта) и итерационный ключ, а всего таких ячеек будет 32.

for i in 0..32 {
    let temp = a1;
    a1 = a0 ^ self.transform_g(a1, self.round_keys[i]);
    a0 = temp;
}

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

let mut result = Vec::with_capacity(BLOCK_SIZE);
result.extend_from_slice(&a1.to_be_bytes());
result.extend_from_slice(&a0.to_be_bytes());

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

5. Функция расшифровывания

let mut a0 = u32::from_be_bytes([block[0], block[1], block[2], block[3]]);
let mut a1 = u32::from_be_bytes([block[4], block[5], block[6], block[7]]);

Как и в случае шифрования, разбиваем данные на 2 части.

for i in (0..32).rev() {
    let temp = a1;
    a1 = a0 ^ self.transform_g(a1, self.round_keys[i]);
    a0 = temp;
}

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

let mut result = Vec::with_capacity(BLOCK_SIZE);
result.extend_from_slice(&a1.to_be_bytes());
result.extend_from_slice(&a0.to_be_bytes());

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

Проверка и эталонные значения

Проверка осуществлялась двумя способами:

1. С помощью эталонных значений из RFC 8891.

2. С помощью CyberChef.

Эталонные значения

В документе RFC 8891 заботливо приведены эталонные значения для всех используемых преобразований и функций.

Таким образом мы можем убедиться в том, что хотя бы один блок данных мы можем зашифровать верно.

В этой статье я не стану приводить данные значения, вы можете найти их либо в моем репозитории — там уже готовый тестовый код, либо в документе RFC 8891.

CyberChef

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

Каким-то образом я обнаружил, что CyberChef содержит реализацию как "Магмы", так и "Кузнечика", вот только с одной особенностью — в CyberChef не работает заполнение (padding).

Сверяя результаты я заметил, что все всегда сходится кроме последнего блока. Недолгими поисками я обнаружил, что CyberChef не дополняет данные согласно алгоритму PKCS5/7 (в целом одно и то же, за исключением неважных деталей).

В этом CyberChef подвел. Возможно я что-то упускаю, хотя перепроверил все несколько раз.

Тем не менее CyberChef можно пользоваться, произведя дополнение вручную. В таком случае все режимы шифрования: ECB, CBC, CFB, OFB, CTR отрабатывают верно.

Заключение проверки

running 7 tests
test tests::cipher::magma::decrypt_test::test_decryption ... ok
test tests::cipher::magma::encrypt_test::test_encryption ... ok
test tests::cipher::magma::keys_test::test_invalid_key_lenght - should panic ... ok
test tests::cipher::magma::keys_test::test_invalid_zeroed_key - should panic ... ok
test tests::cipher::magma::keys_test::test_key_generation ... ok
test tests::cipher::magma::transform_g_test::test_transform_g ... ok
test tests::cipher::magma::transform_t_test::test_transform_t ... ok

test result: ok. 7 passed; 0 failed; 0 ignored; 0 measured; 16 filtered out; finished in 0.00s

Все проверки использовали небольшое количество данных, считанные байты, хотя корректнее было бы сравнить зашифровав большой объект, например, видео.

Тем не менее — фундаментальные функции работают верно, составные функции, такие как шифрование и расшифровывание работают верно, а еще более высокоуровные функции, такие как шифрование в определенном режиме, также работают верно.

Заключение

digit4lsh4d0w

Автор

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

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

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

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

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

Весь код сохранен в репозитории GitVerse.

Напоследок про Rust

Иногда можно услышать вопрос: "А почему вы пишете на Rust? Разве Python не был бы более понятным?"

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

Кроме того, Rust позволяет явно указать, что и куда перемещается. Это может быть полезно. Python, напротив, создаёт абстракции, что мне не всегда удобно.

Для тех, кто не хочет изучать Rust или не хочет воспринимать мой код как псевдокод (что, в целом, не составляет труда), я могу порекомендовать использовать LLM, такие как GigaCode. Эти инструменты без ошибок переведут код на любой удобный язык программирования. Часть информации по реализации некоторых алгоритмов я получил именно таким образом, например, конвертируя код с Java.

Источники

• Википедия — Шифр "Магма".

• RFC 8891 — Шифр "Магма" и эталонные значения.

• Википедия — Сеть Фейстеля.

• RFC 7836 — Узлы замены.