Змей (шифр)
 Стадия линейного смешивания Serpent | |
| Общий | |
|---|---|
| Дизайнеры | Росс Андерсон , Эли Бихам , Ларс Кнудсен |
| Впервые опубликовано | 1998-08-21 |
| Получено из | Квадрат |
| Сертификация | финалист AES |
| Деталь шифрования | |
| Размеры ключей | 128, 192 или 256 бит |
| Размеры блоков | 128 бит |
| Структура | Сеть замены-перестановки |
| Раунды | 32 |
| Лучший публичный криптоанализ | |
| Все общеизвестные атаки вычислительно неосуществимы, и ни одна из них не затрагивает полный 32-раундовый Змей. Атака 2011 года разбивает 11-раундовый Змей (все размеры ключей) с помощью 2 116 известные открытые тексты, 2 107.5 время и 2 104 память (как описано в [1] ). В той же статье описаны две атаки, которые разрушают 12 снарядов Змея-256. Для первого требуется 2 118 известные открытые тексты, 2 228.8 время и 2 228 память. Другая атака требует 2 116 известные открытые тексты и 2 121 памяти, но также требует 2 237.5 время. | |
Serpent — это с симметричным ключом блочный шифр , который был финалистом конкурса Advanced Encryption Standard (AES) , в котором он занял второе место после Rijndael . [2] Змей был разработан Россом Андерсоном , Эли Бихамом и Ларсом Кнудсеном . [3]
Как и другие материалы AES , Serpent имеет размер блока 128 бит и поддерживает размер ключа 128, 192 или 256 бит. [4] Шифр работающую представляет собой 32-раундовую сеть подстановки-перестановки, на блоке из четырех 32-битных слов . В каждом раунде один из восьми 4-битных S-блоков применяется 32 раза параллельно. Serpent был разработан таким образом, чтобы все операции могли выполняться параллельно , используя 32- битные срезы . Это максимизирует параллелизм, но также позволяет использовать обширную работу по криптоанализу, выполненную на DES .
Serpent придерживался консервативного подхода к безопасности, отдавая предпочтение большому запасу безопасности: разработчики посчитали, что 16 раундов достаточно для защиты от известных типов атак, но указали 32 раунда в качестве страховки от будущих открытий в криптоанализе. [5] В официальном отчете NIST о конкуренции AES Serpent классифицируется как имеющий высокий уровень безопасности, такой как MARS и Twofish , и в отличие от достаточного уровня безопасности RC6 и Rijndael (в настоящее время AES). [2] В итоговом голосовании у Serpent было наименьшее количество отрицательных голосов среди финалистов, но он занял второе место в общем зачете, поскольку у Rijndael было значительно больше положительных голосов, причем решающим фактором было то, что Rijndael позволил гораздо более эффективно реализовать программное обеспечение. [ нужна ссылка ]
Алгоритм шифрования Serpent находится в открытом доступе и не запатентован . [6] Эталонный код является общедоступным программным обеспечением , а оптимизированный код распространяется под лицензией GPL . [7] Никаких ограничений и обременений относительно его использования нет. В результате каждый может включить Serpent в свое программное обеспечение (или в аппаратные реализации) без уплаты лицензионных сборов.
Ключевое расписание [ править ]
Расписание ключей Змея состоит из 3 основных этапов. На первом этапе ключ инициализируется путем добавления при необходимости дополнения. Это сделано для того, чтобы короткие ключи сопоставлялись с длинными ключами длиной 256 бит: к концу короткого ключа добавляется один бит «1», за которым следуют биты «0», пока короткий ключ не будет сопоставлен с длинным ключом. [4]
На следующем этапе «предварительные ключи» получаются с использованием ранее инициализированного ключа. 32-битные части ключа подвергаются операции XOR, FRAC , который представляет собой долю золотого сечения , и индекс раунда подвергаются операции XOR с частями ключа, результат операции XOR поворачивается влево на 11. FRAC и индекс раунда были добавлены для достижения равномерное распределение битов ключей во время раундов. [4]
Наконец, «подключи» получаются из ранее сгенерированных «предварительных ключей». В результате всего получается 33 128-битных «подключа». [4]
В конце раундовый ключ или «подключ» помещается в «начальный IP-адрес перестановки», чтобы поместить ключевые биты в правильный столбец. [4]
Расписание клавиш в C++ [ править ]
#define FRAC 0x9e3779b9 // fractional part of the golden ratio
#define ROTL(A, n) ((A) << n | (A) >> 32-n)
uint32_t key[8]; // key provided by user
uint32_t subkey[33][4]; // roundkeys
const uint8_t S[8][16] = {}; // S-boxes
/* key schedule: get prekeys */
void get_pre(uint32_t w[4*33], const uint32_t k[8]) {
uint32_t x[4*33+8];
for (int i = 0; i < 8; i++)
x[i] = k[i];
for (int i = 8; i < 140; i++) {
x[i] = ROTL(x[i-8] ^ x[i-5] ^ x[i-3] ^ x[i-1] ^ FRAC ^ (i-8), 11);
w[i-8] = x[i];
}
}
/* key schedule: get subkeys */
void get_sk(const uint32_t w[4*33], uint32_t (*sk)[4]) {
uint8_t i, p, j, s, k;
for (i = 0; i < 33; i++) {
p = 32 + 3 - i;
for (j = 0; j < 4; j++)
sk[i][j] = 0;
for (k = 0; k < 32; k++) {
s = S[p % 8][((w[4 * i + 0] >> k) & 0x1) << 0 |
((w[4 * i + 1] >> k) & 0x1) << 1 |
((w[4 * i + 2] >> k) & 0x1) << 2 |
((w[4 * i + 3] >> k) & 0x1) << 3 ];
for (j = 0; j < 4; j++) {
sk[i][j] |= ((s >> j) & 0x1) << k;
}
}
}
}
void key_schedule() {
uint32_t w[4*33];
get_pre(w, key);
get_sk(w, subkey);
}
S-Box [ править ]
S-блоки Serpent представляют собой 4-битные перестановки и подчиняются следующим свойствам:
- разница на входе в 1 бит никогда не приведет к разнице на выходе в 1 бит, вероятность дифференциальной характеристики составляет 1:4 или меньше. [8]
- линейные характеристики имеют вероятность от 1:2 до 1:4, линейная связь между входными и выходными битами имеет вероятность от 1:2 до 1:8. [8]
- нелинейный порядок выходных битов как функция входных битов равен 3. Однако были обнаружены выходные биты, которые в зависимости от входных битов имеют порядок только 2. [8]
S-блоки Serpent созданы на основе 32 строк S-блоков DES . Они были преобразованы путем замены записей, в результате чего массивы с желаемыми свойствами были сохранены как S-блоки Serpent. Этот процесс повторялся до тех пор, пока не было найдено в общей сложности 8 s-блоков. В этом процессе использовался следующий ключ: "sboxesforserpent". [4]
Перестановки и преобразования [ править ]
Начальная перестановка (ИП) [ править ]
Первоначальная перестановка работает с 128 битами за раз, перемещая биты.
for i in 0 .. 127
swap( bit(i), bit((32 * i) % 127) )
Окончательная перестановка (ФП) [ править ]
Последняя перестановка работает с 128 битами за раз, перемещая биты.
for i in 0 .. 127
swap( bit(i), bit((4 * i) % 127) )
Линейное преобразование (LT) [ править ]
Состоит из операций XOR, S-Box, битового сдвига влево и битового поворота влево. Эти операции выполняются над четырьмя 32-битными словами.
for (short i = 0; i < 4; i++) {
X[i] = S[i][B[i] ^ K[i]];
}
X[0] = ROTL(X[0], 13);
X[2] = ROTL(X[2], 3 );
X[1] = X[1] ^ X[0] ^ X[2];
X[3] = X[3] ^ X[2] ^ (X[0] << 3);
X[1] = ROTL(X[1], 1 );
X[3] = ROTL(X[3], 7 );
X[0] = X[0] ^ X[1] ^ X[3];
X[2] = X[2] ^ X[3] ^ (X[1] << 7);
X[0] = ROTL(X[0], 5 );
X[2] = ROTL(X[2], 22);
for (short i = 0; i < 4; i++) {
B[i + 1] = X[i];
}
Рейндал против Змея [ править ]
Rijndael — это сеть преобразования с линейным замещением с десятью, двенадцатью или четырнадцатью раундами, в зависимости от размера ключа, и с размерами ключей 128 бит, 192 бит или 256 бит, определяемыми независимо. Serpent — это сеть замен-перестановок, состоящая из тридцати двух раундов, а также начальной и конечной перестановок для упрощения оптимизированной реализации. Функция округления в Rijndael состоит из трех частей: нелинейного уровня, уровня линейного смешивания и слоя XOR смешивания ключей. Функция раунда в Serpent состоит из XOR для смешивания ключей, тридцати двух параллельных приложений одного и того же S-блока 4×4 и линейного преобразования, за исключением последнего раунда, в котором линейное преобразование заменяется другим XOR для смешивания ключей. Нелинейный слой в Rijndael использует S-блок 8×8, тогда как Serpent использует восемь различных S-блоков 4×4. 32 раунда означают, что у Serpent более высокий запас прочности, чем у Rijndael; однако Rijndael с 10 раундами быстрее и проще реализовать для небольших блоков. [9] Таким образом, Rijndael был выбран победителем конкурса AES.
Змей-0 против Змея-1 [ править ]
Оригинальный Serpent, Serpent-0, был представлен на 5-м семинаре по быстрому программному шифрованию , но на конкурс AES была представлена несколько доработанная версия Serpent-1. В документе, представленном AES, обсуждаются изменения, в том числе различия в планировании ключей.
Безопасность [ править ]
Атака XSL , если бы она была эффективной, ослабила бы Serpent (хотя и не так сильно, как ослабила бы Rijndael , ставшую AES ). Однако многие криптоаналитики считают, что если принять во внимание соображения реализации, атака XSL будет более дорогостоящей, чем атака методом перебора . [ нужна ссылка ]
В 2000 году статья Коно и др. представляет собой атаку «встреча посередине» против 6 из 32 раундов Змея и усиленную атаку бумерангом против 9 из 32 раундов Змея. [10]
Атака 2001 года, проведенная Эли Бихамом , Орром Данкельманом и Натаном Келлером, представляет собой атаку линейного криптоанализа , которая взламывает 10 из 32 раундов Serpent-128 с помощью 2 118 известные открытые тексты и 2 89 время, и 11 раундов Змея-192/256 с 2 118 известные открытые тексты и 2 187 время. [11]
В статье 2009 года было отмечено, что нелинейный порядок S-блоков Serpent не равен 3, как утверждали дизайнеры. В частности, четыре элемента имели порядок 2. [8]
Атака Хонгджун Ву, Хуаксьонга Вана и Фуонг Ха Нгуена в 2011 году, также использующая линейный криптоанализ, взломала 11 раундов Serpent-128 с помощью 2 116 известные открытые тексты, 2 107.5 время и 2 104 память. [1]
В той же статье описаны две атаки, которые разрушают 12 снарядов Змея-256. Для первого требуется 2 118 известные открытые тексты, 2 228.8 время и 2 228 память. Другая атака требует 2 116 известные открытые тексты и 2 121 памяти, но также требует 2 237.5 время.
См. также [ править ]
- Tiger — хэш-функция тех же авторов
Сноски [ править ]
- ↑ Перейти обратно: Перейти обратно: а б Хуасюн Ван, Хонгджун Ву и Фуонг Ха Нгуен (2011). «Улучшение алгоритма 2 в многомерном линейном криптоанализе» (PDF) . Информационная безопасность и конфиденциальность . Конспекты лекций по информатике. Том. 6812. ACISP 2011. стр. 61–74. дои : 10.1007/978-3-642-22497-3_5 . ISBN 978-3-642-22496-6 . Архивировано из оригинала (PDF) 14 апреля 2017 года . Проверено 25 сентября 2014 г.
- ↑ Перейти обратно: Перейти обратно: а б Нечватал, Дж.; Баркер, Э.; Бэшем, Л.; Берр, В.; Дворкин, М.; Фоти, Дж.; Робак, Э. (май 2001 г.). «Отчет о разработке расширенного стандарта шифрования (AES)» . Журнал исследований Национального института стандартов и технологий . 106 (3): 511–577. дои : 10.6028/jres.106.023 . ISSN 1044-677X . ПМЦ 4863838 . ПМИД 27500035 .
- ^ «Домашняя страница Змеи» .
- ↑ Перейти обратно: Перейти обратно: а б с д и ж Росс Дж. Андерсон (23 октября 2006 г.). «Змей: кандидат на блочный шифр для расширенного стандарта шифрования» . Компьютерная лаборатория Кембриджского университета . Проверено 14 января 2013 г.
- ^ "змей.pdf" (PDF) . Проверено 25 апреля 2022 г.
- ^ Змей держит ключ к интернет-безопасности - объявлены финалисты всемирного конкурса шифрования (1999 г.)
- ^ SERPENT - кандидат на блочный шифр для расширенного стандарта шифрования «Serpent теперь полностью находится в свободном доступе, и мы не налагаем никаких ограничений на его использование. Об этом было объявлено 21 августа на Первой кандидатской конференции AES. Оптимизированные реализации в пакет отправки теперь находится под лицензией General Public License (GPL), хотя некоторые комментарии в коде по-прежнему говорят об обратном. Вы можете использовать Serpent для любого приложения. Если вы его используете, мы будем признательны, если вы сообщите нам об этом! " (1999)
- ↑ Перейти обратно: Перейти обратно: а б с д Бхупендра Сингх; Лекси Александр; Санджай Бурман (2009). «Об алгебраических отношениях змеиных S-блоков» (PDF) .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Брюс Шнайер; Джон Келси; Дуг Уайтинг; Дэвид Вагнер; Крис Холл. Нильс Фергюсонк; Тадаёси Коно; Майк Стэй (2000). «Заключительные комментарии команды Twofish по выбору AES» (PDF) . Архивировано из оригинала (PDF) 2 января 2010 года . Проверено 19 января 2015 г.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Тадаёси Коно; Джон Келси и Брюс Шнайер (2000). «Предварительный криптоанализ змеи уменьшенной круглой формы» .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Эли Бихам, Орр Данкельман и Натан Келлер (2001). «Линейный криптоанализ уменьшенного круглого змея». ФСЕ 2001. CiteSeerX 10.1.1.78.6148 .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь )
Дальнейшее чтение [ править ]
- Андерсон, Росс; Бихам, Эли; Кнудсен, Ларс (1998). «Криптография – 256-битные шифры: эталонная реализация (отправка AES)» .
- Бихам, Эли. «Змей — новое предложение блочного шифрования для AES» . Архивировано из оригинала 17 июня 2014 года . Проверено 15 января 2013 г.
- Хальбфингер, Дэвид М. (5 мая 2008 г.). «В деле Пелликано: уроки навыков прослушивания телефонных разговоров» . Нью-Йорк Таймс .
- Стахано, Франк (10 февраля 2006 г.). «Эталонная реализация Serpent» . Компьютерная лаборатория Кембриджского университета.
Внешние ссылки [ править ]
- Официальный сайт
- 256-битные шифры — эталонная реализация SERPENT и производный код
