eSTREAM: дитя лохнесского чудовища

eSTREAM: дитя лохнесского чудовища

В.Г. Грибунин
к.т.н, эксперт

В 2000-2003 гг. под эгидой Евросоюза проходил конкурсный отбор криптографических примитивов различных типов - NESSIE (New European Schemes for Signature, Integrity and Encryption). По итогам этого проекта ведущими криптографами мира были отобраны рекомендуемые алгоритмы (табл. 1).

Любопытным результатом конкурса NESSIE явилось то, что ни один из шести представленных алгоритмов поточного шифрования не прошел проверки на стойкость. В первой части статьи мы рассмотрим вкратце эти шифры и методику их тестирования. Неудача побудила специалистов в рамках стартовавшего в феврале 2004 г. четырехлетнего проекта ECRYPT организовать конкурс eSTREAM, которому посвящена вторая часть настоящей статьи.

Поточные шифры для NESSIE

Напомним, что поточным шифром называется шифр, осуществляющий позначное шифрование в алфавитах небольшой мощности. В пределе алфавит может быть (0;1), но на практике, для увеличения скорости, применяют алфавиты из многобайтных слов. Внимание к подобным шифрам обусловлено тем, что они способны обеспечить большие скорости шифрования. При этом эффект размножения ошибок, характерный для основных режимов работы блочных шифров, у них отсутствует.

Поточные шифры делятся на самосинхронизирующиеся и синхронные, у которых гамма наложения зависит лишь от ключа. На конкурсе рассматривались только синхронные аддитивные шифры, которые можно представить в виде генератора гаммы, складывающейся по модулю два с открытым текстом.

Шифры SNOW, LILI-128, SOBER-t16, SOBER-t32 основаны на популярной структуре, называемой "регистр сдвига с линейными обратными связями" (РСЛОС). Свойства РСЛОС хорошо изучены в криптографии, при правильном выборе параметров он позволяет получить гарантированный период повторения гаммы.

Для получения стойких шифров используются, в основном, три способа:

• комбинирование РСЛОС;
• неравномерное тактирование прохождения через него элементов алфавита;
• нелинейное усложнение выходной гаммы.

Они и применялись в шифрах NESSIE.

Поточный шифр-конкурсант BMGL получен из блочного шифра (типа AES), работающего в сравнительно новом режиме обратной связи по ключу. Шифр LEVIATHAN сконструирован специально для эффективной программной реализации, поэтому он не был основан на РСЛОС.

Стандартом де-факто поточных шифров является RC4, но ввиду его известных "слабостей" он в проекте NESSIE даже не рассматривался.

Криптоанализ поточных шифров

Анализ поточных шифров сводится к анализу математических и статистических свойств генератора гаммы. Порождаемая, известная криптоаналитику гамма должна:

• исключать восстановление ключа шифра;
• не допускать предсказание гаммы по известному ее отрезку (как вперед, так и назад);
• ничем не отличаться от случайной последовательности.

Восстановление ключа является наиболее сильной атакой, а нахождение отличий от случайной последовательности -самой слабой. Поэтому большое внимание уделяется неотличимости последовательности бит гаммы от истинно случайной последовательности, имеющей распределение Бернулли. Для нахождения отличий используются самые разнообразные статистические тесты. Многие из них описаны в рекомендации NIST. В ходе конкурса NESSIE использовались и другие тесты, в том числе такой экзотический, как "percolation test" (симулирование распространения пожара в лесу).

Другая группа статистических тестов была призвана подтвердить достаточный период и высокую линейную сложность гаммы (иначе можно построить эквивалентный РСЛОС небольшого размера).

Стоит отметить, что "непрохождение" генератором того или иного теста практически сразу означает его некачественность, а вот "прохождение" - еще ни о чем не говорит, так как тестов можно придумать множество. Применявшиеся статистические тесты прошли все конкурсанты.

Такие характеристики, как большой период, высокая линейная сложность и хорошие статистические свойства, -необходимы, но их недостаточно для того, чтобы шифр был криптографически стойким.

В ходе NESSIE криптографами были проведены глубокие исследования представленных шифров, описания которых выходят за рамки статьи. У всех шифров оказалось возможным отличить порождаемую гамму от истинно случайной последовательности, поэтому они и были отвергнуты. Слабее других в этом отношении оказался шифр LEVIATHAN разработки Cisco, его специалисты отвергли еще на первом этапе проекта.

eSTREAM: состояние дел

В ноябре 2004 г. организаторами проекта ECRYPT было объявлено о приеме предложений по алгоритмам поточных шифров. Сбор предложений закончился в апреле 2005 г. На конкурс eSTREAM было представлено 34 (!) алгоритма (сравните с 6 поточными шифрами проекта NESSIE). В феврале 2006 г. завершился первый этап оценки шифров, в июле начался второй этап, который продлится до сентября 2007 г. В январе 2008 г. планируется представить окончательный отчет о проделанной работе.

Главная цель проекта - получить для широкого использования шифр, который не только окажется более быстрым, чем AES, но и свободным от его недостатков (например, будет не подвержен так называемой timing attack).

К настоящему времени все представленные шифры поделены организаторами на два профиля по три группы в каждой (табл. 2 и 3). Профили означают направленность шифров на аппаратную или программную реализацию.

В группы объединены шифры:

1)наиболее перспективные; 2)другие; 3)не рассматриваемые далее.

Впервые в истории в международном криптографическом конкурсе достигли успехов -вышли во второй этап - и российские шифры. Это очень быстрый шифр АВС разработки ученых из РГГУ и шифр YAMB разработки небезызвестного (в области несертифицированной криптографии) Лан Крипто. В шифре YAMB были найдены уязвимости, авторы ответили спустя несколько месяцев. Была "взломана" первая версия шифра АВС, авторы выпустили вторую версию, и она тоже "взломана"... Но так как шифр ABC оказался одним из самых быстрых, его также продолжают рассматривать.

Интересным промежуточным результатом конкурса eSTREAM стоит считать предложенные новые статистические тесты генераторов. В отличие от предыдущих подходов ("генератор - черный ящик"), в этих тестах внимание уделяется анализу зависимостей между гаммой и ключом, между гаммой и синхропосылкой (IV), между отрезками гаммы, сгенерированными при разных IV, а также влиянию на свойства гаммы внутреннего состояния генератора. Эти наборы тестов позволяют выявить неочевидные свойства генераторов гаммы.

Перспективы поточных шифров

Итак, задача построения надежных поточных шифров оказалась сложнее, чем это представлялось организаторам NESSIE. Многочисленные исследования, проводимые в последнее десятилетие, позволяют надеяться на получение такого шифра по итогам eSTREAM. Интересно, какова будет его область применения?

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

Остается быстродействие последних. Но с развитием вычислительной техники и появлением специализированных микросхем достигнутого быстродействия блочных шифров для большинства приложений оказывается более чем достаточно. Так, известна реализация 256-битного AES на выполненной по 0,25-технологии интегральной схеме, имеющей 26 тыс. транзисторов. В этом варианте предусмотрена скорость шифрования 36 Гбит/с. Понятно, что для шифрования, скажем, магистрального трафика такой скорости недостаточно. Но ведь можно создать микросхемы больших размеров, по более "тонкой" технологии, распараллелить процесс шифрования и т.д.

Видимо, практически единственным приложением поточных шифров могут быть низкопотребляющие устройства, обладающие малым объемом памяти и вычислительных ресурсов. Примером подобного приспособления является RFID. А так как некоторые из конкурсантов eSTREAM выполняют не только шифрование, но и аутентификацию (например, разработка Б. Шнайера - Phelix), то они и будут применяться в названных устройствах.

В.И. Фатюхин
"Компания "Информационная Индустрия"

В СТАТЬЕ В. Г. Грибунина рассмотрены предварительные итоги конкурсного проекта eSTREAM в части поточных шифров. Поточные шифры, так же как и блочные, являются частным случаем симметричных криптосистем шифрования (системы с секретным ключом). Разделение между этими шифрами не следует считать закостенелым. Так, например, блочные шифры, работающие в режиме обратной связи по выходу, аналогичны синхронным поточным шифрам, а самосинхронизирующимся поточным шифрам соответствуют блочные шифры с обратной связью по шифртексту. В статье автор предполагает довольно ограниченную область использования поточных шифров в низкопотребляющих устройствах с ограниченным объемом памяти и вычислительными ресурсами. Однако значение исследований в области поточных шифров шире. Основными требованиями, предъявляемыми к поточным шифрам, являются большой период генерируемой гаммы, "хорошие" статистические свойства и высокая линейная сложность ее формирования. Именно "плохие" статистические свойства генераторов гаммы обусловили отрицательные результаты тестов алгоритмов, представленных на предыдущем конкурсе NESSIE. Это же требование относится и к блочным шифрам, содержащим генератор гаммы. Особенностью поточных шифров является также то, что методы и решения их "взлома" более разнообразны по сравнению с блочными шифрами. Поэтому криптографические исследования поточных шифров явились источником ряда задач для фундаментальных направлений дискретной математики.