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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:39, 3 октября 2016.
(Наши результаты.)
(Сопутствующая работа)
 
(не показано 12 промежуточных версий этого же участника)
Строка 62: Строка 62:
  
 
Попробуем первую попытку (безуспешную) сделать шифрование Эль-Гамаля устойчивым к утечке. К концу мы сделали описание состояния и разделили его на две части Dec1<sup>*</sup> и Dec2<sup>*</sup>. Секретный ключ аддитивно поделен на x = σ<sub>0</sub> + σ<sup>'</sup><sub>0</sub> устанавливая σ<sub>0</sub> = x − r<sub>0</sub> и σ<sup>'</sup><sub>0</sub>= x + r<sub>0</sub>. Дешифровка работает следующим образом :Dec1<sup>*</sup> вычисляет  σ<sub>i</sub> = σ<sub>i-1</sub>+ r<sub>i</sub> mod p,  K<sup>'</sup>=C<sup>'σ<sub>i</sub></sup> и проходит K<sup>'</sup> к следующей части.  Dec2<sup>*</sup> вычисляет σ<sub>i</sub> = σ<sub>i-1</sub>- r<sub>i</sub> mod p, а затем K=K<sup>'</sup>*C<sup>'σ<sub>i</sub></sup>. Отметим, что информация о состоянии - случайно перераспределяемый субъект к σ<sub>i</sub> + σ<sup>'</sup><sub>i</sub>=x. Однако эта схема неустойчива к утечкам так как атакующий может адаптивно изучить определенное количество битов из σ<sub>i</sub>=x+R<sub>i</sub> и σ<sup>'</sup><sub>i</sub>=x-R<sub>i</sub>(где R<sub>i</sub><math>\sum_{i}^{j=0}\cdot r_{j}</math>) которая позволяет ему полностью реконструировать секретный ключ x.
 
Попробуем первую попытку (безуспешную) сделать шифрование Эль-Гамаля устойчивым к утечке. К концу мы сделали описание состояния и разделили его на две части Dec1<sup>*</sup> и Dec2<sup>*</sup>. Секретный ключ аддитивно поделен на x = σ<sub>0</sub> + σ<sup>'</sup><sub>0</sub> устанавливая σ<sub>0</sub> = x − r<sub>0</sub> и σ<sup>'</sup><sub>0</sub>= x + r<sub>0</sub>. Дешифровка работает следующим образом :Dec1<sup>*</sup> вычисляет  σ<sub>i</sub> = σ<sub>i-1</sub>+ r<sub>i</sub> mod p,  K<sup>'</sup>=C<sup>'σ<sub>i</sub></sup> и проходит K<sup>'</sup> к следующей части.  Dec2<sup>*</sup> вычисляет σ<sub>i</sub> = σ<sub>i-1</sub>- r<sub>i</sub> mod p, а затем K=K<sup>'</sup>*C<sup>'σ<sub>i</sub></sup>. Отметим, что информация о состоянии - случайно перераспределяемый субъект к σ<sub>i</sub> + σ<sup>'</sup><sub>i</sub>=x. Однако эта схема неустойчива к утечкам так как атакующий может адаптивно изучить определенное количество битов из σ<sub>i</sub>=x+R<sub>i</sub> и σ<sup>'</sup><sub>i</sub>=x-R<sub>i</sub>(где R<sub>i</sub><math>\sum_{i}^{j=0}\cdot r_{j}</math>) которая позволяет ему полностью реконструировать секретный ключ x.
=== Наши результаты.===
+
===Полученные результаты.===
Предположительно устойчивое к утечкам шифрование Эль-Гамаля. Мы предполагаем метод практической рандомизации для создание PKE схеме Эль-Гамаля, устойчивой к утечкам под выбранными шифротекстовыми атакам в вышеобозначенном смысле.  В контексте устойчивости к утечкам этот метод был уже предложен. Центральная идея использовать мультипликативного обмена секретами для обмена секртеными ключами x т.е., x обменива.т как <math>\sigma_i = xR_i^-1\mod p</math> и <math>\sigma_i = R_i\mod p</math> для случайных <math>R_i\in Z_p^*</math>. Точнее, первая часть дешифровки высчитывает <math>\sigma_i = \sigma_{i-1}r_i^{-1}\mod p</math> и <math>K'=C^{\sigma_i}</math>. Вторая часть считает<math>\sigma'_i = \sigma'_{i-1}r_i\mod p</math>, а затем <math>K=K'^{\sigma'_i}</math>. Опять же заметим, что информации о состоянии случайно перераспределяется объектами к <math>\sigma_i\cdot \sigma'_i=x</math>.Мы отмечаем что наш метод не  модифицирует алгоритм шифрования Эль-Гамаля, только лишь модифицирует способ которым шифротекст зашифрован.В частности, публичные ключи и шифротексты такие же как в шифровании Эль-Гамаля и потому наши методы предлагают привлекательный путь обновления существующих систем Эль-Гамаля с алгоритмом защиты против атак по сторонним каналам. К несчастью мы не можем доказать, что метод изложенный выше устойчив к утечкам, и потому мы можем лишь предполагать, что схема защищена.
+
Предположительно устойчивое к утечкам шифрование Эль-Гамаля. Мы предполагаем метод практической рандомизации для создание PKE схеме Эль-Гамаля, устойчивой к утечкам под выбранными шифротекстовыми атакам в вышеобозначенном смысле.  В контексте устойчивости к утечкам этот метод был уже предложен. Центральная идея использовать мультипликативного обмена секретами для обмена секртеными ключами x т.е., x обменива.т как <math>\sigma_i = xR_i^-1\mod p</math> и <math>\sigma_i = R_i\: mod\: p</math> для случайных <math>R_i\in Z_p^*</math>. Точнее, первая часть дешифровки высчитывает <math>\sigma_i = \sigma_{i-1}r_i^{-1} \: mod\: p</math> и <math>K'=C^{\sigma_i}</math>. Вторая часть считает <math>\sigma'_i = \sigma'_{i-1}r_i\: mod\: p</math>, а затем <math>K=K'^{\sigma'_i}</math>. Опять же заметим, что информации о состоянии случайно перераспределяется объектами к <math>\sigma_i\cdot \sigma'_i=x</math>.Мы отмечаем что наш метод не  модифицирует алгоритм шифрования Эль-Гамаля, только лишь модифицирует способ которым шифротекст зашифрован.В частности, публичные ключи и шифротексты такие же как в шифровании Эль-Гамаля и потому наши методы предлагают привлекательный путь обновления существующих систем Эль-Гамаля с алгоритмом защиты против атак по сторонним каналам. К несчастью мы не можем доказать, что метод изложенный выше устойчив к утечкам, и потому мы можем лишь предполагать, что схема защищена.
  
Доказано устойчивое к утечкам шифрование Эль-Гамаля. Мы также предлагаем применение мультипликативного обмена секретами для схемы шифрования Эль-Гамаля над билинейными группами. Наша основная теорема (Теорема 1) утверждает, что схема устойчива к утечкам против атак CCA1 в модели generic group.Обсервация ключа состоит в том, что секретный ключ - элемент группы X и дешифровка проводит парные операции с элементами группы X как с одной фиксированной базой. Это позволяет нам мультипликативно обмениваться секретными ключами как элементами группы, то есть <math></math>. Интуитивно мы используем тот факт, что в модели generic group некоторые бит репрезентующие <math>\sigma_i</math> и <math>\sigma'_i</math> выглядят случайными и потому бесполезны для утечек противника. Формально мы доказываем это, однако, оказывается, что это внезапно сложно.
+
Доказано устойчивое к утечкам шифрование Эль-Гамаля. Мы также предлагаем применение мультипликативного обмена секретами для схемы шифрования Эль-Гамаля над билинейными группами. Наша основная теорема (Теорема 1) утверждает, что схема устойчива к утечкам против атак CCA1 в модели generic group. Наблюдение ключа состоит в том, что секретный ключ - элемент группы X и дешифровка проводит парные операции с элементами группы X как с одной фиксированной основанием. Это позволяет нам мультипликативно обмениваться секретными ключами как элементами группы, то есть <math>X=\sigma_{i}\sigma_i'\in \mathrm{G}</math>. Интуитивно мы используем тот факт, что в модели generic group некоторые бит репрезентующие <math>\sigma_i</math> и <math>\sigma'_i</math> выглядят случайными и потому бесполезны для утечек противника. Однако, оказывается, что формально доказать это утверждение на удивление сложно.
  
 
Мы также отмечаем доказательства того, что модель generic group имеет свои очевидные слабости. В частности в связи с атаками по сторонним каналам модель generic group может "абстрактно отдать" слишком важную информацию и противник получат реальную имплементацию схемы. Это должно быть принято во внимание когда описывается наше формальное утверждение защиты. Однако наш результат кажется является первой PKE схемой, которая устойчива к утечкой. К тому же, схема весьма практична. Другой возможной интерпретацией нашего результата является то, что защита экспоненциальной функции против атак по сторонним каналам мультипликативной техникой раздачи секретов лучше, чем аддитивной техникой.
 
Мы также отмечаем доказательства того, что модель generic group имеет свои очевидные слабости. В частности в связи с атаками по сторонним каналам модель generic group может "абстрактно отдать" слишком важную информацию и противник получат реальную имплементацию схемы. Это должно быть принято во внимание когда описывается наше формальное утверждение защиты. Однако наш результат кажется является первой PKE схемой, которая устойчива к утечкой. К тому же, схема весьма практична. Другой возможной интерпретацией нашего результата является то, что защита экспоненциальной функции против атак по сторонним каналам мультипликативной техникой раздачи секретов лучше, чем аддитивной техникой.
  
  
Устойчивая к утечкам эскпонентация и операция спаривания. Говоря о наших вышеобозначенных методах защиты Эль-Гамаля против атак по сторонним каналам, можно отметить, что возможно сделать дискретную экспонентацию и операцию спаривания устойчивой к утечкам. Пусть <math>G</math> будет группой порядка p и g будет генератором <math>G</math>. В дискретной эскпонентации требуется взять публичные элементы группы <math>Y_{i}</math> чтобы обнаружить фиксированную секретную силу x (которая утекает только через <math>g^{x}</math>). Мы предлагаем раздавать x как <math>x={x}'*{x}'' mod  p</math>
+
Устойчивая к утечкам эскпонентация и операция спаривания. Говоря о наших вышеобозначенных методах защиты Эль-Гамаля против атак по сторонним каналам, можно отметить, что возможно сделать дискретную экспонентацию и операцию спаривания устойчивой к утечкам. Пусть <math>G</math> будет группой порядка <math>p</math>, и <math>g</math> будет генератором <math>G</math>. В дискретной эскпонентации требуется взять публичные элементы группы <math>Y_{i}</math> чтобы обнаружить фиксированную секретную степень <math>x</math> (которая утекает только через <math>g^{x}</math>). Мы предлагаем раздавать x как <math>x={x}'\times{x}''\: mod\: p</math> и подсчитывать значения <math>K_i=Y_i^x</math> за два шага итерации <math>{K_i}{'}=Y_i^{x'}</math> и <math> K_i=(K_i^{'})^{x''}</math>. После таких вычислений <math>x'</math> и <math>x''</math> получают случайно созданный субъект <math>x=x'*x''\: mod\: p</math>
  
 
=== Сопутствующая работа===
 
=== Сопутствующая работа===
== Значение==
+
В сообществе аппаратных средств важность раздача секретов в контексте принятия мер по сторонним каналам хорошо известна. В частности раздача секретов была предложена как контрмера против "дифференциальных атак силового анализа" для экспонентциальных алгоритмов, но без формального анализа.
 +
 
 +
Большая часть работ по контрмерам по сторонним каналам, включая вышеобозначенные, предполагает контрмеры против конкретных атак по сторонним каналам. Микали и Рейзин в своей работе "physically observable cryptography” предложили влияющую теоретическую основу для захвата атак по сторонним каналам на более общем уровне.
 +
 
 +
Помимо устойчивости к утечкам существуют другие модели, котороые предполагают криптосистемы, пока остаются защищенными даже если функция f(sk) (выбранная атакующим из широкого количества функций)  ключа sk была получена. Мы отмечаем эти модели ниже. Главное отличие устойчивости к утечкам в том, что эти модели предполагают использование криптосистем независимых от состояния, и потому не могут они не могут выдерживать продолжительных утечек. С другой стороны функция утечки в этих работах остается незименной при вводе, а не только когда доступ к части состояний был получен.
 +
 
 +
==Определения==
 +
 
 +
Если А является определяющим алгоритмом, то мы используем следующую запись: обозначающую что А на выходе дает , используя как входные данные. Если А определяется как случайное значение, мы используем или если мы хотим получить случайность , используя представленный алгоритм (для дальнейшего использования).
 +
 
 +
Ключевые механизмы механизмы инкапсуляции.
 +
Ключевой механизм инкапсуляции (КМИ) имеет те же характеристики,  как и система шифрования с открытым ключом, за исключением того, что при инкапсуляции механизм шифрования не предусматривает значимости вводных данных: значимым является результат шифрования случайного ключа К, который потом может быть использован совместно с ключом в любой симметричной системе для того, чтобы зашифровать само послание.
 +
Используя более точные определения, КМИ состоит из трех алгоритмов.
 +
Первый является вероятностным алгоритмом создания ключа, который при вводе защищенного параметра к выводит пару ключей -- публичный и защищенный. Вероятностный алгоритм инкапсуляции и декапсуляции удовлетворяют следующему уравнению правильности для всех к:
 +
 
 +
 
 +
Защита ССА1 (также известная как защита против (!!)) в КМИ определяется следующей практикой:
 +
 
 +
 
 +
Пусть определяет вероятность того, что в вышеописанном эксперименте. После этого определяется преимущество как . В ССА2 (3)
 +
 
 +
 
 +
 
 +
 
 +
 
 +
Инкапсуляция с проверкой состояния ключа и устойчивость к утечке информации.
 +
Для того, чтобы определить устойчивость к утечке информации, за инкапсуляцию с проверкой состояния ключа принимается механизм , в котором декапсуляция проводится с проверкой параметров и может быть формально разделена на на две последовательные стадии:
 +
Таким образом, соотношение зависимости данных ввода-вывода остается таким же, как и в стандартных КМИ.
 +
 
 +
Более формально, алгоритм создания ключа () создает ключ с общим доступом и два начальных состояния (). При этом, оба начальных состояния делят между собой секретный ключ все системы и используются в механизмах декапсуляции с проверкой параметров (состояний).
 +
 
 +
На () использования механизма декапсуляции, декапсулированный ключ рассчитывается по следующей схеме:
 +
 
 +
Здесь () и () являются случайными величинами двух случайных алгоритмов, () и () являются обновленными параметрами и () -- параметрические данные, транслирующиеся от () к ().
 +
 
 +
Устойчивость к утечке определяется следующим образом. Пусть () является параметром утечки. Пусть в определении участвуют атаки, где противник может не только составить ряд () для декапсулированных значений (), но и может воспользоваться дополнительной информацией благодаря вычислениям и использованием этих двух значений. Таким образом, в эксперименте, противник может (дополнительно к данных выхода С) определить две эффективные и подсчитываемые функции утечки () с уровнем (), получая дополнительно к стандартным данным вывода () (), которые определяются как:
 +
 
 +
с такими же обозначениями, как и в (1). Таким образом, функции () берут в качестве вводных данных те же данные, что и (). CCLA1 как уровень безопасности КМИ определяется в эксперимент, описанном ниже (обратите внимание, что теперь нам необходимо не только определить параметр безопасности (), но и уровень утечки ()):
 +
 
 +
Пусть () определяет вероятность того, что ()  в вышеописанном эксперименте. После этого определяется преимущество () как ().
 +
 
 +
Известно, что в CCA1  безопасный КМИ вместе с одноразовым симметричным шифрованием (?) позволяет использовать ССA1-безопасную систему PKE. Таким образом, это заявление также верно и для CCLA1 КМИ, так что для достижения наших целей достаточно всего лишь создаить CCLA1 КМИ.
 +
С другой стороны, необходимо отметить, что схема со сложением компонентов, описанных выше, в целом неверна для CCLA2 КМИ. То-есть, CCLA2 КМИ и CCA DEM вместе не составятся CCLA2 PKE систему.
 +
 
 
==Устойчивое к утечкам шифрование Эль-Гамаля==
 
==Устойчивое к утечкам шифрование Эль-Гамаля==
 
===Энкапсуляция ключа Эль-Гамаля===
 
===Энкапсуляция ключа Эль-Гамаля===

Текущая версия на 16:39, 3 октября 2016

Leakage Resilient ElGamal Encryption
Faster Fully Homomorphic Encryptions.png
Авторы Eike Kiltz[@: 1], Krzysztof Pietrzak[@: 2]
Опубликован 2011 г.
Сайт Homepage of Damien Stehle
Перевели Шикунов Юрий Игоревич
Год перевода 2011 г.
Скачать оригинал
Аннотация. Сокрытие это популярная и хорошо известная контрмера для защиты криптосистем с публичными ключами против атак по сторонним каналам. Идея высокого уровня — рандомизировать экспонентацию для предотвращения множественных измерений одной операции на разных данных, такие измерения могут позволить неприятелю узнать секретную экспоненту. Различные варианты сокрытия изложены в литературе, использующие аддитивные или мультипликативные секреты обмена чтобы сокрыть или базу или экспонету. Контрмеры обычно нацелены на предотвращение конкретных атак по сторонним каналам(по большей части анализ питания) и проходят без формальной защитной гарантии. В этой работе мы исследуем какое расширенное сокрытие может предоставить продвинутую защиту против основных атак по сторонним каналам. Внезапно оказывается, что в контексте дешифровки публичных ключей некоторые техники сокрытия подходят больше, чем другие. В частности мы предлагаем мультипликативную сокрытую версию шифровки публичного ключа Эль-Гамаля, где мы доказываем, что эта схема, подтвержденная более чем на миллионах групп первоначального порядка 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, область значений которой принадлежит к некоторому фиксированному бит с каждого запроса. После 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 у которой линейная коммуникативная комплексность.

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

Схема шифрования Эль-Гамаля над цикличной группой прямого порядка p работает как положено. Публичный ключ состоит из генератора g принадлежащего к и = yxгде x ∈ Zp - секретный ключ. Шифрование определяет шифротекст как C=gr и использует симметрический ключ K=Xr для сокрытия сообщения. Описание реконструирует ключ посредством вычисления K=Cx. В гибридной версии шифрование Эль-Гамаля содержит много стандартных тел и это общепринятый стандартный метод шифрования над эллиптическими кривыми. В данный момент будет полезно узнать почему шифрование Эль-Гамаля не устойчиво к утечкам. Противник на i-ой описательной очереди может специфицировать функцию утечки которая выводит i-й бит секретного ключа x. После q = |x| запроса к предсказанию утечки весь ключ может быть восстановлен.


Попробуем первую попытку (безуспешную) сделать шифрование Эль-Гамаля устойчивым к утечке. К концу мы сделали описание состояния и разделили его на две части Dec1* и Dec2*. Секретный ключ аддитивно поделен на x = σ0 + σ'0 устанавливая σ0 = x − r0 и σ'0= x + r0. Дешифровка работает следующим образом :Dec1* вычисляет σi = σi-1+ ri mod p, K'=Ci и проходит K' к следующей части. Dec2* вычисляет σi = σi-1- ri mod p, а затем K=K'*Ci. Отметим, что информация о состоянии - случайно перераспределяемый субъект к σi + σ'i=x. Однако эта схема неустойчива к утечкам так как атакующий может адаптивно изучить определенное количество битов из σi=x+Ri и σ'i=x-Ri(где Ri) которая позволяет ему полностью реконструировать секретный ключ x.

Полученные результаты.

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

Доказано устойчивое к утечкам шифрование Эль-Гамаля. Мы также предлагаем применение мультипликативного обмена секретами для схемы шифрования Эль-Гамаля над билинейными группами. Наша основная теорема (Теорема 1) утверждает, что схема устойчива к утечкам против атак CCA1 в модели generic group. Наблюдение ключа состоит в том, что секретный ключ - элемент группы X и дешифровка проводит парные операции с элементами группы X как с одной фиксированной основанием. Это позволяет нам мультипликативно обмениваться секретными ключами как элементами группы, то есть . Интуитивно мы используем тот факт, что в модели generic group некоторые бит репрезентующие и выглядят случайными и потому бесполезны для утечек противника. Однако, оказывается, что формально доказать это утверждение на удивление сложно.

Мы также отмечаем доказательства того, что модель generic group имеет свои очевидные слабости. В частности в связи с атаками по сторонним каналам модель generic group может "абстрактно отдать" слишком важную информацию и противник получат реальную имплементацию схемы. Это должно быть принято во внимание когда описывается наше формальное утверждение защиты. Однако наш результат кажется является первой PKE схемой, которая устойчива к утечкой. К тому же, схема весьма практична. Другой возможной интерпретацией нашего результата является то, что защита экспоненциальной функции против атак по сторонним каналам мультипликативной техникой раздачи секретов лучше, чем аддитивной техникой.


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

Сопутствующая работа

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

Большая часть работ по контрмерам по сторонним каналам, включая вышеобозначенные, предполагает контрмеры против конкретных атак по сторонним каналам. Микали и Рейзин в своей работе "physically observable cryptography” предложили влияющую теоретическую основу для захвата атак по сторонним каналам на более общем уровне.

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

Определения

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

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


Защита ССА1 (также известная как защита против (!!)) в КМИ определяется следующей практикой:


Пусть определяет вероятность того, что в вышеописанном эксперименте. После этого определяется преимущество как . В ССА2 (3)



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

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

На () использования механизма декапсуляции, декапсулированный ключ рассчитывается по следующей схеме:

Здесь () и () являются случайными величинами двух случайных алгоритмов, () и () являются обновленными параметрами и () -- параметрические данные, транслирующиеся от () к ().

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

с такими же обозначениями, как и в (1). Таким образом, функции () берут в качестве вводных данных те же данные, что и (). CCLA1 как уровень безопасности КМИ определяется в эксперимент, описанном ниже (обратите внимание, что теперь нам необходимо не только определить параметр безопасности (), но и уровень утечки ()):

Пусть () определяет вероятность того, что () в вышеописанном эксперименте. После этого определяется преимущество () как ().

Известно, что в CCA1 безопасный КМИ вместе с одноразовым симметричным шифрованием (?) позволяет использовать ССA1-безопасную систему PKE. Таким образом, это заявление также верно и для CCLA1 КМИ, так что для достижения наших целей достаточно всего лишь создаить CCLA1 КМИ. С другой стороны, необходимо отметить, что схема со сложением компонентов, описанных выше, в целом неверна для CCLA2 КМИ. То-есть, CCLA2 КМИ и CCA DEM вместе не составятся CCLA2 PKE систему.

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

Энкапсуляция ключа Эль-Гамаля

Билинейная энкапсуляция ключа Эль-Гамаля

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

  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.