id: Гость   вход   регистрация
текущее время 22:19 13/05/2021
Владелец: 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 (18/08/2009 19:36)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
По поводу "коструктивность vs неконструктивность в математике" ещё можно высказать такое замечание (компиляция ответа со стороны Vadim_Z по личной переписке):

Каждому же ясно, что не существует иррац. чисел, непрерывных функций, интегралов и т.п. вещей, но ровно так же не существует и многих физических идеализаций типа точечного источника и других. Можно провести аналогии между тем и тем: физические идеализации позволяют строить вменяемые физические модели, а неконструктивная математика – математические модели. Представьте, что все бы работали с суммами а не с интегралами :) Парадоксально, но стремление к конструктивности делает решение многих реально неконструктивным. Я для себя это называю "парадоксом дельта-функции в физике" (она, казалось бы, более сложное понятие, чем обычная, но, в то же время, является гораздо большей идеализацией и жизнь с ней реально проще). Иными словами, неконструктивная математика в конечном итоге позволяет сильно упростить теорию моделей, в т.ч. моделей внутриматематических. Точно так же и с симметриями: их не существует, но они являются важными и полезными идеализациями. Резюмируя, физические модели и неконструктивная математика "существуют" как платоновские эйдосы, как реализация реально видимых вещей.
— spinore (18/08/2009 20:09, исправлен 18/08/2009 21:36)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
Ещё более забавный пример. Дети (например я в своё время) часто интересуются, какое же самое большое натуральное число? Взрослые с трудом объясняют, что его не существует, а зря. Согласно неконструктивной математике такое число есть! Точнее говоря, есть число, большее всех натуральных, и называется оно Алеф-нуль. Оно является лишь первым из так называемых трансфинитных чисел, которые существуют из-за принятия аксиомы выбора. Основы функционального анализа, вообще, – интересная штука (что-то типа "матанализа для взрослых"), жаль в общевузовской программе нематематиков его нет.

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

Популярная шутка о разной степени интуитивности:

"The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who
can tell about Zorn's lemma?"

© Jerry Bona

This is a joke: although the three are all mathematically equivalent, most mathematicians
find the axiom of choice to be intuitive, the well-ordering principle to be counterintuitive,
and Zorn's lemma to be too complex for any intuition.

Кстати, из 3х вышеперечисленных, лемму Цорна чаще всего и используют: самая удобная.
— unknown (18/08/2009 21:07)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
PS: спасибо за перевод, конечно. Очень поучительная статья, систематизирует.


Присоединяюсь. Осознание существующих проблем — суть залог движения вперёд. Автор — молодец, переводчик — тоже. :-)


Всегда рад представить интересный материал, да ещё из серии "не могу молчать" :-)

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

Думаю он полезен как теоретикам, так и разработчикам-практикам.

Да, с корнями ступил, думал, подумал о чём-то сложном, а это простой и известный пример ;-)

заодно было интересно ознакомиться с материалами, что кроме теоремы Геделя в математике всё больше областей, где и с определениями и с доказательствами нет полной определённости.
— Гость (18/08/2009 21:39)   <#>
Тем не менее, некоторые парадоксальные разбиения возможны и на плоскости: круг можно разбить на конечное число кусков и составить из них квадрат равной площади.

© Из http://ru.wikipedia.org/wiki/Парадокс_Банаха_—_Тарского. Опять же, поблагодарим неконструктивную (прогрессивную) математику за то, что мы никогда не увивдим вживую этого разбиения... но оно "есть" :-D

PS (от Vadim_Z): Еще ни про одно утверждение, следующее из аксиомы выбора, не доказано что оно ложное. Однако, не отрицается построение такой аксиоматики, где аксиома выбора будет не нужна, а нужно будет (кроме совсем экзотики) более безобидное утверждениее. Это опять же к вопросу о моделях. Сейчас и экзотика и нужные вещи перемешаны. Можно сказать, что "логическая истинность != истинности "на самом деле". Cубъективности тут не больше чем в физике. Везде рулит консенсус и традиция: есть всякие более слабые варианты аксиомы выбора, типа ADC и т.п., с помощью них что-то можно доказать, а что-то нет, и мб то, что "нельзя" – самая дичь (типа базиса Гамеля) и есть. Не знаю насколько попытки "отделить перемешанное" были успешны до сего момента. ADC равносильна теореме Бэра о категории (без которой функциональный анализ не построишь), но она не позволяет доказать существование неизмеримых множеств R, например. В чистой теории Цермело-Френкеля даже вещественный анализ не построить, так что все равно нужны дополнительные аксиомы.

Можно не лезать глубоко и взять множество Кантора – оно строгой аксиомы выбора не требует, но насколько оно конструктивно, если про заданную точку заведомо за конечное число шагов нельзя сказать, принадлежит ли она этому множеству? Так что даже более слабые варианты аксиомы выбора дадут некие "артифакты", а без них, как уже было выше сказано, прийдется обойтись без вещественного анализа.

PPS: Vadim_Z попросил не рассматривать эти суждения как "истину в последней инстанции", т.к. он не математик по специальности. Аналогичное я добавляю и относительно своих рассуждений. Это всего лишь взгляд физиков со стороны :-)
— spinore (18/08/2009 21:44)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
ой, s/типа базиса Гамеля/типа Парадокса Банаха—Тарского/
— unknown (18/08/2009 22:11)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Мы может определить систему как вычислительно стойкую, если лучший алгоритм взлома требует N операций, где N — некоторое определённое, очень большое число. Проблема в том, что никакая практическая криптосистема не может быть доказуемо стойкой согласно этому определению.

А почему?! Не хорошо умалчивать и говорить недомёками. Ну, допустим, нет сейчас хорошей теории алгоритмов, не почему такая уверенность, что она не появится в будущем?

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

Т.е. можно точно сказать: нужно 2n шагов исполнения, столько-то памяти, столько открытых текстов и т.д. по условию конкретной атаки.

Поэтому система и не является доказуемо стойкой
"согласно этому определению". Стена ведь не является "доказуемо стойкой" только на основании того, что её трудно прошибить лбом.

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

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

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

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

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

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

Статья краткая, хоть и не ускоспециализированная, а про криптографию вообще, но рассчитана на специалистов, знакомых с определениями основных понятий и автор просто не раскрывает всех определений (кстати с ними опять же не всё может быть точно и в разных работах и научных школах определения и применимость тех же оракулов могут отличаться).
— spinore (18/08/2009 22:54)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
тут похоже непонимание определения автора. Попытаюсь за него дообъяснить. Вычислительная стойкость возможна только против одной конкретной атаки — атаки грубой силой, атаки с невозможными дифференциалами, атаки, опубликованной Шамиром этим летом и т.д.

А кто мешает взять теоретический максимум по всем возможным атакам?

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

Кстати, ни кидание игральных костей, ни подбрасывание монеток не является иедеально-случайным процессом. У нас один деятель на спор подкидывал монетку 20 раз, каждый раз ловя определённую её сторону. Всё же это математическая абстракция :-)

PS: спасибо за уточнения.
— Гость (19/08/2009 00:55)   <#>
Кстати, ни кидание игральных костей, ни подбрасывание монеток не является иедеально-случайным процессом
А что скажете насчёт существования волшебников с картинки?
— spinore (19/08/2009 00:59)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
А что скажете насчёт существования волшебников с картинки?

Они не тревожили моё детство :-) Я сконяюсь к тому, что деда Мороза и прочих на самом деле нет :(
— Гость (19/08/2009 02:02)   <#>
Ну так и идеальных костей нет. Они тоже с той же картинки :)

зы
Анекдот времён "перестройки":
– Дети, напишите предложение: "Вороне где-то Бог послал кусочек сыра"
– МарьИванна, а бога нет!
– Сыра тоже нет, что же теперь и диктант не писать?
— Гость (22/08/2009 21:48)   <#>
spinore, написал: "А кто мешает взять теоретический максимум по всем возможным атакам?" Наличие ума в мозге.
Предлагайте критерий. Я берусь предложить лучший.

spinore, написал: "У нас один деятель на спор подкидывал монетку 20 раз, каждый раз ловя определённую её сторону."

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

Таким образом, Ваш пример может касаться только и исключительно злонамеренно закрытого крипто. Типа ГОСТ-а в части перестановок. Предлагаете ввести "мамой клянусь" в анализ стойкости? Сомневаюсь, что здесь у Вас получится.
— spinore (23/08/2009 22:15)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
Гость (22/08/2009 21:48), комментарии выделяются вот так: <[цитируемое]>

Предлагайте критерий.

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

Во-первых, в орлянке монету не ловят.

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

Таким образом, Ваш пример

Какой конкретно?
— SATtva (24/08/2009 18:33)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4094
О (не)случайности в подбрасывании монетки, вот, появилось у Шнайера.
— spinore (25/08/2009 00:41)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
Угу, жжот ацки:
A coin will land on its edge around 1 in 6000 throws, creating a flipistic singularity.
В русских анекдотах ещё были варианты "улетит в космос" и "зависнет в воздухе".
— poptalk (25/08/2009 14:26)   профиль/связь   <#>
комментариев: 271   документов: 13   редакций: 4
Насколько мне известно, конструктивное математическое доказательство — то, которое использует интуиционистскую математическую логику, и неконструктивное математическое доказательство — то, которое использует классическую математическую логику. Какая физика, какая аксиома выбора, какое это имеет отношение к криптографии? =:-о
На страницу: 1, 2, 3 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3