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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 03:14, 21 декабря 2015.
Computer-Aided Security Proofs for the Working Cryptographer[прим. 1]
Computer-Aided Security Proofs for the Working Cryptographer.png
Авторы Gilles Barthe[@: 1],
Benjamin Gregoire[@: 2],
Sylvain Heraud[@: 3] and
Santiago Zanella Beguelin[@: 4]
Опубликован 2011 г.
Перевели Pavel Shestakov
Год перевода 2015 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Мы представляем EasyCrypt, автоматизированный инструмент для разработки доказательства безопасности криптографических систем с доказательством эскизы — компактное, официальные представления о сущности доказательства как последовательность игр и намеков. Доказательство эскизов проверяются автоматически, используя готовые Компания SMT решателей и автоматизированного доказательства теорем, а затем компилируются в проверке доказательств в CertiCrypt рамки. Утилита поддерживает большинство общих рассуждений структуры и значительно проще в использовании, чем его предшественники. Мы утверждаем, что EasyCrypt является вероятным кандидатом принятия рабочих криптографов и проиллюстрировать ее применение к доказательств безопасности Крамера-Шоупа и хэшированных криптосистем Эль-Гамаля.


Ключевые слова: Доказуемая безопасность, проверка безопасности, игры на основе доказательств, криптосистема Крамера-Шоупа, шифрование Эль Гамаля.

Введение

Игры-техника игры[1][2][3] является устоявшейся методологии для структурирования криптографические доказательства. Суть ее заключается в предоставлении точных математических описаний, называют игры, взаимодействия между противниками и Oracle систем. Доказательства организованы в виде последовательностей из игры, начиная от игры, что представляет собой целевое состояние (например, неразличимость в отношении избранных-шифротекстов атаки), и приступать к играм, которые представляют безопасности предположений (например, решения Диффи-Хеллмана) путем последовательных преобразований, что может быть показано, чтобы сохранить или изменить только немного общей безопасности. При обычном шаге в игре на основе доказательства цель-соотнести вероятность события в игре для вероятности возможно различные мероприятия в игре может быть . Например, целью может быть установление неравенства виде , где -арифметическое выражение, которое зависит от количества запросов Oracle, сделанное противником. Преобладающие практики, подтверждающие обоснованность таких доказательств действия заключается в использовании стандартных математических инструментов, которые перемежения рассуждения о семантике игр с информационно-теоретической или арифметических аргументов.

В коде-ориентированного подхода к игровой методике[1][2] игры отлиты как вероятностные алгоритмы. Принятие идиомами программирования позволяет дать точные определения игры и прокладывает путь для применения языка программирования, методы доказательства, чтобы оправдать действия строго. Как и прогнозировали их сторонники, на основе кода игры-играть доказательства поддаются формальной верификацией, и целый ряд инструментов, оказывающие поддержку в их укреплении.[4] - это инструмент для проведения доказательства безопасности в игре на основе обстановки, в которой игры моделируются как процессы и переходы оправданные посредством процесса - алгебраические понятия, такие как бисимуляций. Одна из сильных сторон , помимо того, что это первый инструмент, который поддерживает игры на основе доказательств, заключается в том, что это касается как протоколов и примитивов; он успешно применялся для проверки протокола Kerberos[5] и Полный Домен Хэш (FDH) подпись схеме[6].[7] является другой механизм, допускающий интерактивное построение игры на основе доказательств в доказательство помощника[8]. Одна специфика заключается в том, что доказательства могут быть проверены самостоятельно и автоматически с помощью небольшой достоверной проверки; он успешно применялся для проверки известных криптографических конструкций, включая OAEP[9], FDH[10], и нулевым знанием протоколов[11].

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

Тезисом настоящей статьи является то, что проверке безопасности может значительно выиграть от автоматизации с использованием состоянии самые современные технологии проверки, и проверяемый игры на основе доказательства могут быть построены только с умеренным усилием. В диссертации реализуется с презентации , автоматизированный инструмент, который строит машину-проверено доказательства от доказательства зарисовки, которые предлагают семантическое представление сущности ценной доказательство. Мы утверждаем, что значительно проще в использовании, чем предыдущие средства, делая важный шаг в направлении принятия системы автоматизированного доказательства безопасности, работая криптографов и, следовательно, к выполнению программы Халеви. Чтобы обосновать наши претензии, мы представляем автоматизированного доказательства безопасности хэшированных схем Эль-Гамаля шифрования и криптосистемы Крамера-Шоупа.

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

Вводный пример: Хэшированое шифрования Эль-Гамаля

В данном разделе показано применение доказательство безопасности шифрования хэшированных схем Эль-Гамаля в случайной модели Oracle. Пример служит для введения понятия доказательства эскиза и дает читателю представление входных данных, ожидающих инструмент. Он также допускает предварительное сравнение между и . Мы отсылаем читателя к [12] для доказательства аналогичного результата в

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

вернет
вернет
вернет

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

На рисунке 1 показана последовательность игры, используемые для обоснования безопасности снижения. Это является важной частью доказательства эскиз, который поступает на вход , и который состоит из пяти частей:[прим. 2]

1.Типы, константы и операторы объявления, которые вводят объекты, которыми манипулирует схема. В этом случае они включают тип для элементов циклической группы , константы, представляющие длиной сообщения , то порядок группы и генератор , и операторы, обозначающие группы права и возведение в степень, и исключающее или над битовыми строками;
2.Аксиомы, которые обхватывают математические свойства этих объектов, и используются автоматизированными инструментами для проверки достоверности доказательства эскиз. Мы используем аксиомы состояния права группы и возведение в степень, и оператор исключающее или;
3.Игра определения, где противники указаны как абстрактные процедуры с доступом к Oracle. Во всех играх на рисунке хэш-функции моделируется как случайные Oracle и противник представляется как две процедуры и , которые совместно используют состояние. Процедуры, представляющие противника получают доступ к оболочке для oracle хэш, который просто хранит запросы в списке до отправки их :
если тогда вернет
вернет
4.Суждения в pRHL. Общая форма суждения является , где и являются игры, и условие и пост-условием являются отношения по программе воспоминания (воспоминания карте программных переменных значений). Пре - и пост-условия первого порядка формулы построены из реляционные выражения, в которых языковые выражения с тегами или или для обозначения их интерпретации в первой или второй игре. Мы часто считаем, воспоминания эквивалентности на множестве переменных ; мы используем как сокращение для формулы
5.Утверждает о вероятности, построен из величин вероятностей (вероятность события в игре), арифметические операторы и математические отношения (например =,<,≤). Заключительное заявление, которое выражает общую безопасность Гарантия принес доказательство эскиз обычно является утверждение, что верхней границы вероятности успеха противника в игре первого нападения с точки зрения вероятности одного или нескольких противников, нарушая безопасность допущений.
Рис. 1. Эскиз доказательства безопасности хэширования Эль-Гамаля.

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

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

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

Окончательный переход выполняет сокращение до , выставляя противника , использующего как вложенные процедуры и для которого совпадают семантики игр и . Наконец от предыдущих претензий, преимущество может быть ограничен вероятность в решении . Получившийся рисунок доказательства составляет около 250 строк, примерно в 5 раз меньше, чем доказательство в сообщили в [12] — и возможно намного проще и недалеко от доказательства ручки-и-бумаги.

Обзор EasyCrypt

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

назначение
случайная выборка
if then else условие
вызов процедуры
skip
последовательность

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

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

Реляционные суждения пре - и пост-условий в pRHL суждения первого порядка формулы построены из реляционных выражений. Реляционные выражения произвольных Булевых выражений более логических переменных и переменных программы с тегами , ; единственное ограничение заключается в том, что логические переменные могут появляться только количественно. Путем злоупотребления обозначения, мы пишем ehii за выражение , в которой все переменные были помечены с . Пусть стенд для произвольного логического выражения над тегами и логические переменные, логические формулы определяются следующей грамматикой:

Логическая формула интерпретируется как отношение на программу воспоминаний. Например, формула интерпретируется как отношение

В pRHL суждения является допустимым, если для любой пары начальных воспоминания удовлетворения предварительных условий , распределений и удовлетворить отмене пост-условия . Снятие отношение к распределению определяется как максимум-отрезать мин-проблемы с движением, в стиле [13]. Формально, пусть быть распределение вероятностей на множестве и распределения вероятностей на множестве . Мы определяем подъем соотношения , и определяются следующим образом:[прим. 3]

где проекции и от определяются как

Утверждения о вероятности могут быть производным от действительных реляционных суждений с помощью следующих правил:

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

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

1.Вызовы процедур не противником, исключаются из игры путем последовательного встраивание их определения. В случае отсутствия рекурсии преобразование завершается успешно, и остаются только вызовы противника;
2.Случайные назначений перемещаются вперед. Результирующий код состоит из последовательности случайных назначений, с последующим детерминированным кодом, возможно со звонками противника;
3.Реляционное слабейшего предусловия исчисление применяется к детерминированному фрагменту игры, с помощью реляционной спецификации справляться с вызовами противника. Каждая спецификация противника индуцирует доказательство обязательства, выраженные как pRHL решения суда, на оракулов в своем интерфейсе. Самостоятельной состав применяется для проверки кода оракулов в отношении этих суждений pRHL. Это приводит в решении формы
4.Отображение выбран и использован для генерации проверки состояния , определяется как
При определенных условиях на , см [15], действительность влечет за собой действия соответствующего решения pRHL. На практике как правило, достаточно, чтобы требуют что сопоставления 1-1 и принимая как тождественная функция работает большую часть времени. Однако в некоторых случаях необходимо использовать другие сопоставления. Например чтобы доказать эквивалентности между игры и в доказательство хэширования Эль-Гамаля, описанных в предыдущем разделе, необходимо доказать решение следующим образом:
СП остановится после вычисления слабым предпосылкой для детерминированной фрагмент из двух программ, приносит
Эта эквивалентность доказывается в , предоставляя биективная функция как свидетель. Тот факт, что является биективное устанавливается автоматически, поскольку является идемпотентной. В общем случае это доказано, предоставляя также обратное сопоставление.
5.Так как формулы первого порядка, его действия может устанавливаться готовых инструментов. Чтобы выделить несколько инструментов, генерирует его проверки условий в промежуточном формате инструмента [16]. Затем мы используем доказательство [17] и решатель [18] выполнять условия (хотя многие другие доказательства поддерживаются, включая в интерактивные доказательства теорем таких как ).

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

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

Рассуждения о недостаточности событий игры на основе доказательств часто включают в себя действия, в котором утверждается, что две игры и действуют одинаково, если назначенное недостаточности событие возникает. Такие переходы оправданы с использованием так называемой фундаментальной Леммы [1][3], что позволяет связывать разницу между вероятностью события в игре и возможно различные события в игре с вероятностью в ту или иную игру. Хотя синтаксическая характеристика этой лемма часто используется, в которой событие сбой представлено булевым флагом в коде игры, мы констатируем более общий вариант леммы с использованием реляционной логики.

TemplateTheoremIcon.svg Теорема Лемма 1(Основная лемма)
Пусть и две игры и , и такие события, что

Тогда, если ,

1.
2.
Доказательство
Гипотеза леммы может быть проверена с помощью pRHL доказательства. Ключ к доказательству обоснованности решения находит соответствующую спецификацию для противников. определяет для каждого вызова противника отношение и проверяет действительность решения

.

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


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

Генерации достоверных доказательств реализует компилятор, который превращает эскизы в доказательство файлы, совместимые с рамки и могут быть проверены с помощью проверки . Компилятор служит двум целям: во-первых, это существенно повышает уверенность в доказательство эскизы по производству независимой проверке доказательств и предоставления возможности проверить непротиворечивость набора аксиом, используемых в доказательство эскиз. Во-вторых это открывает возможность для проведения доказательств общего назначения помощника доказательства шагов, которые выпадают из сферы автоматизированных методов. Мы кратко опишем, как работает компилятор. Заявления, определений игр, аксиомы и доказательства эскиз признать немедленного перевода в . Рекомендуется доказать, что аксиомы используются в . В большинстве случаев аксиомы уже существуют в , или простые последствия доказанные факты. Затем, используя доказательства, производящих вариант pRHL доказательство, все суждения доказательства эскиза составляются в pRHL язык в . Наконец компилятор создает для каждой претензии в доказательство эскиз лемма, что может потребоваться вручную завершить с обоснованиями вероятность рассуждений, выполненных .

Расширенное применение: Криптосистема Крамера-Шоупа

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

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

TemplateDifinitionIcon.svg Определение «Определение 1 (Целевое столкновение сопротивлений) »
Пусть ключ семейства хеш-функций. Преимущество противника при сопротивлении целевой столкновения определяется как

где эксперимент определяется с помощью следующей игры:

TemplateDifinitionIcon.svg Определение «Определение 2 (CCA преимущество) »
Пусть схемы асимметричного шифрования. CCA преимущество противника ограничивается расшифровкой запросов адаптивной выбрали шифротекста безопасности схемы определяется как

где эксперимент определяется по следующей игре:

Bsbd002.png

TemplateTheoremIcon.svg Теорема Теорема 1(Безопасность Крамера-Шоупа)
Пусть противник против безопасности Крамера-Шоупа ограничивается расшифровкой запросов. Тогда существует алгоритм для решения проблемы в и противник против целевого столкновения сопротивлений хэш-функций таким образом, что

Доказательство
Доказательство на рис.2.
Рис. 2 Эскиз доказательства IND-CCA безопасности криптосистемы Крамера-Шоупа


На рисунке 2 показан эскиз доказательства вышеуказанной теоремы в . Доказательство следит за представленным в [2], но мы приведем здесь лишь общее описание. Игра на рисунке получена напрямую из игры конкретизированной для Крамера-Шоупа на встраивание определений генерации ключей и шифрования процедур, распространяющихся назначения и замены выражений на равноценные. Мы наблюдаем, что все проверки условия, обеспечивающие обоснованность этого преобразования может быть освобожден автоматически с помощью SMT решателя. Это превосходит ожидания Халеви [2], который предложил такую трансформацию делить на три шага так, чтобы он мог быть обработан с помощью автоматического инструмента.

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

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

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

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

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


Ограничения и расширения

находится на ранних стадиях развития; Мы кратко прокомментируем некоторые из его основных ограничений и возможных расширений:

Язык программирования: по сравнению с , в языке отсутствуют циклы, рекурсивные процедуры, и рисунок от асимметричные распределения. Мы не видим необходимости расширения текущего языка с рекурсивных процедур. Напротив мы считаем, что более общие формы для выборки и ограниченная циклов являются полезными и не предусматривают конкретные сложности в добавлении их в языке (Обратите внимание, что аннотации цикла с инвариантами могут потребоваться для проверки состояния поколения);
Проверяемые доказательства: порождает лишь частично поддающихся проверке доказательства. Поскольку на данный момент нет SMT решателей, которые генерируют доказательств, проверки условий принимаются для того, чтобы сделать вывод отведений отмечаемое в доказательствe помощником. SMT решатели доказательство производителей является активным субъектом исследования [19], и прогресс в направлении этой цели пользуются сразу в ;
Вычисление вероятностей: генерирует каркасы доказательств для утверждения о вероятности, а не полностью машино-провереными доказательствами. А это полностью осуществимо, чтобы расширить компилятор для оправдания больших рассуждений, более принципиальное решение потребует инструмент, который может символически вычислить вероятность события в дистрибутив.

Дальнейшие исследования в теории криптографических доказательств, в строке [20], необходимо расширить сферу применения и эффективность . Основные цели заключаются в предоставлении официального аккаунта полезных рассуждений принципов, таких как перематывать доводы или монетки-фиксации, и понятия, такие как статистические расстояния, которые еще не были рассмотрены в наших условиях. По-прежнему имеются широкие возможности для применения методов из языков программирования и формальной верификации для автоматизированного криптографические доказательства.Отметим две интересные возможности для улучшения автоматизации в . Первый способ - улучшить наш механизм для извлечения реляционных характеристики противников: там большой объем знаний на выведение инварианты, и полезно было бы перенести их в нашей условия. Более спекулятивно, программа синтеза может использоваться, чтобы обнаружить часть последовательности игр, требующихся для доказательства, и для построения противников, которые оправдывают сокращение криптографических предположений. Обе спецификации логического вывода и синтеза программ полагаются на проверки состояния поколение и SMT решение, отсюда и основные блоки для проведения такого расследования на месте. Наконец, Халеви [2] подчеркивает, что «полезность инструмента () будет зависеть критически готовность клиентов (в данном случае криптографической сообщество) использовать его» и предлагает на этот счет, что соответствующий пользовательский интерфейс будет одним из важнейших компонентов инструмента. Мы полностью присоединиться к его мнению и увидеть здание такой интерфейс как одной из важных целей для дальнейшей работы.

Сравнение с CertiCrypt

Таблица 1 сравнивает и на различные доказательства безопасности, официально в обеих системах. На процессоре Intel Core 2 Duo 2,8 ГГц с 4 ГБ оперативной памяти под Mac OS X 10.6.7 измеряются времена. Для сравнения мы показываем, размер и время проверки доказательств извлеченные из доказательство эскизы. Это не совсем справедливое сравнение, потому что извлеченные доказательства себя как аксиом доказательство обязательства проверяются автоматизированных provers. Как эксперимент мы завершили интерактивно извлеченные доказательства безопасности шифрования Эль-Гамаля, получая таким образом полное доказательство проверке под . В результате доказательства длины 1173 (что означает, что только 43 линии необходимо доказать в доказательстве обязательства, проверяться автоматизированными доказательствами) и занимает 25с для проверки.

Таблица 1. Сравнение размера доказательств и проверка времени между CertiCrypt и EasyCrypt.

CertiCrypt EasyCrypt Извлеченные
Строки Время Строки Время Строки Время
Эль-Гамаль () 565 45с 190 12с 1130 23с
Хэширование Эль-Гамаля () 1255 1 мин 5с 243 33с 1772 41с
Полное-Доменное Хэш () 2035 5 мин 46с 509 1 мин 26с 2724 1 мин 11с
Крамер - Шоуп () н/д н/д 1637 5 мин 12с 5504 3 мин 14с
OAEP () 2451 3 мин 27с н/д н/д н/д н/д
OAEP () 11162 37 мин 32с н/д н/д н/д н/д

Заключение

Автоматизированная верификация криптографических протоколов в символическую модель устоявшаяся область научных исследований: надежные инструменты доступны и успешно используются для анализа реалистичные протоколов (например, [21][22][23][24]). В отличие от мало до работы на компьютерной криптографии доказательства в расчетной модели. Важность таких доказательств было предложено самостоятельно Белларом и Рогауэем [1] и, более конкретно, по Халеви [2], который убедительно утверждает, что их можно рассматривать как “естественный следующий шаг на этом пути просмотра криптографические доказательства в виде последовательности вероятностных игр”. На сегодняшний день существует два основных инструмента для автоматизированного криптографические доказательства: , который способствует общности и проверке доказательств, и , что способствует автоматизации. Мы представили , новый инструмент, который обеспечивает первую гибкую и автоматизированную инфраструктуру для построения машины-отмечаемое криптографические доказательства, и показано ее использование посредством автоматизированного доказательства безопасности хэшированных схем Эль-Гамаля шифрования случайного Оракула и модель Крамера-Шоупа криптосистемы в рамках стандартной модели. Эти примеры демонстрируют, что доказательств в значительно проще и быстрее строить, чем в любой предыдущий инструмент, обеспечивая при этом гарантии, похожими на . В целом, мы считаем, что делает важный шаг в направлении принятия системы автоматизированного доказательства рабочих криптографов.

Благодарности Мы благодарны Дэниелу Хедину и Энн Пакалет за их участие в начальных этапах проекта, Яссину Лакнеч и Дэвиду Поинтчевалу за полезные обсуждения и анонимным рецензентам за их ценные замечания.

Контакты авторов материала

  1. IMDEA Software Institute, Madrid, Spain
  2. INRIA Sophia Antipolis-Mediterranee, France
  3. INRIA Sophia Antipolis-Mediterranee, France
  4. IMDEA Software Institute, Madrid, Spain

Примечание

  1. Частично финансируемый европейский проект FP7-256980 NESSoS, французский проект ANR SESUR-012 SCALP, испанский проект TIN2009-14599 DESAFIOS 10, и Мадридский региональный проект S2009TIC-1465 PROMETIDOS
  2. Первые два изображения на рисунке опущены. Мы включаем выписку из фактического входного файла для справки в приложении А.
  3. Для ясности изложения будем предполагать, что A и B являются дискретными и отбросим наши определения с помощью обычного представления распределений. Тем не менее, инструмент строит на монадическом представление распределений, как и в [6].

Литература

  1. 1,0 1,1 1,2 1,3 Bellare, M., Rogaway, P.: The security of triple encryption and a framework for code-based game-playing proofs. In: Advances in Cryptology – EUROCRYPT 2006. Lecture Notes in Computer Science, vol. 4004, pp. 409–426. Springer, Berlin (2006)
  2. 2,0 2,1 2,2 2,3 2,4 2,5 2,6 Halevi, S.: A plausible approach to computer-aided cryptographic proofs. Cryptology ePrint Archive, Report 2005/181 (2005)
  3. 3,0 3,1 Shoup, V.: Sequences of games: a tool for taming complexity in security proofs. Cryptology ePrint Archive, Report 2004/332 (2004)
  4. Blanchet, B.: A computationally sound mechanized prover for security protocols. In: 27th IEEE symposium on Security and Privacy, S&P 2006. pp. 140–154. IEEE Computer Society (2006)
  5. Blanchet, B., Jaggard, A.D., Scedrov, A., Tsay, J.K.: Computationally sound mechanized proofs for basic and public-key Kerberos. In: 15th ACM conference on Computer and Communications Security, CCS 2008. pp. 87–99. ACM, New York (2008)
  6. Blanchet, B., Pointcheval, D.: Automated security proofs with sequences of games. In: Advances in Cryptology – CRYPTO 2006. Lecture Notes in Computer Science, vol. 4117, pp. 537–554. Springer, Berlin (2006)
  7. 7,0 7,1 Barthe, G., Gr´egoire, B., Zanella B´eguelin, S.: Formal certification of code-based cryptographic proofs. In: 36th ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages, POPL 2009. pp. 90–101. ACM, New York (2009)
  8. The Coq development team: The Coq Proof Assistant Reference Manual Version 8.3. Online – http://coq.inria.fr (2010)
  9. 9,0 9,1 Barthe, G., Gr´egoire, B., Lakhnech, Y., Zanella B´eguelin, S.: Beyond provable security. Verifiable IND-CCA security of OAEP. In: Topics in Cryptology – CT- RSA 2011. Lecture Notes in Computer Science, vol. 6558, pp. 180–196. Springer, Berlin (2011)
  10. Zanella B´eguelin, S., Gr´egoire, B., Barthe, G., Olmedo, F.: Formally certifying the security of digital signature schemes. In: 30th IEEE symposium on Security and Privacy, S&P 2009. pp. 237–250. IEEE Computer Society, Los Alamitos, Calif. (2009)
  11. Barthe, G., Hedin, D., Zanella B´eguelin, S., Gr´egoire, B., Heraud, S.: A machine-checked formalization of Sigma-protocols. In: 23rd IEEE Computer Security Foundations symposium, CSF 2010. pp. 246–260. IEEE Computer Society, Los Alamitos, Calif. (2010)
  12. 12,0 12,1 Barthe, G., Gr´egoire, B., Heraud, S., Zanella B´eguelin, S.: Formal certification of ElGamal encryption. A gentle introduction to CertiCrypt. In: 5th International workshop on Formal Aspects in Security and Trust, FAST 2008. Lecture Notes in Computer Science, vol. 5491, pp. 1–19. Springer, Berlin (2009)
  13. Jonsson, B., Yi, W., Larsen, K.G.: Probabilistic extensions of process algebras. In: Bergstra, J., Ponse, A., Smolka, S. (eds.) Handbook of Process Algebra, pp. 685–710. Elsevier, Amsterdam (2001)
  14. Barthe, G., D’Argenio, P., Rezk, T.: Secure information flow by self-composition. In: 17th IEEE workshop on Computer Security Foundations, CSFW 2004. pp. 100–114. IEEE Computer Society, Washington (2004)
  15. Zanella B´eguelin, S.: Formal Certification of Game-Based Cryptographic Proofs. Ph.D. thesis, Ecole Nationale Sup´erieure des Mines de Paris – Mines ParisTech (2010)
  16. Filliˆatre, J.C.: The WHY verification tool: Tutorial and Reference Manual Version 2.28. Online – http://why.lri.fr (2010).
  17. Detlefs, D., Nelson, G., Saxe, J.B.: Simplify: A theorem prover for program checking. Tech. Rep. HPL-2003-148, HP Laboratories Palo Alto (2003)
  18. Conchon, S., Contejean, E., Kanig, J., Lescuyer, S.: CC(X): Semantic combination of congruence closure with solvable theories. Electronic Notes in Theoretical Computer Science 198(2), 51–69 (2008)
  19. Stump, A.: Proof checking technology for satisfiability modulo theories. Electr. Notes Theor. Comput. Sci. 228, 121–133 (2009)
  20. Barthe, G., Daubignard, M., Kapron, B., Lakhnech, Y.: Computational indistinguishability logic. In: 17th ACM conference on Computer and Communications Security, CCS 2010. pp. 375–386. ACM, New York (2010)
  21. Backes, M., Maffei, M., Unruh, D.: Computationally sound verification of source code. In: 17th ACM conference on Computer and Communications Security, CCS 2010. pp. 387–398. ACM, New York (2010)
  22. Bhargavan, K., Fournet, C., Gordon, A.D.: Modular verification of security protocol code by typing. In: 37th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL 2010. pp. 445–456. ACM (2010)
  23. Cremers, C.: The Scyther Tool: Verification, falsification, and analysis of security protocols. In: 20th International Conference on Computer Aided Verification, CAV 2008. Lecture Notes in Computer Science, vol. 5123, pp. 414–418. Springer, Berlin (2008)
  24. Paulson, L.C.: The inductive approach to verifying cryptographic protocols. J. of Comput. Secur. 6(1-2), 85–128 (1998)