Физически неклонируемые функции в универсальной композиционной структуре

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:13, 22 декабря 2015.
Physically Uncloneable Functions in the Universal Composition Framework
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Christina Brzuska [@: 1]
Marc Fischlin [@: 2]
Heike Schröder [@: 3]
Stefan Katzenbeisser [@: 4]
Опубликован 2011 г.
Перевели Roman Titov
Год перевода 2015 г.
Скачать оригинал


Содержание

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

1. Введение

Криптографические протоколы, одновременно удовлетворяющие высоким требованиям эффективности и безопасности (как компонуемая безопасность), недостаточны. Одной из последних тенденций в этой области является использование потенциала аппаратных компонентов: таких как карточки с образцами подписи [1], одноразовые программы [2], стандартные смарт-карты [3], или даже более сложные ключи [4]. Большинство из этих протоколов аппаратной поддержки в действительности приводит к безопасности в структуре универсального состава (UC) Канетти [5] и таким образом обеспечивают высокие гарантии безопасности.

1.1 Физически неклонируемые функции

В этой статье мы рассмотрим другой тип аппаратного компонента, который в последнее время получил большую известность из-за высокого уровня их реализации: Физические неклонируемые функции (PUFs) [6],[7]. В основном, PUF – шумное устройство получается в ходе физически сложного производственного процесса, такого что поведение PUF сложно поддается анализу и копированию. Сам PUF может быть оценен как физический сигнал (иначе запрос), на который он обеспечивает шумный ответ. Моделирование PUFs соответственно является весьма нетривиальной задачей. Самое главное, что есть различные виды PUFs с вариативными (физическими) свойствами. Кроме того, кажется, нет главного соглашения по общей безопасности свойств PUFs, даже для единственного типа (например, односторонний ли PUF или нет, или если выходное значение псевдослучайно). [8] [9] для получения дополнительной информации. Таким образом, мы рассмотрим очень минималистичную модель, которая в основном говорит, что только сторона во владении PUF может оценить его, послав некоторый сигнал для PUF и наблюдая результат, и где изучение выходных значений для некоторых сигналов не облегчает задачу определения выходного значения функции для других сигналов. Было несколько подходов к определению PUFs криптографически, посмотрите [10], [11] [12], [13], [14] . Однако эти определения обычно либо неформальные, или основаны на более строгом игровом подходе , но предусматривают неклонируемость и защиту от несанкционированного доступа в качестве внешнего свойства « вне игры». Недавнее исключение - работа Armknecht и др. [15], которая обеспечивает основанные на игровом подходе определения для неклонируемости на физическом уровне. В мире UC, такие особенности более удобно сформулировать. Мы, прослеживая предыдущие подходы для других символьнозависимых протоколов к модели PUFs формально в структуре UC, выявляя несколько особенностей для этого вида аппаратного обеспечения.

1.2 PUFs и структура UC

Структура UC. Структура UC легко поддерживает моделирование устойчивых к внешним воздействиям аппаратных ключей через идеальные функции. Грубо говоря, идеальная функциональность захватывает абстрактные свойства безопасности ключа, и он рассматривает гибридную природу, в которой реальные протоколы и партии также имеют доступ к этому идеалу функциональности (то есть ключу). Это - подход, который широко использован в литературе [16],[17], [18] и который мы также используем для моделирования PUFs в структуре UC, в частности для моделирования ограниченного доступа в зависимости от владения ключом или неклонируемостью. В своем первоначальном виде гибридная модель поддерживает декомпозицию криптографических задач на базовые простые блоки и обеспечивает безопасность протоколов, которые составлены из таких стандартных блоков. Грубо говоря, теорема Канетти состоит или фактически является следствием более общего утверждения, что | говорит, если протокол π^F UC – надежно реализует некоторую функциональность G в гибридный мир с эффективной функциональностью F и некоторый протокол Ро UC безопасной реализации F, тогда полученный протокол π в степени F, который включает Ро, зависящее от π будет вызывать F, также UC надежно реализующее G. PUFs в Структуре UC. Наша идеальная функциональность для PUFs обеспечивает только сторону, отправляющую запрос, чтобы получить ответ, тем самым обеспечивая ограниченный доступ. Неклонируемость осуществляется через непредсказуемость. Стороны могут передавать PUF другим сторонам. Во время передачи мы даем злоумышленнику временный доступ прежде чем PUF достигнет получателя. Эти модели являются классическим примером PUF – банковские кредитные карты, отправленные через почтовую службу, которые считываются, прежде чем будут доставлены. Как в других работах на основе аппаратных ключей, мы предполагаем некоторые доказательства несанкционированного доступа в том смысле, что получатель может позже проверить подлинность и целостность PUF. Мы отмечаем, что это не должно быть обеспеченно самой технологией PUF. Можно также рассмотреть надежную доставку (в этом случае у злоумышленника будет доступ только для чтения во время процесса обработки). Наша идеальная функциональность охватывает различные виды технологий PUF и включает даже PUFs с маленьким значением входного или выходного значения (в этом случае непредсказуемость следует понимать относительно небольшого выходного значения). Отметим, что для проектирования безопасных протоколов, промежуточный доступ злоумышленника также требует то, что пространство значения PUF – супер-многочлен; иначе злоумышленник легко может клонировать PUF. Это требование домена может быть в настоящее время неверно для всех видов технологии PUF; мы комментируем это в полной версии статьи. Использование компонентов аппаратных средств в контексте UC, особенно PUFs, все же включают несколько нежелательных побочных эффектов. В первую очередь, не известны полиномиально - простые реализации алгоритма на машине Тьюринга для PUFs, во- вторых, производственный процесс неотъемлемо основан на физических свойствах. Следовательно, в то время как требования к гибридной модели технически нормальные, любая реализация на практике через фактический PUFs оставляет пробел в безопасности составленного протокола, как, строго говоря, теорема композиции только применяется к полиномиально сложным вычислениям функциональностей F. К счастью, Канетти [5] доказывает теорему композиции для более широкого класса интерактивных машин Тьюринга, и мы даем набросок в полной версии этой статьи для PUFs. Невычисляемость PUFs через определение алгоритмов вызывает другую проблему, когда дело доходит до сложных криптографических протоколов. Для любого основанного на PUF протокола, опираясь далее на криптографические предположения, такие как сложно вычисляемые дискретные логарифмы, оценку нужно провести относительно дополнительной вычислительной мощности через PUFs. Таким образом, данную проблему трудно будет решить даже для злоумышленников с «более, чем полиномиальной вычислительной мощностью ". Поэтому выгодно для того, чтобы избежать дополнительных криптографических предположений в протоколах и предоставлены решения со статистической безопасностью. Непрограммируемость. Для PUFs другой аспект - внутренняя непрограммируемость этих ключей:даже изготовитель обычно не имеет никакого контроля над функциональным поведением PUF. Следовательно, появление возможности построения абстрактной модели PUF через идеальную функциональность в гибридном исполнении, представляется нам оптимистичным. Аналогичное наблюдение было сделано Нильсеном [19] о непрограммируемости случайных оракулов в структуре UC. Грубо говоря, Нильсен устраняет возможность симулятора программировать случайное оракул, предоставляя окружающей среде прямой доступ к случайному оракулу. Поддерживая аргумент в пользу непрограммируемого PUFs, мы также отмечаем это для случайных оракулов прямо к программе, последовательно даем частичный обзор функции для других значений, обеспечивая независимые случайные значения; для PUFs это менее ясно, так как нужно было бы взять (не обязательно эффективный), условное распределение специальной PUF. Мы принимаем подход Нильсена и увеличиваем способность окружающей среды, давая также доступ к конкретному экземпляру PUF, используемому в протоколе. В отличие от этого общедоступного случайного оракула, тем не менее, окружающая среда может только получить доступ к этому PUF, когда им обладает злоумышленник, т.е., мы принимаем то, что PUF могут быть доступны только этому пользователю. Это соответствует честному пользователю, который предотвращает дальнейший несанкционированный доступ. В более сильной версии можно было также позволить дальнейшее неконтролируемое взаимодействие между окружающей средой, т.е., другими протоколами и PUF, даже во владении честного пользователя. Это каким- то образом соответствовало бы постоянно разделенной функциональности PUF в модели [20] GUC. Однако многие преимущества развертывания PUFs для проектирования эффективных протоколов затем исчезают.

1.3 Основанные на PUF протоколы в структуре UC

Мы наконец иллюстрируем удобство использования нашей PUF модели, представляя базовые протоколы PUF для трех классических областей: временная передача (OT), загрузка, и обмен ключами. Наши протоколы - UC-безопасные в гибридном мире (где мы предоставляем доступ окружающей среды к экземпляру PUF, как описано выше), и как правило, требуется только нескольких операций кроме оценок PUF. В частности все протоколы требуют только отправки одной стороне ключа на первой стадии. Протоколы не следует делать на дополнительных криптографических предположениях, за исключением прошедших проверку каналов. Проектирование протоколов на основе PUF не является просто вопросом принятия других ключей. Несомненно, одной из причин является свойство непрограммируемости, которая как правило не предусматривается для других ключей . На самом деле большинство протоколов используют в своих интересах возможность сходу адаптировать выводимые лексемы. Но что еще важно, главная разница между PUFs и другими символами, что PUFs по своей природе непредсказуемы даже для разработчика. Из этого следует, что только у стороны во владении PUF есть полный доступ к тайнам; другие стороны могут только вывести из небольшого набора ранее выбранные дискретные значения. Для сравнения, для обертки маркеры, например, разработчик еще знает программу, помещенную внутри маркера и лексемы владельца может полностью получить доступ к этой программе по пути в черный ящик. Следовательно, обе стороны так или иначе имеют полное представление о тайне. Для PUFs ситуация пожалуй «ассиметрична». Наш протокол передачи имеет некоторое сходство с протоколом PUF на основе протокола Ruhrmair [21]. Его протокол, однако, имеет высокую сложность, обусловленную различным шагом хеширования. Тем не менее, указывает на то, что используя симметрию передачи [22] в том смысле, что можно изменить роли отправителя и получателя, одна сторона получает протокол передачи, в который другая сторона посылает PUF. Мы подтверждаем, что эта симметрия имеет место и в установке UC. Проектирование UC-безопасной схемы обязательств с помощью наших PUFs оборотов будет довольно сложным. Непрограммируемость наших PUFs тормозит свойство, позволяющее соответственно адаптировать совершенные значения и которые обычно требуются для загрузки [23]. Поэтому мы используем основанный на PUF наш протокол передачи , чтобы получить UC-безопасную схему загрузки. Интересно, в то время как стандартная конструкция схемы загрузки [24] использует методы сокращения передачи с линейным числом передачи, наше преобразование не добавляет никаких значительных накладных расходов. Необходимо только одно выполнение протокола OT и одно дополнительное сообщение. Мы были не в состоянии проследить эту идею в другой предыдущей работе. Примечательный аспект, что это в то время, как наш ОТ-протокол только противостоит статическим искажениям, наша полученная схема загрузки безопасна в наличии адаптивных искажений. Причина состоит в том, что для загрузки, в отличие от OT, адресат не получает любой внешний вход; значения, используемые в подпротоколе, выбраны внутри. Это облегчает моделирование со стороны получателя. Следовательно, если мы используем наше преобразование, мы получаем адаптивно безопасный протокол загрузки от статически безопасного ОТ- протокола! Наконец, наш протокол ключевого обмена придерживается традиционного подхода использования PUF для транспортировки ключа, так как наш протокол заявлен и оформлен в структуре UC. Таким образом, отправитель пробует некоторые пары проблемы/ответа, посылает PUF, и потом показывает вызов к получателю, который восстанавливает изображение с помощью PUF. Обе стороны используют изображения в качестве ключа, после применения нечеткого установщика для устранения ошибки и коррекции результата. Понятно, что для протокола ключевого обмена, где только одна сторона посылает PUF, требуется некоторый дополнительный, односторонний механизм идентификации. Иначе злоумышленник с временного доступа к PUF мог исполнить роль законного адресанта. Все наши протоколы позволяют снова использовать PUF для нескольких исполнений. По непредсказуемому характеру PUFs, однако, ясно, что число исполнений должно быть заранее известно сторонам: отправитель, однажды посылавший PUF, не может больше получить доступ к PUF и должен, таким образом, послать вызов PUF прежде достаточно часто, если PUF часто не обменивается или далее Символы PUF посылают. Отметьте, что в этом случае, нападения , описанные в [25] будут также защищены доказательством безопасности. Интересной особенностью является то, что PUFs в отличие от других ключей аппаратных средств, используют протоколы PUFs, автоматически защищенные от повторных атак, потому что они осуществляют (зашумляющие) функции.

2 Физически Неклонируемые Функции

Физически Неклонируемые Функции (PUF) - источник хаотичности, которая реализуется с помощью физической системы.Грубо говоря, хаотичность PUFs зависит от неконтролируемых производственных отклонений во время их изготовления. Для оценки PUF, физическая система запрашивает причины, обычно называемые проблемой. Затем устройство производит физический результат, которая обычно называют как ответ. Пару входа и выхода называют проблемой/ответом (CRP). Кроме того,PUF, будучи физической системой, не обязательно осуществляет математическую функцию, т.е., дважды запрашивая PUF на ту же проблему может дать различные ответы. Тем не менее, мы требуем, чтобы такой \шум" был ограничен так, чтобы эти два ответа были тесно связаны с точки зрения расстояния.

2.1 Определение PUF

PUF-семья состоит из двух (не обязательно эффективных) алгоритмов примеров и оценки. Индекс выбранного образца алгоритма, который получает в качестве вводных данных безопасный параметр и ответы в качестве выходного индекса идентификатора семьи PUF в процессе изготовленияPUF. Алгоритм оценки берет в качестве ввода вызова c, оценивает PUF по c и создает на выходе соответствующий ответ r. Обратите внимание на то, что нам требуется вызов пространства, равного полному набору строк определенной длины. Для некоторых классов PUF этого естественно достаточно, например, арбитр PUF и SRAM PUF. Для других типов это может быть достигнуто с помощью необходимого кодирования, как с точки зрения оптического PUF.

Определение 1 (Физически Неклонируемые Функции). Пусть указывает размерность диапазона PUF- ответов PUF-семьи, и пусть dnoise быть привязанный шум PUF. Пара представляет собой семейство (rg; dnoise) - PUF, если это удовлетворяет следующие свойства:
Выборка индекса Пусть I_ λ будет набором индекса. Алгоритм выборки Образца выходов на входе параметра безопасности 1, an index id I_ λ.. Мы не требуем, чтобы выборка индекса была сделана эффективно. Каждый id 2 индекса I соответствует набору распределений. Для каждого c принадлежащего {0,1} в степени λ; Did содержит распределение, Did (c) на f0; 1grg (). Мы не требуем, чтобы это Did имело краткий вид или эффективный алгоритм.
Оценка Оценка алгоритма Eval получает в качестве входа кортеж (1; id; c), где c принадлежит{0,1} в степени λ. Он выдает ответ r принадлежит{0,1} в степени rg от λ. согласно распределению Did(c). Не требуется, чтобы Eval был алгоритмом PPT.
Ограничение шума Для всех индексов ID из I, для всех вызовов C принадлежит{0,1} в степени лямбда. мы имеем, что при работе Eval (1 в степени λ; id; c) дважды, затем расстояние Хэмминга любых двух выходов R1, R2 алгоритма меньшего, чем dnoise (λ).

Вместо Did (с), мы обычно пишем PUF id (с). Кроме того, если недоразумения маловероятны, мы записываем D (с) вместо Did (с) и PUF вместо PUF id. Наконец, мы обычно пишем RG вместо RG (λ), И я вместо I_ λ.

2.2 Безопасность PUF

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

Теперь обратимся к нашему основному свойству для безопасности PUF, а именно, непредсказуемости. Поведение PUFна входе вызова c должно быть непредсказуемым, т.е., имеется некоторое количество знаков внутренней энтропии, даже если PUF был вычислен до того, как некоторые значения изменились. Здесь (условно) минимальная энтропия - главный инструмент. Это достигается индикацией остаточной минимальной энтропии с минимальным значением для вызова c, когда уже измерили PUF на (не обязательно различный), до вызова c_1, …,c_l. Поскольку случайные ответы находятся не под контролем, мы можем смотреть на остаточную энтропию для ответа на r, выбрав среднее число по всем возможным значениям r_1,…, r_l. Требование, чтобы имеет определенная средняя минимальную энтропию [26], слабее, чем все запрашиваемые возможные ответы , что остаточная энтропия остается выше определенного уровня. Это требование удовлетворяет нашим целям. Так как вызовы c выбраны злоумышленником, мы хотим видеть среднюю минимальную энтропию высокой для всех вызовов и определяем по максимально вероятному возможному ответу .

Определение 2 (Средняя минимальная энтропия) Средняя мин энтропия отвечающего стандарту измерения проблемы C = (c_1,...,c_l) определение

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности) превысило время ожидания от «http://mathoid.bmstu.cloud:10042/»): \tilde{H}_{∞}(PUF(c))|(PUF(c))<\math> ~H 1(PUF(c)jPUF(C)) := 􀀀log _ Eri PUF(ci) h max r Pr[PUF(c) = rjr1 = PUF(c1); : : : ; r` = PUF(c`)] i_ := 􀀀log _ Eri PUF(ci) h 2􀀀H1(PUF(c)jr1=PUF(c1);:::;r`=PUF(c`)) i_ ; где вероятность взята по выбору id от I и выбору возможные ответы PUF на вызов c. Термин PUF (C) обозначает последовательность из случайных переменных PUF (c1), …, PUF (c') каждое соответствие оценке PUF для вызова Сk. Мы иногда также пишем H∞ (PUF (c) /C) как сокращение для H1∞ (PUF (c) / PUF (C)). Мы теперь перейдем к нашему определению непредсказуемости, которое получено из понятия непредсказуемости для случайных переменных.  :: '''Определение 3 (Непредсказуемость)''' <math> A (rg; dnoise)-PUF - семья P = (Sample; Eval) для безопасного параметра 1_ is (dmin(_);m(_))-unpredictable if for any c 2 f0; 1g_ and any challenge list C = (c1; : : : ; c`), one has that, if for all 1 _ k _ l the Hamming distance satis_es disham(c; ck) _ dmin(_), then the average min-entropy satis_es ~. Которая a PUF-семья называется - семья


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

2.3 PUF и Нечеткие Экстракторы

По своей природе PUF признается шумной такой, что те же самые запросы выдают различные результаты. Мы используем нечеткие экстракторы Dodis и др. [26], чтобы преобразовать шум, измерения высокой энтропии PUF в воспроизводимых случайных величинах.(m; l; t; ε) - нечеткий экстрактор состоит из пары алгоритмов . Алгоритм генерации Gen принимает в качестве ввода измерений шума w и производит выход l- разрядный ключ st вместе с вспомогательными данными p. Вспомогательные данные помощника могут храниться открыто, так как это не раскрывает информацию о тайне:до тех пор измерение содержит m биты минимальной энтропии, секрет имеет статистический расстояние эпсилон до однородного распределения, даже если известно p. Вспомогательные данные помощника позже используются для воспроизведения того же секрета st от связанных измерений в пределах определенного расстояние t в некотором метрическом пространстве. Теперь определяем параметры совместимости PUF и нечеткого экстрактора, чтобы добиться почти равномерно случайных значений. Мы задаем параметры нечеткого экстрактора, зависящих от параметров PUF. Предположим, что мы имеем (rg (); dnoise (); dmin (); m ())-PUF семья с dmin сложности o (λ/log(λ)). Определяем соответствующие параметры для нечеткого экстрактора следующим образом. Пусть l(λ): = λ - длина параметра для значения st. Пусть ε( λ) – пренебрежимо малая функция и пусть t ( λ ) = dnoise (λ ). Для каждого λ, пусть (Gen; Rep) будет a(m (λ); l(λ); t (λ); ε(λ)) - нечеткий экстрактор. Метрическое пространство M является гранью размерности rg (λ) с расстоянием по Хэммингу DISham.

Определение 4. Если PUF и нечеткий экстрактор удовлетворяют вышеупомянутым требованиям, тогда у них есть cоответствие параметрам.Если у PUF и нечеткого экстрактора есть соответствующие параметры, то следующие свойства широко распространенного домена, независимости извлечения и последовательного ответа выполняются.
Широко Распространенная Область Для всех полиномиальных p (λ) и всех наборов вызовов c1, … , Cp (λ), вероятность для случайного вызова с расстоянием меньшим dmin для любого из Сk крайне мала.
Независимость извлечения Для всех вызовов c1, … , Cp (λ), это означает, что оценка PUF для вызова c с dis(ck, c) > dmin для всех 1<= k <= p (λ) и последующее применение Gen дает почти равномерное значение е, даже для тех, кто просматривает р.
Последовательность Ответа Карта нечетких экстракторов содержит два значения того же самого PUF к той же самой случайной последовательности, т.е., если PUF измерена дважды для вызова c и ответы r и r’, затем для (st, p)  Gen(r), у каждого есть st Rep (r’, p).


3 Универсальная структура безопасности и PUF

Мы моделируем PUF в универсальной структуре состава, введенной Канетти. Обратите внимание, что мы используем, помимо прочего, хорошо изученные основы UC, такие как проверка подлинности передачи сообщений.

3.1 Моделирование PUF в UC

В дальнейшем мы предлагаем идеальную функциональность FPUF, которая будет моделировать PUF. Функциональность представлена в рисунке 1 и выполняет следующие операции: (1) сторона Pi находится в PUF; (2) Pi может запросить PUF; (3) Pi , которая дает PUF доступ к Pj, который может также запрашивать устройство; (4) злоумышленник может запросить PUF во время передачи. Функциональность FPUF поддерживает список L кортежей (sid; Pi; id; тау), где sid (открытая) сессия идентификатора, и id - (внутренний)PUF - идентификатор , который является описанием распределения выхода. Обратите внимание на то, что сама PUF не использует sid. Элемент тау из {trans (Pj); notrans} обозначает, является ли PUF в переходе к Pj. Для trans( Pj ), указывая, что PUF находится в переходе к Pj, злоумышленник в состоянии запросить PUF. В свою очередь, если это установлено в notrans тогда только владеющая сторона может запросить PUF. PUF- функциональность FPUF индексируетPUF- параметры (rg; dnoise; dmin; m) и получает параметр безопасности λв бинарном кодировании в качестве дополнительного входа. Это требуется для того, чтобы удовлетворить свойство ограничения шума для dnoise (λ) и свойство непредсказуемости для (dmin (λ); m (λ)). Это доказывает, что выходы подчиняются основным требованиям энтропии PUF (аналогично требованиям для случайной оракульной машины, чтобы произвести случайные и независимые выходы). Мы записываем FPUF и FPUF (rg; dnoise; dmin; m) попеременно.

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

3.2 Непрограммируемость

Как пояснили в введении, мы представляем себе непрограммируемую версию PUF. Функциональность выше, если используется стандартным способом в гибридной модели, более программируемой, тем не менее, потому что окружающая среда не будет иметь прямой доступ (даже если PUF в распоряжении злоумышленника). С одной стороны обеспечение непрограммируемости означает переход на расширенную модель UC (EUC) [20] где все стороны, включая окружающую среду, разделяют вышеупомянутую функциональность. PUFмог тогда также быть оценена окружающей средой, когда симулятор сообщил о проблеме и ответе. Для упрощения мы задерживаемся в пределах основной структуры UC и вместо этого позволяем окружающей среде послать специальные вопросы PUF противнику/симулятору. Это запрос нуждается в честном ответе, отправленному к подлинной PUF, и ответ будет возвращен окружающей среде. Иначе, мы поставим некоторое ограничение на то, как ведет себя симулятор, формально давая доказательство UC-безопасности, который будет передан модели EUC.

4 Забывающий Трансфер с PUF

В 1-ом , 2-ом протоколах забывающей передачи (OT) отправитель имеет два секрета s0; s1 и приемник имеет выбор бит b 2 {0,1}^г, тем самым выбирая один из эти двух секретов. 1-из- 2 OT-протоколов гарантирует выполнение в конце протокола, приемник не узнает секретный sb, но ничто о s1 ?? b, и отправитель не узнает ничего о выборе bit b.

Забывающая Передача - широко используемый криптографический примитив для многих криптографических приложений [22,9,13]. Однако во многих из этих применений узким местом OT являются вычислительные требования, поскольку, например, необходимы нескольким общественным ключевым операциям. Мы здесь показываем, как избежать ряд общественных ключевых операций по принятию аппаратных средств. В дальнейшем мы вспоминаем забывающий трансфер идеальной функциональности и затем предоставляем основанный на PUF забывающий протокол передачи. Как отмечено в введении, мы представляем сценарий, в который PUF используется многократно. В простой модели UC, однако, был бы новый PUF должен быть направлен для каждого выполнения OT. Альтернатива должно быть переключение на теорему совместной структуры (JUC) [8] для рамках UC. Однако JUC применяет a переход к оригинальному протоколу, и если один сеанс протокола PUF требует передать PUF один раз, преобразование JUC также потребует передачу за сеанс. Ничего не будет получено. Таким образом мы определяем и анализируем протоколы мультисессии вместо более распространенных протоколов одной сессией.

4.1 Забывающий Трансфер Идеальная Функциональность

1 –из -2 забывающих передач взаимодействие между отправителем π и управляющим Pj, где окружающая среда Z предоставляет Пи два входа s0; s1 и Pj с вход бит b. Как только обе стороны обеспечили свои входы (и симулятор S позволяет доставку), идеальная функциональность возвращает секретную sb приемнику. Идеальная функциональность для забывающей передачи FOT дана в рисунке 2. Мы подчеркиваем, что эта функциональность поддерживается статическим искажением и может использоваться ограниченное количество раз, и только сторонами, обменивающимися с PUF. Каждое выполнение будет сопровождаться уникальной sub сессией идентификатора ssid.


4.2 Забывающая схема передачи

На рисунке 3 мы представляем забывающий протокол передачи. Для простоты изложения, , мы используем следующие обозначения. Для возможно пустого набора C мы даем (c; C)> dmin, обозначающий проверку, где каждый элемент ci в C удовлетворяет es (c; ci)> dmin. В противном случае мы предполагаем, что соответствующая сторона прерывается. Кроме того, взаимодействуя с PUF (функциональность), мы просто пишем, например, r (evalPUF; sid0; π; c) обозначая факт что, для вызова (evalPUF; sid0; π; c) функциональность ответила с (eval0edPUF; sid0; c; r). Здесь, sid0 – сессия идентификатора для FPUF, в отличии от sid и ssid для протокола забывающей передачи. Мы отмечаем, что протокол не достигает идеальной завершенности в смысле то, что исполнение между честными сторонами может потерпеть неудачу. Хотя вероятность этого незначительна. Это непосредственно следует из факта, что домен очень распространен: Все (в большинстве полиномиальные) проблемы являются независимыми случайными величинами так, что каждый находится в пределах небольшого расстояния от других с пренебрежительно малой вероятностью. Если все проблемы – достаточно обособлены друг от друга, приемник всегда получает правильное значение. Теперь мы наметим аргументы безопасности для OT-протокола на рисунке 3, т.е., в конце протокола (1) OT злоумышленник ничего не узнает о бите b и (2) злонамеренный получатель узнает только секрет sb и не обратит внимание на s1b. Для случая (1), получатель выберет вызов c наугад. Таким образом, v = c xb скрывает xb информацию теоретически и таким образом также b. Рассмотрим теперь случай (2). Для простоты предположим, что b = 0. Затем отправитель должен не обращать внимание на любую информации о s1. Если st1 выглядит в форме отправителя, то s1 теоретически информационным образом скрыт. Если нечеткий экстрактор и PUF имеют параметры соответствия (см. Определение 4), затем с подавляющей вероятностью это, как очень распространенной собственности домена (см. Подраздел 2.3), | вероятность, что получатель подвергнет сомнению PUF на значения ck с disham (ck; v x1) <dmin незначителен и проверяет отправителя в списке l,при условии, что отправитель не показывает ответы PUF на критические проблемы.


Теорема 1. Принятие этого - нечеткий генератор и это PUF = (Образец; Оценка), PUF- семья с соответствующими параметрами (см. Определение 4), затем протокол PUF OT надежно реализует функциональность FOT в FPUF- гибридная модель.Безопасность держится в статистическом смысле, то есть взгляды с двух сторон статистически близки. Это остается верным для неограниченных алгоритмов A; S, и Z, при условии, что количество оценок PUF ограничено. Доказательство представлено в полной версии статьи.
TemplateTheoremIcon.svg Теорема Теорема 1
Если схема подписи детерминирована и строго конфиденциальна, а также схема шифрования IND-CCA2 безопасна, тогда схема шифрования и подписи конфиденциальна в высоко-энтропийной модели. Практически, если существует атакующий А, против высоко-энтропийной безопасности схемы шифрования и подписи, тогда существуют атакующие против IND-CCA2 безопасности схемы шифрования и строгой конфиденциальности схемы подписи, такой как

, где время выполнения равняется одному из А плюс

.
Доказательство
Безопасность этой схемы может быть доказана схоже с теоремами состава шифрования/подписи, доказанных Аном.


4.3 Рассеянная передача с отправителя PUF

Наш OT-протокол требует, чтобы получатель послал PUF отправителю. Иногда может быть желательно, чтобы отправитель подготовил PUF. Это может быть достигнуто путем переключая роли отправителя и получателя через протокол Wolf и Wullschleger [32], но за счет линейного многих OT- выполнений для длины строк. Это неизбежно так, как получатель в OT-протокол просто входит биты таким образом, что, действуя как отправитель, он может передать только один бит. В этом протоколе отправитель внешнего OT-протокола как получатель во внутреннем OT-протоколе, при этом посылая PUF.

Протокол в [32] требует только одного раунда дополнительной связи. Это - UC- безопасный в FOT-гибридном мире и наследует свойства безопасности (статистической против вычислительной безопасности и адаптивный против статических искажений). С линейного и другого дополнительного раунда связи каждый может получить OT-протокол для строк, который является также UC- безопасным в FOT-гибридном мире для битовой функциональности FOT. Окончательный протокол - теперь OT-протокол UC- безопасности для последовательностей с линейным множеством вызовов для FOT, несколько дополнительных раундов, и наследуются все характеристики безопасности от FOT.

5 Схема Обязательства, основанная на PUF

Схема обязательства – двухсторонний протокол между отправителем и получателем, где отправитель (также называемый субъект) первый посылает зашифрованную версию значения получателю, таким образом, что, позже, только это значение может быть обнаружено. Более того, схема обязательства позволяет субъекту вычислять значение сообщение пары (com; decom) таким образом, что com ничего не показывает о сообщении стоимости, но с использованием пары (com; decom) можно открыть сообщение. Кроме того, невозможно найти значение decom0 таким образом, что (com; decom0), показывает msg0 6= msg..

5.1 Схема Обязательства Идеальной Функциональности

В мире UC схема обязательства реализуется понята (ограниченной) функциональностью Fcom следующим образом: Fcom получает входной сигнал (передача; sid; ssid; msg) от некоторого субъекта Pi, где сообщение – величина msg. После подтверждения срока действия сессии идентификатора sid, Fcom делает запись значения msg. Впоследствии, функциональность позволяет и приемнику Pj и получателю S передать некоторые значения, вычислив открытый выход (приход; sid; ssid) и отправка его к Pj (этот этап называют фазой обязательства). Чтобы начать фазу необязательства, субъект Pi посылает (открытый; sid; ssid) к функциональности Fcom. Вслед за этим Fcom проверяет, существует ли значение сообщения; если так, то функциональность вычисляет открытую задержку выхода (открытый; sid; ssid; сообщение) и посылает его в Pj. Когда злоумышленник искажает субъекта, посылая (искаженный субъект; sid; ssid) к Fcom, функциональность показывает записанное сообщение злоумышленнику S. Кроме того, если значение получения не была доставлено Pj, то Fcom позволяет злоумышленнику изменить зафиксированное значение. Это делается для того, чтобы иметь дело с адаптивной искажением. Идеальная функциональность для схем Fcom обязательства даны в рисунке 4.

5.2 Схема обязательства, основанная на PUF

Мы теперь представляем универсальный переход от OT-протоколов к битовым передающим схемам , которые нам хорошо знакомы, не были рассмотрены до сих пор. Предыдущий преобразования зависят от сокращения и выбора и требуют много исполненных OT-протоколов. Наше преобразование только требует одно дополнительное сообщение, которое будет отправлено после выполнения OT-протокола. Основная идея протокола на рисунке 5 показывает противоположные роли отправителя и получателя. OT-протокол передает два секрета, и субъект изучается только на одном из них, а именно на том, который соответствует его секрету битовой b. Эта секрет затем используется для открытия обязательства. Основная задача – поменять роли отправителя и получателя. Протокол обязательства использует OT-протокол в качестве основного блока так, как мы работаем в структуре UC, соответствующей идеальной OT-функциональности. Рассмотрим схему обязательства с OT-отправителем Pi и OT-получателем Pj. Затем Pj субъект, имеющий секретный битный b, который он представляет в OT-функциональности. Получатель Pj создает две достаточно длинные случайные последовательности s0 и s1, которые подчиняется OT-функциональности. OT-функциональность затем предоставляет Pj с секретом sb. Это завершает фазу обязательства. В начальной фазе субъект Pj посылает пару (b;sb). Получатель Pi затем проверяет, соответствует ли секретsb b-th секрету. Протокол является обязательным так , как OT-функциональность не позволяет изменять секретный бит b и секретный s1 b статистически скрыт от Pi. Таким образом Pi может определить s1 b только с незначительной вероятностью. Протокол скрывает, поскольку OT-функциональность не показывает информация о битовой b от Pi.

Теорема 2. Протокол обязательства в рисунке 5 надежно UC реализует функциональность Fcom в FOT-гибридной модели.

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

Мы просто предоставляем эскиз доказательства для Теоремы 2. Обратите внимание, что в случае, где оба пользователя подлинны, только моделирование последних сообщения быть учтены. Тренажер узнает секрет битный b от функциональность обязательства Fcom. Затем составляет произвольную строку v из {0,1}g_ и посылает (sendauth; sid; ssid; b; v). Если получатель не подлинный, то он обеспечивает FOT с секретной битовой b s0; s1. Тренажер позволяет отправителю обеспечить случайный битb0 в моделируемой FOT. Это получает обратно секретный sb0. В начальной стадии, S узнает, что (реальный) секретный битный b от обязательств функциональности и моделирует последнее сообщение протокола как (sendauth; sid; ssid; b; sb). Симулятор создает две случайные строки s0; s1 и передает их в моделируемою FOT, которая передает sb получателю. Симулятор передает бит отправителя b в идеальном виде. Если отправитель посылает сообщение (sendauth; sid; ssid; b; v) тогда S проверяет если sb = v. Если так, это информирует Fcom открыть обязательство. Все моделирования являются совершенными.

5.3 Адаптивно безопасные обязательства

Рассмотрите конкретный протокол обязательства, где мы включаем наш OT-протокол от предыдущей секции в абстрактную схему выше (и работа в FPUF- гибридная модель вместо FOT-гибридной модели), то мы наблюдаем следующее: В фазе обязательств (т.е., OT-фазе), сообщение, посланное OT-получателю (совершение передачи) статистически независимо от его секретного ввода данных: OT-получатель просто посылает единственное случайное сообщение. Для OT-отправителя, дело обстоит не так: имея доступ к PUF, один может извлечь обе тайны из простой расшифровки стенограммы протокола. Это позволяет симулятору S получить оба секрета из расшифровки протокола, поскольку имеется доступ к PUF. Таким образом, можно обеспечить подделку с открытых сообщений также битных значений. Поскольку остальная часть объекта просто состоит в паре вызов/ответ, симулятор может таким образом обеспечить подлинность внутренней структуры.

6 Обмен ключами с PUF

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

6.1 Обмен ключами идеальной Функциональности

Главная идея обмена ключами идеальной функциональности Fke заключается в следующем: если обе стороны подлинные, функциональность предоставляет им общие случайные значения, которые невидимы для злоумышленника. Если один из них поврежден, тем не менее, противник полностью определяет ключ сеанса , таким образом моделирование участия от поврежденной стороны. Определение обмена ключами функциональности Fke изображено на рисунке 6 [27].

6.2 Минимальные требования

Мы представляем протокол обмена ключами Разделе 6.3, который посылает PUF в установочной фазе. Впоследствии, одно сообщение о выполнении протокола передается через однонаправленный удостоверенный канал. Как упомянуто во введении, желательно обойдите использование теоретически сложных предположений. Однако по практическим соображениям, передачи PUF должны быть сведены к минимуму. Если происходит только одна PUF передача, тогда предположение об однонаправленном заверенном канале проверки не может будь пропущено: отправитель PUFнесколько раз измерил PUF и послал его получателю. Злоумышленник может запросить PUF в период его перехода. Если у отправителя нет никакой секретной информации для идентификации, тогда злоумышленник может выполнить те же самые вычисления как отправитель. Таким образом, протокол не может быть безопасным против нападений перевоплощения. В дальнейшем, мы используем стандартную двунаправленную функциональность Fauth. Соответствующее получение однонаправленный определений просто.

6.3 PUF, основанная на ключевой схем обмена

Интуитивно, наш протокол обмена ключами происходит следующим образом. В фазе регистрации сервер выдает PUF, измерения для ряда соответствующих ответов случайно выбранных задач и наконец гарантируют бесшумное измерение PUF путем создания для каждого ответа r нечеткого секрета экстрактора st из набора случайных секретов, а также соответствующие данные помощника p. Сервер посылает PUFклиенту. По чистовой регистрация поэтапно осуществляют передача сервером a случайно выбранного вызова c включая вспомогательные данные p клиенту и наборам k = st , чтобы получить ключ протокола. Клиент оценивает PUF на вызов c, вычисляет соответствующую нечеткий секрет st , благодаря вспомогательным данным p, и получает ключ протокола, устанавливая = st. Следовательно, обе стороны используют нечеткий секрет экстрактора st, как их общий ключ протокола. Мы снова отмечаем, что отправитель информируется о моменте времени, когда приемник находится в распоряжении PUF.

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

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

Мы благодарим анонимных рецензентов за полезные комментарии. Марк Фишлин поддержан Программой Эмми Нётер Fi 940/2-1 Немецкого Исследовательский Фонда (DFG). Эта работа была поддержана CASED (http://www .cased.de).

Литература

  1. Columbia University
  2. Google Inc
  3. NEC Japan
  4. Columbia University
  1. Dennis Hofheinz, Dominique Unruh, and J¨orn M¨uller-Quade. Universally composable zero-knowledge arguments and commitments from signature cards. Tatra Mt. Math. Pub., pages 93–103, 2007.
  2. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. One-time programs. In CRYPTO, volume 5157 of LNCS, pages 39–56. Springer, 2008.
  3. Carmit Hazay and Yehuda Lindell. Constructions of truly practical secure protocols using standard smartcards. In ACM CCS, pages 491–500. ACM, 2008.
  4. Jonathan Katz. Universally composable multi-party computation using tamperproof hardware. In EUROCRYPT, volume 4515 of LNCS, pages 115–128. Springer, 2007.
  5. 5,0 5,1 Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In FOCS, pages 136–145, 2001.
  6. R. Pappu, B. Recht, J. Taylor, and N. Gershenfeld. Physical one-way functions.Science, 297:2026–2030, 2002.
  7. Ravikanth Srinivasa Pappu. Physical One-Way Functions. Phd thesis, Massachusetts Institut of Technology, 2001.
  8. Roel Maes and Ingrid Verbauwhede. Physically Unclonable Functions: a Study on the State of the Art and Future Research Directions, section 1. Towards HardwareIntrinsic Security. Springer, 2010.
  9. Ulrich Rührmair, Jan Sölter, and Frank Sehnke. On the foundations of physical unclonable functions. Cryptology ePrint Archive, Report 2009/277, 2009.
  10. Frederik Armknecht, Roel Maes, Ahmad-Reza Sadeghi, Berk Sunar, and Pim Tuyls. Memory leakage-resilient encryption based on physically unclonable functions. In ASIACRYPT, volume 5912 of LNCS, pages 685–702. Springer, 2009.
  11. Keith B. Frikken, Marina Blanton, and Mikhail J. Atallah. Robust authentication using physically unclonable functions. In ISC, volume 5735 of LNCS, pages 262–277. Springer, 2009.
  12. Blaise Gassend, Marten van Dijk, Dwaine E. Clarke, Emina Torlak, Srinivas Devadas, and Pim Tuyls. Controlled physical random functions and applications. ACM Trans. Inf. Syst. Secur., 10(4), 2008.
  13. Ahmad-Reza Sadeghi, Ivan Visconti, and Christian Wachsmann. Enhancing RFID Security and Privacy by Physically Unclonable Functions. Towards HardwareIntrinsic Security. Springer, 2010.
  14. Jorge Guajardo, Sandeep S. Kumar, Geert-Jan Schrijen, and Pim Tuyls. Fpga intrinsic pufs and their use for ip protection. In CHES, pages 63–80. Springer,2007.
  15. Frederik Armknecht, Roel Maes, Ahmad-Reza Sadeghi, Francois-Xavier Standaert,and Christian Wachsmann. A formal foundation for the security features of physical functions. To appear at IEEE S&P, 2011.
  16. Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, and Amit Sahai. Interactive locking, zero-knowledge pcps, and unconditional cryptography. In CRYPTO, volume 6223 of LNCS, pages 173–190. Springer, 2010.
  17. Vipul Goyal, Yuval Ishai, Amit Sahai, Ramarathnam Venkatesan, and Akshay Wadia. Founding cryptography on tamper-proof hardware tokens. In TCC, volume 5978 of LNCS, pages 308–326. Springer, 2010.
  18. Tal Moran and Gil Segev. David and goliath commitments: Uc computation for asymmetric parties using tamper-roof hardware. In EUROCRYPT, volume 4965 of LNCS, pages 527–544. Springer, 2008.
  19. Jesper Buus Nielsen. Separating random oracle proofs from complexity theoretic proofs: The non-committing encryption case. In CRYPTO, volume 2442 of LNCS,pages 111–126. Springer, 2002.
  20. 20,0 20,1 Ran Canetti, Yevgeniy Dodis, Rafael Pass, and Shabsi Walfish. Universally composable security with global setup. In TCC, volume 4392 of LNCS, pages 61–85. Springer, 2007.
  21. .Ulrich R¨uhrmair. Oblivious transfer based on physical unclonable functions. In TRUST, volume 6101 of LNCS, pages 430–440. Springer, 2010.
  22. Stefan Wolf and Jürg Wullschleger. Oblivious transfer is symmetric. In EUROCRYPT, volume 4004 of LNCS, pages 222–232. Springer, 2006.
  23. Ran Canetti and Marc Fischlin. Universally composable commitments. In CRYPTO, volume 2139 of LNCS, pages 19–40. Springer, 2001.
  24. Claude Cr´epeau. Equivalence between two flavours of oblivious transfers. In CRYPTO, volume 293 of LNCS, pages 350–354. Springer, 1987.
  25. Christian Jaeger Ulrich Rührmair and Michael Algasinger. An attack on pufbased session key exchange and a hardware-based countermeasure: Erasable pufs.In Proc. Financial Cryptoghraphy 2011.
  26. 26,0 26,1 Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM J. Comput., 38:97–139, 2008.
  27. Ran Canetti and Hugo Krawczyk. Universally composable notions of key exchange and secure channels. In EUROCRYPT, volume 2332 of LNCS, pages 337– 351.Springer, 2002