Неправильные, но полезные модели
0,0
рейтинг
29 ноября 2015 в 18:42

Разработка → Лёгкий блочный шифр 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
Дмитрий Майоров @dimview
карма
58,0
рейтинг 0,0
Неправильные, но полезные модели
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (9)

  • +1
    Впоследствии же оказалось, что эти изменения сделали DES более стойким к дифференциальному криптоанализу, неизвестному в то время криптологическому сообществу, а DES так и не был взломан за свою долгую историю службы.

    Линейный криптоанализ разработан Matsui. Этот метод позволяет восстановить ключ DES с помощью анализа 2^43 известных открытых текстов, при этом требуется примерно 2^43 шагов для выполнения. Первый экспериментальный криптоанализ DES, основанный на открытии Matsui, был успешно выполнен в течение 50 дней на автоматизированных рабочих местах 12 HP 9735.
    • 0
      Можете скинуть ссылку на первоисточник?
      • +2
        Конкретно эта инфа в вики

        Но я это читал, к примеру, и у Шнайера. Он еще такой интересный вывод делал: так как АНБ защитило DES от ДКА, но не защитило от ЛКА, то в плане криптоанализа АНБ опережает открытых ученых на, примерно, 20 лет.
  • 0
    Надо отметить, что в данном случае линейный криптоанализ был чисто теоретической атакой. На практике проще перебрать в лоб 256 ключей, чем генерить 243 открытых текстов.

    Собственно именно поэтому DES и вывели из употребления. В 1977 году мало кто ожидал такого роста скорости грубого перебора.
  • +2
    Непонятны пара вещей: Что такое «сложение по модулю 2 в степени длины слова», неужто инвертирование старшего бита?
    И что такое входы 0 и 1.
    Непонятно, как эту схему превратить в реальный алгоритм на последовательном вычислительном устройстве, где шифруемые данные представлены последовательностью бит.
    • +3
      Что такое «сложение по модулю 2 в степени длины слова», неужто инвертирование старшего бита?

      Это просто поиск суммы s ≡ a + b (mod 2^N). Обычное сложение двоичных чисел с отбрасыванием бита переноса.

      И что такое входы 0 и 1.

      Вы, наверное, про генерацию псевдослучайных чисел. Так как зашифрованный текст очень похож на случайный шум (в идеале с равномерным распределением), то этим можно воспользоваться, чтобы генерировать псевдослучайные числа. Для этого просто шифруем какую-то последовательность (не обязательно случайную). Например, 0, 1, 2, 3 и т. д.

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

      Это блочный шифр, он шифрует за раз не биты, а блоки. Разбиваете входной поток на блоки указанного размера (в таблице приведены поддерживаемые) и шифруете их, объединяя блоки с помощью какого-либо режима.
    • 0
      masai всё правильно написал.

      Если вопрос про вход 0 и вход 1 касается раундовой функции, то это два слова, из которых состоит блок. Например, у Speck 64/128 длина блока 64 бит. Этот блок разбивается на два слова по 32 бит -вход 0 и вход 1. После шифрования получается тоже два слова, выход 0 и выход 1.

      В режиме CTR на вход 0 можно подать счётчик, на вход 1 — nonce. Последовательность входных бит разбить на блоки и ксорить с выходом Speck, увеличивая счётчик после каждого блока.
      • 0
        Значит первая мысль была верна, только это вовсе не очевидно из описания алгоритма.
        Опять же, входы не равноправны а значит чтобы реализации алгоритма были совместимы, должна быть привязка к тому какая часть блока считается старшей и идёт на 1 вход а какая младшей и идет на 0 вход. Иначе один девайс не сможет расшифровать то что зашифровано на другом.
        • 0
          В оригинальной статье есть тестовые векторы, они же используются в примерах кода и результаты совпадают. Но даже если там что-то перепутано, оба устройства скорее всего будут использовать ту же самую библиотеку с тем же самым порядком, а на криптостойкость порядок не влияет.

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