В этой статье мы рассмотрим один из простых алгоритмов шифрования, алгоритм под названием ChaCha, о предшественнике которого, под названием Salsa20, мы уже упоминали. Алгоритм ChaCha очень известен и широко применяется, а также имеет за собой стандартизированное в RFC описание, которое в упрощенном виде будет показано далее.
ChaCha — это потоковый алгоритм шифрования, а это значит, что алгоритм шифрует набор байтов не разбивая на блоки, а сразу использует байтовый поток целиком. ChaCha использует 256-битный ключ (key), 32-битный счетчик (counter) и 96-битное однократно используемое число (nonce) и имеет также некоторую настройку — количество раундов. Чаще всего используются следующие количества раундов — 20 и 8, и алгоритмы, реализующие ChaCha в таком виде, имеют отдельные наименования — ChaCha20 и ChaCha8. Первый вариант применяется в шифровании данных, размер который не больше 256 гигабайт, и некоторых сетевых протоколах, а второй вариант применяется в некоторых криптографических генераторах случайных чисел. Также стоит отметить, что ChaCha стандартизирован в документе RFC 7539.
Сам алгоритм в своем составе содержит следующие операции:
- сложение по модулю 2 ^^ 32
- побитовое сложение по модулю 2 (xor)
- циклическое сдвиги влево
Эти операции составляют основной строительный блок алгоритма — операцию «четверть раунда» (quarterRound), которая принимает некоторый массив из 16 32-разрядных беззнаковых чисел (uint в терминологии D), а также набор из 4 32-разрядных чисел. Эти числа согласно стандарту обозначены четырьмя первыми буквами латинского алфавита — a, b, c и d. Для произвольного массива x в D эта операция может быть описана так:
static void quarterRound(ref uint[16] x, int a, int b, int c, int d) { x[a] += x[b]; x[d] = rotl32(x[d] ^ x[a], 16); x[c] += x[d]; x[b] = rotl32(x[b] ^ x[c], 12); x[a] += x[b]; x[d] = rotl32(x[d] ^ x[a], 8); x[c] += x[d]; x[b] = rotl32(x[b] ^ x[c], 7); }
Операция rotl32 — это циклический сдвиг влево, который в D может быть описан следующим образом:
static uint rotl32(uint x, int n) { return x << n | (x >> (-n & 31)); }
Но в спецификации ChaCha используется не 4 числа, а 16. Эти 16 32-битных беззнаковых числа образуют то, что условно можно назвать состоянием (state) самого шифра. Операция quarterRound рассматривает состояние как единый вектор с индексами элементов в нем от 0 до 15. Данный строительный блок алгоритма принимает четыре заранее предопределенных числа, которые соответствуют определенным индексам состояния, и для которых выполняется своеобразная трансформация, псевдослучайным образом смешивающая биты состояния в зависимости от того, что уже в состояние загружено.
ChaCha имеет своеобразную функцию, которая применяется «для блока» (block function). Эта функция и является центральной для всего алгоритма: она комбинирует четверть-раундовые функции в основное преобразование, которое можно в D записать следующим образом:
void encryptBlock(ref uint[16] inbuf, ref ubyte[64] outbuf) { uint[16] x = inbuf.dup; for (int i = NUMBER_OF_ROUNDS; i > 0; i -= 2) { quarterRound(x, 0, 4, 8, 12); quarterRound(x, 1, 5, 9, 13); quarterRound(x, 2, 6, 10, 14); quarterRound(x, 3, 7, 11, 15); quarterRound(x, 0, 5, 10, 15); quarterRound(x, 1, 6, 11, 12); quarterRound(x, 2, 7, 8, 13); quarterRound(x, 3, 4, 9, 14); } for (int i = 0; i < 16; i++) { x[i] += _state[i]; } serialize(x, outbuf); }
Функция serialize выполняет вспомогательную роль, превращая состояние в набор из 64 байтов, которые выглядят как случайный набор байтов. Все, что выполняется до процедуры serialize и делает развертку состояния в набор байтов, которые в дальнейшем и будут использоваться в качестве потока ключей, который складывается с потоком открытого текста.
Вот так serialize выглядит в D:
static void serialize(ref uint[16] inbuf, ref ubyte[64] outbuf) { for (int i = 0; i < 16; i++) { u32t8le(inbuf[i], outbuf[i*4..i*4+4].ptr); } }
Функция u32t8le превращает 32-битное целое в массив байтов, который передается в функцию как указатель на массив байтов:
static void u32t8le(uint v, ubyte* p) { p[0] = v & 0xff; p[1] = (v >> 8) & 0xff; p[2] = (v >> 16) & 0xff; p[3] = (v >> 24) & 0xff; }
Возвращаясь, к самому алгоритму, стоит упомянуть о том, что состояние ChaCha перед выполнением всех преобразований должно быть нужным образом подготовлено. Эта подготовка включает в себя предварительную загрузку в сам массив состояния 4 констант, 8 32-битных значений составленных из самого ключа, 1 счетчика. Последние 3 числа в векторе состояния — это значения, полученные из байтов однократно используемого числа.
Функция получения нужного состояния из ключа, счетчика и однократно используемого числа выглядит так:
void initState() { _state[0] = 0x61707865; _state[1] = 0x3320646e; _state[2] = 0x79622d32; _state[3] = 0x6b206574; for (int i = 0; i < 8; i++) { _state[4 + i] = u8t32le(_key[i*4..i*4+4]); } _state[12] = _counter; for (int i = 0; i < 3; i++) { _state[13 + i] = u8t32le(_nonce[i*4..i*4+4]); } } static uint u8t32le(ubyte[] p) { uint value = p[3]; value = (value << 8) | p[2]; value = (value << 8) | p[1]; value = (value << 8) | p[0]; return value; }
Первые блоки состояния — это константы, которые согласно спецификации представляют собой просто байты фразы «expand 32-byte k», которые скомбинированы в несколько целочисленных 32-битных числах с порядком байтов little-endian. Обычно используются именно эти константы, так как они рекомендованы разработчиком алгоритма Д. Бернштейном, но ничто не мешает использовать иные варианты.
Функция u8t32le является вспомогательной и превращает набор байтов в 32-битное число, принимая в себя набор байтов как массив.
После того, как выполнена инициализация состояния и оно загружено и если есть некоторое сообщение, которое нужно зашифровать и которое представлено набором байтов, то шифрование/расшифровывание можно выполнить через простое смешивание ключевого потока (который получается последовательным вызовом функции, которая дает набор ключей «для блока») и байтов сообщения через операцию xor:
void encryptDecrypt(ubyte[] inbuf, ubyte[] outbuf) { ubyte[64] block; int length = cast(uint) inbuf.length; initState; for (uint i = 0; i < length; i += 64) { encryptBlock(_state, block); _state[12]++; for (uint j = i; j < i + 64; j++) { if (j >= length) { break; } outbuf[j] = inbuf[j] ^ block[j - i]; } } }
Теперь можно собрать все детали реализации в один класс, который можно параметризовать количеством раундов:
import std.stdio; static void u32t8le(uint v, ubyte* p) { p[0] = v & 0xff; p[1] = (v >> 8) & 0xff; p[2] = (v >> 16) & 0xff; p[3] = (v >> 24) & 0xff; } static uint u8t32le(ubyte[] p) { uint value = p[3]; value = (value << 8) | p[2]; value = (value << 8) | p[1]; value = (value << 8) | p[0]; return value; } static uint rotl32(uint x, int n) { return x << n | (x >> (-n & 31)); } class ChaCha(uint NUMBER_OF_ROUNDS) { private { uint[16] _state; ubyte[32] _key; uint _counter; ubyte[12] _nonce; } private { static void quarterRound(ref uint[16] x, int a, int b, int c, int d) { x[a] += x[b]; x[d] = rotl32(x[d] ^ x[a], 16); x[c] += x[d]; x[b] = rotl32(x[b] ^ x[c], 12); x[a] += x[b]; x[d] = rotl32(x[d] ^ x[a], 8); x[c] += x[d]; x[b] = rotl32(x[b] ^ x[c], 7); } static void serialize(ref uint[16] inbuf, ref ubyte[64] outbuf) { for (int i = 0; i < 16; i++) { u32t8le(inbuf[i], outbuf[i*4..i*4+4].ptr); } } void initState() { _state[0] = 0x61707865; _state[1] = 0x3320646e; _state[2] = 0x79622d32; _state[3] = 0x6b206574; for (int i = 0; i < 8; i++) { _state[4 + i] = u8t32le(_key[i*4..i*4+4]); } _state[12] = _counter; for (int i = 0; i < 3; i++) { _state[13 + i] = u8t32le(_nonce[i*4..i*4+4]); } } } void encryptBlock(ref uint[16] inbuf, ref ubyte[64] outbuf) { uint[16] x = inbuf.dup; for (int i = NUMBER_OF_ROUNDS; i > 0; i -= 2) { quarterRound(x, 0, 4, 8, 12); quarterRound(x, 1, 5, 9, 13); quarterRound(x, 2, 6, 10, 14); quarterRound(x, 3, 7, 11, 15); quarterRound(x, 0, 5, 10, 15); quarterRound(x, 1, 6, 11, 12); quarterRound(x, 2, 7, 8, 13); quarterRound(x, 3, 4, 9, 14); } for (int i = 0; i < 16; i++) { x[i] += _state[i]; } serialize(x, outbuf); } void encryptDecrypt(ubyte[] inbuf, ubyte[] outbuf) { ubyte[64] block; int length = cast(uint) inbuf.length; initState; for (uint i = 0; i < length; i += 64) { encryptBlock(_state, block); _state[12]++; for (uint j = i; j < i + 64; j++) { if (j >= length) { break; } outbuf[j] = inbuf[j] ^ block[j - i]; } } } this(ubyte[32] key, uint counter, ubyte[12] nonce) { _key = key; _counter = counter; _nonce = nonce; } }
Для испытания алгоритма потребуется небольшая функция, которая позволяет выводить 16-ричные значения в удобном виде:
auto printHexDump(ubyte[] data) { foreach (i, e; data) { if (! (i % 16)) { writef("\n"); } writef("%02x ", e); } writeln; }
А также потребуется задать ключ, счетчик (по умолчанию равен 1), а также nonce, которые можно для сравнения взять из стандарта RFC 7539 (что мы сделали) и пример открытого текста для шифрования:
ubyte[32] key = [ 0x00, 0x01, 0x02, 0x03, 0x05, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f ]; ubyte[12] nonce = [ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x4a, 0x00, 0x00, 0x00, 0x00 ]; ubyte[114] input = [ 0x4c, 0x61, 0x64, 0x69, 0x65, 0x73, 0x20, 0x61, 0x6e, 0x64, 0x20, 0x47, 0x65, 0x6e, 0x74, 0x6c, 0x65, 0x6d, 0x65, 0x6e, 0x20, 0x6f, 0x66, 0x20, 0x74, 0x68, 0x65, 0x20, 0x63, 0x6c, 0x61, 0x73, 0x73, 0x20, 0x6f, 0x66, 0x20, 0x27, 0x39, 0x39, 0x3a, 0x20, 0x49, 0x66, 0x20, 0x49, 0x20, 0x63, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x6f, 0x66, 0x66, 0x65, 0x72, 0x20, 0x79, 0x6f, 0x75, 0x20, 0x6f, 0x6e, 0x6c, 0x79, 0x20, 0x6f, 0x6e, 0x65, 0x20, 0x74, 0x69, 0x70, 0x20, 0x66, 0x6f, 0x72, 0x20, 0x74, 0x68, 0x65, 0x20, 0x66, 0x75, 0x74, 0x75, 0x72, 0x65, 0x2c, 0x20, 0x73, 0x75, 0x6e, 0x73, 0x63, 0x72, 0x65, 0x65, 0x6e, 0x20, 0x77, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x62, 0x65, 0x20, 0x69, 0x74, 0x2e ];
В результате получаем следующую функцию main для эксперимента:
void main() { ubyte[32] key = [ 0x00, 0x01, 0x02, 0x03, 0x05, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f ]; ubyte[12] nonce = [ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x4a, 0x00, 0x00, 0x00, 0x00 ]; ubyte[114] input = [ 0x4c, 0x61, 0x64, 0x69, 0x65, 0x73, 0x20, 0x61, 0x6e, 0x64, 0x20, 0x47, 0x65, 0x6e, 0x74, 0x6c, 0x65, 0x6d, 0x65, 0x6e, 0x20, 0x6f, 0x66, 0x20, 0x74, 0x68, 0x65, 0x20, 0x63, 0x6c, 0x61, 0x73, 0x73, 0x20, 0x6f, 0x66, 0x20, 0x27, 0x39, 0x39, 0x3a, 0x20, 0x49, 0x66, 0x20, 0x49, 0x20, 0x63, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x6f, 0x66, 0x66, 0x65, 0x72, 0x20, 0x79, 0x6f, 0x75, 0x20, 0x6f, 0x6e, 0x6c, 0x79, 0x20, 0x6f, 0x6e, 0x65, 0x20, 0x74, 0x69, 0x70, 0x20, 0x66, 0x6f, 0x72, 0x20, 0x74, 0x68, 0x65, 0x20, 0x66, 0x75, 0x74, 0x75, 0x72, 0x65, 0x2c, 0x20, 0x73, 0x75, 0x6e, 0x73, 0x63, 0x72, 0x65, 0x65, 0x6e, 0x20, 0x77, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x62, 0x65, 0x20, 0x69, 0x74, 0x2e ]; ubyte[114] encrypt; ubyte[114] decrypt; auto chacha = new ChaCha!20(key, 1, nonce); chacha.encryptDecrypt(input, encrypt); chacha.encryptDecrypt(encrypt, decrypt); write("key:"); printHexDump(key[]); writeln; write("nonce:"); printHexDump(nonce[]); writeln; writeln("plaintext:"); printHexDump(input[]); writeln("encrypted:"); printHexDump(encrypt[]); writeln("decrypted:"); printHexDump(decrypt[]); writeln; }
Сам алгоритм при этом дает следующий результат, которые совпадает с приведенным в RFC примером:
key: 00 01 02 03 05 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f nonce: 00 00 00 00 00 00 00 4a 00 00 00 00 plaintext: 4c 61 64 69 65 73 20 61 6e 64 20 47 65 6e 74 6c 65 6d 65 6e 20 6f 66 20 74 68 65 20 63 6c 61 73 73 20 6f 66 20 27 39 39 3a 20 49 66 20 49 20 63 6f 75 6c 64 20 6f 66 66 65 72 20 79 6f 75 20 6f 6e 6c 79 20 6f 6e 65 20 74 69 70 20 66 6f 72 20 74 68 65 20 66 75 74 75 72 65 2c 20 73 75 6e 73 63 72 65 65 6e 20 77 6f 75 6c 64 20 62 65 20 69 74 2e encrypted: 3f 87 4c a4 bf ec 8c 79 30 e5 b6 c2 82 cd 96 de 80 12 0f 25 e5 78 97 e9 ea bd 82 cf f6 5a ae 74 43 e9 a1 12 21 0f 69 78 31 4c 94 3d 6e 8d e6 37 22 99 4b 0d 1a 1a 1c 75 11 d1 3f fb 56 62 57 be a0 4f 23 53 9e 6e a3 86 c0 a2 82 93 c7 78 78 c2 76 41 f7 e1 40 62 a7 60 41 27 82 16 6b 29 5a 9e dd 33 9a 0b 2d f0 44 5b 22 b3 a7 d7 38 e7 f5 9b e5 1f decrypted: 4c 61 64 69 65 73 20 61 6e 64 20 47 65 6e 74 6c 65 6d 65 6e 20 6f 66 20 74 68 65 20 63 6c 61 73 73 20 6f 66 20 27 39 39 3a 20 49 66 20 49 20 63 6f 75 6c 64 20 6f 66 66 65 72 20 79 6f 75 20 6f 6e 6c 79 20 6f 6e 65 20 74 69 70 20 66 6f 72 20 74 68 65 20 66 75 74 75 72 65 2c 20 73 75 6e 73 63 72 65 65 6e 20 77 6f 75 6c 64 20 62 65 20 69 74 2e
Таким образом, мы получили практически буквальное переложение псевдокода из RFC и минимальную работоспособную версию реализации ChaCha в D. Естественно, в алгоритме есть много вещей, которые стоит проработать: убрать некоторые элементы в стиле C (появились в нашем коде под влиянием этой реализации), уделить больше времени оптимизации работы и безопасности некоторых элементов, но это все не входит в тему статьи и не являлось нашей целью.
Алгоритм в данной реализации не готов к использованию в реальных приложениях, а скорее служит в качестве демонстрационного примера и строительного блока для других алгоритмов, например, аутентифицированного шифрования. Поэтому, напоминаем о том, что не стоит писать криптографию самостоятельно — используйте уже существующие и известные библиотеки.
На этом все, и ниже мы покажем не ООП-версию кода, опирающуюся на уже упомянутую нами реализацию:
import std.stdio; extern(C) { //void* memcpy(scope return void* s1, scope const(void*) s2, ulong n) pure nothrow @nogc; int printf(scope const(char*) format, ...); } static void u32t8le(uint v, ubyte[] p) { p[0] = v & 0xff; p[1] = (v >> 8) & 0xff; p[2] = (v >> 16) & 0xff; p[3] = (v >> 24) & 0xff; } static uint u8t32le(ubyte[] p) { uint value = p[3]; value = (value << 8) | p[2]; value = (value << 8) | p[1]; value = (value << 8) | p[0]; return value; } static uint rotl32(uint x, int n) { // http://blog.regehr.org/archives/1063 return x << n | (x >> (-n & 31)); } // https://tools.ietf.org/html/rfc7539#section-2.1 static void chacha20_quarterround(ref uint[16] x, int a, int b, int c, int d) { x[a] += x[b]; x[d] = rotl32(x[d] ^ x[a], 16); x[c] += x[d]; x[b] = rotl32(x[b] ^ x[c], 12); x[a] += x[b]; x[d] = rotl32(x[d] ^ x[a], 8); x[c] += x[d]; x[b] = rotl32(x[b] ^ x[c], 7); } static void chacha20_serialize(ref uint[16] inbuf, ref ubyte[64] outbuf) { for (int i = 0; i < 16; i++) { //u32t8le(inbuf[i], outbuf.ptr + (i << 2)); u32t8le(inbuf[i], outbuf[i*4..i*4+4]); } } static void chacha20_block(ref uint[16] inbuf, ref ubyte[64] outbuf, int num_rounds) { uint[16] x = inbuf; //memcpy(x.ptr, inbuf.ptr, uint.sizeof * 16); for (int i = num_rounds; i > 0; i -= 2) { chacha20_quarterround(x, 0, 4, 8, 12); chacha20_quarterround(x, 1, 5, 9, 13); chacha20_quarterround(x, 2, 6, 10, 14); chacha20_quarterround(x, 3, 7, 11, 15); chacha20_quarterround(x, 0, 5, 10, 15); chacha20_quarterround(x, 1, 6, 11, 12); chacha20_quarterround(x, 2, 7, 8, 13); chacha20_quarterround(x, 3, 4, 9, 14); } for (int i = 0; i < 16; i++) { x[i] += inbuf[i]; } chacha20_serialize(x, outbuf); } // https://tools.ietf.org/html/rfc7539#section-2.3 static void chacha20_init_state(ref uint[16] s, ubyte[32] key, uint counter, ubyte[12] nonce) { // refer: https://dxr.mozilla.org/mozilla-beta/source/security/nss/lib/freebl/chacha20.c // convert magic number to string: "expand 32-byte k" s[0] = 0x61707865; s[1] = 0x3320646e; s[2] = 0x79622d32; s[3] = 0x6b206574; for (int i = 0; i < 8; i++) { s[4 + i] = u8t32le(key[i*4..i*4+4]); } s[12] = counter; for (int i = 0; i < 3; i++) { s[13 + i] = u8t32le(nonce[i*4..i*4+4]); } } void chacha20_xor(ubyte[32] key, uint counter, ubyte[12] nonce, ubyte[] inbuf, ubyte[] outbuf) { uint[16] s; ubyte[64] block; int length = cast(int) inbuf.length; chacha20_init_state(s, key, counter, nonce); for (int i = 0; i < length; i += 64) { chacha20_block(s, block, 20); s[12]++; for (int j = i; j < i + 64; j++) { if (j >= length) { break; } outbuf[j] = inbuf[j] ^ block[j - i]; } } } void main() { int i; ubyte[32] key = [ 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f ]; ubyte[12] nonce = [ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x4a, 0x00, 0x00, 0x00, 0x00 ]; ubyte[114] input = [ 0x4c, 0x61, 0x64, 0x69, 0x65, 0x73, 0x20, 0x61, 0x6e, 0x64, 0x20, 0x47, 0x65, 0x6e, 0x74, 0x6c, 0x65, 0x6d, 0x65, 0x6e, 0x20, 0x6f, 0x66, 0x20, 0x74, 0x68, 0x65, 0x20, 0x63, 0x6c, 0x61, 0x73, 0x73, 0x20, 0x6f, 0x66, 0x20, 0x27, 0x39, 0x39, 0x3a, 0x20, 0x49, 0x66, 0x20, 0x49, 0x20, 0x63, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x6f, 0x66, 0x66, 0x65, 0x72, 0x20, 0x79, 0x6f, 0x75, 0x20, 0x6f, 0x6e, 0x6c, 0x79, 0x20, 0x6f, 0x6e, 0x65, 0x20, 0x74, 0x69, 0x70, 0x20, 0x66, 0x6f, 0x72, 0x20, 0x74, 0x68, 0x65, 0x20, 0x66, 0x75, 0x74, 0x75, 0x72, 0x65, 0x2c, 0x20, 0x73, 0x75, 0x6e, 0x73, 0x63, 0x72, 0x65, 0x65, 0x6e, 0x20, 0x77, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x62, 0x65, 0x20, 0x69, 0x74, 0x2e ]; ubyte[114] encrypt; ubyte[114] decrypt; chacha20_xor(key, 1, nonce, input, encrypt); chacha20_xor(key, 1, nonce, encrypt, decrypt); printf("\nkey:"); for (i = 0; i < 32; i++) { if (!(i % 16)) { printf("\n"); } printf("%02x ", key[i]); } printf("\n\nnonce:\n"); for (i = 0; i < 12; i++) { printf("%02x ", nonce[i]); } printf("\n\nplaintext:"); for (i = 0; i < 114; i++) { if (!(i % 16)) { printf("\n"); } printf("%02x ", input[i]); } printf("\n\nencrypted:"); for (i = 0; i < 114; i++) { if (!(i % 16)) { printf("\n"); } printf("%02x ", encrypt[i]); } printf("\n\ndecrypted:"); for (i = 0; i < 114; i++) { if (!(i % 16)) { printf("\n"); } printf("%02x ", decrypt[i]); } printf("\n"); }