Алгоритмы SAFER К и SAFER SK

Алгоритм блочного симметричного шифрования SAFER К-64 был разработан в 1993 г. известным криптологом Джеймсом Мэсси из Технологического Института г. Цюрих, Швейцария, для американской корпорации Cylink. Название алгоритма — аббревиатура от Secure and Fast Encryption Routine, т. е. «сильный и быстрый алгоритм шифрования»; «К-64» в названии алгоритма обозначает использование 64-битного ключа шифрования [251].

Структура алгоритма SAFER К-64

SAFER К-64 шифрует данные 64-битными блоками. Блок данных представляется в виде 8-байтового массива (байты нумеруются слева направо от 1 до 8). Алгоритм представляет собой подстановочно-перестановочную сеть (см. разд. 1.3), в каждом раунде которой выполняются следующие преобразования (рис. 3.162) [251]:

1. Первое наложение ключа: на данные накладывается 8-байтный фрагмент расширенного ключа , где i — номер текущего раунда (раунды нумеруются, начиная с 1; процедура расширения ключа будет описана далее). Байты ключа №№ 1, 4, 5 и 8 накладываются на аналогичные байты данных с помощью побитовой логической операции «исключающее или» (XOR); для наложения остальных байтов ключа используется операция сложения по модулю 256.

2. Нелинейное преобразование:

• байты данных №№ 1, 4, 5 и 8 обрабатываются следующей операцией (на рис. 3.162 обозначена как Е):

Рис. 3.164. Раунд расшифровывания алгоритма SAFER К-64

2.     Обратное второе наложение ключа: на данные накладывается 8-байтный фрагмент расширенного ключа K2R+2-ii • Байты ключа №№ 2, 3, 6 и 7 накладываются на аналогичные байты данных с помощью операции XOR; для наложения остальных байтов ключа используется описанная выше операция вычитания.

3.     Обратное нелинейное преобразование:

•                 байты данных №№ 1, 4, 5 и 8 обрабатываются операцией L;

•                 остальные байты обрабатываются операцией Е.

4.     Обратное первое наложение ключа, полностью аналогичное описанному выше входному преобразованию; здесь используется фрагмент расширенного КЛЮЧа f^2R+\-2i •

Как видно, при расшифровывании происходит выполнение обратных операций в обратном порядке.

Преобразование 1РНТ также может быть заменено умножением на матрицу М~х (аналогично описанному выше для РНТ) [281] (табл. 3.100).

Таблица 3.100

1

-1

-1

1

-1

1

1

-1

-1

1

1

-1

2

-2

-2

2

-1

2

1

-2

1

-2

-1

2

1

-2

-1

2

-2

4

2

-4

-1

1

2

-2

1

-1

-2

2

1

-1

-2

2

-2

2

4

-4

1

-2

-2

4

-1

2

2

-4

-1

2

2

-4

2

-4

-4

8

Процедура расширения ключа

Процедура расширения ключа алгоритма SAFER К-64 достаточно проста. Она состоит из 2/? + 1 раундов, в каждом из которых вычисляется один из 8-байтных фрагментов расширенного ключа. Раунд процедуры расширения ключа состоит из следующих операций (рис. 3.165):

1. Каждый байт результата шага 1 предыдущего раунда вращается влево на 3 бита (на рис. 3.165 эта операция обозначена как <«в). В первом раунде процедуры расширения ключа вместо результата шага 1 предыдущего раунда используется исходный 8-байтный ключ шифрования.

Рис. 3.165. Процедура расширения ключа алгоритма SAFER К-64

2. Результат предыдущего шага складывается побайтно по модулю 256 с константой В1 (где i — номер раунда процедуры расширения ключа, i = 2…2/? + 1). Константы В( определяются с помощью описанной выше операции Е:

где 5Ду] — j-й байт константы Bt. Стоит отметить, что константы В{ могут как вычисляться в процессе расширения ключа, так и быть заданы в виде набора констант (для 10 раундов шифрования, начиная с В2) [339] (табл. 3.101).

Таблица 3.101

16733В1E8E70BD86

FDFB1740Е6511D41

477E2456F1778846

8F29DD0480DEE731

B1BAA3B7100AC537

7F01A2F739D A6F23

С95А28АС64А5ЕСАВ

FE3 ADO 1 CD 1303Е12

C66795580DF89AF6

CD0FE0A8AF82592C

66DC053DD38AC3D8

7DADB2EFC287CE75

6AE9364943BFEBD4

1302904F2E723385

9B68A0655D57921F

8DCFA981E2C4272F

715СВВ22С1ВЕ7ВВС

7A9F52E115382BFC

63945F2A61B83432

42С708Е409555Е8С

Фрагмент расширенного ключа Кх эквивалентен исходному ключу шифрования без каких-либо изменений.

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

Криптоанализ алгоритма SAFER К-64

Криптоанализ алгоритма SAFER К-64 был начат Ларсом Кнудсеном в 1995 г. Он предложил атаку на связанных ключах [213]: для почти каждого ключа К существует ключ К‘ (отличающийся от К значением одного байта), такой, что для достаточно большого множества открытых текстов (до 2 из возможных 264) после 6 раундов шифрования результаты шифрования каждого из текстов на ключах К и К’ абсолютно эквивалентны. Финальное преобразование делает результаты шифрования различными, но только в одном байте шифртекста. Данная особенность позволяет вычислить 8 битов 64-битного ключа шифрования алгоритма SAFER К-64 на основе от 244 до 247 выбранных открытых текстов. Найденная Кнудсеном атака не снижает практической криптостойкости алгоритма. Однако, согласно [213], в случае, если SAFER К-64 используется в режиме хэширования, то для нахождения коллизии (двух текстов с одинаковым хэш-значением) требуется 223 операций шифрования вместо 232 (последнее следует из парадокса дней рождения), что делает весьма сомнительной возможность использования данного алгоритма’в качестве основы хэш-функций. Вывод автора [213] состоит в том, что для достижения достаточной криптостойкости алгоритму SAFER К-64 недостаточно раундов: необходимо, как минимум, 10 вместо 6.

Данная атака была усилена Джоном Келси, Брюсом Шнайером и Дэвидом Вагнером [197]: их вариант атаки для нахождения с высокой вероятностью 28 битов ключа требует от 224 до 229 выбранных открытых текстов (и их зашифровывание на 256 связанных ключах). Как пишут авторы [197], алгоритм SAFER К-64 подвержен атакам на связанных ключах из-за его достаточно простой и «однообразной» (генерация подключей происходит с минимальными отличиями) процедуры расширения ключа.

Еще одна слабость процедуры расширения ключа была описана в работе [273].

Описанный далее алгоритм SAFER SK-64 противостоит приведенным выше атакам.

В работах [216] и [217] описана атака на 5-раундовый (из 6 раундов) SAFER К- 64, для которой требуется 245 выбранных открытых текстов и 246 операций шифрования или 246 выбранных открытых текстов и 235 операций.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100