Опасности и ограничения при построении неразличимой модели

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:58, 27 сентября 2015.
Careful with Composition Limitations of the Indifferentiability Framework
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Томас Ристенпарк[@: 1]
Ховав Шахман[@: 2]
Томас Шримптон [@: 3]
Опубликован 2010 г.
Сайт Department of Computer Science
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Содержание

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


Введение

Подход к неразличимости Маурера, Реннера, и Холенстайна (MRH)[1]поддерживает модульные доказательства безопасности для криптосистем. Важным применением для модели была возможность перевода доказательства для модели случайного алгоритма (ROM)[2] в другие идеализированные вычислительные модели, где случайные алгоритмы заменяются хэш-функциями, построенными из идеальных функций сжатия. Это происходит с помощью теоремы о соединениях, обычная интерпретация для которой выглядит следующим образом: доказательство безопасности для произвольной криптосистемы с использованием функционала (например, случайного алгоритма) выполняется, когда криптосистемы вместо этого используют второй функционал (например, хэш-функции от идеальной функции сжатия), до тех пор, пока является неотличимым от .

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

Случайные алгоритмы и неразличимость

Дадим некоторые пояснения относительно того, почему неразличимость оказывается столь полезной. Широкий спектр практически применимых, используемых криптографических схем ограничивается доказательством безопасности в ROM модели[2], а для некоторых схем, ROM доказательства являются единственными известными. Но большинство из используемых построений хэш-функций не подходят для моделирования как алгоритмы, даже при допущении, что примитивы, лежащие в основе хэш-функций идеальны (например, идеальная функция сжатия), потому, что они подвержены атакам, расширяющим длину[3]. Эти атаки нарушают структуру основных итеративных хэш-функций, таких как MD5, SHA-1 и SHA-2. Их слабость приводит к практической ненадежности[4]. Конечно, мы можем построить хэш-функций, которые сопротивляются подобным атакам, но пока остается неясным будут ли результирующие функции также противостоять непредвиденным атакам, нарушающим структуру.

Корон и соавт. в работе[5], предложили подход, в котором хэш-функции "ведут себя" как случайные алгоритмы. В частности, это требует, чтобы хэш-функция будет безопасна, когда безопасен случайный алгоритм. Теорема о MRH соединении обеспечивает это условие, при и , последняя хэш-функция строится на (идеальных) примитивах . Таким образом, требуется, чтобы хэш-функция была неразличима от . Важно отметить, что такой подход сохраняет доказательства безопасности: MRH теорема переводит доказательство безопасности для криптосистем в доказательство безопасности при использовании неразличимых хэш-функций. В ряде недавних работ была доказана неразличимость для построений (например,[6][7][8][9][10][11][12][1]), в том числе и для NIST SHA-3. Учитывая все это, мы приходим к мнению, что неразличимость осуществима при функциях "ведущих себя" как RO, при наличии атак на структуру и когда криптосистема является безопасной в ROM моделе с использованием любого совместимого неразличимого хэш построения.

Хэш схемы хранения и аудита данных

Теперь мы опишем приложение, в котором данные выводы не выполняются. При создании безопасных систем распределения, возникает следующий важный вопрос: как стороны в системе могут убедиться, что сервер на самом деле сохраняет те файлы, которые нужно? Вредоносный сервер может вмешиваться в этот процесс произвольным образом; также возможен отброс файлов для экономии места. Эта проблема привлекла много внимания, после того как она была формализована в 2007 году[13][14]. Частный пример, который мы рассматриваем в этой статье, использует протокол запросов-ответов, являющийся частью предложенной ранее системы безопасного хранения [15].

Рассмотрим следующий протокол. Клиент посылает случайных запрос серверу; сервер доказывает наличие файла , вычисляя с помощью криптографических кэш функций Hash, и отправляя обратно клиенту, который выполняет те же вычисления, используя свою копию , сравнивает результаты. Предположим, для простоты, что и файл , и запрос , имеют размер в бит и рассмотрим случай, когда , где является идеальной функцией сжатия, выводящей строки размером в бит и , выводит первые бит для . ( является фиксированной строкой констант). Это построение является неразличимым от , как было показано в [5]. Таким образом, MRH теорема о соединении в сочетании с тем фактом, что протокол является безопасным в ROM модели, доказывают, что протокол является безопасным при использовании . Совершенно непонятно, каким образом сервер может жульничать! Сервер просто вычисляет , после получения , затем удаляет и записывает (короткий) . Чтобы ответить на запрос , сервер вычисляет и возвращает первую половину в качестве ответа на запрос. Проверка клиента происходит, даже если не сохраняется. Возможные атаки нарушают структуру типичных хэш-функций, проводящих онлайн вычисления. Хэш-функция обладает этим свойством, когда она может обрабатывать свои входы в последовательных блоках, сохраняя только часть информации и внутренних состояниях между блоками. Это свойство необходимо на практике, и все неразличимые хэш построения обладают им (см., например, [6][7][8][9][10][12]). Однако, как показывает наш пример, онлайн вычисления могут быть опущены.

Подведем некоторые итоги. В разделе 4 мы докажем, что схемы аудита с безопасным хранением безопасны в ROM модели. Доказательство для неразличимости функции , проведенное Короном и соавт. в работе [5], и доказательство MRH теоремы применимы в нашем случае. Но сервер все еще каким-то образом может нарушить структуру . Так в чем же здесь проблема?

Описание проблемы

Сложная проблема состоит в том, MRH теорема не полностью применима. Тщательно пересмотрев MRH теорему и ее доказательство, мы находим, что (грубо говоря) она применима только тогда, когда безопасность криптосистемы измеряется относительно безопасности игры с одним статичным противником. Например, неразличимость стороны[16] для схем шифрования и достоверность при выбранной атаке на сообщения [17] определяются при наличии только одного статичного противника. Но безопасность только что описанного протокола аудита с запросами и ответами определяется в две стадии. На первом стадии, противник (сервер) получает сообщение , определяет из некоторое состояние , меньшее, чем размер , и забывает . На второй стадии он пытается ответить на запросы, используя только . Это является примером того, что мы называем многоэтапной игрой.

В предыдущих исследованиях неразличимости подразумевается наличие ограничения на одноэтапные игры при описании криптосистем и противников. Это ограничение не упоминается в литературе, и мы предполагаем, что исследователи (до сих пор) не знают о нем. Для полноты описания мы вновь представим MRH теорему о неразличимом строении и дадим ее доказательство для одноэтапных игр в разделе 3.

Последствия

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

Все это ставит под сомнение безопасность каких-либо схем по отношению к многоэтапным играм. Схемы вполне могут быть безопасными в ROM модели, но это не предполагают отсутствие опасных атак на структуру, даже при использовании неразличимых хэш построений. И, к сожалению эта опасность имеет широкое распространение. Все последние понятия безопасности для детерминированных [18][19][20], ограниченных[21] , и эффективно обнаруживающих[18] шифровок с открытым ключом (PKE) являются многоэтапными. При описании криптографии с паролями (например, [22][23]), для того, чтобы позволить наличие произвольных хэш-зависимых алгоритмов выбора пароля, используются многоэтапные игры. Недавно предложенное понятие о неизменной безопасности хэш-функций[24] является многоэтапным. Интересно, что это единственное понятие (из известных нам), которое описывает безопасность от расширяющих длину атак, и, хотя мы предполагаем наличие, но не имеем доказательств того, что эти построения могут противиться подобным атакам.

Таким образом, в целом мы не можем использовать модель на основе неразличимого построения, чтобы утверждать безопасность в контексте многоэтапных игр. Но возможно, что неразличимость оставляет возможность для обеспечения безопасности для хэш-функций аудита. Можно было бы надеяться доказать, без применения MRH теоремы, что модель ROM доказательства (скажем) для детерминированной схемы PKE шифрования выполнена даже при использовании любого неразличимого хэш построения. Это представляется разумным, поскольку для описанных приложений, онлайн вычисления хэш-функций не однозначно подразумевает безопасность. Тем не менее, мы покажем, что таких доказательств не существует. А именно, в разделе 5 будет показано, что неразличимость не предполагает безопасности в многоэтапных случаях, упомянутых выше.

Неразличимость сброса

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

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

Прямые доказательства

Невозможность применения MRH соединения для доказательства безопасности ROM модели многоэтапной игры в условиях, когда используются хэш структуры из идеальных примитивов, приводит к тому, что мы рассматриваем специфические случаи шифрования с открытым ключом. Мы доказываем теорему о безопасности при распределенной атаке (CDA) для ряда смежных, ROM безопасных PKE схем, когда они используют любые неразличимые хэш-функции, построенные в соответствии с парадигмой Додиса, Ристенпарка и Шримптона[11]. Понятие CDA безопасности [4] включает конфиденциальность сообщения для PKE схем, когда сообщения и случайности являются (совместно) непредсказуемыми, либо контролирующими противников. В частности, это понятие необходимо в контексте детерминированных PKE схем [18][19][20], ограниченных PKE схем (которые обеспечивают конфиденциальность сообщений, даже при малой случайности)[21][25] и эффективно обнаруживающих шифровках (при расширении детерминированных PKE схем)[18]. Как и ожидалось, прямое доказательство безопасности сложно, потому что мы должны работать непосредственно в моделе идеальных примитивов, лежащих в основе хэш-функций. Данный пример показывает, что прямые результаты для безопасности возможны и показывает, что в некоторых многоэтапных случаях безопасность возможна для предлагаемых неразличимых хэш конструкций.

Другие ограничения

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

Универсальная компонуемость

Наши результаты имеют аналогичные последствия для модели соединения как и для неразличимости; это универсальная компонуемость[27]. Мы обсуждаем другие подходы в полной версии работы [26].

Обсуждение

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

Предварительные сведения

Модель для игр с кодами

Мы описываем версию игры с кодами Беллара и Рогвейа[28] для представления анализа безопасности и неразличимости. Мы считаем подобные игры с кодами полезными для формализации определения безопасности, в частности, потому, что они позволяют нам определить семантику исполнения (т.е. определить что и как работает, и в каком порядке). Здесь мы приведем лишь наиболее важные детали, а остальные опишем в полной версии этой статьи. Процедура состоит в последовательном применении операторов для нуля или более входов (переменных) и для нуля или более выходов (переменных). Неопределенной процедурой является та, псевдокод, входы и выходы которой понятны из контекста. Противник является примером неопределенной процедуры. Вызов процедуры означает обеспечение ее входами и запуск последовательности операторов. Во время ее исполнения может сама инициировать другие процедуры. Скажите, что код для может вызывать до различных процедур. Запишем , чтобы показать, что эти вызовы осуществляются за счет . Процедуры и имеют одинаковый интерфейс, если их входы и выходы совпадают по размеру и типу. Это как правило, ясно из контекста.
Рис. 1. Процедуры реализации функционалов для модели случайных алгоритмов (ROM) (Слева) и для модели идеальных примитивов (IPM) (справа). Число r задается для каждого конкретного контекста

Основная процедура не принимает входы и дает только некоторые выходы. Мы обозначим ее как main. Она не может быть вызвана ни одной другой процедурой, а она сама имеет доступ ко всем переменным других процедур. (Но не к другим неопределенным процедурам). еременные сводятся к первоначальным значениям, то есть целое число устанавливается 0, массивы сводятся к нулевым и т.д. Переменные по умолчанию являются локальными, то есть могут быть использованы только в рамках одной процедуры. Переменные, использованные в процедуре, не меняют свое состояние между запросами. Набор процедур это набор из одной или нескольких процедур, которые могут обмениваться своими переменными. Мы обозначаем набор процедур как , где является общим префиксом. Иногда мы будем ссылаться на уникальные индексы , как на интерфейсы .

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

Для любых двух функционалов , обозначим через (F1,F2) функционал, который вызывает процедуру запросов и процедуру доступа к .

Игра состоит из одной основной процедурой, обозначенной как "main ", вместе с пустым или более набором других процедур. (См. рис 2.) Игра может использовать функционал совместно с рядом процедур противника , что будет обозначать наличие такового. Обозначим этот случай как . Зафиксируем условие, что основная и указанные процедуры из могут вызвать и (но не могут вызвать ), в то время как процедуры противника могут вызвать (но не могут вызвать ). Таким образом будет интерфейсом противника в , а будет честным интерфейсом. Для всех и таких, что , являются совместимыми интерфейсами и совместимы для , мы можем записать для игры , запускаемой с одним набором внешних процедур, и для той же игры, но теперь со вторым набором внешних процедур. Запуск игры означает выполнение последовательности операторов для процедуры main и вывод значения для G, полученного из основной процедуры. Обозначим случай, когда выводом для игры будет y, взятое из вероятностного пространства используемых процедур . Если и противник не используют , то мы запишем . Примеры игр, которые не используют функционалы , приведены на рисунке 2, в то время как игры, которые используют их, приведены на рисунках 3 и 4.

Для любого фиксированного функционала и противника две игры и будут эквивалентны, если для всех значений .

Ресурсы

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

Модель неразличимости для одноэтапных игр

Мы описываем модель неразличимости[1] с помощью игр, в отличие от предшествующих подходов, которые использовали случайные системы[29][1] или интерактивных машин Тьюринга[5]. Мы считают, что использование игр с кодами упрощает понимание ограничений для неразличимости, потому что это дает возможность выразить эти ограничения как синтаксические условия для классов, используемых игр. В дополнение к определению неразличимости, мы приведем конкретные версии теоремы о соединении из работы[1] и охарактеризуем наши ограничения.

Неразличимость

Зафиксируем два функционала и . Говоря о неразличимости для случайных алгоритмов, мы используем (для некоторых , ) и . Противник будет выводить бит. Процедура моделирования обозначается как . Рисунок 2 определяет две игры Real (реальную) и Ideal (идеальную). Зафиксируем некоторое значение (например, ). Неразличимость для будет определяться как

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

Рис. 2. Игры, которые определяют неразличимость. Противник и функционалы , являются неопределенными. Моделирование является параметром игры

Смысл "разумности", "эффективности", и "малости" будет понятен из контекста. Чтобы получить асимптотическое определение, можно предположить повсеместное наличие параметра безопасности k, а затем использовать определение[5]: является неразличимым от , если существует такое PT моделирование , что для любого , является пренебрежимо малым в отношении параметра безопасности. Отметим, что в работе [1] использованы другие кванторы. В ней утверждается, что для всех должно существовать такое моделирование , что будет пренебрежимо малым в отношении параметра безопасности. Мы будем называть понятие из[1] слабой неразличимостью а из [5] строгой неразличимостью. Мы будем рассматривать строгую неразличимость, так как она подразумевает слабую.

Построение

Одна из целей неразличимости состоит в том, чтобы позволить проводить анализ безопасности криптографических схем при использовании одного функционала, и подразумевать безопасность, когда будут использованы другие. Это обеспечивается следующим образом, что, по сути, является версией исходной теоремы Маурера, Реннера, и Холенстайна[1] (MRH).

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

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

Доказательство
Доказательство теоремы 1 легко установить путем адаптации доказательства [1]. Мы приводим это доказательство здесь, чтобы упростить наши последующие рассуждения.

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

Будет выполнено . Теперь определим противника следующим образом. Противник запускает. Когда запрашивает свой алгоритм, противник начинает моделирование , используя алгоритм для ответа на запросы от . Затем выводит тоже, что и . За счет такого построения мы получаем ; , а также

для случая когда . Подставляя уравнения 1 и 2 в определение неразличимости, мы выполняем отношения, заявленные в теореме.


Одноэтапные игры

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

Это справедливо независимо от того, как мы определяем . В следующем разделе мы приводим контр-пример, показывающий, что нет никакой возможности доказать это обобщение. Все это означает, что неразличимые соединения могут применяться только к безопасности для одноэтапной игры, которую мы сейчас определим. Рассмотрим игру, имеющую m процедур. Мы говорим, что игра имеет минимум этапов, если все игры , которые эквивалентны , используют столько же процедур для противника. Теперь сосредоточимся на таких играх. Пусть игра с m этапами будет называться m-игрой. Одноэтапная игра это та, для которой , а для многоэтапной игры . Пусть будет обозначать множество всех одноэтапных игр. Отметим, что включает в себя игры, с описанной выше неразличимостью и классическими понятиями безопасности шифрования, такими как IND-CPA[16], IND-CCA[30] или UF-CMA[17] и многими другими. Если определяет множество всех игр, тогда будет множеством не одноэтапных игр. Мы будем называть любую игру из многоэтапной. Примеры многоэтапных игр включают безопасность распределения атак на шифрование с открытыми ключами[21] (см. рисунок 4), неизменность хэш-функций[24], обмен ключами с паролями [22], и другие.

Рассуждения

Игра, которая использует несколько процедур для противника, но эквивалентна игре с одной процедурой, не считается многоэтапной согласно нашему определению. Многие эксперименты формализуются процедурами для противника; но в игре состояние процедуры передается от одной к последующей. Очевидно, что такие игры на самом деле эквивалентны тем, что используют одну процедуру для противника. Некоторые игры позволяют передачу части состояния непосредственно от одной процедуры к другой. Примером может служить свойство безопасности для хэш аудита, описанное на рисунке 3. Здесь, однако, состояние не является произвольным, его размер фиксирован, и поэтому эта игра не может быть записана с одной процедурой для противника.

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

Практический контр-пример

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

Хэш системы хранения и аудита данных

Свойство, которые мы изучаем и обозначаем его как CRP, вызвано протоколами аудита с запросами для безопасного распределенного хранения [15]. Считаем, что клиент хочет сохранить некоторые данные на удаленном сервере. Позже мы покажем, что сохраняется при отправке
Рис. 3. Игра для нашей хэш-функции с запросами
случайного запроса к серверу и дальнейшей проверке соответствия ответа сервера значению . Понятно, что если является случайным алгоритмом, то для сервера нет никакой возможности смошенничать: он должен на самом деле сохранить , или угадать заранее запрос, чтобы отреагировать правильно. (Выбор запросов из достаточно большого пространства или повторение протокола сделает вероятность того, что сервер сможет угадать запрос, пренебрежимо малой). В частности, если сервер сохраняет некоторое состояние вместо , и , тогда сервер не в состоянии ответить правильно. CRP эксперимент на рисунке 3 показывает слегка упрощенную версию этого примера.

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

TemplateTheoremIcon.svg Теорема Теорема 2
Фиксируем . Пусть будет противником, который делает запросов. Затем

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

Доказательство
без доказательства


Онлайн вычислимость и CRP безопасность

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

Отметим, что большинство построений хэш-функции онлайн вычислимы для различных значений . Например, так называемое NMAC построение из [5]. Для этого оно использует два основных идеальных объекта и . Пусть будет маркировкой, определенной следующим образом: при входных и для всех вычисляется , где является некоторой фиксированной n-битной строкой, и выводится . Пусть теперь , где доменом будет . Это построение - онлайн вычислимо для любых кратных . Пусть для любого и . Тогда и .

Точно так же многие другие построения будут онлайн вычислимы для таких параметров, например EMD[7], MDP[12], так называемые HMAC построения [5], а также многочисленные SHA-3 кандидаты. Легко заметить, что любая - онлайн вычислимая хэш-функция не может CRP безопасной для тех же параметров. Для NMAC примера, приведенного выше, выводит . Пусть выводит . В таком случае выигрывает с единичной вероятностью.

Безопасное хранение и аудит на практике

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

Невыполнимость неразличимости для многоэтапных игр

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

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

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

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

TemplateTheoremIcon.svg Теорема Теорема 3
Пусть , будут функционалами и будет расширенной версией для . Пусть обозначает моделирование. Тогда существует такое , что для всех неразличимых противников существуют такие противники , что
  • требуется столько же времени и запросов, сколько и ;
  • требуется время как для с небольшим дополнением и с тем же числом запросов.
Доказательство
без доказательства


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

TemplateExampleIcon.svg Пример Пример: CDA безопасность для шифрования с открытым ключом
Задачи для определения безопасности PKE шифрования с открытым ключом и атаки с выбранным распределением определены в разделе 7. CDA атака обобщает понятия безопасности для детерминированных PKE шифровок[18][19][20], и CDA-безопасные PKE схемы полезны для эффективного поиска в зашифрованных данных [18] и защиты от случайных неудач[25]. Легко заметить, работать в модели, то понятие безопасности недостижимо. Чтобы атаковать любую схему, противник с первого этапа равномерно выбирает и запрашивает . Противник на втором этапе запрашивает для получения , шифрует оба сообщения по r, сравнивает результаты с зашифрованным текстом, и выводит соответствующие биты. Этот противник выигрывает с единичной вероятностью.

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

для неразличимых хэш построений[5].


Обсуждения

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

Неразличимость при сбросе моделирования

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

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

Неразличимость сброса

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

Для согласования с нашими определениями игр Real и Ideal (рис. 2) мы неявно предполагаем, что есть некоторый символ, который при получении входа от процедуры Prim, вызывает выполнение nop либо , соответственно. Мы получаем следующую теорему соединения.

TemplateTheoremIcon.svg Теорема Теорема 4

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

Кроме того:

где
  • являются максимальными временами работы для ;
  • являются максимальным количеством запросов, сделанных в одном исполнении;
  • это максимальное количество запросов, сделанных G из честного интерфейса в -й процедуре для противника, соответственно.
Доказательство
Доказательство этой теоремы легко получить путем адаптации доказательства теоремы 1. Пусть для . Это означает, в частности, что некоторые моделирования используются в каждой процедуре Затем мы определяем противника для любого совместимого функционала путем такого замещения что при сбросе запрашивается непосредственно предшествующий запрос .


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

Практическое расширение доменов при сбросе

Как уже упоминалось ранее, онлайн вычислимые хэш-функций не могут быть неразличимо сброшены. Это происходит потому, что теорема о соединении тогда будет требовать, чтобы такие хэш-функции обладали и CRP свойствами, что показано в разделе 4. Но некоторые эффективные хэш построения обладают CRP свойствами, и поэтому остается открытым вопрос, могут ли какие-либо эффективные построения обладать неразличимостью сброса. Мы отвечаем на этот вопрос отрицательно, исключая неразличимость сброса в RO модели для большого класса "эффективных" построений.

Зафиксируем некоторые так, что и пусть . Пусть будет произвольным идеальным примитивом. Мы ограничиваемся расширением доменов для построений . , которые могут быть записаны в виде для любых . Здесь обозначает уникальное кодирование для , в -битную строку; а также и . Важно отметить, что справедливость означает, что сжимается. Мы требуем, чтобы время для расчета кодирований и находилось в пределах небольшого, абсолютно неизменного времени для вычисления . В качестве конкретных примеров могут быть взяты все онлайн вычислимые функции, при простом задании . Гибкость, которой наделена произвольная кодировка, также означает, что мы охватываем широкий спектр таких , которые не будут онлайн вычислимыми. Например, какая-либо хэш-функция единичной передачи может быть записана в описанном выше виде. С другой стороны, построения подобные хэш-связкам[31] (делающим две передачи для сообщения), не рассматриваются.

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

TemplateTheoremIcon.svg Теорема Теорема 5
Пусть целые числа , функционал и построение соответствуют приведенному выше описанию. Пусть RO функционал реализует случайный алгоритм с диапазоном {0, 1}r. Тогда существует такой неразличимо сбрасываемый противник , что при моделировании c запросами справедливо
Доказательство
без доказательства


Детерминированные, ограниченные, эффективно обнаруживающие шифрования

Полученные до сих пор результаты показывают, что схемы доказуемо безопасносны в ROM модели могут не быть безопасными при использовании практических хэш-функций построения и если безопасность измеряется для многоэтапной игры. Как показано в разделе 5 это включает в себя многочисленные важные криптографические задачи. В качестве первого шага, мы здесь приводим пример для детерминированных, ограниченных, или эффективно обнаруживающих шифрований с открытым ключом, совместно с доказательством безопасности при использовании любого из числа неразличимых хэш построений. Мы выбрали этот пример в связи с широким использованием ROM модели и ее практической значимостью [18][21][25]. Конечно, мы не можем полагаться на теорему 1, так как наше доказательство выполнено для идеальных примитивов. Тем не менее, наш основной результат охватывает широкий перечень PKE и хэш-функций.

Рис. 4. (Левый) неадаптивные CDA игры. (Правый) IND-SIM и PRA игры

Мы ориентируемся на хэш построение из [11], которое представляет собой функции для прообразов (см. ниже) с фиксированной входной RO длиной. Хотя мы можем сделать анализ, не используя прообразы, но это упрощает наш результат. Пусть будет функцией, использующей некоторые основные примитивы . Пусть тоже будет функцией. Пусть определяется как . Отметим, что многие хэш-функции попадают в эти рамки, в том числе так называемые NMAC построения[5], MCM[32], NIRP[33], а также различные SHA-3 конкуренты.

Шифрование с открытыми ключами

Напомним, что PKE схемы шифрования с открытыми ключами состоят из трех алгоритмов. Алгоритм генерации ключей выводит открытый ключ, и пару секретных ключей. Шифрование принимает открытый ключ, сообщение и случайность , а выводит зашифрованный текст. Расшифровка принимает секретный ключ, зашифрованный текст, а выводит текст или индикатор . Следуя[18], определим для любой схемы максимальную вероятность нарушения открытого ключа, как

CDA безопасность

На рисунке 4 мы детализируем игру для (неадаптивных) атак с заданным распределением[21]. Это понятие, ортогональное к традиционному для IND-CPA, охватывает безопасность PKE схем, когда используемая случайность r не может быть (достаточно долго) строкой равномерных битов. В остальных случаях для данного раздела, фиксируем значение случайности и длину сообщения . будет вероятностным алгоритмом, который выводит такой вектор , что , все компоненты являются бит строками длины , а все компоненты являются бит строками длины и для всех и .

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

Осведомленность для прообразов

Свойство осведомленности для прообраза Додиса, Ристенпарта и Шримптона [11] обобщает сопротивление противникам. PrA игры определены на рисунке 4. Функционалу поставим в соответствие хэш построение , передатчик и противника , тогда PrA преимущество определяется как

Мы отмечаем, что PrA игра не соблюдает наше условие, что только противник запрашивает . Таким образом, теоремы 1 и 4 не применимы, если . Это не проблема для последних из приводимых нами результатов, оба из которых не реализуют PrA через неразличимые построения.

IND-SIM безопасность

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

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

CDA безопасность для PKE схем

Теорема 6 так устанавливает CDA безопасность для PKE схем, что во время шифрования, применяется однократно к хеш и , в том числе при декодировании открытых ключей, до тех пор, пока схема обладает безопасностью. ROM схемы для детерминированных, ограниченных или эффективно обнаруживающих шифровок [18][21][25] обладают безопасностью, предполагаемой за счет IND-CPA безопасности основных схем шифрования. Мы не делаем никаких предположений для , и поэтому результат применим как к хэш-функциям с идеальным шифром, так и к идеальным функциям сжатия.

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

TemplateTheoremIcon.svg Теорема Теорема 6
Пусть будет функционалом и FIL RO схемой. Пусть для некоторой процедуры . Также пусть будет PKE схемой, запрашивающей для каждого сообщения (включающего открытый ключ) при запросе. Пусть будет CDA противником, запрашивающим из и из , где это . Тогда при любом моделировании S и PrA передатчике существует противник и PrA противник С такие, что

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

Доказательство
Без доказательства


Благодарности

Томасу Ристенпарту была оказана поддержка грантом СРС- 0915675 от Центра сетевых систем. Ховав Шахам получил грант № FA9550-08-1-0352 по программе Кошланда для докторских стипендий. Томас Шримптон получил грант CNS-0845610. Мы благодарим Михира Беллара, Майка Далина, Даниэля Мицианцио, и Мони Наор за полезные комментарии к данной работе.

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

  1. Кафедра компьютерных наук, Университет Висконсин-Мэдисон, США, E-mail: rist@cs.wisc.edu
  2. Кафедра компьютерных наук и инженерии, UC Сан Диего, США, E-mail: hovav@cs.ucsd.edu
  3. Кафедра компьютерных наук, Портландский Университет, США teshrim@cs.pdx.edu

Примечание

Литература

  1. 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 Maurer, U.M., Renner, R., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004)
  2. 2,0 2,1 Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: Ashby, V. (ed.) ACM CCS 1993, Fairfax, Virginia, USA, November 3-5, pp. 62–73. ACM Press, New York (1993)
  3. 32. Tsudik, G.: Message authentication with one-way hash functions. In: Proceedings IEEE INFOCOM 1992, vol. 3, pp. 2055–2059. IEEE, Los Alamitos (1992)
  4. Franks, J., Hallam-Baker, P., Hostetler, J., Leach, P., Luotonen, A., Sink, E., Stew- art, L.: An Extension to HTTP: Digest Access Authentication. RFC 2069 (Pro- posed Standard) (January 1997), Obsoleted by RFC 2617
  5. 5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8 5,9 Coron, J.-S., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-damg ̊ard revisited: How to construct a hash function. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 430–448. Springer, Heidelberg (2005)
  6. 6,0 6,1 Andreeva, E., Mennink, B., Preneel, B.: On the indifferentiability of the grøstl hash function. In: Garay, J.A., Prisco, R.D. (eds.) SCN 2010. LNCS, vol. 6280, pp. 88–105. Springer, Heidelberg (2010)
  7. 7,0 7,1 7,2 Bellare, M., Ristenpart, T.: Multi-property-preserving hash domain extension and the EMD transform. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 299–314. Springer, Heidelberg (2006)
  8. 8,0 8,1 Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the indifferentiabil- ity of the sponge construction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 181–197. Springer, Heidelberg (2008)
  9. 9,0 9,1 Chang, D., Nandi, M.: Improved indifferentiability security analysis of chopMD hash function. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 429–443. Springer, Heidelberg (2008)
  10. 10,0 10,1 Dodis, Y., Reyzin, L., Rivest, R.L., Shen, E.: Indifferentiability of permutation- based compression functions and tree-based modes of operation, with applica- tions to MD6. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 104–121. Springer, Heidelberg (2009)
  11. 11,0 11,1 11,2 11,3 Dodis, Y., Ristenpart, T., Shrimpton, T.: Salvaging merkle-damg ̊ard for practical applications. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 371–388. Springer, Heidelberg (2009)
  12. 12,0 12,1 12,2 Hirose, S., Park, J.H., Yun, A.: A simple variant of the merkle-damg ̊ard scheme with a permutation. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 113–129. Springer, Heidelberg (2007)
  13. Ateniese, G., Burns, R., Curtmola, R., Herring, J., Kissner, L., Peterson, Z., Song, D.: Provable data possession at untrusted stores. In: De Capitani di Vimercati, S., Syverson, P. (eds.) Proceedings of CCS 2007, pp. 598–609. ACM Press, New York (October 2007)
  14. Juels, A., Kaliski, B.: PORs: Proofs of retrievability for large files. In: De Capitani di Vimercati, S., Syverson, P. (eds.) Proceedings of CCS 2007, pp. 584–597. ACM Press, New York (October 2007)
  15. 15,0 15,1 15,2 Kotla,R.,Alvisi,L.,Dahlin,M.:SafeStore:Adurableandpracticalstoragesystem. In: Chase, J., Seshan, S. (eds.) Proceedings of USENIX Technical 2007, pp. 129– 142. USENIX (June 2007)
  16. 16,0 16,1 Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and Sys- tem Sciences 28(2), 270–299 (1984)
  17. 17,0 17,1 Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing 17(2), 281–308 (1988)
  18. 18,0 18,1 18,2 18,3 18,4 18,5 18,6 18,7 18,8 Bellare, M., Boldyreva, A., O’Neill, A.: Deterministic and efficiently searchable encryption. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 535–552. Springer, Heidelberg (2007)
  19. 19,0 19,1 19,2 Bellare, M., Fischlin, M., O’Neill, A., Ristenpart, T.: Deterministic encryption: Definitional equivalences and constructions without random oracles. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 360–378. Springer, Heidelberg (2008)
  20. 20,0 20,1 20,2 Boldyreva, A., Fehr, S., O’Neill, A.: On notions of security for deterministic en- cryption, and efficient constructions without random oracles. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 335–359. Springer, Heidelberg (2008)
  21. 21,0 21,1 21,2 21,3 21,4 21,5 Bellare, M., Brakerski, Z., Naor, M., Ristenpart, T., Segev, G., Shacham, H., Yilek, S.: Hedged public-key encryption: How to protect against bad randomness. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 232–249. Springer, Hei- delberg (2009)
  22. 22,0 22,1 22,2 Bellare, M., Pointcheval, D., Rogaway, P.: Authenticated key exchange secure against dictionary attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 139–155. Springer, Heidelberg (2000)
  23. Yao, F.F., Yin, Y.L.: Design and analysis of password-based key derivation func- tions. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 245–261. Springer, Heidelberg (2005)
  24. 24,0 24,1 24,2 Boldyreva, A., Cash, D., Fischlin, M., Warinschi, B.: Foundations of non-malleable hash and one-way functions. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 524–541. Springer, Heidelberg (2009)
  25. 25,0 25,1 25,2 25,3 Ristenpart, T., Yilek, S.: When good randomness goes bad: Virtual machine reset vulnerabilities and hedging deployed cryptography. In: Network and Distributed Systems Security – NDSS 2010. ISOC (2010)
  26. 26,0 26,1 Ristenpart,T.,Shacham,H.,Shrimpton,T.:Carefulwithcomposition:Limitations of the indifferentiability framework. Full version of this paper
  27. Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: 42nd FOCS, Las Vegas, Nevada, USA, October 14-17, pp. 136–145. IEEE Computer Society Press, Los Alamitos (2001)
  28. Bellare, M., Rogaway, P.: The security of triple encryption and a framework for code-based game-playing proofs. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 409–426. Springer, Heidelberg (2006)
  29. Maurer, U.M.: Indistinguishability of random systems. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 110–132. Springer, Heidelberg (2002)
  30. Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ci- phertext attacks. In: 22nd ACM STOC, Baltimore, Maryland, USA, May 14-16. ACM Press, New York (1990)
  31. Liskov, M.: Constructing an ideal hash function from weak ideal compression func- tions. In: Biham, E., Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 358–375. Springer, Heidelberg (2007)
  32. Ristenpart, T., Shrimpton, T.: How to build a hash function from any collision- resistant function. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 147–163. Springer, Heidelberg (2007)
  33. Lehmann, A., Tessaro, S.: A Modular Design for Hash Functions: Towards Making the Mix-Compress-Mix Approach Practical. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 364–381. Springer, Heidelberg (2009)