SÁFER ( — безопасная и быстрая процедура шифрования) — в криптографии семейство симметричных блочных криптоалгоритмов на основе подстановочно-перестановочной сети. Основной вклад в разработку алгоритмов внёс Джеймс Мэсси. Первый вариант шифра был создан и опубликован в 1993 году.
История Существует несколько вариантов шифра, отличающихся друг от друга длиной ключа шифрования и размерами блоков исходного текста.
Первая разновидность алгоритма — SAFER K-64 - была разработана Джэймсом Мэсси для калифорнийской корпорации «Cylinc» в 1993 году. Опубликованный в том же году, алгоритм имел блок и ключ шифрования длиной в 64 бита. Для него рекомендовалось использовать 6 раундов шифрования. Однако, из-за необходимости увеличить длину ключа до 128 бит (так как была обнаружена слабость в первоначальном варианте алгоритма), Мэсси разработал новый вариант шифра SAFER K-128, который был опубликован на следующий год после SAFER K-64. Новый алгоритм включал в себя расписание ключей, разработанное министерством внутренних дел Сингапура, и в дальнейшем использовался им для различных целей. Также для этого алгоритма рекомендовалось использовать 10 (максимум 12) раундов шифрования.
Спустя некоторое время в первых вариантах алгоритма выявились некоторые слабости, обнаруженные Ларсом Кнудсеном и Шоном Мёрфи. Это повлекло за собой создание новых версий алгоритма, названных SAFER SK-64 и SAFER SK-128, в которых расписание ключей было изменено в соответствии со схемой, предложенной Кнудсеном. Также был разработан вариант с длиной ключа, уменьшенной до 40 бит — SAFER SK-40. Сокращение «SK» в названии алгоритмов расшифровывается как «Strengthened Key schedule» (Усиленное расписание ключей). Для новых вариантов шифра предлагалось использовать не 6, а по крайней мере 8 (максимум 10) раундов шифрования.
Алгоритм SAFER+ был разработан в 1998 году калифорнийской корпорацией Cylinc совместно с Армянской академией наук для участия в конкурсе AES, на котором прошёл лишь первый отборочный тур. Данный шифр имеет входной блок длиной 128 бит и размер ключа 128, 192 или 256 бит.
Последней из созданных разновидностей алгоритма SAFER является SAFER++, разработанный Мэсси в 2000 году и ставший дальнейшим развитием алгоритма SAFER+. Алгоритм принял участие в европейском конкурсе алгоритмов NESSIE, где был представлен в двух вариантах: шифр с 64-битным блоком и 128-битным блоком. Он прошёл во вторую фазу конкурса, но не был выбран в набор рекомендуемых NESSIE криптографических примитивов. Эксперты сочли, что шифр слишком медленный на всех машинах, кроме 8-битных (таких как смарт-карты), а запас безопасности шифра слишком мал.
Алгоритмы SAFER не являются частной собственностью и не защищены авторскими правами, то есть могут быть использованы без каких либо ограничений. Поскольку они целиком состоят из простых байтовых операций (за исключением поворота байтов при генерации ключей), эти алгоритмы могут быть реализованы процессорами с малой разрядностью.
Ниже приведена сводная таблица всех существующих вариантов шифра SAFER
название англ. дата создания длина блока длина ключа число раундов SAFER K-64 key 64 bit 1993 64 64 6 SAFER K-128 key 128 bit 1995 64 128 10 (максимум 12) SAFER SK-64 Strengthened Key schedule, 64 bit 1995 64 64 8 (минимум 6, максимум 10) SAFER SK-128 Strengthened Key schedule, 128 bit 1995 64 128 10 (максимум 12) SAFER SK-40 Strengthened Key schedule, 40 bit 1995 64 40 SAFER+ SAFER Plus 1998 128 128, 192, 256 8, 12, 16 SAFER++ SAFER Plus Plus 2000 64, 128 128, 256 7, 10
SAFER K-64
Алгоритм шифрования
Длина шифруемого блока и длина ключа равны 64 битам. Алгоритм является итеративным блочным шифром, то есть одна и та же функция шифрования последовательно применяется к входному блоку r раз, при этом на каждом этапе используются различные ключи. На каждой итерации (этапе, раунде) в рассматриваемом алгоритме берутся два 64-битных подключа.
Структура одного раунда алгоритма представлена на схеме. Опишем алгоритм поэтапно (ниже i пробегает значения от 1 до r, где r — число раундов шифрования): Входной блок B и оба ключа и разбиваются на 8 частей длиной по одному байту (8 бит). Соответствующие подблоки входного текста и ключа либо складываются по модулю два (операция XOR) — для подблоков № 1, 4, 5 и 8, либо складываются по обычным правилам (операция сложения байтов по модулю 256) — для подблоков № 2, 3, 6 и 7. Результаты сложения проходят через так называемые S-блоки (S-boxes). Их содержимое представляет собой одну из нелинейных операций: (где y = 0 когда x = 128) либо (y = 128 когда x = 0). Здесь x — входной байт, y — выходной байт. Данные операции являются операциями в конечном поле GF(257), где 45 — примитивный элемент поля. Поскольку каждый раз рассчитывать результаты этих операций в практических реализациях алгоритма весьма неудобно, как правило используются специально составляемые таблицы для получения результатов их действия. Над результатами предыдущего действия производится операция, аналогичная п.1, с той лишь разницей, что используется второй подключ , а операции XOR и сложения по модулю 256 меняются местами. Полученные байты проходят через многоуровневую систему преобразований, взаимно складываясь в различном порядке. Это делается для достижения лучшего лавинного эффекта, то есть увеличения зависимости выходных битов от всех битов входного блока. На схеме преобразования представлены в виде сети операций сложения по модулю 256. Эта сеть эквивалентна трём уровням псевдопреобразований Адамара (Pseudo-Hadamard Transform, PHT). Каждое преобразование действует таким образом, что при входных байтах и на выходе получим:
По завершении последовательных раундов, над полученным результатом применяется операция, аналогичная п.1, где в качестве ключа используется последний подключ.
Автор алгоритма рекомендует использовать раундов, но можно увеличить их количество для увеличения надёжности.
Алгоритм расшифрования Расшифрование производятся в обратном порядке, но при этом операции заменяются обратными. Так, операции сложения по модулю 256 заменяются операциями вычитания, а сложение по модулю 2 выполняется точно так же, как и при зашифровании. Операции и меняются местами. Псевдопреобразования Адамара заменяются обратными (Inverse PHT, IPHT), действующими следующим образом:
Генерация ключей Первый ключ шифрования является секретным ключом, задаваемым пользователем. Каждый последующий ключ шифрования получается из предыдущего по формуле (сложение производится по модулю 256, при этом байты складываются отдельно). Здесь операция «» — побайтовый циклический сдвиг влево на 3 бита, то есть сдвиг происходит внутри каждого отдельного байта ключа. Величина называется константой этапа шифрования. Получить её можно следующим образом: если — j-й байт константы i-го этапа, то все константы этапов выражаются следующей формулой: . Получаемые таким образом константы этапов с хорошей точностью ведут себя как случайные числа. Как правило, значения для всех этих констант хранят в специальных таблицах, чтобы уменьшить время на вычисления.
Формальное описание алгоритма генерации ключей:
ВХОД: 64-битовый ключ ; количество раундов .
ВЫХОД: 64-битовые подключи . Байт — -байт ключа (нумерация слева направо).
Пусть — 8-битовые величины. Пусть — j-й байт константы i-го этапа шифрования. . . Для от до : для от 1 до 8: . для от 1 до 8: .
Криптоанализ алгоритма Джэймс Мэсси доказал, что после шести раундов шифрования алгоритмом SAFER K-64 обеспечивается абсолютная устойчивость к дифференциальному криптоанализу. При этом, уже после трёх раундов шифрования линейный криптоанализ также становится неэффективным для взлома.
Несмотря на это, в 1995 году Ларсом Кнудсеном была обнаружена слабость в алгоритме генерации ключей для SAFER K-64. Он показал, что для любого ключа шифрования можно найти один или несколько (вплоть до девяти) ключей (отличающихся от него значением лишь одного байта), таких, что при зашифровании двух различных исходных текстов и получается один и тот же шифротекст, что можно записать в виде . Число различных открытых текстов M, из которых получается один и тот же шифротекст, лежит в промежутке между и из возможных текстов. Таким образом, путём анализа от до открытых текстов можно вычислить 8 бит секретного ключа длиной 64-бита. Эта атака в дальнейшем была значительно усилена Джоном Келси, Брюсом Шнайером и (). Авторы атаки утверждали, что алгоритм легко поддаётся атакам на связанных ключах за счёт очень простой и однообразной процедуры генерации подключей.
Это свойство значительно уменьшает надёжность алгоритма SAFER K-64 при использовании его в качестве однонаправленной хеш-функции. Его надёжность как алгоритма шифрования при этом не уменьшается. Тем не менее, эта слабость алгоритма, вместе с атакой, в дальнейшем опубликованной Мёрфи, побудили Мэсси улучшить алгоритм генерации ключей. В результате в сентябре 1995 года им был опубликован алгоритм SAFER SK-64.
Ещё одна сертифицированная атака на алгоритм SAFER K-64 была осуществлена Ларсом Кнудсеном и (). Она была рассчитана на исходный текст длиной , зашифрованный 5 раундами алгоритма SAFER K-64. Хотя эта атака и не была способна взломать шифротекст уже при 6 раундах шифрования, она показала, что криптостойкость алгоритма меньше, чем изначально заявлял Мэсси (он утверждал, что алгоритм является абсолютно стойким к методам линейного криптоанализа).
Французский криптограф () показал, что при замене содержимого S-блоков случайными перестановками, алгоритм SAFER K-64 становится менее криптостойким.
SAFER K-128
Алгоритм отличается от SAFER K-64 только длиной пользовательского ключа и, соответственно, самим способом генерации ключей. Этот способ был разработан Министерством внутренних дел Сингапура и впоследствии использован Джеймсом Мэсси в его алгоритме.
Генерация ключей В этом алгоритме вместо одного ключа длиной 64 бита используется ключ длиной 128 бит, что эквивалентно заданию двух ключей длиной по 64 бита. Из этих двух ключей по методу, крайне схожему с использованным в шифре SAFER K-64, генерируются две независимые последовательности подключей. Ключи из этих последовательностей попеременно используются на всех раундах шифрования.
Как видно из схемы, на каждом этапе происходит побитовый сдвиг байтов ключа не на 3, а на 6 бит. Это приводит к тому, что, задавшись одинаковыми начальными ключами , получим, что 128-битовый ключ совместим с 64-битовым ключом . То есть, используя ключ вида в алгоритме SAFER K-128 и ключ в SAFER K-64, получим одинаковые последовательности подключей, а значит и само шифрование в SAFER K-128 ничем не будет отличаться от такового в SAFER K-64.
Криптоанализ При всей схожести алгоритма SAFER K-128 с его предшественником, существует и ряд отличий. Так, в новой версии алгоритма Джеймс Мэсси рекомендует использовать уже не 6, а 10 (максимум 12) раундов шифрования. Это связано с тем, что при меньшем количестве итераций алгоритм, так же как и SAFER K-64, подвержен атаке, осуществлённой Ларсом Кнудсеном. Напомним, что она касается использования алгоритма в качестве основы для хеш-функции. Увеличение же количества раундов шифрования, по мнению автора, значительно повышает криптостойкость алгоритма в этом смысле.
SAFER SK-64 Данный алгоритм отличается от SAFER K-64 лишь способом генерации подключей. Этот способ был предложен Ларсом Кнудсеном, после того как им же была найдена атака на алгоритм SAFER K-64. Рекомендуемое количество раундов шифрования увеличено по сравнению с изначальным вариантом с 6 до 8. Различия в способах расширения ключа хорошо видны при формальном описании алгоритма:
Формальное описание алгоритма генерации ключей:
ВХОД: 64-битовый ключ ; количество раундов .
ВЫХОД: 64-битовые подключи . Байт — -байт ключа (нумерация слева направо).
Пусть — 8-битовые величины. Пусть — -байт константы -го этапа шифрования. ; (сложение производится по модулю 2).
Для от до : для от 1 до 9: . для от 1 до 8: .