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

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

Структура алгоритма SAFER К-64
SAFER К-64 шифрует данные 64-битными блоками. Блок данных представляется в виде 8-байтового массива. Алгоритм представляет собой подстановочно-перестановочную сеть, в каждом раунде которой выполняются следующие преобразования.

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

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

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

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

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

По материалам книги Сергея Панасенко «Алгоритмы шифрования»