Алгоритм SHACAL

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

Подобное «родство» алгоритма симметричного шифрования и алгоритма хэширования в данном случае интересно, в частности, по следующим соображениям.

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

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

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

Алгоритм SHACAL-1

-1 (или просто SHACAL) был изначально предложен на конкурс NESSIE (см. разд. 2.2) [173]. Он основан на преобразованиях алгоритма SHA-1. Эта книга не содержит описания всех функций SHA (подробное описание можно найти в [152]) — здесь описаны только те преобразования, которые используются непосредственно в алгоритме шифрования.

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

Рис. 3.190. Раунд алгоритма SHACAL-1

В алгоритме SHACAL-1 предусмотрено 80 раундов шифрования. Шифруемое сообщение представляется в виде пяти 32-битных субблоков Л, В, С, D и Е, над которыми в каждом раунде выполняются следующие действия (рис. 3.190):

где:

?     i — номер раунда (/= 0…79);

?       Ki — фрагмент расширенного ключа для /-го раунда;

?      ft — функция для /-го раунда (см. далее);

?                   

Криптоанализ алгоритма SHACAL-1

Первичный криптоанализ алгоритма SHACAL-1 был выполнен авторами алгоритма в [172] и [173], где была отмечена стойкость алгоритма к линейному и дифференциальному криптоанализу.

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

?      В работе [335] описаны слабости процедуры расширения ключа алгоритма SHACAL-1, с помощью которых можно атаковать данный алгоритм с использованием связанных ключей.

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

Таблица 3.130

Размер ключа в битах

Количество раундов

Требуемое количество выбранных открытых текстов

Количество тестовых операций шифрования

160

37

2158,8

287,8

256

39

2158,5

2250,8

512

47

2158,5

2508,4

?      В работе [69] были скорректированы результаты предыдущей работы: предложенная атака на вариант с 512-битным ключом распространена на 49 раундов, для ее осуществления требуется 21519 выбранных открытых текстов или выбранных шифртекстов и 25085 операций.

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

?      В том же году авторы работы [140] сделали вывод, что, в связи с «наследственностью» SHACAL-1 от SHA-1, новые результаты в поиске коллизий в SHA-1 будут выливаться в новые атаки на алгоритм SHACAL-1 на связанных ключах, которые действуют, как минимум, на класс слабых ключей. В данной работе была предложена первая атака на полнораундовый SHACAL-1 с 512-битным ключом с использованием 4-х связанных ключей. Для этой атаки требуется 2159,8 выбранных открытых текстов и 2423 операций шифрования или 21538 выбранных открытых текстов и 25042 операций. Авторы отмечают, что атака является абсолютно теоретической, поскольку требуемые для атаки ресурсы безусловно превышают существующие вычислительные возможности.

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

Кроме того, в работе [294] утверждается, что алгоритм SHACAL относительно сложно защищать от атак по потребляемой мощности.

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

Однако в финале конкурса SHACAL-1 не оказался в числе алгоритмов- победителей из-за сомнений экспертов в стойкости его процедуры расширения ключа [305].

Криптоанализ алгоритма SHACAL-2

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

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

вариант SHACAL-2 с 512-битным ключом, для которой требуется наличие

7А1 4R                                                                                                                                            4X8 47

2 ‘ выбранных открытых текстов на двух связанных ключах и 2 ‘ операций.

В работе [202] описаны другие варианты атак на SHACAL-2, однако они еще менее эффективны, чем упомянутая выше атака на 42 раунда алгоритма.

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

Вы можете следить за любыми ответами на эту запись через 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