Разница между теорией и практикой безопасности и криптографии?

Какие интересные различия существуют между теорией и практикой безопасности и криптографией?

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

Ответы могут включать (но не ограничиваются ими):

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

...

Предостережение

Если ваш ответ по существу имеет форму «Теория об асимптотике, но практика - нет», то либо теория должна быть действительно центральной, либо ответ должен включать конкретные примеры, где практический опыт в реальных случаях отличается от основанного на ожиданиях по теории.

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

Ох, парень, с чего начать.

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

В качестве иллюстрации, если вы посмотрите на формальный анализ протоколов безопасности, например, логики BAN , вы увидите, что симметричное шифрование рассматривается как «идеальный блочный шифр». Здесь есть тонкое различие - логика BAN (и другие методы анализа протокола) не претендуют на доказательство безопасности; скорее они являются методами поиска недостатков. Поэтому не совсем верно, что здесь используется идеальная модель шифра. Однако эмпирически верно, что большая часть анализа безопасности имеет тенденцию ограничиваться формальной моделью, поэтому эффект тот же.

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

Чтобы увидеть, насколько серьезна проблема, рассмотрите эту рекомендацию по безопасности, касающуюся подделки сигнатур API. Ошибка отчасти связана с атакой с удлинением длины в конструкции Меркле-Дамгарда (которая действительно очень проста) и затрагивает Flickr, DivShare, iContact, Mindmeister, Myxer, RememberTheMilk, Scribd, Vimeo, Voxel, Wizehhive и Zoomr. Авторы отмечают, что это далеко не полный список.

Я думаю, что практикующие заслуживают львиную долю вины за это печальное положение дел. С другой стороны, возможно, теоретики крипто-теории должны пересмотреть свою позицию. Их линия звучала так: «черные ящики невозможно построить; мы даже не собираемся пробовать». На что я говорю, поскольку ясно, что ваши конструкции все равно будут (неправильно) использоваться как черные ящики, почему бы хотя бы не попытаться сделать их как можно ближе к черным ящикам?

Газета « Возвращение Меркле-Дамгард» - отличный пример того, о чем я говорю. Они изучают понятие безопасности, что «хеш-функция произвольной длины H должна вести себя как случайный оракул, когда строительный блок фиксированной длины рассматривается как случайный оракул или идеальный блочный шифр». Этот вид теоретического исследования потенциально может быть чрезвычайно полезным на практике.

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

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

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

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

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

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

Ответ Randomwalker очень хорош. Мой любимый разрыв между теорией и практикой - модель случайного оракула. Это кажется очень безопасной эвристикой на практике (если предположить, что люди не делают глупостей и, по крайней мере, правильно увеличивают длину, см. Также ответ случайного наблюдателя), но у нас нет никаких положительных теоретических результатов по этому поводу. На самом деле все теоретические результаты об этой эвристике отрицательны. Я думаю, что это большой вопрос исследования, и надеюсь, что когда-нибудь будут получены некоторые интересные положительные результаты об этой модели.

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

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

Примеры, когда теория предполагает, что что-то возможно, но на практике это никогда не используется:

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

Примеры, когда теория предполагает, что что-то безопасно, а не безопасно на практике:

Этот вопрос немного расплывчатый, поэтому я не уверен, что ответ на него есть - но существует множество примеров «доказуемо безопасных» схем, которые на практике нарушаются, поскольку определение безопасности не соответствует сценарию развертывания. Только за последние несколько лет были совершены атаки на (доказуемые варианты) SSH и IPSec, среди прочих.

Примеры чего-то широко распространенного в практическом использовании имеют мало теории:

Я предполагаю, что вы имеете в виду в мире крипто, а не в мире общей безопасности. Хорошим примером являются подписи DSS, которые не имеют доказательств безопасности.

$M$$M'$$M'$$w \iff M$ отбросы $w$такой, что $M'$ принимает строку $w \iff M$ принимает $w$ и такой, что сложность во время выполнения $M'$ такой же как $M$на всех входах. Наконец, есть дополнительное условие, что$M'$должно быть трудно понять и изменить. Промышленность рассматривает такое запутывание как хороший компромисс, предусматривающий пожертвование небольшим (постоянным временем) накладным расходом в пользу увеличения сложности для противников, заинтересованных в понимании, взломе или краже ИС из$M$,

Есть много коммерческих компаний, которые предлагают бинарные решения для запутывания, а также есть несколько решений с открытым исходным кодом. Точные методы обфускации, конечно же, держатся в секрете; парадигма обфускации, распространенная в промышленности, является эвристической, поэтому знание алгоритмов, используемых для обфускации двоичного файла в этом контексте, как правило, гарантирует некоторое преимущество в деобфускации. Запутывание в промышленности известно как «безопасность через неизвестность».

Существуют теоретические подходы к проблеме запутывания, которые формализуют желания промышленности, но основываются на строго более строгом понятии безопасности, основанном на вычислительной неразрешимости (представьте себе, что замена целочисленных и строковых тестов на эквивалентность выполняется односторонними тестами на эквивалентность функций). В частности, было продвинуто изучение запутываемой точки композита , чтобы попытаться решить проблему запутывания, интересную для промышленности. К сожалению, наиболее распространенная теоретическая модель обфускации, основанная на модели, основанной на защищенном от несанкционированного доступа оборудовании, была дана невозможным результатом в 2001 году Бараком и др. В статье « О (im) возможности запутывания программ ». (Несколько других моделей с тех пор также получили результаты невозможности).

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

Чтобы уточнить, запутывание соответствует вашему третьему примеру: «Примеры чего-то широко распространенного в практическом использовании имеют мало теории». Обфускация сегодня широко используется как промышленностью, так и теми, кто преследует более гнусные цели. Запутывание в промышленности в настоящее время не основано на какой-либо строгой теории, несмотря на попытки.

Существует значительный разрыв, даже когда речь идет о базовых примитивах, таких как псевдослучайные генераторы. Рассмотрим, например, псевдослучайные функции. На практике люди используют такие вещи, как AES , которые отличаются от теоретических кандидатов (Goldreich, Goldwasser, Micali; Naor, Reingold и т. Д.) По нескольким параметрам: во-первых, параметры совершенно разные, например, AES может иметь длину ключа, равную длине ввода , что неслыханно в теоретических построениях. Возможно, еще важнее то, что AES (и многие другие блочные шифры) следуют так называемой парадигме сети замещения-перестановки, которая весьма отличается от того, как идут теоретические конструкции (например, упомянутые выше).

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

Я думаю, что выше приведен такой пример, см., Например, эту статью с Эриком Майлзом (из которого, по сути, взят этот ответ).