Оцененные проектом NESSIE алгоритмы

Предложения проекта NESSIE

Криптографическое сообщество отреагировало с большим энтузиазмом, когда узнало о проведении конкурса. Были получены тридцать девять алгоритмов и одно предложение о методике тестирования. После процесса взаимодействия с участниками, который занял около месяца, все предложения приняли вид соответствующий требованиям конкурса. Здесь представлены 26 симметричных алгоритмов:

§ семнадцать блочных шифров, учитывая повышенное внимание к дизайну и оценке данных шифров, вследствие конкуренции с AES, были присланы Национальным институтом стандартов и технологий США (NIST). Они распределились следующим образом:

o шесть 64-битных блочных шифров: CS-Cipher, Hierocrypt-L1, IDEA, Khazad, MISTY1 и Nimbus;

o семь 128-битных блочных шифров Anubis, Camellia, Grand Cru, 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.

Так же были приняты тринадцать ассиметричных алгоритмов:

§ пять ассиметричных шифровальных схем: ACE Encrypt, ECIES, EPOC, PSEC и RSAOAEP (оба EPOC и PSEC имели по 3 варианта);

§ семь алгоритмов цифровой подписи: ACE Sign, ECDSA, ESIGN, FLASH, QUARTZ, RSA-PSS и SFLASH; и

§ одна схема идентификации: GPS.

Примерно семнадцать предложений были разработаны в Европе (6 из Франции, 4 из Бельгии, 3 из Швейцарии, 2 из Швеции), девять в Северной Америке (7 из США, 2 из Канады), девять в Азии (8 из Японии), три в Австралии и три в Южной Америке (Бразилия). Большинство представленных предложений возникло в результате сотрудничества с какими – либо отраслями промышленности (27); семь пришли из академических кругов, и шесть являются результатом совместных усилий между промышленностью и академическими кругами. Заметим однако, что тот, кто отсылает работу на конкурс, не может считаться изобретателем, следовательно, доля научных исследований, возможно, была выше.

Все материалы доступны на веб-сайте NESSIE [19].

Отбор второго этапа

24 сентября 2001 года, проект NESSIE объявил об отборе кандидатов для второго этапа проекта. Центральной местом в процессе принятия решений была цель проекта, а именно, выйти с портфелем сильных криптографических алгоритмов. Кроме того, существует также мнение, что каждый алгоритм в этом портфеле должны иметь уникальное конкурентное преимущество, относящееся к приложению.

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

Разработчики алгоритмов позволили немного переработать их творения с целью улучшения при сохранении уровня безопасности. Более подробную информацию об изменениях можно найти на веб-страницах проекта NESSIE [19].

Выбранные алгоритмы приведены ниже; переработанные алгоритмы помечены звездочкой*. Блочные шифры:

§ IDEA: MediaCrypt AG, Швейцария;

§ Khazad*: Scopus Tecnologia S. A., Бразилия и K.U.Leuven, Бельгия;

§ MISTY1: Mitsubishi Electric Corp., Япония;

§ SAFER++64, SAFER++128: Cylink Corp., США, ETH Цюрих, Швейцария, Национальная Академия Наук, Армения;

§ Camellia: Nippon Telegraph and Telephone Corp., Япония и Mitsubishi Electric, Япония;

§ RC6: RSA Laboratories Europe, Швеция и RSA Laboratories, США;

§ Shacal: Gemplus, Франция.

Здесь IDEA, Khazad, MISTY1 и SAFER++64 являются 64-битными блочными шифрами. Camellia, SAFER++128 и RC6 являются 128-битными блочными шифрами, которые мы сравним с AES / Rijndael [7, 9]. Shacal является 160-битным блочным шифром, основанным на SHA-1 [8]. 256-разрядная версия Shacal основана на SHA-256 [21], и также была представлена в рамках второго этапа, и сравнена с RC-6 и Rijndael [7] вариант с длиной блока 256 бит (обратите внимание, что этот вариант не включен в стандарт AES). Причиной такого выбора является то, что некоторые приложения (такие как потоковый шифр BMGL и некоторые хэш-функции) могут извлечь выгоду из безопасного 256-битного блочный шифра.

Шифры синхронного потока:

§ SOBER-t16, SOBER-t32: Qualcomm International, Австралия;

§ SNOW*: Lund Univ., Швеция;

§ BMGL*: Королевский Институт Технологий, Стокгольм и Ericsson Research, Швеция.

Весной 2002 года стало ясно, что SOBER-t16, SOBER-t32 и SNOW имеют уязвимости в безопасности, из чего следует, что они не отвечают строгим ее требованиям, установленным проектом NESSIE. Кроме того, алгоритм BMGL гораздо медленнее (более чем в 10 раз медленнее, чем AES), следовательно, он полезен лишь в качестве генератора псевдослучайных бит и не подходит, как высокоскоростной потоковый шифр для больших объемов данных.

MAC-алгоритмы и хэш-функции:

§ Two-Track-MAC: K.U.Leuven, Бельгия и debis AG, Германия;

§ UMAC: Intel Corp., США, Университет Невады в Рино, США, IBM Research Laboratory, США, Technion, Израиль, и Университет Калифорнии в Дэвисе, США;

§ Whirlpool*: Scopus Tecnologia S.A., Бразилия и K.U.Leuven, Бельгия.

Хэш-функции Whirlpool будет сравнена с новыми предложениями FIPS – SHA-256, SHA-384 и SHA-512 [21].

Алгоритмы шифрования открытого ключа:

§ ACE-KEM*: IBM Zurich Research Laboratory, Switzerland (производный от ACE Encrypt);

§ EPOC-2*: Nippon Telegraph and Telephone Corp., Япония;

§ PSEC-KEM*: Nippon Telegraph and Telephone Corp., Япония; (производный от PSEC-2);

§ ECIES*: Certicom Corp., США и Certicom Corp., Канада;

§ RSA-OAEP*: RSA Laboratories Europe, Швеция и RSA Laboratories, США.

Алгоритмы цифровой подписи:

§ ECDSA: Certicom Corp., США и Certicom Corp., Канада;

§ ESIGN*: Nippon Telegraph and Telephone Corp., Япония;

§ RSA-PSS: RSA Laboratories Europe, Швеция и RSA Laboratories, США;

§ SFLASH*: BULL CP8, Франция;

§ QUARTZ*: BULL CP8, Франция;

Схемы идентификации:

§ GPS*: Ecole Normale Sup’erieure, Париж, BULL CP8, France T’el’ecom и La Poste, Франция.

Многие из асимметричных алгоритмов были обновлены в начале второго этапа. Для асимметричных схем шифрования, эти изменения были произведены отчасти благодаря последним событиям в сфере криптографии, которые произошли после окончания срока представления работ на конкурсе NESSIE [10, 16, 28]. Второй причиной этих изменений является прогресс стандартизации в ISO / IEC JTC1 / SC27 [29]. Стандарты развивались в направлении, определяющем гибридную схему шифрования, состоящую из двух компонентов: KEM (механизм инкапсуляции ключа), где асимметричное шифрование используется для шифрования симметричного ключа, и DEM (механизм инкапсуляции данных), который защищает тайну и целостность массивов данных симметричными методами ("цифровой конверт"). Этот подход несколько сложнее для шифрования открытого текста, но предлагает более общее решение с явными преимуществами. Три из пяти алгоритмов NESSIE (ACE Encrypt, ECIES и PSEC-2) были изменены с учетом текущего развития криптографии. В то же время некоторые другие улучшения были введены самими разработчиками, например алгоритм ACE-KEM мог быть основан на любой абстрактной группе, что отсутствовало в случае с ACE Encrypt. Другие разработчики решили не менять свои алгоритмы на данном этапе. Более подробную информацию можно узнать в обширном ISO / IEC документе за авторством V. Shoup [29]. Проект NESSIE будет внимательно следить за этими событиями. В зависимости от прогресса, такие варианты как RSA-REM описаны в [29] и могут быть изучены в рамках проекта NESSIE.

Для схем цифровой подписи существовало меньше проблем безопасности. Не смотря на это, три из пяти схем (ESIGN, QUARTZ и SFLASH) были изменены. В данном случае были конкретные причины для каждого алгоритма (коррекция для применения доказательства безопасности, повышение производительности или предотвращение новой атаки). Два оставшихся алгоритма не были изменены. Следует также отметить, что PSS-R, который предложил очень малый предел хранения подписи, не участвовал в конкурсе NESSIE. Алгоритм QUARTZ предлагает очень короткие подписи (16 байт), но сам по себе алгоритм подписи является очень медленным, а открытый ключ большим.