Устойчивое к утечкам шифрование Эль-Гамаля — различия между версиями

Материал из Национальной библиотеки им. Н. Э. Баумана
(Введение)
(Введение)
Строка 76: Строка 76:
  
 
<b>Домен связи.</b>Домен связи это очень умеренное ограничение.в отличие от радиуса связи, очень трудно представить удаленно реалистчиную атаку по сторонним каналам, которая сломает схему без придерживания ей. Это распределение (как функция утечки математически моделируется) применяется только как аксиома "только вычислительных утечек информации" (которые основаны только на чем-то, что связано с физ свойствами устройства) [40]. Но она также покрывает другие практические атаки, не удовлетворяющие этой аксиоме.Например противник может изучить любую линейную функцию <math>f(S)</math> по всей S (которая разделена, допустим, на две части S<sub>1</sub> S<sub>2</sub>  ) по функция утечки f<sub>1</sub>, f<sub>2</sub> таких, что  <math>f</math><sub>1</sub>(a)+ <math>f</math><sub>2</sub>(b)= <math>f</math>(a,b) .Как аргументировано Dziembowski, это распределение не только покрывает все линейные функции <math>f</math>(a,b) =<math>f</math><sub>1</sub>(a)+ <math>f</math><sub>2</sub>(b),но и любую функцию <math>f</math>(a,b) которая имеет коммуникативную комплексность на всех λ. Реальным примером функции, подходящей под это условие послужит <math>f</math>(a,b)= Σ<sub>i</sub>a<sub>i</sub>*b<sub>i</sub>mod 2 у которой линейная коммуникативная комплексность.
 
<b>Домен связи.</b>Домен связи это очень умеренное ограничение.в отличие от радиуса связи, очень трудно представить удаленно реалистчиную атаку по сторонним каналам, которая сломает схему без придерживания ей. Это распределение (как функция утечки математически моделируется) применяется только как аксиома "только вычислительных утечек информации" (которые основаны только на чем-то, что связано с физ свойствами устройства) [40]. Но она также покрывает другие практические атаки, не удовлетворяющие этой аксиоме.Например противник может изучить любую линейную функцию <math>f(S)</math> по всей S (которая разделена, допустим, на две части S<sub>1</sub> S<sub>2</sub>  ) по функция утечки f<sub>1</sub>, f<sub>2</sub> таких, что  <math>f</math><sub>1</sub>(a)+ <math>f</math><sub>2</sub>(b)= <math>f</math>(a,b) .Как аргументировано Dziembowski, это распределение не только покрывает все линейные функции <math>f</math>(a,b) =<math>f</math><sub>1</sub>(a)+ <math>f</math><sub>2</sub>(b),но и любую функцию <math>f</math>(a,b) которая имеет коммуникативную комплексность на всех λ. Реальным примером функции, подходящей под это условие послужит <math>f</math>(a,b)= Σ<sub>i</sub>a<sub>i</sub>*b<sub>i</sub>mod 2 у которой линейная коммуникативная комплексность.
 +
 +
====Шифрование Эль-Гамаля====
  
 
== Контакты авторов материала ==
 
== Контакты авторов материала ==

Версия 00:22, 23 декабря 2015

Leakage Resilient ElGamal Encryption
Faster Fully Homomorphic Encryptions.png
Авторы Eike Kiltz[@: 1], Krzysztof Pietrzak[@: 2]
Опубликован 2011 г.
Сайт Homepage of Damien Stehle
Перевели Шикунов Юрий Игоревич
Год перевода 2011 г.
Скачать оригинал
Аннотация.Abstract. Blinding is a popular and well-known countermeasure to

protect public-key cryptosystems against side-channel attacks. The high level idea is to randomize an exponentiation in order to prevent multiple measurements of the same operation on different data, as such measurements might allow the adversary to learn the secret exponent. Several variants of blinding have been proposed in the literature, using additive or multiplicative secret-sharing to blind either the base or the exponent. These countermeasures usually aim at preventing particular side-channel attacks (mostly power analysis) and come without any formal security guarantee.

Устойчивое к утечкам шифрование Эль-Гамаля

Эйк Килтз и Кристоф Пьетрзак

Университет Рухра, Бохум, Германия.

Абстрактно. Сокрытие это популярная и хорошо известная контрмера для защиты криптосистем с публичными ключами против атак по сторонним каналам. Идея высокого уровня — рандомизировать экспонентацию для предотвращения множественных измерений одной операции на разных данных, такие измерения могут позволить неприятелю узнать секретную экспоненту. Различные варианты сокрытия изложены в литературе, использующие аддитивные или мультипликативные секреты обмена чтобы сокрыть или базу или экспонету. Контрмеры обычно нацелены на предотвращение конкретных атак по сторонним каналам(по большей части анализ питания) и проходят без формальной защитной гарантии. В этой работе мы исследуем какое расширенное сокрытие может предоставить продвинутую защиту против основных атак по сторонним каналам. Внезапно оказывается, что в контексте дешифровки публичных ключей некоторые техники сокрытия подходят больше, чем другие. В частности мы предлагаем мультипликативную сокрытую версию шифровки публичного ключа Эль-Гамаля, где мы доказываем, что эта схема, подтвержденная более чем на миллионах групп первоначального порядка p(где p-1 не подходит), устойчива к утечкам в модели generic-group. Здесь мы рассматриваем модель избранной-шифротекстовой защиты через присутствие постоянных утечек, то есть схема остается избранно-шифротексто защищенной даже если каждое описание очереди противника может выучить связанное количество(приблизительно log(p)/2 bits) из произвольных, противопоставлено выбранной информации на тему компиляции. Мы предполагаем, что эта схема иллюстрирующая примерами над произвольными группами из главного порядка p( где p-1 не подходит), устойчива к утечкам.

Введение

Атаки по сторонним каналам это криптоаналитические атаки против физических имплементаций против криптосистем которые используют некоторый тип утечек из криптодевайсов во время выполнения. Традиционные меры защищенности(такие как избранная-шифротекстовая безопасность для расшифровывательных систем) не предоставляют никакой гарантии безопасности против таких атак, и многие применения возможности защиты криптосистем были сломаны с помощью атак по сторонним каналам, эксплуатирующие сторонние каналы, такие как: время исполнения [1], электромагнитная радиация [2] [3], потребляемая мощность[38], обнаруживаемые ошибки[8,6] и многие другие[46,43]. Контрмеры против них могут быть на алгоритмическом или аппаратном уровне. В последнем случае в главную очередь пытаются построить устройства способные терять в результате утечек минимально возможное кол-во информации (например через защиту электромагнитной радиации). Алгоритмические контр меры представляют собой разработанные так алгоритмы, что их описание предоставляет защиту против атак по сторонним каналам(например против своевременных атак посредством уверения что время выполнения алгоритма должно оставаться в секрете). Традиционно алгоритмические контрмеры (такие как сокрытие[43] для списках важных документов) по большей части к месту из-за того, что они защищают против специфичных и известных атак.

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

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

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

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

Моделирование Устойчивости К Утечкам. Представим некоторые криптосистемы CS, пусть S0 обозначает начальное состояние и Si - после iго вызова. На iый вызов CS противник выбирает некоторый введенный Xi и получает Yi, где (Si+1, Yi) ← CS(Si,Xi).

В оригинальном значении устойчивости к утечкам противник получает дополнительную силу для выбора, между обычным Xi и некоторой функцией утечки fi, область значений которой принадлежит к некоторому фиксированному λ ∈ N бит с каждого запроса. После iтого запроса она не только получает обычный выходной Yi, но также и утечку Λi ← fi(Si+, R), где R - случайность, которую CS использует во время вычислений и Si+ - подмножество над множеством Si к которому был получен доступ во время вычислений . Обратите внимание, что чтобы быть устойчивым к утчекам, примитив должен иметь состояние(т.е. Si≠Si), так как иначе может утечь множество λ bits за один раз.

В этой статье мы будем использовать более атомарное понятие устойчивости к утечкм, где вызов CS( который будет в дешифровальном запросе) разделен на две фазы, каждая из которых утекает индивидуально. Более важно, вычисление дешифровки может быть синтаксически разделено на две фазы Dec1* и Dec2* , каждая из которых выполняется в последовательном порядке для дешифровки сообщения. При адаптивной атаке на основе шифротекста(CCA), противник может дешифровать запросы с соответствием к шифротексту C и может далее специфицировать две (эффективно вычисляемых) функции утечки, f и g, чья область значений связана ограничена λ бит. В дополнение к дешифровке C противник получает выход f и g примененный ко входу Dec1* и Dec2*, соответственно включая алгоритм внутренних бросков монеты.

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

Радиус связи: f принадлежит к {0, 1}λдля некоторого параметра λ ∈ N.


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


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


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


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


Атака по сторонним каналам использующая малое число битов. Многие атаки по сторонним каналам сначала считают огромное кол-во утечек Λ1, Λ2, . . . из каждого вызова. Затем, во превых, каждая утечка Λi предварительно обрабатывается для того, чтобы извлечь важную информацию Λi (это Λi может, например, быть списком самых подходящих подключей). Атака продолжает пытаться восстановить секретный ключ Λ1, Λ2… . Такие атаки покрываются устойчивость к утечкам тогда, когда кол-во извлеченной информации [Λi] не более суммы утечки λ, к которой получен доступ по время вызова.


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

Домен связи.Домен связи это очень умеренное ограничение.в отличие от радиуса связи, очень трудно представить удаленно реалистчиную атаку по сторонним каналам, которая сломает схему без придерживания ей. Это распределение (как функция утечки математически моделируется) применяется только как аксиома "только вычислительных утечек информации" (которые основаны только на чем-то, что связано с физ свойствами устройства) [40]. Но она также покрывает другие практические атаки, не удовлетворяющие этой аксиоме.Например противник может изучить любую линейную функцию по всей S (которая разделена, допустим, на две части S1 S2 ) по функция утечки f1, f2 таких, что 1(a)+ 2(b)= (a,b) .Как аргументировано Dziembowski, это распределение не только покрывает все линейные функции (a,b) =1(a)+ 2(b),но и любую функцию (a,b) которая имеет коммуникативную комплексность на всех λ. Реальным примером функции, подходящей под это условие послужит (a,b)= Σiai*bimod 2 у которой линейная коммуникативная комплексность.

Шифрование Эль-Гамаля

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

  1. Ruhr-Universit¨at Bochum, Germany, E-mail: eike.kiltz@rub.de
  2. CWI, Amsterdam, The Netherlands, E-mail: pietrzak@cwi.nl


Литература

  1. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In Neal Koblitz, editor, CRYPTO’96, volume 1109 of LNCS, pages 104–113. Springer-Verlag, Berlin, Germany, August 1996.
  2. Jean-Jacques Quisquater and David Samyde. Electromagnetic analysis (ema): Measures and counter-measures for smart cards. In E-smart, pages 200–210, 2001
  3. Karine Gandolfi, Christophe Mourtel, and Francis Olivier. Electromagnetic analysis: Concrete results. In CHES, pages 251–261, 2001.