id: Гость   вход   регистрация
текущее время 23:08 28/03/2024
Владелец: unknown (создано 17/08/2009 22:26), редакция от 13/09/2009 01:20 (автор: unknown) Печать
Категории: криптография, инфобезопасность, алгоритмы, протоколы, безопасная разработка
https://www.pgpru.com/Библиотека/Статьи/ПолемикаОКриптобезопасности
создать
просмотр
редакции
ссылки

Полемика по поводу понятий криптографической безопасности


Дуглас Стинсон. Академия компьютерных наук университета Ватерлоо. Онтарио, Канада.
19 июля 2004 года

1. Введение


Коблиц и Менезис недавно написали очень интересную работу по теме доказуемой безопасности в криптографии. Их работа представляет убедительные итоги относительно некоторых значительных результатов из области доказуемой безопасности. В дополнение в работе предлагаются некоторые интересные и проницательные комментарии о роли доказуемой безопасности в криптографии.

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

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

2. Что такое доказуемая безопасность?


В криптографии рассматриваются несколько уровней безопасности. Сейчас мы дадим определение некоторых используемых критериев.

Вычислительная безопасность (стойкость). Это мера определения вычислительных ресурсов, необходимых для взлома криптосистемы. Мы может определить систему как вычислительно стойкую, если лучший алгоритм взлома требует N операций, где N — некоторое определённое, очень большое число. Проблема в том, что никакая практическая криптосистема не может быть доказуемо стойкой согласно этому определению. На практике, люди часто изучают вычислительную стойкость криптосистемы по отношению к определённым видам атак. Например, имеет смысл следующее утверждение — AES безопасен против атаки простого перебора (взлома грубой силой) в настоящее время и в обозримом будущем. Разумеется, безопасность против одного определённого типа атак не гарантирует безопасности против какого-нибудь другого вида атак.


Доказуемая безопасность (стойкость). Другим способом предоставить доказательство стойкости является редуцирование безопасности криптосистемы к какой-нибудь положенной в её основу хорошо изученной математической проблеме, которая считается трудноразрешимой. Например, легко доказать утверждение типа "Криптосистема Рабина безопасна (по отношению к дешифрованию шифртекста) если модуль n не может быть факторизован". Криптосистемы такого типа часто называются доказуемо безопасными, но должно быть ясно, что такой подход обеспечивает только доказательство безопасности по отношению к другой проблеме, что не является абсолютным докзательством безопасности. Для вышеупомянутого примера нет никакого доказательства, что сама факторизация сложна, поэтому мы не можем давать заключение по поводу сложности криптосистемы. Фактически все результаты доказательств безопасности включают редукцию (в значении алгоритмов теории комплексности), так что иногда используется альтернативный термин редукционистская безопасность.


Безусловная безопасность (стойкость). Эта мера стойкости криптосистем используется, когда считают, что противник не ограничен в вычислительных ресурсах. Криптосистема считается безусловно стойкой даже с привлечением бесконечных вычислительных ресурсов. Например, хорошо известно, что одноразовый блокнот безусловно стойкий (то есть изучение отдельного шифртекста не даёт никакой информации о соответствующем открытом тексте). Доказательства безусловной стойкости не включает вычислительной сложности, а скорее зависит от комбинаторного и информационно-теоретического анализа. Точная формулировка безусловной стойкости обычно включает вычисление вероятности того, что противник способен достичь определённой цели.


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

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


Улучшение безопасности криптографических алгоритмов. Это отсылает нас к ситуации, когда мы доказываем, что "улучшенный" криптографический алгоритм предоставляет определённый (более высокий) уровень безопасности, по сравнению с "базовым" алгоритмом, предоставляющим определённый (более низкий) уровень безопасности. Например, OAEP стоек по отношению к атакам с подобранным шифртекстом, если базовый алгоритм RSA является односторонней функцией.


Редуцирование криптографических протоколов к алгоритмам более низкого уровня. Это значит, что криптографический протокол (например схема согласования ключей) доказуемо безопасен, если подразумевается, что криптографические алгоритмы, используемые в протоколе, безопасны. Например, определённые версии схемы согласования ключей "Станция-Станция" безопасны, если схема подписи и/или аутентификации сообщений, используемые в этом протоколе, являются стойкими.

3. Действительность доказательств доказуемой безопасности


Доказуемая безопасность в криптографии имеет достаточно пёструю историю. Ларс Кнудсен сказал:

If it's provably secure, it's probably not

"Если это доказуемо безопасно, то вероятно это не так".
Однако я верю, что такое восприятие доказуемой безопасности связано по большей части с дебатами вокруг важности доказательств, чем с их действительностью как таковых.
Давайте изучим структуру типичного доказательства безопасности, которое, как было вышеупомянуто, обычно принимает форму редукции. Обычно в основе лежат некоторые предположения, которые могут быть или не быть выражены в явном виде. Это включает в себя законы среды, в которой имеет место гипотетическая атака. В модели атаки перечисляются точная криптографическая информация, доступная противнику, осуществляющему атаку. Это включает определения следующего:

  • криптографические данные, доступные атакующему (например атака с подобранным шифртекстом);
  • какие определены аспекты криптографичеких алгоритмов (например определение хэш-функции, используемой в алгоритме может быть доступно атакующему или нет — это важно в модели случайного оракула);
  • какие определены аспекты исполнения (белый ящик, серый ящик, чёрный ящик); и
  • вычислительные ресурсы, доступные атакующему.

    Атакующий пытается достигнуть предопределённых криптографических целей (которые будут составлять взлом системы). Взлом может включать вычисление неизвестного ключа или различение двух определённых открытых текстов.
    Редукция, которая составляет доказательство — это доказательство того, что если атакующий может достигнуть цели взлома, то атакующий (с небольшим дополнительным объёмом работы) способен достичь и некоторой другой цели, дополнительного взлома, возможно связанным с "примитивом" более низкого уровня, на котором основана схема.
    То, что на самом деле доказывается, имеет утверждение вида:


    "Если противник может сделать 'X', то он также должен уметь делать 'Y'".


    Какое это имеет отношение к безопасности? Обычно мы конструируем такое доказательство, чтобы 'Y' являлось каким-либо видом вычислений, которое мы считаем трудноосуществимым. Если мы верим, что противник не может сделать 'Y', то следует логический вывод доказательства, что мы также должны верить в то, что противник не может сделать 'X' (по крайней мере если он действует в рамках данной модели атаки).
    Ситуация становится несколько туманнее, если мы попытаемся интерпретировать доказательства из доказуемой безопасности в "реальном мире". Тогда мы должы задаться вопросом, является ли модель атаки разумной. Мы должны рассмотреть возможность, что противник будет "играть не по правилам", как они определены в модели атаки (например мы можем доказать безопасность в модели чёрного ящика, но противник попытается провести атаку на побочные каналы, если у него есть доступ к определённой реализации системы). Также у нас остаётся вопрос о том, что невозможность противника сделать 'Y' действительно обоснованна.
    Исторически, фундаментальное допущение, известное как "принцип Кирхгофа", играло важную роль в создании реалистичных подходов к концепции криптографической безопасности. На языке современной криптографии этот принцип звучит как то, что не следует считать модель атаки "разумной", до тех пор пока описание криптографического алгоритма (безопасность которого изучена) не предоставлено противнику. Однако, в последние годы стало очевидно, что противник может иметь информацию о специфической реализации криптографического алгоритма, что даёт ему возможность осуществлять атаки по побочным каналам, таким как атаки на измерение времени исполнения. Так могут быть рассмотрены несколько моделей, в зависимости от уровня детальности сведений, которыми владеет противник о криптосистеме и как она выполнена в реальном воплощении.
    Наконец, мы должны помнить, что не стоит уповать на то, что математические доказательства могут быть применены к "реальному миру". Мы не ожидаем, что инженер математически доказывает непотопляемость корабля (может быть Титаник?) или то, что мост не рухнет (первый подвесной мост Tacoma Narows рухнул 7 ноября 1940 года из-за вибраций, вызванных ветром). Аналогично, нам не следует ожидать, что мы можем доказать, что реализованный криптографический алгоритм не может быть взломан. Для этого слишком много неизвестных: криптографический алгоритм — компонент более сложного протокола. Протокол выполнен (в аппаратном или программном виде) на некоторой платформе, на которой запущена некоторая операционная система, которая может быть подключена к интернету. Как мы можем ещё надеяться на доказательство того, что конечная система будет безопасна?


    В итоге, важно помнить, что валидность и релевантность (действительность и область применимости) доказательства в криптографии — это часто две соверешнно разные вещи:
  1. Валидность (действительность) доказательства отсылает нас к корректности этого доказательства, в пределах полностью конкретизированной и консистентной (непротиворечивой) математической модели. Если всему даны верные определения, то возможно (по крайней мере в принципе), определить, что данное доказателство является действительным.
  2. Релевантность (область применимости) доказательства намного более субъективна. Для вынесения оценки о релевантности доказательства, мы оцениваем потенциальное соответствие определений и математической модели, используемой в доказательстве, к тому что существует в реальном мире. В лучшем случае доказуемая безопасность предоставляет некоторые вероятные или правдоподобные свидетельства, а не доказательства (подчинённые некоторым правдоподобным или вероятным допущениям) того, что криптографическая схема будет безопасна при использовании в реальном мире.

4. Модель случайного оракула


Модель случайного оракула достигла высокого уровня известности. Крамер и Шуп написали, что любое доказательство, включающее модель случайного оракула должно рассматриваться как "эвристическое доказательство". Возможно даже более важно, что имелось некоторое количество опубликованых результатов, которые были доказанно стойкими в модели случайного оракула и становились нестойкими, как только случайного оракула заменяли любой реальной хэш-функцией (например SHA-1) (прим. перев.: эти результаты были получены когда SHA-1 и её аналоги считались криптостойкими функциями и для них не было известно никаких серьёзных уязвимостей, т.е. имеется ввиду, что даже если любая хэш-функция стойкая, она не могла заменить случайный оракул, по крайней мере на том этапе знаний в созданий хэшей). В любом случае, можно заметить существование широко распространённых мнений, что существует громадный "зазор" между доказательством, которое использует модель случайного оракула и доказательством, которое её не использует.
Дебаты показывают реальную обеспокоенность о роли модели случайного оракула как инструмента в криптографии. Другими словами, являются ли доказательства в модели случайного оракула релевантными по отношению к "реальному миру"? Точнее — являются ли доказательства в модели случайного оракула фундаментально или в значительной степени отличными, в терминах релевантности по отношению к реальному миру, если сравнивать их с доказательствами, не использующими модель случайного оракула?
Источник этой дискуссии уходит обратно к истокам работы 1993 года Беллэйра и Рогуэя в которой была представлена модель случайного оракула. Беллэйр и Рогуэй сформулировали следущее в реферативном предисловии к своей работе:

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

Это действительно попытка "взять быка за рога"! В основном Беллэйр и Рогуэй проталкивают тезис о том, что доказательство в модели случайного оракула является хорошим индикатором безопасности в реальном мире. Несмотря на результаты некоторых работ, я в целом могу согласиться с такой оценкой.
Мы приводим аргументы в пользу того, что никакое доказательство доказуемой безопасности не является доказательством в реальном мире. Существуют различные модели атак, которые могут быть рассмотрены в контексте любого доказательства безопасности. В идеале мы должны искать наименее ограничивающую модель атаки, когда выводим результат из доказательства (это может быть самый "сильный" результат стойкости). Существует множество вариаций модели атаки от самой сильной до самой слабой, и по моему мнению, модель случайного оракула может рассматриваться только как один из множества вариантов.
Если мы принимаем модель случайного оракула, это значит, что атакующий ограничен атаками, в которых хэш-функция является случайным оракулом (независимо от того является она на самом деле случайным оракулом или нет). Такие атаки обоснованно называют атаками, свойственными для всех хэшей ("хэш-генериками"). Доказательство безопасности в модели случайного оракула означает, что рассматриваемая схема не может быть взломана (в предмете различных допущений) никакой хэш-генерик атакой. (Прим. автора статьи: Насколько мне известно такая интерпретация впервые была предложена Бэйк-Вилсоном, Джонсоном и Менезисем.). Другими словами мы завершаем рассмотрение тем, что данная схема не может быть взломана определённым типом атак — и это всё что мы можем сделать с помощью доказательств доказуемой безопасности, по-любому.
Разумеется, доказательство в модели случайного оракула как правило не исключает возможность успешной атаки, которая использует специфические свойства хэш-функции, выполненной в схеме. Однако, это и не даёт мне особенных причин для беспокойства, отчасти потому что крайне сложным является подход, основанный на атаке "реальной" схемы на хэш-функции, которая считается безопасной (Автор статьи приводит ссылки на работу, где этот вопрос освещается подробнее).
Чтобы добавить немного рациональности к моим вышеприведённым аргументам, возможно имеет смысл рассмотреть другой компонент многих криптографических схем, который обычно не рассматривают при выводе доказательств доказуемой безопасности. А именно: многие схемы шифрования, схемы подписи и др. используют генераторы случайных чисел. Хорошо известно, что использование слабого генератора случайных чисел может подвергнуть полному взлому схемы, которые в противном случае были бы безопасными. С другой стороны, часто остаётся несформулированным, включая утверждения в доказательствах доказуемой безопасности, что совершенные случайные числа доступны всегда, когда бы они не потребовались (например в схеме подписей Шнора). Разумеется, это не такой случай и на практике случайные числа часто генерируются генераторами псевдослучайных чисел. Генераторы псевдослучайных чисел не более совершенны, чем генераторы истинно случайных чисел, как и хэш-функции не более совершенны, чем случайный оракул. Однако, не видно, чтобы какие-либо споры в будущем шли вокруг легитимности оставшейся невысказанной "модели совершенного генератора случайных чисел", лежащей в основе многих доказательств доказуемой безопасности. (Прим. автора статьи: Я не утверждаю никакого типа "эквивалентности" между хэш-функциями, исполняющими роль случайного оракула в качестве противоположности генераторов псевдослучайных чисел, исполняющих роль генераторов совершенных случайных чисел. Есть один момент: генератор псевдослучаных чисел имеет неизвестное секретное значение, в то время как хэш-функции полностью открыты).

5. Культура публикаций материалов конференций


Часто можно услышать жалобы, что многие работы по доказуемой безопасности наполнены жаргоном, сложны для чтения, неточны и часто некорректны. Однако эти претензии могут быть применимы ко многим работам по криптографии и теоретической комьютерной науке в целом. Математические работы могут тоже быть такими, что читать их не легче, но очевидно имеется широкораспространённое мнение, что опубликованные доказательства в математике более корректны, чем опубликованные доказательства в криптографии. Если это и на самом деле так, то почему это является правдой?
Мне кажется, что большая разница между культурой публикаций в математике и компьютерных науках это то, что форумом для математических исследований служат впервую очередь журналы, в то время как исследования в области компьютерных наук гораздо чаще издаются в материалах конференций.
Публикации для конференций имеют преимущество в быстроте издания, так что исследования быстро распространяются. К сожалению, рассмотрение программным комитетом обычно представляет собой плохую замену рассмотрения квалифицированными экспертами в вопросах представленных статей в реферативных журналах (для более обстоятельных дискуссий смотрите вэб-страницу Голдрейха по программным комитетам).
Другие помехи в публикациях на конференциях включают следующее:

  • Статьи для конференций часто подготавливаются в спешке (чтобы успеть к дате последнего приёма работ).
  • Работы для конференций могут не подвергаться пересмотру или обновлениям после презентации на конференции (часто материалы конференции публикуются до начала её фактического проведения).
  • Доказательства и разъяснения деталей часто отсутствуют (возможно всвязи с ограничением на количество страниц) .
  • У авторов часто мало стимулов для того, чтобы проделать дополнительную работу и подготовить "журнальную версию" своей работы. Например, публикация в ведущей конференции может иметь больший вес в умах председателей комитетов, чем журнальные публикации.

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

6. Трудности с определениями


Проблема с необходимостью давать точные определения в криптографии является серьёзным вызовом. Даже такое очевидно простое понятие как "односторонняя функция" крайне трудно в формальном определении. Более сложные концепции, такие как идея "существования подмены данных в адаптивных атаках с подобранными сообщениями" для того, чтобы определить безопасность схемы подписи, требует многих лет разработок. Определения безопасности для криптографических протоколов (таких как электронное голосование) всё ещё являются более комплексным. Разве не удивительно, что такого рода формальные, строгие определения в криптографии являются чем-то таким, что трудно обеспечить? Наконец, как мы можем доказать что-либо, если нам не ясно что именно вообще мы пытаемся доказать?
Эти типы трудностей с определениями по большей части не существуют в традиционной чистой математике. Мы не наблюдаем групп математиков, спорящих, является ли определение конечного поля "корректным" определением. Концепции и терминология в математике слишком стандартизированы и хорошо понятны тем, кто применяет их на практике. Может быть нелегко доказать, что теорема классификации конечных простых групп истинна, но по крайней мере нет неоднозначности в интерпретации того, о чём говорит эта теорема.
Причина такого контраста между математикой и криптографией может быть основана на ориентированности криптографии в сторону прикладных наук. Криптографы пытаются анализировать и доказывать вещи, которые имеют правдоподобное отношение к реальному миру. Изобилие различных моделей определений которые появляются в криптографических исследованиях — это отражение факта того, что не существует единственно "правильного" пути изучения криптографии. С другой стороны, математики и математические доказательства действуют внутри формальной модели и обычно это не имеет смысла, если модель "согласовывается" с реальным миром любым осмысленным способом. Полемика вокруг действительности доказательств в криптографии часто подогревается разницами в интерпретациях и непониманием, относящимся к положенным в основу определениям.
Для меня, попытка классифицировать определения является наиболее удивительным аспектом криптографии, особенно потому, что это так трудно сделать. Эта одна из особенностей исследований в области криптографии, которая очевидно фундаментально отличается от исследований в математике. В итоге криптографические исследования более плодотворны (и вызывают больше возражений, являются более сомнительными) по этой причине.

7. Итоги


В итоге изложенные в моём эссе аспекты сводятся к следующему:

  • Доказательства доказуемой безопасности (стойкости) — это всего лишь доказательства определённого типа безопасности в определённой модели атаки. Никакое доказательство из области доказуемой безопасности не может быть интерпретировано как доказательство безопасности в реальном мире.
  • Модель случайного оракула — всего лишь одна из множества моделей атак, которая может рассматриваться в контексте доказуемой безопасности. Она не является фундаментально "отличающейся" от многих других моделей атак.
  • Необходимо сделать больший акцент на размещении публикаций в "журнальных версиях" публикаций из конференций в порядке неободимости иметь архивные записи полных и корректных версий важных исследовательских результатов.
  • Точное определение концепций в криптографии является одной из ведущих задач в хороших криптографических исследованиях.

 
На страницу: 1, 2, 3 След.
Комментарии [скрыть комментарии/форму]
— spinore (25/08/2009 16:23)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
какое это имеет отношение к криптографии?

Так вот в том-то и проблема, что "математика не имеет никакого отношения к криптографии", а должна была бы... по логике вещей. Точнее говоря, это "криптография не имеет никакого отношения к математике" :-D
— Гость (25/08/2009 19:14)   <#>
Да и в математике, если приглядеться, не всё так гладко, как принято считать. Есть некоторые параллели.
— poptalk (25/08/2009 21:19)   профиль/связь   <#>
комментариев: 271   документов: 13   редакций: 4
Так вот в том-то и проблема, что "математика не имеет никакого отношения к криптографии", а должна была бы... по логике вещей.

Вроде имеет, если вычесть из неё человеческий фактор. Или я отстал от жизни?
— xy_й (22/08/2011 01:10)   <#>
Перевод ][yевый, зуб сломишь.
— Гость (22/08/2011 14:57)   <#>
Ну так предложите свой, лучше :)
— SATtva (22/08/2011 23:42)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Страница доступна для правки, если кто желает.
На страницу: 1, 2, 3 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3