Реферат: Проект 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, 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].

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

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 байт), но сам по себе алгоритм подписи является очень медленным, а открытый ключ большим.

4.3  Интеллектуальная собственность

Если бы все алгоритмы, рекомендованные NESSIE, считались бы общественным достоянием, то это было бы идеально для людей пользующихся результатами проекта, но при этом, к сожалению надо сознавать, что на данный момент это не реально. Сотрудники NESSIE PIB заявили, что они предпочитают видеть бесплатные алгоритмы, предпочтительно в сочетании с открытым исходным кодом. Однако поставщики интеллектуальной собственности, как правило, имели другую точку зрения.

Существует мнение, что в прошлом, всегда была очень большая разница между симметричными и асимметричными криптографическими алгоритмами. По этой причине не удивительно, что NIST потребовал от разработчиков блочных шифров выбравших AES отдать все свои права, если бы их алгоритмы был выбраны. Очевидно, что не стоит ожидать этого от проекта NESSIE.

Резюмировать заявленные требования об интеллектуальной собственности мы попытаемся втором этапе. Заметим, что такое толкование является лишь предварительным, для окончательного ответа мы рекомендуем всем, включая участников проекта, ознакомиться с заявлением на веб-сайте NESSIE [19].

Одиннадцать из 22 алгоритмов, существуют как общедоступные или разработчики собираются выдать лицензию на безвозмездное использование. К ним относятся блочные шифры Khazad, Misty1, Shacal, Safer++, потоковый шифр BMGL, MAC-алгоритмы Two-Track-MAC и UMAC, хэш-функция Whirlpool, алгоритм с открытым ключом шифрования RSA-OAEP и схемы цифровой подписи SFLASH и RSA-PSS.

Лицензия, не требующая авторских отчислений, будет предоставлена при очень широких условиях блочному шифру Camellia, алгоритму шифрования открытого ключа EPOC-2 и PSEC-KEM, для схемы цифровой подписи ESIGN. Главное исключение происходит тогда, когда кто-либо владеет правами интеллектуальной собственности на примитив в одном и том же классе и тем самым получает права на полный класс рекомендованных алгоритмов.

Блочный шифр IDEA является бесплатным только для некоммерческого использования, для коммерческих приложений требуется лицензия. Лицензии на справедливых, разумных и недискриминационных условиях будут предоставлены для схемы шифрования с открытым ключом ACE-KEM (подробные условия лицензии являются довольно сложными) и для схемы цифровой подписи QUARTZ.

Дополнения к "разумным и недискриминационным" условиям, необходимы для алгоритмов открытого ключа ECDSA и ECIES и схемы идентификации GPS. Они требуют, чтобы обладатель лицензии разделял некоторые из своих прав.

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

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

5.  Заключение

Открытые оценочные инициативы, такие как AES, RIPE, CRYPTREC и NESSIE могут принести очевидные преимущества для криптографического научного сообщества, пользователей и разработчиков криптографических алгоритмов. Когда криптографы разрабатывают точные и хорошо описанные схемы, они думают об оптимизации производительности, а также рассматривают все практические последствия их исследований. Во время отсева множества вариантов, конечный результат в итоге стоит проделанных усилий. Разработчики и пользователи явно извлекают выгоду из наличия набора четко описанных в стандартизированной форме алгоритмов.

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

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

Проект NESSIE приглашает сообщество для дальнейшего анализа безопасности, производительности и статусу интеллектуальной собственности кандидатов с соответствующими комментариями во втором этапе. Проект принимает комментарии до середины декабря 2002 года, и окончательный выбор, вероятно, будет объявлен в феврале 2003 года.

Ссылки

криптографический алгоритм цифровой подпись лицензирование

[1] R.J. Anderson, "Why cryptosystems fail," Communications ACM, Vol. 37, No. 11, November 1994, pp. 32–40.

[2] E. Biham, A. Shamir, "Differential Cryptanalysis of the Data Encryption Standard," Springer-Verlag, 1993.

[3] E. Biham, A. Shamir, "Differential fault analysis of secret key cryptosystems," Advances in Cryptology, Proceedings Crypto’97, LNCS 1294, B. Kaliski, Ed., Springer-Verlag, 1997, pp. 513–525.

[4] A. Biryukov, A. Shamir, D. Wagner, "Real time cryptanalysis of A5/1 on a PC," Fast Software Encryption, LNCS 1978, B. Schneier, Ed., Springer-Verlag, 2000, pp. 1–18.

[5] D. Boneh, R. A. DeMillo, R. J. Lipton, "On the importance of checking cryptographic protocols for faults," Advances in Cryptology, Proceedings Eurocrypt’97, LNCS 1233, W. Fumy, Ed., Springer-Verlag, 1997, pp. 37–51.

[6] CRYPTREC project, http://www.ipa.gov.jp/security/enc/CRYPTREC/index-e.

html.

[7] J. Daemen, V. Rijmen, "AES proposal Rijndael," September 3, 1999, available from http://www.nist.gov/aes.

[8] FIPS 180-1, "Secure Hash Standard," Federal Information Processing Standard (FIPS), Publication 180-1, National Institute of Standards and Technology, US Department of Commerce, Washington D.C., April 17, 1995.

[9] FIPS 197 "Advanced Encryption Standard (AES)," Federal Information Processing Standard (FIPS), Publication 197, National Institute of Standards and Technology, US Department of Commerce, Washington D.C., November 26, 2001.

[10] E. Fujisaki, T. Okamoto, D. Pointcheval, J. Stern, "RSA-OAEP is secure under the RSA assumption," Advances in Cryptology, Proceedings Crypto’01, LNCS 2139, J. Kilian, Ed., Springer-Verlag, 2001, pp. 260–274.

[11] L.K. Grover, "A fast quantum mechanical algorithm for database search," Proc. 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 212–219.

[12] B. Kaliski, "On hash function firewalls in signature schemes," Topics in Cryptology, CT-RSA 2002, LNCS 2271, B. Preneel, Ed., Springer-Verlag, 2002, pp. 1–16.

[13] P. Kocher, "Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems," Advances in Cryptology, Proceedings Crypto’96, LNCS 1109, N. Koblitz, Ed., Springer-Verlag, 1996, pp. 104–113.

[14] P. Kocher, J. Jaffe, B. Jun, "Differential power analysis," Advances in Cryptology, Proceedings Crypto’99, LNCS 1666, M.J. Wiener, Ed., Springer-Verlag, 1999, pp. 388– 397.

[15] B.-J. Koops, "Crypto law survey," http://rechten.kub.nl/koops/cryptolaw.

[16] J. Manger, "A chosen ciphertext attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as standardized in PKCS #1 v2.0," Advances in Cryptology, Proceedings Crypto’01, LNCS 2139, J. Kilian, Ed., Springer-Verlag, 2001, pp. 230–238.

[17] M. Matsui, "The first experimental cryptanalysis of the Data Encryption Standard," Advances in Cryptology, Proceedings Crypto’94, LNCS 839, Y. Desmedt, Ed., Springer-Verlag, 1994, pp. 1–11.

[18] A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, "Handbook of Applied Cryptography," CRC Press, 1997.

[19] NESSIE, http://www.cryptonessie.org.

[20] NIST, AES Initiative, http://www.nist.gov/aes.

[21] NIST, "SHA-256, SHA-384, SHA-512," Washington D.C.: NIST, US Department of Commerce, Draft, 2000.

[22] B. Preneel, B. Van Rompay, L. Granboulan, G. Martinet, S. Murphy, R. Shipsey, J. White, M. Dichtl, P. Serf, M. Schafheutle, E. Biham, O. Dunkelman, V. Furman, M. Ciet, J.-J. Quisquater, F. Sica, L. Knudsen, H. Raddum, "NESSIE Phase I: Selection of Primitives" NESSIE Report, September 2001, available from [19].

[23] B. Preneel, S.B. ¨ Ors, A. Biryukov, L. Granboulan, E. Dottax, S. Murphy, A. Dent, J. White, M. Dichtl, S. Pyka, P. Serf, E. Biham, E. Barkan, O. Dunkelman, M. Ciet, F. Sica, L.R. Knudsen, H. Raddum "Update on the selection of algorithms for further investigation during the second round," NESSIE Deliverable D18, March 2002, available from [19].

[24] B. Preneel, A. Biryukov, E. Oswald, B. Van Rompay, L. Granboulan, E. Dottax, S. Murphy, A. Dent, J. White, M. Dichtl, S. Pyka, M. Schafheutle, P. Serf, E. Biham, E. Barkan, O. Dunkelman, M. Ciet, F. Sica, L. Knudsen, M. Parker, H. Raddum, "NESSIE Security Report," NESSIE Deliverable D20, October 2002, available from [19].

[25] B. Preneel, B. Van Rompay, B. Van Rompay, S.B. ¨ Ors, A. Biryukov, L. Granboulan, E. Dottax, M. Dichtl, M. Schafheutle, P. Serf, S. Pyka, E. Biham, O. Dunkelman, J. Stolin, M. Ciet, J-J. Quisquater, F. Sica, H. Raddum, M. Parker, "Performance of Optimized Implementations of the NESSIE Primitives," NESSIE Deliverable D21, October 2002, available from [19].

[26] RIPE, "Integrity Primitives for Secure Information Systems. Final Report of RACE Integrity Primitives Evaluation (RIPE-RACE 1040)," LNCS 1007, A. Bosselaers, B. Preneel, Eds., Springer-Verlag, 1995.

[27] P.W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring," Proc. 35nd Annual Symposium on Foundations of Computer Science, S. Goldwasser, Ed., IEEE Computer Society Press, 1994, pp. 124–134.

[28] V. Shoup, "OAEP reconsidered," Advances in Cryptology, Proceedings Crypto’01, LNCS 2139, J. Kilian, Ed., Springer-Verlag, 2001, pp. 239–259.

[29] V. Shoup, "A Proposal for an ISO Standard for Public Key Encryption," Version 2.0, September 17, 2001, available from http://www.shoup.net.

[30] L.M.K. Vandersypen, M. Steffen, G. Breyta, C.S. Yannoni, M.H. Sherwood, I.L. Chuang, ‘’Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance," Nature, 414, 2001, pp. 883–887.