LIMB
Вход Регистрация

тема

Алгоритм ChaCha 20/8

DESTR0Y · · 4 ответов · 626 просмотров

К разделу
Приветствую всех пользователей форума LIMB.cc
Сделано эксклюзивно для форума LIMB.cc

В данной теме пойдет речь о алгоритме шифрования ChaCha20/8(Имеется ввиду про 2 варианта алгоритма)
ChaCha20 - часто используемый и известный алгоритм шифрования, примечателен своей скоростью и простотой реализацией.
Не будем углублятся в историю ChaCha20, так как тема не об этом, можно коротко сказать что ChaCha20 улучшенная версия Salsa20. Широко используется в OpenSSH, WireGuard, libsodium, Google, Cloudflare, и других системах. Принят в TLS (например, TLS 1.3) как часть ChaCha20-Poly1305 AEAD.

У алгоритма который мы будем рассматривать в этой теме имеются различные вариации:
XChaCha20(HChaCha20)
ChaCha20-Poly1305(AEAD)
TLS ChaCha20
ChaCha20/12/8

Обсуждение будет о дефолтной версии ChaCha20 и укороченной ChaCha8. Моя реализация будет на ЯП C++. Тем не менее, я настоятельно рекомендую использовать C для реализации ChaCha20/8 (особенно с работой под Linux), он даст преимущество над уровнем контроля, производительности, + оптимальная работа с AVX (зависит от компилятора и задач). Также очень рекомендую Rust как отличную альтернативу. Я использую C++ для максимальной наглядности и понимания каждой части обработки раундов алгоритма, так как язык является высокоуровневым, я постараюсь показать наглядно все шаги и действия с входными байтами.

Тема будет разделена на части:
1. Принцип криптографии
2. Особенности и характеристика ChaCha20/8
3. Теория
4. Практика
5. ChaCha8 использующиеся у Akira
6. Заключение

1. Принцип криптографии
Не будем много времени уделять этой части, так как основная задача реализовать алгоритм ChaCha20. Но стоит сказать несколько вещей про сам принцип, ведь криптография в плане алгоритма который мы рассматриваем довольно таки простая, дело в том что само шифрование в смысле компьютерной информации это просто изменение исходных байтов в конечное(зашифрованное) Plaintext → Ciphertext.

Терминология:
Plaintext - входные байты(те которые нам нужно зашифровать)
Ciphertext - уже зашифрованные байты алгоритмом
Round(раунд) - итерация преобразования внутреннего состояния алгоритма с помощью математических операций
XOR - побитовое сложение байт(^)
Little-endian - формат хранения байтов в 32-битных словах
In-place - Шифрование данных прямо в исходном буфере(AES тоже может работать in-place в некоторых режимах, например, CTR)
(Возможно многим эти термины известны, а кому не понятны некоторые определения, мы их будем подробно разбирать ниже)

Множество Ransom используют AES, и не удивительно, на самом деле это очень хороший алгоритм, проверенный временем, быстро работает, стойкий к криптоанализу, 256-битный ключ, который почти невозможно перебрать брутфорсом. Но у AES-256 есть свои минусы, рассматривать всех их мы не будем, так как тема обсуждения не про это, но быстро пробежимся:
1. Поддержка аппаратного ускорения в процессоре, без него процесс шифрования замедляется в разы (придётся вызывать AESENC, AESDEC, AESKEYGENASSIST и т.д., что не всегда бывает выгодным, особенно для более незаметной работы софта).
2. Сложность идеальной реализации. Несмотря на понятный принцип работы алгоритма и раундов, сделать реализацию без утечек памяти, с корректной математической логикой и правильной последовательностью бывает сложно.
3. AES - блочный шифр, с которым нужно работать совместно с буфером(в большей мере), что делает дополнительный геморой, так как особенно при шифровке файлов рекомендуется использовать CBC режим, в котором формирование нового блока зависит от предыдущего.
Существуют и другие минусы, но о них мы поговорим в другой раз, ведь я хочу разобрать алгоритм ChaCha20 и показать его преимущества и существенные плюсы по сравнению с AES.

В контексте быстроты, стойкости и легкости реализации алгоритма я отдам предпочтение ChaCha20/8.

2. Особенности и характеристика ChaCha20/8

ChaCha20 - это прежде всего "Потоковый шифр", в отличии от блочных(AES), потоковый шифр обрабатывает данные по байтам, а не по блокам фиксированной величины. Алгоритм симметричный, тоесть ключ для шифровки и расшифровки один и тот же.
В ChaCha20 процесс шифрования происходит через взаимодействие с initial state(блок данных, это не те же самые блоки данных которые использует AES). Ранее я упоминал работу AES с буфером. Но на самом деле, полный in-place в ChaCha20 невозможен - лишь потому, что необходимо сохранять неизменённый блок данных (initial state). Поэтому приходится прибегать к использованию буфера, но в значительно меньшем объёме, чем в AES.
ChaCha20 не имеет режимов(по типу как в AES - CBC, ECB, OFB и т.д).
Ниже показана структура initial state:

Спойлер: initial state
Кол-во слов в initial state - 16 слов

Размер каждого слова - 4 байта

Первая часть initial state это 4 константы которые означают - expand 32-byte k(16 байт, стандарт)

Ключ занимает половину блока(initial state) - 8 слов

Всего лишь 1 слово занимает счетчик(counter) - 4 байта

Последняя часть это nonce(3 слова) - 12 байт

(В итоге initial state так и получается 16 + 32 + 4 + 12 = 64 байт)

ChaCha20 имеет больше раундов, чем AES - если не говорить о версии ChaCha8, которую использует Akira (об этом позже).
На деле это не 20 отдельных раундов, а 10 «двойных», каждый из которых включает в себя две фазы матриц: Column Round и Diagonal Round.
Алгоритм работает со состоянием из 16 слов (по 32 бита каждое), организованных в квадратную матрицу 4×4(визуально).

Теперь перейдем к теории, я попытаюсь подробно изложить и показать как устроен сам алгоритм ChaCha20.

3. Теория

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

Ключ.

Нужно сгенерировать ключ, который должен состоять из 32 байт(256 бит). Ключ хранится в каждом блоке сеанса шифрования к которому он принадлежит, позиция ключа state[4] -  state[11], ключ занимает 8 слов в блоке. Использование одного ключа для нескольких сеансов шифрования не рекомендуется.

Nonce.

Nonce(number used once) - уникальный набор байтов, используемый один раз для каждого сеанса шифрования занимающий позиции state[12]–state[14], размер 12 байт - 3 слова. Может передаваться и не скрывается от юзера. Многие путают nonce с IV, но это немного другое, они оба про уникальность но все же имеют различия, мы их не будем рассматривать так как тема не об этом.  Важно не использовать один и тот же nonce более одного раза с одним ключом, так как повторное использование опасно и делает легкий криптоанализ.

Счетчик.

Counter(счетчик) - занимает позицию state[15], размер 1 слово (4 байта). Его функция заключается в том, чтобы нумеровать блоки, которые определяют размер шифротекста. Максимальный размер, который может поместить в себе счетчик, - это 256 Гб данных(2^32 блоков * 64 байта = 2^32 * 2^6 = 2^38). Вообще изредка, когда нужно зашифровать что-то выше 256 Гб одним сеансом, но даже при таком раскладе, достигая лимита счетчика, вы создаете новые конфигурации для initial state. Счетчик как правило начинается с "1"(стандарт RFC 7539). Итог: counter занимает 1 слово в блоке, и нужен для счета блоков.

Constants.

Constants - это константы которые используются в начале initial state, занимает всего 4 слова(16 байт) и выглядят как 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574. Эти байты из себя представляют фразу "expand 32-byte k". Сами эти константы являются стандартом ChaCha20, они используются в начале initial state. Константы упорядочены в Little-endian. Стоит упомянуть что, вы можете подставить любые значения вместо "expand 32-byte k" лишь бы символы соответствовали 4 словам в блоке, но стоит понимать что вы меняете стандарт и параметры шифровки и расшифровки.

Не удалось прогрузить медиа


Что происходит с блоком, после генерации всех вышеперечисленных элементов у нас собирается initial state, который сразу же копируется в буфер, это важно понимать, так как нам нужно будет работать с оригинальным состоянием initial state. Все, у нас есть копия блока, запомнили. Теперь делим один блок на 2 типа:
1. Оригинальный не модифицированный блок который мы скопировали в буфер(buffer state)
2. Блок который мы прогнали через 20 раундов алгоритма.(working state)

Разберемся с блоком, который мы прогоняем через раунды. Сразу зафиксируем, то, что мы создали копию блока и записали ее в буфер, отложим ее. Теперь мы дальше работаем с блоком, который нужно преобразовать (working state).
В ChaCha20 используется комбинация из 2 фаз матриц преобразования, как я и упоминал выше, - это Column Round и Diagonal Round. Общая структура образована так, что working state изменяет свое состояние с помощью математических операций 10 раз подряд, используя 2 матрицы, всё же, если считать 1 манипуляцию с матрицей за отдельный раунд, то и получается 20 раундов.
Порядок прогона working state через матрицы идет поочерёдно каждый раунд, то есть это выглядит так: Column Round → Diagonal Round → Column Round → Diagonal Round.
Как и говорилось, эти матрицы размером 4х4, но в их структуре есть такое понятие, как четверть раунда - QRound. Это логическая часть одного раунда, будь то Column или Diagonal. Дело в том, что алгоритм преобразует один раунд через 4 операции с QRound с помощью формулы. Ещё более понятным языком working state прогоняется через раунды путем преобразования байтов по 4 слова каждые, это является, так сказать, минимальным шагом, итого: 80 раундов образно, я упоминал об этом выше

Не удалось прогрузить медиа

Блок working state начинает свое преобразование через матрицы, хочу сказать, что именно матрица подстраивается под QRound, так как последовательность state такая же, 0–15. А сами операции, проводимые над четвертями блока, имеют формат как "QRound(state[0], state[4], state[8], state[12])" — Column Round, "QRound(state[0], state[5], state[10], state[15])" — Diagonal Round.

Не удалось прогрузить медиа


Раунды и математические операции.

QRound обрабатывает 4 слова за раз через математическую операцию(формулу) которая представляет из себя 3 этапа, примечательно то что меняется только a и c между собой а так же уменьшается число сдвига влево. Представим что "QRound (state[a], state, state[c], state[d])", ниже на скрине представлена сама формула:

Не удалось прогрузить медиа


1. Сложение по модулю 2^32
a += b - это сложение по модулю mod2^32, это означает, что даже если байты при сложении дали результат более 32 бит, то биты после >32 отбрасываются, что и даёт нам определённые ограничения в модуле.
Пример: 0xF77BA691 + 0xDF9B21AA = 0x1D7168A3B. У нас тут теперь 36 битов вместо 32, далее просто отбрасываем лишние биты, 36 - 4 = 32, то есть отбрасываем "1", получается 0xD7168A3B (мы отбрасываем все биты старше 32-го, от 33 и выше). "a" при сложении присваивает себе сумму a + b, сама "b" остаётся неизменной

2. Операция XOR
d ^= a - дефолт XOR операция. XOR - одна из самых часто используемых операций в криптографии, это простейшая операция "Исключающее ИЛИ". Правила XOR'а приведены ниже:

Не удалось прогрузить медиа

биты слов "d" и "a" выполняют XOR между собой и результат присваивается "d"

3. Циклический сдвиг влево ROTL
d <<<= 16 - циклический сдвиг влево, ещё более простая операция, просто берём кусок битов (в нашем случае это 16) с левой части и ставим его в правую часть. Приведём простой пример, с циклическим сдвигом в 7 бит:
32 бита: 01101000 00101101 11001010 11100110, из них берём 7 старших бит, это "0110100"
Теперь вставляем их в правую часть слова и получается: 00010110 11100101 01110011 00110100

Не удалось прогрузить медиа


Это все основные математические операции, проводимые в раундах ChaCha20. Формула, которая преобразует наши 4 слова в QRound, применяется по очереди 4 раза на 1 QRound. И так 80 раз на весь блок. Но всё же правильнее говорить 20 раундов в контексте работы алгоритма, так как QRound - это всё же не полный раунд, а 1/4 от него

Не удалось прогрузить медиа


Сложение initial state между собой.

И так, теперь у нас есть преобразованный блок с помощью 20 раундов(working state) и не измененный блок который мы как раз таки и сохраняли в буфер(buffer state). Следующим шагом нужно будет сделать сложение по модулю 2^32. Да то самое которое мы применяли в раундах. Сложение происходит между словами из working state и buffer state (буферной копии исходного состояния). Тоесть 1 слово из working state складывается с словом buffer state, и так все 16 слов

Не удалось прогрузить медиа


После сложения наших блоков, мы получаем самый важный элемент алгоритма ChaCha20, это keystream. Keystream уже взаимодействует с plaintext, тоеть еще не с зашифрованными данными.
Keystream взаимодействует с plaintext через XOR, по 1 байту! Поэтому ChaCha20 является потоковым шифром, тоесть мы шифруем ПОБАЙТОВО. После Xor-а keystram и plaintext мы уже получаем сам ШИФРОТЕКСТ


Не удалось прогрузить медиа


Расшифровка.

Расшифровка в ChaCha20 идентична процессу шифрования, так как алгоритм является симметричным потоковым шифром. Используется тот же keystream, сгенерированный из ключа, nonce и счётчика (начинается с 1 по [RFC 7539]). Шифротекст побайтно комбинируется с keystream через операцию XOR:

plaintext = ciphertext ⊕ keystream

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

4. Практика.

Продемонстрирую работу с SIMD - AVX2/AVX512. Альтернативным способом сперва показана более медленная работа без иснтрукций.
Будут приведены в пример различные режимы: Полное шифрование всех байтов, Шифрование по частям, и шифрование какого либо фрагмента файла

Генерация initial state.

Создаем блок с помощью компонентов указанных выше.
Первым делом генерируем ключ и nonce, я сделал это через RDSEED, не рекомендую использовать просто RDSEED, советую с чем то комбинировать.
Подключаем #include <immintrin.h>

C++: 
inline void generateKeyAndNonce(uint32_t key[8], uint32_t nonce[3]) {
    for (int i = 0; i < 8; ++i) {
        unsigned int val = 0;
        while (!_rdseed32_step(&val)) {}
        key[i] = val;
    }
    for (int i = 0; i < 3; ++i) {
        unsigned int val = 0;
        while (!_rdseed32_step(&val)) {}
        nonce[i] = val;
    }
}

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

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

C++: 
inline void qr(uint32_t& a, uint32_t& b, uint32_t& c, uint32_t& d) {
    a += b; d ^= a; d = (d << 16) | (d >> 16);
    c += d; b ^= c; b = (b << 12) | (b >> 20);
    a += b; d ^= a; d = (d << 8) | (d >> 24);
    c += d; b ^= c; b = (b << 7) | (b >> 25);
}
(С версии С++20, для циклического сдвига вы можете юзать std::rotl(d, x);, вместо (d << x) | (d >> x))

Функция block - простое оформление блока(прогон через раунды). Создаем output и передаем байты именно для XOR с plaintext, поэтому мы делаем массив 64 и разбиваем все на байты. Функция в себе содержит 16 слов которые и формируют блок. Сохраняем в "x" исходное состояние(state), прогоняем через раунды → складываем с state и получаем keystream.

C++: 
inline void block(uint8_t output[64], uint32_t key[8], uint32_t nonce[3], uint32_t counter) {
    uint32_t state[16] = {
        0x61707865, 0x3320646e, 0x79622d32, 0x6b206574,
        key[0], key[1], key[2], key[3], key[4], key[5], key[6], key[7],
        counter, nonce[0], nonce[1], nonce[2]
    };

uint32_t x[16];
    std::memcpy(x, state, sizeof(state));

    for (int i = 0; i < 10; ++i) {
        qr(x[0], x[4], x[8], x[12]);
        qr(x[1], x[5], x[9], x[13]);
        qr(x[2], x[6], x[10], x[14]);
        qr(x[3], x[7], x[11], x[15]);
        qr(x[0], x[5], x[10], x[15]);
        qr(x[1], x[6], x[11], x[12]);
        qr(x[2], x[7], x[8], x[13]);
        qr(x[3], x[4], x[9], x[14]);
    }

    for (int i = 0; i < 16; ++i) {
        x[i] += state[i];
    }

    std::memcpy(output, x, 64);
}

Функция encrypt - Финальная в изменении байтов, на input мы подаем байт из plaintext, на выход мы подаем уже output, что означает ciphertext

C++: 
void encrypt(uint32_t key[8], uint32_t nonce[3], uint32_t counter,
    const uint8_t* input, uint8_t* output, size_t len) {
    const size_t block_size = 64;
    uint8_t keystream[64];

    for (size_t i = 0; i < len; i += block_size) {
        size_t remaining = std::min(block_size, len - i);
        chacha20_block(keystream, key, nonce, counter + (uint32_t)(i / block_size));

        for (size_t b = 0; b < remaining; ++b) {
            output[i + b] = input[i + b] ^ keystream[b];
        }
    }
}

Задаем размер блока, len - длинна файла(в байтах). В цикле участвует сам XOR plaintext с keystream, это основная задача, но так же

C++: 
size_t remaining = std::min(block_size, len - i);

Это проверка на остаток, то есть шифрование только тех байтов которые остались в ласт блоке < 64

C++: 
chacha20_block(keystream, key, nonce, counter + (uint32_t)(i / block_size));

Формирование Keystream с новым счетчиком + 1 на итерацию

C++: 
for (size_t b = 0; b < remaining; ++b) {
    output[i + b] = input[i + b] ^ keystream[b];
}

Ну и сам XOR с остатком/без

В main собираем наш алгоритм.

C++: 
std::string filename = "file.exe";
std::ifstream file(filename, std::ios::binary | std::ios::ate);

size_t size = file.tellg();
std::vector<uint8_t> input(size), output(size);
const size_t chunk_size = 1024 * 1024;
file.seekg(0);
for (size_t i = 0; i < size; i += chunk_size) {
    size_t chunk = std::min(chunk_size, size - i);
    file.read(reinterpret_cast<char*>(input.data() + i), chunk);
}
file.close();

Начинаем работу с файлом который мы шифруем,
Читаем файл, ставим курсор в конец, определяем размер. Создаем вход(plaintext) и выход(ciphertext)
Читаем файл по 1мб(можно изменить это значение, но как по мне самое оптимальное)
Создаем предохранитель для остальных байтов в ласт чанке
Закрываем работу с файлом

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

C++: 
std::ofstream out("file.xyz", std::ios::binary);
for (size_t i = 0; i < size; i += chunk_size) {
    size_t chunk = std::min(chunk_size, size - i);
    out.write(reinterpret_cast<const char*>(output.data() + i), chunk);
}

Финальная обработка, открываем для чтения, пишем байты через цикл
(output.data() + i) - указатель на текущую позицию в выходном буфере
Преобразуем данные через reinterpret_cast, так же не забываем про предохранитель std::min(chunk_size, size - i)

Запускаем в Release x64

Не удалось прогрузить медиа


Время шифрования: 390 мс (172 MB 443.015 MB/s)

Скорость 443MB в секунду.
Реализация алгоритма самая простая, это максимально наглядный пример ChaCha20.

Теперь давайте напишем алгоритм с помощью SIMD: AVX2/AVX512

Процессор: Ryzen 7 7700
Версия компилятора: MSVC 19.42
Версия С++: 20
Свойства проекта:

Не удалось прогрузить медиа


Сначала проверьте есть ли на процессоре AVX512

C++: 
_may_i_use_cpu_feature(_FEATURE_AVX512F)

или:

C++: 
bool cpu_supports_avx512() {
    int cpuInfo[4];
    __cpuid(cpuInfo, 0);
    if (cpuInfo[0] < 7) return false;
    __cpuidex(cpuInfo, 7, 0);
    return (cpuInfo[1] & (1 << 16)) != 0;
}
(Функции для автоматического применения определенных инструкций, если они доступны на процессоре)

Ниже я приведу переписанные функции под AVX инструкции.
Реализация математических алгоритмов для раундов.

AVX2:
C++: 
inline void qr(__m256i& a, __m256i& b, __m256i& c, __m256i& d) {
    a = _mm256_add_epi32(a, b); d = _mm256_rol_epi32(_mm256_xor_si256(d, a), 16);
    c = _mm256_add_epi32(c, d); b = _mm256_rol_epi32(_mm256_xor_si256(b, c), 12);
    a = _mm256_add_epi32(a, b); d = _mm256_rol_epi32(_mm256_xor_si256(d, a), 8);
    c = _mm256_add_epi32(c, d); b = _mm256_rol_epi32(_mm256_xor_si256(b, c), 7);
}

AVX512:
C++: 
inline void qr(__m512i& a, __m512i& b, __m512i& c, __m512i& d) {
    a = _mm512_add_epi32(a, b); d = _mm512_rol_epi32(_mm512_xor_si512(d, a), 16);
    c = _mm512_add_epi32(c, d); b = _mm512_rol_epi32(_mm512_xor_si512(b, c), 12);
    a = _mm512_add_epi32(a, b); d = _mm512_rol_epi32(_mm512_xor_si512(d, a), 8);
    c = _mm512_add_epi32(c, d); b = _mm512_rol_epi32(_mm512_xor_si512(b, c), 7);
}

Важный момент! Функция __mm256/512_rol_epi32 может не поддерживаться в вашем процессоре/компиляторе/библиотеке. Эта функция циклического сдвига AVX-512VL или AVX-512BW/DQ. (https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=_mm256_rol_epi32&expand=4682)
Если же у вас в <immintrin.h> не поддерживаются циклические сдвиги.
Вы можете написать отдельную функцию:
C++: 
inline __m512i rotl32_avx512(__m512i x, int r) {
    return _mm512_or_si512(_mm512_slli_epi32(x, r), _mm512_srli_epi32(x, 32 - r));
}
C++: 
inline __m256i rotl256_avx2(__m256i x, int r) {
    return _mm256_or_si256(_mm256_slli_epi32(x, r), _mm256_srli_epi32(x, 32 - r));
}

AVX2 позволяет реализовать 8 параллельных блоков, поэтому в функции мы сразу будем обрабатывать 8 блоков, вместо 1:

C++: 
void block_avx2(uint8_t output[8][64], uint32_t key[8], uint32_t nonce[3], uint32_t counter_base) {
    uint32_t counters[8];
    for (int i = 0; i < 8; i++) counters[i] = counter_base + i;

    __m256i v[16];
    v[0] = _mm256_set1_epi32(0x61707865);
    v[1] = _mm256_set1_epi32(0x3320646e);
    v[2] = _mm256_set1_epi32(0x79622d32);
    v[3] = _mm256_set1_epi32(0x6b206574);

    for (int i = 0; i < 8; i++) {
        v[4 + i] = _mm256_set1_epi32(key[i]);
    }

    v[12] = _mm256_loadu_si256((__m256i*)counters);
    v[13] = _mm256_set1_epi32(nonce[0]);
    v[14] = _mm256_set1_epi32(nonce[1]);
    v[15] = _mm256_set1_epi32(nonce[2]);

    __m256i w[16];
    for (int i = 0; i < 16; i++) w[i] = v[i];

    for (int i = 0; i < 10; i++) {
        qr(w[0], w[4], w[8], w[12]);
        qr(w[1], w[5], w[9], w[13]);
        qr(w[2], w[6], w[10], w[14]);
        qr(w[3], w[7], w[11], w[15]);
        qr(w[0], w[5], w[10], w[15]);
        qr(w[1], w[6], w[11], w[12]);
        qr(w[2], w[7], w[8], w[13]);
        qr(w[3], w[4], w[9], w[14]);
    }

[I][B]    [/B][/I]for (int i = 0; i < 16; i++) {
        w[i] = _mm256_add_epi32(w[i], v[i]);
    }

    alignas(32) uint32_t buf[16][8];
    for (int i = 0; i < 16; i++) {
        _mm256_store_si256((__m256i*)buf[i], w[i]);
    }

    for (int block = 0; block < 8; block++) {
        for (int word = 0; word < 16; word++) {
            std::memcpy(output[block] + word * 4, &buf[word][block], 4);
        }
    }
}

Используем параллельную обработку:
output[8][64] - 8 блоков, 64 - байт
Функция _mm256_set1_epi32 одна из важнейших. Она создает 256-битный векторный регистр, в котором все 8 32-битных элементов содержат одинаковое значение. Тем самым работая с 8 параллельными блоками
Все элементы делаем параллельными 32*8, после чего копируем их в рабочее состояние w = v
Прогоняем через раунды, складываем с исходным состоянием
Конвертируем регистры обратно в массивы __mm256 → uint32_t

Далее сам XOR с plaintext:

C++: 
void encrypt_avx2(uint32_t key[8], uint32_t nonce[3], uint32_t counter,
    const uint8_t* input, uint8_t* output, size_t len) {

    uint8_t keystream_blocks[8][64];

    for (size_t i = 0; i < full_blocks; i++) {
        block_avx2(keystream_blocks, key, nonce, counter + (uint32_t)(i * 8));

        for (int b = 0; b < 8; b++) {
            const uint8_t* in_ptr = input + (i * 8 + b) * 64;
            uint8_t* out_ptr = output + (i * 8 + b) * 64;
            for (int j = 0; j < 64; j++) {
                out_ptr[j] = in_ptr[j] ^ keystream_blocks[b][j];
            }
        }
    }
}

Такой же принцип, просто уже с 8 блоками.
Берем 8 блоков по 64 байта и для каждого байта делаем XOR из Keystream, все записываем в output.
Так же нужна будет обработка последних 8 блоков и последних байт

Абсолютно то же самое с AVX512, теперь мы можем обрабатывать параллельно 16 блоков
Такая же структура, просто меняем __m256i на __m512i, _mm256_set1_epi32 на _mm512_set1_epi32, _mm256_store_si256 на _mm512_store_si512 и т.д
Изменяем в циклах 8 на 16, так как параллельно блоков мы обрабатываем 16 вместо 8

Итоги, скорость шифрования(полного):
ChaCha20(без SIMD) ~ 450 MB/S
ChaCha20(AVX2) ~ 2100 MB/S
ChaCha20(AVX512) ~ 2500 MB/S

Не полное шифрование.

Как я упоминал выше, мы попробуем шифрование с пятнами, то есть какие-то блоки мы будем шифровать, а какие-то нет. Пример будет 1/4, это означает, что 1 блок из 4 будет шифроваться.

Добавим в код цикл на обработку в encrypted, уже в последнюю функцию, когда идет xor с plaintext.

C++: 
if (global_block % 4 == 0) {
    size_t offset = global_block * block_size;
    size_t bytes_left = len > offset ? len - offset : 0;
    size_t bytes_to_xor = (bytes_left > block_size) ? block_size : bytes_left;

    for (size_t b = 0; b < bytes_to_xor; b++) {
        output[offset + b] = input[offset + b] ^ keystream_blocks[i][b];
    }
}
else {
    size_t offset = global_block * block_size;
    size_t bytes_left = len > offset ? len - offset : 0;
    size_t bytes_to_copy = (bytes_left > block_size) ? block_size : bytes_left;

    std::memcpy(output + offset, input + offset, bytes_to_copy);
}

if - выполняем операцию с блоком, else - пропускаем
Делаем смещение в байтах с начала файла до текущего блока: номер блока * размер блока
Еще 2 проверки на кол-во байтов оставшихся до конца файла от смещения
Сколько байт реально нужно обработать в XOR
В else - если блок не кратен 4, то мы просто копируем блок без изменений

Итоги, скорость шифрования с пропуском блоков:
ChaCha20(без SIMD) ~ 2000 MB/S
ChaCha20(AVX2) ~ 2900 MB/S
ChaCha20(AVX512) ~ 3500 MB/S

Шифрование только начала файла(20%):
Шифрует только первые 20% plaintext, вы можете поставить свое значение вместо 20

Передаем в функцию параметр переменную для %:
C++: 
void encrypt(uint32_t key[8], uint32_t nonce[3], uint32_t counter,
    const uint8_t* input, uint8_t* output, size_t total_len, double percent

Определяем сколько всего нужно зашифровать:
C++: 
size_t encrypt_len = static_cast<size_t>(total_len * percent);
size_t encrypt_blocks = (encrypt_len + block_size - 1) / block_size;

После чего в самом main, можно изменять значения процента:
C++: 
double percent = 0.20;
encrypt(key, nonce, counter, input.data(), output.data(), size, percent);

Скорость по шифрованию будет такая же на какой реализации вы его собрали(без SIMD, AVX2, AVX512), отличие в том, что вы шифруете 1/5 НАЧАЛА файла, а следующие байты даже не трогаете. Поэтому общее время выполнения меньше, и итоговая скорость в MB/s может быть выше, чем при полном шифровании.

В заключение хочу сказать, что лучше, конечно, использовать SIMD-инструкции, AVX2 на процессоре есть у большинства пользователей, поэтому, используя их, вы значительно ускоряете работу алгоритма в 7–10 раз чем при обычной реализации.

5. ChaCha8 использующиеся у Akira.

Akira юзает 8 раундовую версию в ChaCha, что делает буст по скорости.
Еще одно отличие это 128 битный ключ, на самом деле он  все так же оставляет inital state размером 512 бит, просто дублирует 128бит подряд.

Хочу отметить что Akira начало шифрует Kcipher2, но это не столь важная деталь в этой теме

Единственное что нужно изменить нам в реализации это кол-во раундов в цикле

C++: 
for (int i = 0; i < 10; i++) {
    qr(w[0], w[4], w[8], w[12]);
    qr(w[1], w[5], w[9], w[13]);
    ...

на:
C++: 
for (int i = 0; i < 4; i++) {
    qr(w[0], w[4], w[8], w[12]);
    qr(w[1], w[5], w[9], w[13]);
    ...

Давайте запустим и посмотрим на скорость
(Я буду юзать все тот же ключ на 256 бит, так как прироста к скорости с помощью 128 бит нет)

Запуск на AVX512:
Скорость: ~ 3000 MB/S

Давайте поэкспериментируем и зашифруем пятнами используя ChaCha8

Не удалось прогрузить медиа


Скорость доходит до:
Скорость: ~ 5100 MB/S

Можно таким же образом шифровать только 10-30% файла, либо еще как то комбинировать с параметрами.
Ссылки на разбор алгоритма у Akira:
Не удалось прогрузить медиа

Расшифровка зашифрованных файлов программы-вымогателя Akira (Linux/ESXi 2024) с использованием набора GPU

Хакер делает из любви то, что другие не стали бы делать и за деньги. Недавно я помог компании восстановить их данные после атаки программы-вымогателя Akira без выплаты выкупа. Я делюсь...
Не удалось прогрузить медиа
 habr.com
Не удалось прогрузить медиа

GitHub - yohanes/akira-bruteforce

Contribute to yohanes/akira-bruteforce development by creating an account on GitHub.
Не удалось прогрузить медиа
 github.com

6. Заключение

Минимальная скорость шифрования: ~ 420 MB/s

Максимальная скорость(в контексте моих экспериментов): ~ 5100 MB/s

ChaCha является действительно качественным и достойным алгоритмом на сегодняшнее время, не удивительно, что его используют множество RaaS.
Легкость реализации, использование SIMD-инструкций и подобных манипуляций объединяет в алгоритме все нужные качества отличного шифра.

Полезные ссылки:
Официальная страница Wiki ChaCha: https://en.wikipedia.org/wiki/ChaCha20-Poly1305
Chrome использующие ChaCha для Cookies: https://github.com/runassu/chrome_v20_decryption
Типы алгоритма: https://pycryptodome.readthedocs.io/en/latest/src/cipher/chacha20.html
Реализация самого ChaCha20(без SIMD): https://pastecode.dev/s/dgzh9vx1
Документация ChaCha20 - RFC 8439: https://datatracker.ietf.org/doc/html/rfc8439

Список директив:
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdint>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <immintrin.h>
#include <intrin.h>

by DESTR0Y
Сделано эксклюзивно для форума LIMB.cc

Не удалось прогрузить медиа
👍46 ❤️9 😁9 🤔9
Топ, надеюсь 200 бачей улетят автору НА И ВСЕ!
Ответgabarage

Топ, надеюсь 200 бачей улетят автору НА И ВСЕ!

Не удалось прогрузить медиа


Спасибо бро
👍1
ОтветDESTR0Y

Не удалось прогрузить медиа Спасибо бро

андрей - GOAT
👍2
Статья оформлена грамотно и красиво. Но она не имеет смысла мы здесь не анализируем щифры ведь. Это на другие форумы где более углублённо в эту тему. Этих методов шифрования и из разбор на столько завален в интернете что можно сказать дохуя и больше . заработать денег не поможет, как бы ты это не изучал и не углублялся. Антивирусные программы в рот ебали эти шифры и не один не поможет либо на очень короткое время. Сейчас все намного труднее. Если конечно шифровать чьи то сервера с данными это да, единственное что можно делать . но сейчас в некоторых странах уже приравняли это к терроризму заниматься этим нужно быть дураком.
👍4

Гостевой просмотр. Чтобы отвечать и ставить реакции, войдите или зарегистрируйтесь.