id: Гость   вход   регистрация
текущее время 02:11 21/08/2017
Владелец: unknown (создано 12/02/2010 09:56), редакция от 07/10/2010 22:33 (автор: unknown) Печать
Категории: сайт проекта, faq
http://www.pgpru.com/FAQ/КриптографияОбщиеВопросы
создать
просмотр
редакции
ссылки

Криптография: Общие вопросы


Оглавление документа:

Что такое криптографический примитив?

Самый нижний уровень криптосистемы. Это самый маленький "кирпичик" или деталь из которых она может быть составлена. Иногда используют название "атомарный примитив (atomic primitive)". Источником примитивов являются труднорешаемые математические проблемы (например проблема дискретного логарифма может служить основой однонаправленной функции) и специально созданные конструкции (блочные шифры, хэш-функции).


Иногда при конструировании примитивов второго рода, термин "примитив" используется к их составным частям — например S-блокам блочного шифра AES, хотя правильнее говорить об "элементах внутренней структуры примитива".


Конструирование примитивов — самая сложная и ответственная задача криптографии. Созданием примитивов занято небольшое число криптографов, а на их криптоанализ и обоснование стойкости тратится больше всего усилий.

Что такое режим использования криптопримитива?

Сам по себе криптопримитив может быть несовершенен и/или недостаточен. Асимметричный алгоритм RSA требует дополнения определённым способом по размеру блока, блочные шифры требуют использования определённого режима шифрования. Режим использования — это промежуточный уровень детализации между самим криптопримитивом и протоколом.

Что такое криптографический протокол?

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

Что такое криптографический стандарт?

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

Что такое информационно-теоретическая, безусловная и абсолютная модели безопасности?

Информационно-теоретическая модель безопасности криптографических систем — такая при которой противник не может совершить взлом, даже обладая бесконечно большими вычислительными ресурсами. При этом доказательства в такой модели выводятся из теории информации. Когда такая модель не опирается на решение проблем, неограниченная вычислительная стойкость которых считается недоказанно стойкой, то говорят о безусловной модели безопасности.


Частный случай информационно-теоретически стойкой модели — абсолютно стойкая модель, при которой не происходит никаких утечек данных в шифртекст. Такими свойствами обладают одноразовый блокнот, некоторые схемы одноразовой аутентификации и разделения секрета. Абсолютно стойкие системы устойчивы к появлению всех возможных новых видов криптоанализа — их стойкость доказана полностью.


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

Что такое стандартная модель безопасности?

Стандартная модель безопасности подразумевает, что если противник способен взломать криптосистему, то он также может решить вычислительно сложную задачу (например разложение чисел на множители). Иными словами, он должен обладать для этого достаточно большими вычислительными ресурсами, которые задаются такими параметрами безопасности системы, чтобы такие ресурсы были для него недостижимы.
Алгоритмы, основанные на стандартной модели, называют вычислительно стойкими. Доказательства в такой модели выводятся на основе теории сложности, а сложные задачи подбираются такими, чтобы их нельзя было решить за полиномиальное время.


Трудность с использованием этой модели состоит в том, что вычислительная сложность большинства задач лишь обоснованно предполагается, но не является доказанной. Если удасться доказать обратное, то протокол, построенный на основе стандартной модели очевидно также окажется нестойким.


Доказательство или построение комплексного протокола с нужными свойствами только в рамках стандартной модели часто невозможно, поэтому в большинстве случаев прибегают к помощи идеализированных моделей — случайного оракула и идеального блочного шифра.
Например, схема дополнения в RSA — RSAOAEP зависит как от стойкости RSA в стандартной модели, так и от стойкости используемых в дополнении хэш-функций в модели случайного оракула.

Что представляет собой модель случайного оракула?

Случайный оракул — это абстрактная функция, которую можно представить в виде следующей модели. Пусть существует некий чёрный ящик, на вход которого можно подать строку любой длины. При первом запросе на выходе случайный оракул (RO — Random Oracle) выдаёт строку истинно случайных чисел фиксированной длины и записывает "запрос/ответ" в память. При последующих запросах RO проверяет: если такой запрос уже был, то выдаётся предыдущий ответ. Если не было, то производится новый цикл: генерация истинно случайной строки, её вывод, запись в память запроса и ответа. Такое гипотетическое устройство могло бы состоять из генератора истинно случайных чисел с памятью и процессором, но при количестве запросов, стремящимся к очень большим величинам (что требуется для моделирования криптопротоколов), его память и быстродействие также должны стремиться к бесконечности.


На основе модели RO построены хэш-функции. Они пытаются воплотить идею RO в реальном мире на основе псевдослучайных функций, отображающие строки длиной от одного байта до примерно 2256 бит в короткие хэш-значения с фиксированной длиной, обычно до 29 (512-бит). Существуют экспериментальные модели хэшей и с выходом длиной, задаваемой также до произвольно больших значений.


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


С другой стороны, протокол, построенный с учётом модели случайного оракула (ROM — Random Oracle Model), будет обладать свойствами неразличимости от идеальной модели. Доказательство стойкости в ROM даёт уверенность в том, что протокол собран из исходных частей правильно при условии, что сами исходные части идеальны. Такое доказательство является разновидностью статистической проверки, в виде расширенного формального языка, адаптированного к анализу криптографических протоколов.


Однако существует опасность, что если хэш-функция не является идеальным RO, то неизвестный или неучтённый различитель сделает в реальности нестойким протокол, стойкость которого доказана в ROM.


ROM получает также распространение для анализа внутренней структуры примитивов (блочных шифров, хэш-функций).

Что такое модель идеального шифра?

Идеальный блочный шифр в такой модели (Ideal Cipher Model — ICM) рассматривается следующим образом. Пусть размер блока шифра — b, размер ключа — k.
Тогда каждый ключ задаёт таблицу псевдослучайной перестановки (Pseudo Random Permutation — PRP) всех возможных вариантов открытого текста во все возможные варианты шифртекста (размер каждого "варианта" равен размеру блока, т.е. b). Число строк в такой таблице будет 2b.


При смене ключа (даже если между ключами есть явные зависимости) должна получаться другая PRP-таблица, не имеющая никакой связи с предыдущей, как если бы её заполнили с помощью генератора истинно случайных чисел. Число таких таблиц — 2k.


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


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


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

Что такое доказуемая безопасность (стойкость)?

Форма доказательства, показывающая, что в рамках модели, рассматривающей широкий спектр атак, противнику придётся проделать для взлома протокола такую же работу, как и для решения сложной математической проблемы (стандартная модель) или для нахождения различителя между протоколом и идеальной моделью (Random Oracle Model, Ideal Cipher Model).

Если принципы доказуемой безопасности подвергаются критике, можно ли доверять результатам работ на её основе?

Этот вопрос является причиной споров по поводу самих основ современной криптографии. Более подробное освещение данной темы дано в статьях "О непростых взаимоотношениях между математикой и криптографией" и "Полемика по поводу понятий криптографической безопасности".


Кроме Коблица и Менезиса, дополнительную критику современной криптографии показывает Николя Куртуа в своей работе file"Новые границы в симметричном криптоанализе". Его аргументы состоят в частности в том, что успешное противостояние криптопримитива n известным атакам не исключает возможности появления новой атаки под номером n+1, против которой он будет нестоек. И точно оценить вероятность появления такой атаки невозможно. Такое возникает, потому что сведение всех атак к некоторой общей проблеме всегда неполно. Проблема неполноты — естественное ограничение методологии доказуемой безопасности.


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


Следует отметить, что алгоритмы и протоколы, в отношении которых вообще не представлено доказательств безопасности, чаще всего не стоит принимать к серьёзному рассмотрению. Исключение могут составлять экспериментальные и теоретические протоколы с предварительным, заведомо неполным или слабым доказательством безопасности. Их иногда называют эвристическими и создают в надежде получить более весомое доказательство позднее, при этом в исходной версии протокола нередко исправляются какие-либо уязвимости.

Я хочу предложить специалистам на рассмотрение новый криптоалгоритм или новую идею в области криптографии. Есть ли такой интернет-ресурс, где это можно сделать?

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


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


Перед тем, как кто-то из специалистов уделит хоть небольшое внимание новому алгоритму, он спросит сам себя:

  • Автор предлагаемого алгоритма известен в научных кругах? Состоит ли он в организациях, занимающихся криптологическими исследованиями? У него есть публикации в журналах по криптологии, он выступал с докладами на конференциях? Какой университет он представляет? С его кафедры уже были успешные работы? Какими работами известен его научный руководитель?
  • Автор публиковал успешные работы по взлому уже существующих алгоритмов? Или хотя бы открыл в них ранее неизученные свойства? Он изобрёл новый вид криптоанализа? У него есть оригинальные теоретические работы по новому направлению в дизайне алгоритмов, которые он публиковал и представлял в сообществе в течении примерно 5-10 лет и которые постепено получили признание специалистами мирового уровня? Можно ли проследить по публикациям прогресс в развитии теории, которую автор положил в основу своего алгоритма?
  • Есть ли у автора какие-то теоретические работы кроме той узкой области, которую он хочет представить? И т.д.

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


К тому же, чаще всего новый шифр, хэш или режим шифрования сам по-себе никому не нужен, даже если автор известен, возможно, что всё равно никто тратить время на его изучение не будет. Есть шанс получить внимание к работе, если выбрать удачный момент и представить работу на конкурс или под запрос на стандарт.


При этом, работа должна быть полной. Полное описание, полный анализ, всё должно быть проделано автором самостоятельно и должно быть видно, что за этим стоят многолетние исследования. Есть и определённые формальности. Плохим тоном считается публикация только исходного кода без развёрнутого теоретического описания, работы без библиографических ссылок, плохо оформленные, с неоправданным использованием собственной нестандартной терминологии и др.


Здесь есть некоторый уровень предвзятости, но это естественно, чтобы отсеять лишнее и не тратить ресурсы исследователей впустую.


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


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


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


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

У меня есть файл, зашифрованный вероятно слабым криптоалгоритмом. Могу я обратиться к криптографам, чтобы мне помогли его расшифровать? (Понятие об отличии сертификационного и практического криптоанализа).

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


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


До практического криптоанализа в открытом сообществе дело обычно не доходит, но иногда его всё-таки проводят.


Основные причины его проведения таковы:


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

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

Что такое квантовая криптография и как оцениваются её ближайшие перспективы?

Под квантовой криптографией понимают использование измерений квантовых состояний и их изменение с помощью физических приборов для выполнения какого-либо криптографического протокола. Большинство таких протоколов достаточно фантастичны. На практике реализованы только протоколы квантового распределения ключей (Quantum Key Distribution — QKD). Вместо использования сложной математической задачи или конструирования аналогов идеальных функций в качестве сложной проблемы в QKD используются принципы квантовой механики (принцип неопределённости Гейзенберга и неклонируемость квантовых состояний). В отличие от недоказанной сложности математических задач, лежащей в основе обычного крипто, эти принципы считаются полностью верными и позволят активно обнаруживать атакующего, который попытается подключится к квантовому каналу и перехватить ключ. Для аутентификации и шифрования на основе переданных по квантовому каналу данных используются также абсолютно стойкие схемы из традиционной криптографии — варианты схемы Картера-Вегмана и одноразовый блокнот (хотя эти два алгоритма относятся к классической криптографии, их абсолютная стойкость считается доказанной в отличие от практически всех остальных алгоритмов классической криптографии, но их использование отдельно от квантовых каналов непрактично), что должно делать системы на QKD абсолютно стойкими независимо от любого последующего прогресса в криптоанализе.


Доводы в пользу квантового распределения ключей рассмотрены в соответствующей статье.


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


 
Много комментариев (15) [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3