...

воскресенье, 29 ноября 2015 г.

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

Устройство на КДПВ шифрует не по алгоритму 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.
Историческое отступление

В своё время АНБ (возможно, с подачи IBM) внесло поправки в таблицы подстановки DES по мало кому тогда понятным причинам, что породило массу конспирологических теорий. Впоследствии же оказалось, что эти изменения сделали DES более стойким к дифференциальному криптоанализу, неизвестному в то время криптологическому сообществу, а 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

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Комментариев нет:

Отправить комментарий