Краткий обзор
Несмотря на более чем 25 лет открытых исследований в области криптографических алгоритмов, большая часть приложений до сих пор используют небезопасные криптографические алгоритмы. Данный материал пытается объяснить эту проблему и то почему требуется непрерывное исследование в этой области. Так же будет обсуждаться статус проекта NESSIE (NewEuropeanSchemesforSignature, IntegrityandEncryption), этого 40 – месячного исследовательского проекта (2000 – 2003), который собирается предложить новое поколение криптографических алгоритмов полученных после открытого конкурса и открытого процесса оценки.
1.
Введение
Криптографические алгоритмы играю ключевую роль в информационном обществе. Когда мы пользуемся банкоматами или кредитными картами, звоним кому – то на мобильный телефон, пользуемся услугами здравоохранения или покупает что – либо через интернет, криптографические алгоритмы активно используются для защиты наших персональных данных. Эти алгоритмы гарантируют, что ни кто не сможет украсть деньги с нашего банковского счета, позвонить за наш счет, подслушать наши телефонные разговоры или получить несанкционированный доступ к важным для нас данным. Очевидно, что информационные технологии распространяются все больше: в ближайшей перспективе мы ожидаем увидеть более развитое электронное правительство, электронное голосование и электронную коммерцию. В этих новых условиях возникают новые вызовы в области безопасности, и здесь нет сомнений, что криптографические алгоритмы и протоколы станут частью решения.
До тех пор пока криптография является важным компонентом в нашей жизни, ее значимость сложно переоценить. И действительно, ответственность за провал в системах безопасности часто возлагается на другие факторы, нежели на криптографическую часть (см. пример Anderson [1]). Тем не менее, криптографические алгоритмы являются частью основы системы безопасности, при том, что любая система безопасности со слабой основой – рухнет. Таким образом, нет смысла использовать слабые криптографические алгоритмы. Тем не менее, слабые криптографические алгоритмы, мы встречаем чаще, чем хотелось бы, и это обуславливается несколькими причинами:
- Криптография является интересной дисциплиной, которая имеет тенденцию притягивать "самостоятельных" людей, не знающих о научных разработках предыдущих 25 лет. Ихсамодельныеалгоритмывзламываютсяэкспертомвтечениенесколькихминут.
- Использование короткого ключа, от части, по причине экспортного контроля (главный образом в США, где доминирует рынок программного обеспечения) который ограничивает длину ключа до 40 бит (или 56 бит) для симметричных шифров, 512 бит для систем, основанных на факторинге (RSA) и дискретного логарифма по модулю большого простого числа (Diffie–Hellman). Экспортные ограничения в большей степени были сняты в январе и октябре 2000 года (подробнее см. Koops [15]). В странах, где такие ограничения все еще действуют, проходит много времени, прежде чем изменения алгоритмов вступают в силу.
- Открытое научное исследование криптоанализа стартовало в середине 1970 годов. Криптография сейчас – это учрежденная дисциплина академических исследований, и IACR (Международная ассоциация криптографических исследований) включает в себя более 1000 сотрудников, вследствие чего, разрабатываются все новые и новые методы взлома криптосистем, в то время как их стойкость так же растет.
- Развитие вычислительных мощностей компьютера: Закон Мура сформулированный в 1965 году, прогнозирует удвоение числа транзисторов каждые 18 месяцев. Эмпирические наблюдения доказали его правоту (по крайней мере для плотности данных) и эксперты верят, что закон будет работать по крайней мере еще 15 лет. Вследствие закона Гордона Мура становится ясно, что вычислительная мощность компьютера удваивается каждые 18 месяцев при той же стоимости производства. Это обстоятельство означает, что найти ключ для симметричного алгоритма через 15 лет будет 1000 раз дешевле (при этом возникает необходимость увеличить длину ключа на 10 бит, чтобы его безопасность осталась на прежнем уровне). Еще большая угроза исходит от новых типов компьютеров: если квантовый компьютер будет создан, разложение на множители станет очень легкой задачей (результат Shor 1994 [27]). В то время как первые эксперименты выглядят многообещающими, эксперты разделились во мнении по вопросу создания мощных квантовых компьютеров в течение следующих 15 лет. Для криптографии с симметричными шифрами, квантовые компьютеры являются меньшей угрозой: квантовые компьютеры могут уменьшить время для поиска 2n-bit ключа на время поиска n-bit ключа (используя алгоритм Гровера [11]). Отсюда следует, что удвоение длинны ключа, позволит поддержать уровень защиты на том же уровне.
Результатом перечисленных выше причин становится то, что небезопасные криптографические алгоритмы распространены больше, чем этого хотелось бы. Для решения этих проблем, адекватные механизмы контроля должны быть установлены на нескольких уровнях:
- Должен пройти длительный период оценки, прежде чем алгоритм будет использоваться. Эксперты пришли к мнению, что потребуется период от 3 до 5 лет между первой публикацией и использованием.
- Во время использования примитива требуется непрерывный контроль для проверки на стойкость. Особенно для примитивов с публичным ключом, являющихся параметрируемыми, где строгий контроль необходим для определения минимальной длинный ключа.
- Соответствующие процедуры должны быть предсказаны для того чтобы вывести алгоритм из строя или улучшить его. Одиночный DES это типичный пример алгоритма, который был использован за пределами своей жизни (для большинства приложений 56 битный ключ не был адекватным уже в 1990 годах). Другой пример это алгоритм GSM шифрования A5/1: эксперты сошлись во мнении, что этот алгоритм не так безопасен, как предполагалось (см. Бирюков и др. [4]), но так же тяжел в обновлении.
На последнюю проблему нужно обратить особое внимание: в целях аутентификации данных, слабые места системы безопасности которые были обнаружены, обычно не чувствительны к старым событиям и долгосрочная безопасность может быть достигнута при помощи таких методов как повторное подписание. Тем не менее, для конфиденциальности данная проблема является гораздо более существенной: невозможно предотвратить доступ к информации противника, имеющего зашифрованный текст, в то время как, в некоторых случаях (например, медицинские бумаги) секретность в 50 – 100 лет является необходимой. Это означает, что алгоритм шифрования, используемый сейчас должен противостоять атакам до 2075 года. Легко представить, как надежно должна была быть спроектирована система шифрования в 1925, чтобы быть надежной в течение 75 лет. Нет ни каких оснований полагать, что эта задача была проще в начале 21 века.
Оставшаяся часть работы организована следующим образом: раздел 2 объясняет, как криптографические задачи могут быть решены и какова роль сложных исследовательских проектов. Раздел 3 вводит в основы проекта NESSIE. В разделе 4 обсуждается статус алгоритмов входящих в проект NESSIE за 6 месяцев до окончания проект, и в разделе 5 будут представлены сделанные выводы.
2.
Решение проблемы криптографии
Следующие элементы имеют особое значение для решения криптографической проблемы: стандартизация, исследование и открытый процесс оценки.
Первым элементом является использование открытых механизмов стандартизации, которые основаны на научной оценке, без влияния коммерческого давления. Очевидно, что алгоритмы должны быть включены в стандарты, только если они были внимательно исследованы. Кроме того, органу по стандартизации следует создать адекватные механизмы обслуживания, с тем, чтобы своевременно отозвать алгоритм или обновить параметры.
Одной из проблем является наличие большого количества органов по стандартизации, каждый из которых имеет свой подход (EESSI, ETSI, IEEE, IETF, ISO, NIST, ANSI,...). Как стандартные процедуры обслуживания - механизмы отзыва алгоритмов, как правило слишком медленны и имеют широкие временные рамки. Примером успешных усилий стандартизации можно считать процесс отбора NIST для Advanced Encryption Standard, процесс длился 4 года, результатом чего стала публикация FIPS 197 в ноябре 2001 года [9].
В течение последних 25 лет, криптографические исследования достигли существенного прогресса и можно честно сказать, что криптография прошла большой путь, начав как "искусство" и закончив научной дисциплиной. Некоторые из наиболее важных событий, были сделаны под влиянием теоретической компьютерной науки: были разработаны строгие определения безопасности (данный процесс может занимать многие годы), и был введен редукционистский подход так же известный как "доказуемая безопасность".
Предполагается, что представлено формальное подтверждение того, что слабость криптографических примитивов будет означать возможность решения сложной проблемы. Следует так же отметить, что это значительно улучшает состояние самого искусства, но не решает ключевой вопрос: какие проблемы трудно решить?
Доказать, что проблема является тяжелой, как известно, трудно. Джеймс Л. Месси говорил: "Трудной проблемой является проблема, над которой ни кто не работает". Как следствие, современная криптография открытого ключа, которая зависит от ограниченного набора задач, считается сложной. Большинство из этих задач происходят из алгебраической теории чисел, наиболее популярные из которых представлены в виде продуктов больших простых чисел и вычислений дискретного логарифма по модулю большого простого числа.
Дискретный логарифм в других алгебраических структурах (определяется при помощи эллиптических и гиперэллиптических кривых) также заслуживает внимания. Однако существует явная необходимость выполнения дополнительных исследований трудных проблем, и построения новых схем других классов трудных задач. В области симметричной криптографии, подобный редукционистской подход используется в настоящее время. Однако в этом случае сложные проблемы, как правило, не являются общими математическими проблемами. Безопасность основана на "специальных" решениях, которые были разработаны на основе многолетнего опыта и на основе оценки в отношении существующих и вновь создаваемых общих и специфических атак.
В этой области очень важна скорость работы. Существует потребность в новых, подвергшихся существенной оценке безопасности, алгоритмах (потоковые и блочных шифры, односторонние функции), которые имеют более высокий уровень безопасности и предоставляют более высокую производительность в новых условиях (64-разрядные процессоры, смарт-карты, приложения ультра-низкой мощности).
Для того чтобы гарантировать успех стандартизации механизмов – независимый и открытый процесс оценки, необходимо преодолеть разрыв между академическим сообществом исследований и требованиями приложений. Есть несколько причин необходимости таких усилий:
- Академические исследования в большей мере сфокусированы на предоставлении широкого спектра решений с различными свойствами, нежели на предоставлении единого решения.
- Научные исследования не всегда могут полностью указать все детали алгоритма, а сосредоточить внимание на общих подходах к проектированию.
- Научные исследования часто игнорируют определенные "малые" кажущиеся "тривиальными" проблемы, которые необходимо решать в приложениях и стандартах. Однако такие мелкие детали могут иметь существенные последствия для безопасности. Хорошим примером является механизм, который указывает, какая хэш-функция была использована вместе со схемой подписи, см. Калински [12].
- Органы стандартизации не всегда в курсе самых последних учебных событий.
Успешные стандарты требуют ограниченного числа полностью заданных алгоритмов, что требуется для функциональной совместимости. Однако алгоритм является полезным только при наличии достаточного доверия, получаемого после проведения тщательной оценки безопасности. Она может включать проверку статистических и очевидных уязвимостей, применяя известные атаки, оценку безопасности от новых атак и тщательную проверку всех доказательств безопасности (необходимость в этом может быть проиллюстрирована, ошибка найдена Шоапом в 7-летний OAEP доказательство безопасности [28], ошибка была исправлена для RSA-OAEP Фуджисаки и др. [10]).
Процедура отбора для алгоритмов требует тщательного сравнения безопасности (на какой проблеме основан примитив, для какой модели требовалось доказать безопасность), производительности в различных условиях и другие вопросы, такие как интеллектуальная собственность. Обычно, органы по стандартизации не имеют ресурсов для такого тщательного сравнения и осмотра, и в связи с этим появляется явная необходимость во взаимодействии между научным сообществом и органами по стандартизации.
3.
Проект
NESSIE
Проект NESSIE (NewEuropeanSchemesforSignature, Integrity, andEncryption) – Новые европейские Схемы для электронной подписи, целостности и шифрования – является научно-исследовательским проектом в рамках технологий информационного общества (IST) Программы Европейской Комиссии. Участники проекта: Католический университет Левена (Бельгия), координатор, Ecole Normale Sup'erieure (Франция), Royal Holloway, Лондонский университет (Великобритания), Siemens Aktiengesellschaft (Германия), Technion - Израильский технологический институт (Израиль), католический университет Лувена (Бельгия), и университет Берген (Норвегия). NESSIE является 40-месячным проектом, начавшегося 1 января 2000 года. Подробная и актуальная информация о проекте NESSIE доступна на http://cryptonessie.org/.
Далее мы обсудим открытый конкурс NESSIE и процедуру оценки, которая включает в себя как оценку безопасности, так и оценку эффективности. Мы также кратко обсудим программные средства, использовавшиеся в ходе оценки.
3.1
Конкурс
NESSIE
В первый год проекта, был открыт конкурс на представление криптографических алгоритмов, а также был запущен процесс оценки методологии таких алгоритмов. Рамки этого конкурса были определены совместно с советом проекта промышленности (PIB); конкурс был объявлен в феврале 2000 года. Последним сроком подачи заявок было 29 сентября 2000 года. В ответ на этот конкурс NESSIE получил 40 предложений, каждое из которых было сопоставлено с предъявляемыми требованиями.
Конкурс NESSIE включает в себя запрос широкого круга алгоритмов, обеспечивающих конфиденциальность данных, аутентификацию данных, а также аутентификацию объектов. Эти алгоритмы включают блочные шифры, потоковые шифры, хеш-функции, MAC-алгоритмы, цифровые схемы подписи, шифрование открытого ключа и схемы идентификации (описание этих алгоритмов, см. [18]). Кроме того, конкурс NESSIE принимает методологии оценки для этих алгоритмов. Хотя ключевые протоколы создания также очень важны, было принято решение, что они должны быть исключены из конкурса, так как рамки конкурса и так достаточно широки.
Рамки конкурса NESSIE были гораздо шире, чем у конкурса AES запущенного NIST [20], который был ограничен лишь 128-битовыми блочными шифрами. Проект NESSIE так же сопоставим с проектом RACE (Research and Development in Advanced Communications Technologies in Europe) – RIPE (RACE Integrity Primitives Evaluation, 1988 – 1992) [26] (алгоритмы конфиденциальности были исключены из RIPE по политическим причинам), и японским проектом CRYPTREC [6] (который также включает в себя протоколы образования ключа и поколение псевдослучайных чисел). Другим отличием проекта NESSIE является то, что AES и CRYPTREC намерены производить алгоритмы для государственных стандартов. Результаты проекта NESSIE не будут приняты каким-либо правительством или Европейской комиссией. Тем не менее, планируется, что соответствующие органы по стандартизации примут эти результаты. Как, например алгоритмы цифровой подписи и хэш-функции могут быть включены в документы стандартизации EESSI, которые определяют алгоритмы, рекомендуемые для директивы европейской электронной подписи.
Конкурсом также определяются основные критерии отбора, которые будут использоваться для оценки поданных работ. Эти критерии являются критериями долгосрочной безопасности, требований рынка, эффективности и гибкости. Примитивы могут быть направлены на достижение специфических задач (например 8-битных смарт-карт или современных 64-разрядных процессоров), так же явным преимуществом будет являться широкая гибкость в использовании. Безопасность выдвигается как наиболее важный критерий, так как безопасность криптографического алгоритма имеет существенное значение для достижения доверия и консенсуса.
Для обеспечения требований безопасности
симметричных алгоритмов, заданы два основных уровня безопасности, называемые нормальным
и высоким
. Минимальные требования для симметричного алгоритма достигаются либо нормальным, либо высоким уровнем безопасности, зависящим от длины ключа, внутренней памяти или выходной длины алгоритма. Для блочных шифров третьего уровня безопасности, для нормального и высокого уровня, считается ключ с размером блока 64 и 128 бит. Примером подобных требований являются такие приложения, как UMTS/3GPP, использование 64-разрядных блочных шифров в которых, планируется в ближайшие 10 – 15 лет. Для асимметричных алгоритмов общепринят изменяемый уровень безопасности, с минимум 280
3-DES шифрования.
Выбранные NESSIE алгоритмы не должны требовать авторских отчислений. Если это невозможно, то доступ не должен быть дискриминационными. Заявитель должен изложить позицию по вопросам интеллектуальной собственности и должны обновлять его по мере необходимости.
Представленные в проекте NESSIEтребования, гораздо менее строгие, чем для AES, особенно в случае с требованиями для программных реализаций (только "портативный C" является обязательным).
3.2
Процедура оценки
NESSIE
Как писалось выше, процесс оценки NESSIE принимает во внимание следующие элементы: безопасность, производительность и статус интеллектуальной собственности. Примерно на полпути в проект был принят новый этап. На данном этапе было выбрано подмножество материалов для более детальной оценки во 2-ом этапе. Ниже мы обсудим оценку безопасности и эффективности и инструменты данной оценки.
3.2.1.
Оценка безопасности
Первый шаг оценки состоит из основных проверок, таких как соответствие условиям конкурса, работа с программным обеспечением, наличие очевидных слабостей и т. д. Цель этой первоначальной проверки состоит в обеспечении того, чтобы материалы были указанных в последовательной и убедительной форме в срок на ноябрь 2000 года, что является жизненно важным для правильной оценки безопасности и означает, что алгоритмы имеют полное описание. Этот процесс требовал обеспечения взаимодействия с отправителями.
Следующий внутренний этап (ноябрь 2000) заключался в оценке каждого предложения в деталях. Важным принципом, которым придерживались в ходе оценки, являлся тот, что если один из проверяющих принимал участие в разработке примитива, то он не должен был участвовать в оценке, при этом все оценки дважды проверяются вторым проверяющим проекта. Если существенные недостатки были обнаружены и подтверждены, в целях оптимизации ресурсов проекта, оценка предложения останавливалась.
Далее, открытый семинар был организован в Egham (Великобритания) 12-13 сентября 2001 года для обсуждения безопасности и производительности анализа представленных материалов. На семинаре присутствовали представители проекта NESSIE, участники конкурса, представители NESSIEPIB и члены криптографического сообщества.
После окончания семинара был опубликован полный доклад об оценке безопасности (D13 [19]). Данный документ давал общее представление о характерных атаках на различные типы алгоритмов. Кроме того, для каждого симметричного алгоритма он представлял краткое описание, требования безопасности разработчиков, описание уязвимостей и известных атак. Часть, посвященная асимметричным алгоритмам, содержала обсуждение предположений безопасности, модели безопасности, а также методологии оценки безопасности. Для каждого алгоритма, краткое описание сопровождалось обсуждением доказуемой безопасности (свойства безопасности доказаны в соответствии с условиями и предположениями), а также конкретные проблемы безопасности.
По окончанию семинара было отобрано определенное количество алгоритмов (для более подробной информации см. п. 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-й этап.
Разработчики алгоритмов позволили немного переработать их творения с целью улучшения при сохранении уровня безопасности. Более подробную информацию об изменениях можно найти на веб-страницах проекта NESSIE [19].
Выбранные алгоритмы приведены ниже; переработанные алгоритмы помечены звездочкой*. Блочные шифры:
- IDEA: MediaCrypt AG, Швейцария;
- Khazad*: ScopusTecnologiaS. A., Бразилия и K.U.Leuven, Бельгия;
- MISTY1: Mitsubishi Electric Corp., Япония;
- SAFER++64, SAFER++128: CylinkCorp., США, 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*: Королевский Институт Технологий, Стокгольм и EricssonResearch, Швеция.
Весной 2002 года стало ясно, что SOBER-t16, SOBER-t32 и SNOW имеют уязвимости в безопасности, из чего следует, что они не отвечают строгим ее требованиям, установленным проектом NESSIE. Кроме того, алгоритм BMGL гораздо медленнее (более чем в 10 раз медленнее, чем AES), следовательно, он полезен лишь в качестве генератора псевдослучайных бит и не подходит, как высокоскоростной потоковый шифр для больших объемов данных.
MAC-алгоритмы и хэш-функции:
- Two-Track-MAC: K.U.Leuven, Бельгияи debis AG, Германия;
- UMAC: IntelCorp., США, Университет Невады в Рино, США, IBMResearchLaboratory, США, Technion, Израиль, и Университет Калифорнии в Дэвисе, США;
- Whirlpool*: ScopusTecnologiaS.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 мог быть основан на любой абстрактной группе, что отсутствовало в случае с ACEEncrypt. Другие разработчики решили не менять свои алгоритмы на данном этапе. Более подробную информацию можно узнать в обширном ISO / IEC документе за авторством V. Shoup [29]. Проект NESSIE будет внимательно следить за этими событиями. В зависимости от прогресса, такие варианты как RSA-REM описаны в [29] и могут быть изучены в рамках проекта NESSIE.
Для схем цифровой подписи существовало меньше проблем безопасности. Не смотря на это, три из пяти схем (ESIGN, QUARTZ и SFLASH) были изменены. В данном случае были конкретные причины для каждого алгоритма (коррекция для применения доказательства безопасности, повышение производительности или предотвращение новой атаки). Два оставшихся алгоритма не были изменены. Следует также отметить, что PSS-R, который предложил очень малый предел хранения подписи, не участвовал в конкурсе NESSIE. Алгоритм QUARTZ предлагает очень короткие подписи (16 байт), но сам по себе алгоритм подписи является очень медленным, а открытый ключ большим.
4.3
Интеллектуальная собственность
Если бы все алгоритмы, рекомендованные NESSIE, считались бы общественным достоянием, то это было бы идеально для людей пользующихся результатами проекта, но при этом, к сожалению надо сознавать, что на данный момент это не реально. Сотрудники NESSIEPIB заявили, что они предпочитают видеть бесплатные алгоритмы, предпочтительно в сочетании с открытым исходным кодом. Однако поставщики интеллектуальной собственности, как правило, имели другую точку зрения.
Существует мнение, что в прошлом, всегда была очень большая разница между симметричными и асимметричными криптографическими алгоритмами. По этой причине не удивительно, что 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.