По окончанию семинара было отобрано определенное количество алгоритмов (для более подробной информации см. п. 4.2.). Начиная со второй половины проекта, отобранные алгоритмы оценивались более детально (см., например, [23, 24]). Результаты второго этапа были представлены на открытом семинаре 6-7 ноября 2002 года в Мюнхене (Германия).
3.2.2.Оценка эффективности
Оценка эффективности является неотъемлемой частью оценки криптографических алгоритмов. Кандидаты тестируются на нескольких платформах (ПК, смарт-карты, специальные аппаратные средства) и в различных приложениях. Некоторые приложения имеют жесткие временные ограничения (например, программы оплаты, сотовые телефоны), для других приложений, важна высокая пропускная способность (например, высокая скорость сети, шифрования жестких дисков).
Первая платформа принималась для сравнения производительности алгоритмов на справедливой и равной основе. Она был использована для оценки всех представленных кандидатов. Прежде всего, был создан теоретический подход. Каждый алгоритм разбивался на три части: установки (не зависящие от ключа и данных), предварительные вычисления (зависят от данных, например ключей) и сам алгоритм (который должен вводиться повторно при каждом использовании). Следующим был определен набор из четырех тестовых платформ, на которых мог быть проверен каждый кандидат. К этим платформам относились: смарт-карты, 32-разрядные ПК, 64-битных процессоры и программируемые логические интегральные схемы (ПЛИС).
Далее были определены правила описывающие, как именно должна измеряться производительность на этих платформах. Параметры выполнения зависят от платформы и могут включать в себя: память, быстродействие, размер кода, площадь кристалла и потребление энергии. В части смарт-карт, приняты во внимание будут только следующие параметры, в порядке убывания важности: использование памяти, скорость, размер кода. На ПК, ОЗУ имеет очень незначительное влияние, по этому, главное внимание уделяется скорости. На ПЛИС, рассматривалась пропускная способность, задержка, площадь кристалла и энергопотребление. К сожалению, ограниченные ресурсы проекта не позволили оценить проблемно – ориентированные интегральные микросхемы (ASIC), но вполне возможно, что команды не участвующие в проекте могли бы предложить свою помощь в оценке некоторых алгоритмов.
Проект также рассмотрит сопротивление реализации к физическим атакам, таким как расчет времени атаки [13], анализ ошибок [3, 5], и анализ мощности [14]. Для не постоянных по времени алгоритмов (зависимость по данным или ключевая зависимость, асимметрия между шифрованием и дешифрованием) зависимость по данным или ключевая зависимость будут проанализированы, в другие элементы, которые будут приняты во внимание, входят разница между шифрованием и дешифрованием, а также между подписью и операцией проверки. Для симметричных алгоритмов, скорость ключа также будет рассмотрена.
Этот подход позволил определить, как тест и сценарий повторного ввода ключа зависит от платформы испытаний. Дешевые смарт-карты будут использованы только для блочных шифров, MAC, хэш-функций, потоковых шифров, поколения псевдослучайных чисел, а также схем идентификации.
Для того чтобы в рамках проекта NESSIE представить информацию об эффективности на постоянной основе, был разработан "Шаблон" производительности. Цель этого шаблона является сбор информации о производительности представленных кандидатов. Первая часть описывает параметры, такие как размер слова, требования к памяти, размер ключа и размер кода. Следующими основными анализируемыми операциями являются такие как сдвиг / поворот, поиск по таблице, перестановки, умножения, дополнения, модульные сокращения, возведение в степень, инверсии. Далее описываются характер и скорость предварительных вычислений (установка, список ключей и т.д.). Элементы, зависящие от ключей, определяют на входе, является ли код постоянно временным или нет. Когда это возможно, исследуются альтернативные представления алгоритмов.
Так же было разработано специальное программное обеспечение для автоматизированного тестирования производительности ПК и рабочих станций. Статус оценки эффективности представлен в [25].
3.2.3.Инструменты
Совершенно очевидно, что в сфере криптоанализа, современные компьютеры и сложные программные средства не могут заменить человека. Тем не менее, программные средства могут играть важную роль в современном криптоанализе. В большинстве случаев обнаруженные криптоаналитиками атаки требуют большого числа вычислений, следовательно, фактическое вычисление атак выполняется именно на компьютере. Однако программное обеспечение и специальные программные инструменты могут быть неотъемлемой частью успешного поиска способа атаки симметричного криптографического алгоритма; примером можно считать дифференциальный и линейный криптоанализ, зависимость тестов и статистических тестов.
В проекте NESSIE, мы выделяем два класса инструментов. Общие инструменты анализа не являются специфичными для алгоритмов. Специальные инструменты, являющиеся специфическими для анализа одного алгоритма, используются, когда в ходе криптоанализа данного алгоритма, возникает необходимость такого инструмента.
Для оценки симметричных алгоритмов, в проекте имеется полный набор общих инструментов. Эти средства частично основаны на улучшенных версиях инструментов, разработанных для проекта RIPE (RACE Integrity Primitives Evaluation) [26]. Испытания включают более 20 статистических тестов.
Проект NESSIE также разрабатывает новый универсальный инструмент для анализа блочных шифров с дифференциальным [2] и линейным криптоанализом [17]. Этот инструмент основан на общем языке описания для блочных шифров.
Данное программное обеспечение не будет доступно за пределами проекта, но все результаты, полученные с помощью этих инструментов, будут обнародовано во всех деталях.
4. Оцененные проектом NESSIE алгоритмы
4.1 Предложения проекта NESSIE
Криптографическое сообщество отреагировало с большим энтузиазмом, когда узнало о проведении конкурса. Были получены тридцать девять алгоритмов и одно предложение о методике тестирования. После процесса взаимодействия с участниками, который занял около месяца, все предложения приняли вид соответствующий требованиям конкурса. Здесь представлены 26 симметричных алгоритмов:
- семнадцать блочных шифров, учитывая повышенное внимание к дизайну и оценке данных шифров, вследствие конкуренции с AES, были присланы Национальным институтом стандартов и технологий США (NIST). Они распределились следующим образом:
o шесть 64-битных блочных шифров: CS-Cipher, Hierocrypt-L1, IDEA, Khazad, MISTY1 и Nimbus;
o семь 128-битных блочных шифров Anubis, Camellia, GrandCru, Hierocrypt-3, Nuekeon, Q и SC2000 (не один из этих семи шифров не пришел из AES);
o один 160-битный блочный шифр: Shacal; и
o три блочных шифра с изменяющейся длинной блока: NUSH (64, 128 и 256 бит), RC6 (около 128 бит) и SAFER++ (64 и 128 бит).
- шесть шифров синхронного потока: BMGL, Leviathan, LILI-128, SNOW, SOBER-t16 и SOBER-t32.
- два MAC алгоритма: Two-Track-MAC и UMAC; и
- одна устойчивая к коллизиям хэш-функция: Whirlpool.
Так же были приняты тринадцать ассиметричных алгоритмов:
- пять ассиметричных шифровальных схем: ACEEncrypt, ECIES, EPOC, PSEC и RSAOAEP (оба EPOC и PSEC имели по 3 варианта);
- семь алгоритмов цифровой подписи: ACESign, ECDSA, ESIGN, FLASH, QUARTZ, RSA-PSS и SFLASH; и
- одна схема идентификации: GPS.
Примерно семнадцать предложений были разработаны в Европе (6 из Франции, 4 из Бельгии, 3 из Швейцарии, 2 из Швеции), девять в Северной Америке (7 из США, 2 из Канады), девять в Азии (8 из Японии), три в Австралии и три в Южной Америке (Бразилия). Большинство представленных предложений возникло в результате сотрудничества с какими – либо отраслями промышленности (27); семь пришли из академических кругов, и шесть являются результатом совместных усилий между промышленностью и академическими кругами. Заметим однако, что тот, кто отсылает работу на конкурс, не может считаться изобретателем, следовательно, доля научных исследований, возможно, была выше.
Все материалы доступны на веб-сайте NESSIE [19].
4.2 Отбор второго этапа
24 сентября 2001 года, проект NESSIE объявил об отборе кандидатов для второго этапа проекта. Центральной местом в процессе принятия решений была цель проекта, а именно, выйти с портфелем сильных криптографических алгоритмов. Кроме того, существует также мнение, что каждый алгоритм в этом портфеле должны иметь уникальное конкурентное преимущество, относящееся к приложению.
Таким образом, стало понятно, что алгоритм не может быть отобран, если он не имеет необходимый уровень безопасности. Вторым условием является удовлетворение условия безопасности установленного разработчиком. Третьей причиной для отсеивания алгоритма, может являться наличие подобного алгоритма, имеющего более высокий уровень безопасности (и сопоставимый уровень производительности) или значительно более высокий уровень производительности (и сопоставимый уровень безопасности). В ретроспективе, очень немногие алгоритмы были отсеяны по соображениям производительности, что может являться причиной отчасти потому, что большое количество предложений не позволило оценить эффективность в нужной степени во время первой фазы. Следует также отметить, что в области блочных шифров выбор был более конкурентоспособным, и было рассмотрено много сильных претендентов. Причины принятых решений представлены в [22]. Обратите внимание, что берущие свое начало в какой-либо отрасли индустрии работы, были наиболее эффективны, и только одно предложение от академического сообщества прошло во 2-й этап.