Алгоритм SHACAL

Алгоритмы семейства SHACAL имеют весьма интересную структуру — они основаны на преобразованиях, используемых функциями хэширования семейства SHA (Secure Hash Algorithm). Алгоритмы SHA являются основой американского стандарта хэширования SHS (Secure Hash Standard), в связи с чем эти алгоритмы получили широчайшее распространение.

Подобное «родство» алгоритма симметричного шифрования и алгоритма хэширования в данном случае интересно, в частности, по следующим соображениям. Алгоритмы SHACAL основаны на очень тщательно исследованных крип-тоаналитиками алгоритмах SHA. Действительно, за годы, в течение которых SHA являются стандартом хэширования (с 1993 г.), данные алгоритмы были весьма тщательно исследованы. И можно утверждать, что семейство SHACAL «унаследовало» результаты криптоанализа алгоритмов SHA.

Достаточно часто алгоритмы хэширования используются вместе с алгоритмами шифрования. Алгоритм семейства SHACAL и соответствующий ему алгоритм SHA могут быть весьма просто реализованы «в паре», поскольку они разделяют один и тот же набор функций.

Семейство SHACAL разработано двумя специалистами французской корпорации Gemplus, которая известна как один из крупнейших в мире производителей смарт-карт и оборудования для работы с ними. Авторы алгоритма: Хелена Хандшух и Давид Насаш (David Naccache).

Алгоритм SHACAL-1
Алгоритм SHACAL-1 (или просто SHACAL) был изначально предложен на конкурс NESSIE. Он основан на преобразованиях алгоритма SHA-1. Эта книга не содержит описания всех функций SHA — здесь описаны только те преобразования, которые используются непосредственно в алгоритме шифрования. Итак, SHACAL-1 шифрует 160-битный блок данных с использованием 512-битного ключа шифрования. Допускается использование более коротких ключей шифрования (не короче 128 битов), которые перед выполнением расширения ключа (процедура расширения ключа также унаследована от SHA-1 и будет описана далее) должны быть дополнены нулевыми битами для достижения 512-битного размера.

Алгоритм SHACAL-0
Стоит отметить, что в некоторых работах наряду с алгоритмом SHACAL-1 упоминается некий алгоритм SHACAL-0. Видимо, имеется в виду возможный (не предложенный авторами семейства SHACAL) вариант, основанный на функции SHA-0. Такой вариант отличался бы от SHACAL-1 только процедурой расширения ключа, в которой в описанной выше формуле вычисления Kt отсутствовал бы циклический сдвиг влево на 1 бит.

Алгоритм SHACAL-2
В 2001 г. авторы алгоритма SHACAL-1 воспользовались тем, что в ходе конкурса NESSIE можно было вносить некоторые незначительные изменения в алгоритм, и представили новый вариант алгоритма SHACAL — SHACAL-2.

Стоит сказать, что в данном случае различия между алгоритмами SHACAL-1 и SHACAL-2 сложно считать несущественными. SHACAL-2 основан на преобразованиях более нового алгоритма хэширования — SHA-256, который принципиально отличается от SHA-1.

Алгоритм SHACAL-2 шифрует данные 256-битными блоками с использованием 512-битного ключа. Аналогично алгоритму SHACAL-1, допускается использование ключей меньших размеров (не менее 128 битов), которые до-полняются битовыми нулями до 512 битов. Криптоанализ алгоритма SHACAL-1
Первичный криптоанализ алгоритма SHACAL-1 был выполнен авторами алгоритма, где была отмечена стойкость алгоритма к линейному и дифференциальному криптоанализу.

В дальнейшем, как отмечено авторами, SHACAL подвергся массированному криптоанализу со стороны ряда экспертов. Из криптоаналитических исследований данного алгоритма стоит отметить следующие.

Ряд экспертов из университета г. Сеул, Корея, предложили атаку усовершенствованным методом бумеранга на SHACAL-1 с различными размерами ключей шифрования.

Были скорректированы результаты предыдущей работы: предложенная атака на вариант с 512-битным ключом распространена на 49 раундов, для ее осуществления требуется 2151'9 выбранных открытых текстов или выбранных шифртекстов и 2508'5 операций.

Уже после конкурса NESSIE, в 2006 г., в которой предложена лучшая на текущий момент атака на алгоритм SHACAL-1 из атак, не использующих связанные ключи. Атака на 55 раундов SHACAL-1 с 512-битным ключом использует дифференциальный криптоанализ.

А в работе, появившейся совсем недавно, предыдущая атака была усилена: авторами работы предложено несколько вариантов атак, одна из которых требует наличия 2101,3 выбранных открытых текстов, зашифрованных на 8 связанных ключах, и выполнения 2101,3 операций. По сравнению с предыдущей атакой предложенная атака выглядит существенно более практичной, что позволило ее авторам сделать вывод о структуре алгоритма SHACAL-1: «Использование линейной процедуры расширения ключа совместно с раундами схожей структуры — не лучший способ создания стойких блочных шифров». Кроме того утверждается, что алгоритм SHACAL относительно сложно защищать от атак по потребляемой мощности.

По результатам первого этапа конкурса NESSIE алгоритм SHACAL-1 был выбран в финал конкурса. Эксперты отметили отсутствие уязвимостей, а также высокое быстродействие алгоритма. Кроме того, интересной показалась возможность интеграции алгоритмов SHACAL-1 и SHA-1, о которой было сказано выше. Однако в финале конкурса SHACAL-1 не оказался в числе алгоритмов-победителей из-за сомнений экспертов в стойкости его процедуры расширения ключа.

Криптоанализ алгоритма SHACAL-2
В рамках конкурса NESSIE не было найдено каких-либо уязвимостей в алгоритме SHACAL-2. Мало того, во время конкурса не были известны какие-либо атаки даже на усеченные версии алгоритма. Алгоритм SHACAL-2 стал одним из победителей конкурса NESSIE, причем, помимо криптостойкости, эксперты отметили и высочайшую скорость шифрования этим алгоритмом.

Уже после окончания конкурса начали появляться различные работы, посвященные атакам на варианты алгоритма SHACAL-2 с уменьшенным количеством раундов. Например, в работе предложена атака на 42-раундовый вариант SHACAL-2 с 512-битным ключом, для которой требуется наличие 2 выбранных открытых текстов на двух связанных ключах и 2 операций.

Алгоритмы симметричного шифрования, основанные на хэш-функциях, были предложены различными криптологами задолго до появления алгоритма SHACAL. Однако все они имели те или иные проблемы с криптостойкостью и/или быстродействием. Таким образом, на сегодняшний день алгоритм SHACAL-2 является единственным широко известным алгоритмом (из основанных на хэш-функциях), не имеющим проблем с криптостойкостью и обладающим высокой скоростью шифрования.