Лёгкий блочный шифр Speck, или пылинка от агенства, которого нет

В июне 2013 года АНБ опубликовало описание двух лёгких блочных шифров — Simon и Speck [1].

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

Прошло два года, практических атак ни на Simon, ни на Speck не появилось [2], а преимущества (простота и гибкость) — остались.

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

Зачем нужен Speck, когда есть AES

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

Эту нишу долго занимал RC4, пока не состарился. Ближайший конкурент Speck скорее не AES, а ChaCha20.

Что там внутри

Speck представляет собой ARX шифр (использует сложение по модулю, циклический сдвиг и исключающее ИЛИ). Можно выбирать длину блока и ключа в зависимости от задачи:

Название	Размер блока, бит	Длина ключа, бит	Количество раундов
Speck 32/64	32	16*4=64	22
Speck 48/72	48	24*3=72	22
Speck 48/96	48	24*4=96	23
Speck 64/96	64	32*3=96	26
Speck 64/128	64	32*4=128	27
Speck 96/96	96	48*2=96	28
Speck 96/144	96	48*3=144	29
Speck 128/128	128	64*2=128	32
Speck 128/192	128	64*3=192	33
Speck 128/256	128	64*4=256	34

Блок разбит на два слова, длина ключа кратна длине слова. Все операции производятся над словами, сложение и вычитание выполняются по модулю 2 в степени размера слова.

Раундовая функция похожа на Threefish:



В Speck 32/64 циклические сдвиги на 7 и 2 бита вместо 8 и 3.

Та же самая функция используется для получения раундовых ключей (ей в качестве ключа подаётся номер раунда). Брюс Шнайер хвалил NSA именно за это.

На картинке справа три раунда Speck, где длина ключа равна длине блока.

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

Если ключ длиннее блока, слова ключа используются по кругу. На картинке слева четыре раунда, дальше всё так же.

Отличительными особенностями Speck является простота имплементации и малое количество используемой памяти. Нет ни магических констант, ни чёрных ящиков подстановки-перестановки. Нет даже отбеливания ключа, это делает первый раунд.

Вот как выглядит одна из возможных реализаций Speck 128/128 на C++:

#include <inttypes.h>

static inline void speck_round(uint64_t& x, uint64_t& y, const uint64_t k)
{
  x = (x >> 8) | (x << (8 * sizeof(x) - 8)); // x = ROTR(x, 8)
  x += y;
  x ^= k;
  y = (y << 3) | (y >> (8 * sizeof(y) - 3)); // y = ROTL(y, 3)
  y ^= x;
}

void speck_encrypt( const uint64_t plaintext[2]
                  , const uint64_t key[2]
                  , uint64_t ciphertext[2]
                  )
{
  uint64_t b = key[0];
  uint64_t a = key[1];
  ciphertext[0] = plaintext[0];
  ciphertext[1] = plaintext[1];
  for (unsigned i = 0; i < 32; i++) {
    speck_round(ciphertext[1], ciphertext[0], b); 
    speck_round(a, b, i); // Посчитать ключ для следующего раунда
  }
}

В этом примере циклический сдвиг реализован слегка громоздко через обычные сдвиги. Если компилятор предлагает функции вроде _lrotl() и _lrotr(), то можно пользоваться ими.

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

Для использования в режиме сцепления блоков шифротекста (CBC) функцию расшифровки всё же придётся добавить. Сделать это несложно — достаточно поменять порядок операций в раундовой функции на противоположный, заменить сложение на вычитание, сдвиг вправо на сдвиг влево и наоборот. Раундовые ключи считать заранее и потом идти по ним задом наперёд, или один раз посчитать последний раундовый ключ и потом применять к нему инвертированную раундовую функцию. Примеры: Speck 64/128, Speck 128/128.

Не шифрованием единым

Блочные шифры находят применение не только в криптографии, но и например в генераторах псевдослучайных чисел. Достаточно взять произвольный ключ, зашифровать на нём 0, потом 1 и так далее. Полученный поток должен выглядеть очень случайным. Speck проходит классическую батарею тестов Big Crush генераторов псевдослучайных чисел Test01. При этом по времени выполнения Speck всего в три раза медленнее, чем PCG32 (это один из наиболее быстрых современных генераторов псевдослучайных чисел, но без претензий на криптостойкость).

Верить или не верить

Возможно АНБ оставило лазейку как в печально знаменитом Dual_EC_DRBG или знает неопубликованный способ атаки, который вот-вот найдёт кто-то из незасекреченных криптографов. Но учитывая простоту Speck сложно представить, где именно там можно спрятать такую лазейку, и Speck в этом отношении больше похож на DES.

Безвозмездно, то есть даром

Speck является общественным достоянием (находится в public domain).

Ссылки на первоисточники

[1] Ray Beaulieu, Douglas Shors, Jason Smith, Stefan Treatman-Clark, Bryan Weeks, Louis Wingers The Simon and Speck Families of Lightweight Block Ciphers PDF

[2] Ray Beaulieu, Douglas Shors, Jason Smith, Stefan Treatman-Clark, Bryan Weeks, Louis Wingers Simon and Speck: Block Ciphers for the Internet of Things PDF