Универсальный распознаватель атак по сторонним каналам: улучшения и ограничения

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 18:53, 11 февраля 2016.
Универсальный распознаватель атак по сторонним каналам: улучшения и ограничения
Авторы Nicolas Veyrat-Charvillon and
Francois-Xavier Standaert
Опубликован 2011 г.
Перевели Polyakov Vladimir
Год перевода 2015 г.
Скачать оригинал


Аннотация. Целью универсального рапознавателя атак по сторонним каналам является разрешение ключевых извлечений против любого типа реализации, при минимальных предположениях на аппаратном уровне. Такие распознаватели особенно интересны в свете последних технологических достижений. Действительно, традиционные модели утечек, использующих атаки по сторонним каналам, основаны на весе или расстоянии Хэмминга для данных, содержащихся в реализации, стали недействительными ввиду постепенно возросшей изменчивости в наноразмерных электронных устройствах. В данной работе, мы соответственно рассматриваем два аспекта, связанных с применением атак по сторонним каналам, анализа против новейших криптографических внедрений. Во-первых, мы описываем новый статистический тест, который призван быть универсальным и эффективным при использовании многомерныхутечек. Предлагаемый распознаватель полностью непараметрический. Он формулирует утечки распределений с использованием копулы и дискриминирует ключи, основанные на обнаружении “выбросного поведения”. Далее, мы предоставляем эксперименты, выдвигая ограничения универсального анализа атак по сторонним каналам в сложных сценариях, где уязвимые устройства защищаются с помощью контрмер. Наши результаты демонстрируют, что все непрофилированные атаки обнаруживаются таким образом, но иногда может возникнуть ложное чувство безопасности из-за неправильных моделей утечки. То есть, существуют настройки, в которых реализация является безопасной в отношении таких непрофилированных атак и может предотвращать их с помощью профилирования. Это подтверждает, что, оценивая криптографические реализации,следует всегда рассматривать профилирование, как наихудший сценарий.

Введение

С момента введения дифференциального анализа мощности Кохером, Яффе и Джуном в конце 1990-х годов [1], физические атаки стали важной проблемой для безопасности криптографических устройств. На академической стороне, это породило много интересных разработок новых атак, контрмер и моделей для оценки (или, в последнее время, доказательства) физической безопасности. В промышленности, защита от таких атак необходима для достижения высоких уровней сертификации для криптографических продуктов. Грубо говоря, атаки по сторонним каналам обычно классифицируются как профилированные или непрофилированные [2]. Профилированные атаки обычно полезны в оценке контекста, в котором можно эксплуатировать устройства с известными ключами для того, чтобы построить точные модели утечек, например шаблоны [3]. Они могут затем быть использованы для того, чтобы получить оценку метрики, такой как взаимный обмен информацией, затем для того чтобы зафиксировать наихудший сценарий [4]. Напротив, непрофилированные атаки, на которых мы будем фокусироваться в данной работе, имеют целью зафиксировать поведение реальных противников, которые не имеют точного предварительного определения характеристик приборов, которые они избрали целями. Они, как правило, не оптимальны с точки зрения сложности данных, и используют оценку “на лету” утечек вероятностных распределений (или их моментов) в целях восстановления секретной информации. В целом, разрыв между этими двумя сценариями может быть больше. Следовательно, профилированные и непрофилированные атаки дополняют друг друга и позволяют по-новому взглянуть на безопасность встроенных устройств.

Вкратце, непрофилированная атака по сторонним каналам вообще работает путем сравнения зависимой от ключа модели утечки с фактическими измерениями. Если атака прошла успешно, ключ кандидат рождая лучшее сравнение-это один манипулируют посредством целевого устройства. Следовательно, давать оценку действиям такого распознавателя обычно можно по двум осям. С одной стороны, атаки должны быть эффективным, это означает, что они позволяют восстанавливать ключи с ограниченными данными (т. е. измерениями), временем и памятью. С другой стороны, атаки должны также быть универсальными, т. е. применимыми в отношении любого типа устройства и (если возможно) нечувствительны к неточным моделям утечки. Краткий взгляд на положение дел говорит о том, что большинство предыдущих работ могут быть рассмотрены как изучение компромисса между этими двумя (как правило, противоречивыми) целями. Например, в докладе Крипто 1999,“однобитный МСД” осуществляется с помощью простого теста разницы в значениях. Этот подход имеет ограниченную эффективность, потому что в одно-битная модель подразумевает низкое ОСШ, и он не может воспользоваться никакими знаниями о целевом устройстве, которые могут быть доступны противнику. Как следствие, многие “многобитовые” расширения уже предлагались в литературе. Следует особо отметить, что Correlation Power Analysis(CPA) представленный в 2004 году работает очень эффективно в случаях, когда устройство утечек хорошо известная и линейная (например, вес Хемминга) модель [5]. Но это тоже немного узкоспециально, и может быть полностью неэффективным, если используется неточная модель утечки. Чтобы избежать этой «моделезависимости» мощные решения строят стохастические модели “на лету”, как предложенные Шиндлером, Лемке и Пааром в 2005 году [6]. Возможный недостаток стохастических моделей заключается в их параметрической природе. Но как обсуждалось в [7], такой линейный регрессионно-ориентированный подход дает отличные результаты в контексте первоочередных атак по сторонним каналам на незащищенные устройства. Альтернативные стохастические модели включают Взаимный Информационный Анализ, введенный в 2008 году [8], и тесты, такие как Крама ЭМ-фон-Мизеса , обсуждаемый в [9]. Эти последние два распознавателя являются довольно универсальными, и могут захватить утечки любого типа зависимостей. Они также могут быть непараметрическими в случае MIA (который еще подразумевает оценку формата PDF, например, с помощью гистограммы или ядер, следовательно, требующих адекватного выбора числа интервалов или ядра пропускной способности [10]) и совершенно свободно перердать параметры теста ЭМ-фон-Мизеса.

Интересно, что последние технологические достижения позволяют предположить, что степень универсальности распознавателей утечек по сторонним каналам может быть важным признаком в оценке будущих криптографических устройств. Действительно, как обсуждалось в [11], движение в сторону наноразмерных электронных схем подразумевает появление новых функций утечек, что сильно отклоняются от традиционных (расстояние, вес Хэмминга) предположений. Кроме того, растущая вариативность устройств предполагает, что каждая целевая реализация может быть охарактеризована с помощью различных моделей утечек. Вполне естественно, что ситуация оказывается еще хуже, когда проводятся более высокоуровневые нападения на устройства, защищенные маскировкой [12],[13]. Действительно, удлинение DPA и CPA требуют введения метода эвристического снижения размерности, как правило, обозначаемый как сочетание функций в литературе [14]. Но как обсуждалось в [15],[16], выбор удачной комбинации функций по сути своей зависим от функций утечек (т. е. целевого устройства), и может только ухудшить объем информации, которой воспользуется распознаватель. Аналогично, расширения стохастической модели являются прямыми в профилированном контексте [17], когда маски доступны во время профилирования, но их применение в непрофилированном сценарии требует оценки формата PDF смесей в неконтролируемой манере (т. е. задача, для которой мы не имеем систематических и эффективных решений), или воспользоваться некоторыми эвристическими предположениями (например, используя комбинацию функций). На самом деле, только MIA непосредственно обобщается на многомерный сторонний канал утечки , не требуя сочетание функций [18], [19], [10]. Учитывая эту привлекательную особенность, кажется естественным исследование как распознаватели могут решать сложные сценарии, сведение нелинейной утечки функций и контрмеры, такие как маскировка. Этот документ представляет два вклада в этом направлении. Во-первых, предложенный тест для анализа стороннего канала, должен быть универсальным и эффективным при эксплуатации высоко-размерных утечек. Для этой цели мы начнем с наблюдения, для того, чтобы быть универсальными, MIA выбирает ключевых кандидатов, которые максимизируют взаимную информацию между ключевых зависимые противника от модели утечки и реальных измерений. Наш новый распознаватель использует альтернативный критерий для выбора ключа-кандидата, для которого эти модели утечки наиболее отклоняются от ссылки (например, равномерного) распределения. Далее, было замечено в экспериментах на MIA, что обобщения на многомерные приступы могут быть менее эффективными, из-за сложности расчета многомерного PDF “на лету”, без определенных предположений [16]. Также, ранее рассмотренные методы оценки, такие как использование гистограмм, списков или сплайнов [20], как правило, требуют для настройки параметров, например, число бинов гистограммы, что напрямую влияет на эффективность атаки. Следовательно, хотя MIA направлен на универсальность больше, чем эффективность, должно быть интересно избегание таких параметров, или возможность сделать свои настройки как можно проще. Наш новый распознаватель использует передовые статистические инструменты в целях устранения данных проблем. Для этой цели, мы сначала применяем утечку трансформации, эксплуатируя копулы [21]. Это проецирует образцы в новое пространство, где их распределение (между каждым измерением) является однородным. Благодаря этому преобразованию, мы основываем наши распознаватели на универсальном критерии подбора ключевых кандидатов, для которых модель максимизирует отклонение от равномерного. Затем мы эксплуатируем расстояние отбора проб, т. е. мы оцениваем распределение расстояния между двумя образцами (ориентируемся на модель утечки), а не распределение единичных образцов. Расстояние отбора проб имеет интересные особенности в многомерных параметрах, так как оно позволяет избежать решения многомерных распределений напрямую (мы скорее оценим одномерное распределение расстояния принятое в течение нескольких измерений). Как результат наш тест является полностью свободным от параметров и в основном требующий для вычисления эмпирической функции распределения, для каждого измерения, принятого самостоятельно. Резюмируя, отмечено в [22], что эффективные потери MIA связаны с проблемой оценки утечки дистрибутивов. Настоящий документ дополняет эту точку зрения и направлен на то, чтобы облегчить этот шаг оценивания.

Во-вторых, мы предлагаем различные эксперименты для того, чтобы оценить этот новый распознаватель. А именно, мы расследовали нападения на незащищенные и маскированные s-box вычисления, в трех разных конфигурациях: симуляция наивного веса Хэмминга, реальные замеры на 65 нм КМОП-чипе, Spice моделирование из двойственной логики. Эти примеры, как ожидается, будут отражать различные утечки функций, которые можно найти в сторонних каналах утечки. Они подчеркивают, что предлагаемые типовые тест сравниваются с MIA благоприятно, во всех исследованных сценариях. Они также подчеркивают, что, несмотря на общий характер MIA и новых распознавателей, их применение в отношении современных электронных устройств могут быть сильно затронуты неточными моделями утечки, и, что последствия такой неточности усиливается с контрмерами, таких, как маскировка. Иными словами, даже обычные тесты могут быть неудачными в определенных контекстах, если только предварительные предположения (аналог профилирования) доступны противнику. Отметим, что это последнее замечание справедливо и для всех непрофилированных распознавателей опубликованных до сих пор. Следовательно, наши результаты ставят вопрос, является ли непрофилированные атак могут быть улучшены в целях решения таких критических контекстах, или, альтернативно, являются ли эти контексты могут быть формализованы и использованы в качестве критериев проектирования для новых контрмер. На настоящий момент, они по крайней мере подтверждают важность профилированной информаций теоретического анализа при оценке утечек криптографических устройств.

Анализ сторонних каналов

В следующих разделах статьи анализируются атаки изображенные на рис. 1, как описано в [18]. То есть мы рассмотрим устройство, выполняющее несколько криптографических вычислений на разных записях открытых изображенных равномерно относительно текстового пространства , с помощью некоторого фиксированного ключа изображенного равномерно относительно ключевого пространства . Во время вычисления (где -случайная величина из ), устройство будет обрабатывать некоторые промежуточные значения (определены как конфиденциальные переменные в [23]), которые зависят от известного входного и неизвестного ключа . На практике интересны чувствительные переменные в DPA атаках - те, которые зависят исключительно от перечисляемого подключа : обозначим их как . В любое время вычисления чувствительной промежуточного значения, устройство генерирует некоторые физические утечки, обозначаемые как .

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

Рис.1

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

Новый универсальный ключ

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

Спецификация

Распознаватель основан на шести основных шагах (один из которых опциональный).

Утечка пространственных преобразований.

Для того, чтобы обойти проблему оценки утечки распределения , наш метод в первую очередь трансформирует образцы со связями. Связка просто применяет вероятность интегрального преобразования к каждой предельной величине, что делает распределение образцов вдоль каждой оси равномерным. Более точно, для , где -размер случайной величины, преобразование связки дает производную переменной ,где это функция распределения , defined by .Интересно, что имеют равномерное распределение по определению вероятности интегрального преобразования, но какая-либо зависимость среди переменных подразумевает соответствующую зависимость среди . Это показано на рисунке 2, где ясно видно, что предельное распределение равномерная после снижения, в то время как условные распределения остаются легко различимы. Для иллюстрации, рисунок представляет собой простой случай одного-битной модели утечки. На практике, так как плотность утечки и его интегральная функция обе неизвестны,то мы вычисляем эмпирическую связку, т.е. связку, где совокупные распределения аппроксимируются эмпирическими распределениями. Для n-го образца устанавливаем изображенной от распределения одномерной случайной переменной ,эмпирическая интегральная функция распределения величины получается от где это индикатор-функция.То есть, требуется только отсортировать образцы и эквивалентно посчитать квантиль для данной выборки. Благодаря теореме Гливенко-Шантеля [3, 9],мы знаем, что эмпирическая интегральная функция распределения сходится почти точно к общей интегральной функции распределения, равномерно по всем . То есть: Преимущества эмпирической связки в том, что восстановленные образцы принимают только факторособенные значения: построенные из вещественных утечек. Следовательно, это позволяет связать с массовыми функциями вероятностей, вместо плотностей, что упрощает расчеты. В общем, количество преобразованных к работе на модифицированных значениях вместо утечек , которые имеют по построению простое однородное распределение, но по-прежнему сохраняют информацию, содержащуюся в исходных утечках.

Утечка разбиений.

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

Fig. 2. Illustrated process of the distinguisher (1D).

Выбор признаков и шаблонов.

Given the (uniform or not) distributions representing the key candidates, one can select a feature of these distributions, that properly captures possible non-uniformities. In the following, we will consider the distance between couples of samples for this purpose, which corresponds to the notion of spacings in statistics [24]. When dealing with multivariate leakages, we define spacings via the or Manhattan distance (instead of the Euclidean one), which avoids dealing with irrational values. The Manhattan distance between two samples and is given by where the sum is taken over the different dimensions of the samples. Next, since the marginal distribution of the leakages is known to be always uniform, we simply build a template for the distribution of the distance between two uniform samples. This template is precomputed once for all attacks, independently of the target implementation. Its shape is actually a spline, which ensure a degree of smoothness (see appendix A for details). We note that the interest of feature selection is not obvious in the univariate attack context of Figure 2. But it implies a dimensionality reduction that becomes convenient in a multivariate setting. It also leads to an efficient solution for the estimation problem, as we now detail.

Оценка.

This is the central step of the attack, in which we try to model the distributions corresponding to the different key candidates. For this purpose, one limitation of MIA was the need to estimate one conditional distribution per model value, for each key candidate. In other words, each of these distributions has to be estimated from only a part of the available samples. By contrast, our new test allows to estimate only one distribution, from all the available samples. This is possible because we know (again thanks to the copula) that the marginal distribution should be uniform for a wrong key candidate. Hence, we can sample the Manhattan distance for all partitions, and combine the results into a single probability mass function, which has to be consistent with uniformly drawn samples. Combined with the previous feature selection, it implies that one can estimate the distributions for each key candidate by iterating the next steps:

  • Pick a random leakage from the complete set of samples.
  • Pick a different random leakage , from the same model category as .
  • Compute their Manhattan distance .

Finally, we obtain the sampled probability mass function of the distance. This distance can only take distinct values, with the number of samples available and the dimensionality of the leakages. This is possible because we use the Manhattan distance (i.e. there are as many possible distances as there are samples). Note that if there are leakages corresponding to a model value , the number of possible couples to sample scales as . In our following experiments, it was always possible to test these couples exhaustively. But in attacks requiring millions of traces, exploiting Monte Carlo sampling would of course be an alternative to reduce the time complexity to more tractable values.

Сглаживание

As can be seen from Figure 2, the distance histograms can be used to discriminate the different partitions, but they remain quite noisy. In order to improve the signal-to-noise ratio of the pdf estimations, one straightforward solution is to apply a lowpass filter. Different solutions can be used for this purpose. A very generic one, that we applied in our experiments, is to use Kernel smoothing with an Epanechnikov function [25] (which is both the most efficient Kernel and the least costly to compute). The advantage of Kernel smoothing is to generalize easily to distributions with any number of dimensions. Its drawback is to introduce a parameter (the window size used in the smoothing). However, we note that this parameter is significantly easier to select than, e.g. the number of bins or Kernel bandwidth in the case of MIA, since we know exactly how the distribution of the wrong key candidates should look like. Namely, this distribution should correspond to the previously described uniform distance template. How to select this parameter adequately will be explained in the next subsection.

Вывод.

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

За и против

One important advantage of this new test is that it nicely extends to multivariate attacks. As illustrated in Figure 3 for a bivariate example (i.e. ) and a Hamming weight leakage model, the leakage transformation is performed independently for each dimension. That is, we just have to compute univariate empirical cumulative functions (rather than one -dimensional distribution when applying MIA). The empirical cumulative functions are straightforward to compute and require no parameter at all. By applying the copula, the leakage samples are transformed in such a way that their marginal distribution along each dimension becomes uniform over [0, 1]. As a result, we can again discriminate key candidates by simply assuming that the leakage model generated with the good key candidate should lead to a partitioning for which the distance to uniform is large. On the negative side, the estimation of the distance distribution follows a multinomial distribution (a generalization of the binomial distribution to more than two categories), which implies that the sampled distribution tends to be noisy. The smoothing part that aims at reducing this noise requires to set a parameter that can be seen as the counterpart of the number of bins or Kernel bandwidth when directly trying to estimate the leakage pdf in MIA. However, this task is arguably easier in our new distinguisher, since we only need to detect departures from a well-characterized distribution. In practice, a Kernel smoothing with window size equal to 1 allows us to only retain the general features of the distance distribution, which is enough to detect departures from the uniform template. This is only suboptimal when dealing with very low-noise scenarios, where a smaller window size is enough to smooth out the estimated densities.

Fig. 3. Illustrated process of the distinguisher (2D).

Эксперименты

We now provide experiments, in order to verify the relevance of the previously introduced generic test and to compare its efficiency with other distinguishers used in side-channel analysis. For this purpose, we consider the following contexts.

1. Different target computations.We investigated three possible cases. In the first one, we target the leakage corresponding to the execution of an unprotected AES S-box, denoted as , where the adversary is provided with the plaintext and leakage . In the second one, we consider the execution of a masked AES S-box, denoted as . In this case, the mask is a uniformly random value and the adversary is provided with the plaintext and leakages . Finally, we consider the execution of a masked S-box where the the adversary only receives the plaintext and a combination of the two leakage samples. Following the previous analyzes in [15],[16], we used the normalized product between the samples, i.e. , where denotes the sample mean operator.

2. Different leakage functions and target devices. We again analyzed three possible cases. In the first one, the leakages are simulated with a Hamming weight function, to which we added a Gaussian noise, with mean 0 and variance . Although not always realistic, the investigation of this setting is justified by the numerous works carried out under this assumption, as a reference. In the second case, we use the leakage measured from an S-box implemented in a 65 nanometer CMOS technology, running at 2MHz and sampled with a 1 Gsample/sec digital oscilloscope), previously analyzed in [11]. In the third case, the leakage of a dualrail pre-charged S-box, implemented in the same 65 nanometer technology and using the logic style described in [26], was simulated with Spice. The details of this S-box are out of the scope of this paper, but it was selected as an example of leakage function that strongly deviates from the Hamming weight model. Both for the CMOS and the dual-rail S-boxes, we selected one single leakage sample per target operation. This selection is not supposed to be optimal, but was the same for all the investigated attacks, in order to allow fair comparisons.

3. Different distinguishers. First, correlation attacks based on Pearson’s coefficient were applied, following the descriptions in [5]. Next, we performed MIA3 with histogram-based pdf estimation, following [8]. The number of bins in histograms was selected according to Scott’s rule of thumb [27]. Third, we used the stochastic approach first described in [6] and analyzed in the non-profiled setting by Doget et al. [7]. The goal of the stochastic approach is to approximate the S-box leakages with a linear function , where the coefficients are determined by regression, and the ’s correspond to the base functions used in the attack. Finally, we experimented our new generic test, with the window size in the Kernel smoothing step systematically set to one in the attacks (i.e. a version of the distinguisher completely free of parameters).

4. Different leakage assumptions. As detailed in Section 2, the non-profiled distinguishers studied in this paper need to rely on some preliminary assumptions on the leakage. For correlation attacks, MIA and the new test, we first evaluated the Hamming weight and identity leakage models (where one takes as the Hamming weight, or the 7 least significant bits of , respectively). These are usual assumptions when performing a side-channel attack. However, as will be discussed in the remaining of the section, these models were not sufficient to perform successful key recoveries in all the investigated contexts. Hence, we additionally used a profiled leakage model in some experiments. Different solutions are possible for this purpose, e.g. exploiting templates [3]. In the following, we built model classes by grouping together transitions leading to similar leakage values (e.g. 9 such groups would appear for an 8-bit Hamming weight model, corresponding to the 9 possible weights). The model groups were built using a K-means clustering algorithm. Again, this selection is not supposed to be optimal, but to serve as a background to discuss generic distinguishers. As for the stochastic approach, one just needs to select the base vectors used in the adversary’s predictions. We followed the classical strategy and used the target S-box output bits for this purpose (i.e. a 9-element basis, with 8 bits and a constant).

As our goal is to compare distinguishers, the evaluations we performed followed the security metrics in [4]. For each investigated context, we computed the success rate of the attacks, over a set of 100 to 500 independent experiments. The figures corresponding to these experiments have been reported in appendix. They allow a number of interesting observations that we now detail.

Observation 1. On different types of leakage functions. The different leakage functions considered imply very different constraints for the non-profiled adversaries. In the case of Hamming weight leakages (Figures 4 and 5 left), this function is purely linear, i.e. with the th bit of the S-box output and all coefficients set to 1. In addition, as shown in [16], the bivariate distribution of the leakages conditioned on the key, for a masked S-box, is accurately characterized by the correlation between the samples and in this case. As a result, all investigated attacks are very efficient. By contrast, when moving to the analysis of real measurements on a 65nm chip (Figures 5 right and 6), the Hamming weight assumption becomes invalid, and the quadratic, cubic,. . . terms in are non-negligible. As a result, attacks using this model are not successful anymore. Interestingly, the stochastic attack using a linear basis is still efficient, confirming the analysis in [24] that the linear terms of the leakage function are still significant. Surprisingly, the correlation attacks in Figure 6 suggests that a masked S-box may be easier to attack than an unmasked one, under a Hamming weight assumption. This is explained by the fact that actual leakages are not accurately predicted by Hamming weights in the unprotected case, whereas their inter-sample correlation remains informative in a second-order attack against a masked S-box. Eventually, the (simulated) dual-rail S-box is an example of implementation with completely non-linear leakages, as witnessed by the impossibility to perform a successful stochastic attack using a linear basis (see Figure 7).

Observation 2. On the limits of generic distinguishers and models. Generic distinguishers are expected to capture any type of leakage dependency. Still, they are dependent on the leakage model used to build the partitions in a side-channel attack. An interesting outcome of our experiments is that these distinguishers are in fact strongly affected by incorrect assumptions. For example, the Hamming weight leakage model does not lead to successful attacks, neither against the 65nm CMOS chip, nr against the dual-rail pre-charged one. More critically, the identity leakage model that is supposed to provide a generic way to target any implementation in [8], is not successful either in certain cases (Figures 5 right, 7). For Figures 5 right and 7 left, only models obtained through profiling lead to successful key recoveries with the new distinguisher. For Figure 7 right, only template attacks are successful. These limitations are due to the lack of relevance of the leakage models used by the adversary. They are in fact not new: already in 2005, Mangard et al. observed an implementation for which even single-bit leakage models were not accurate enough to perform a successful DPA [28]. More generally, and as also emphasized in [29], MIA-like distinguishers can naturally exploit identity models when applied to non-bijective S-boxes (as in the DES), because such S-boxes imply a meaningful partition by design. But the genericity of this model does not extend to bijective S-boxes (or other block cipher components), excepted if justified by specific implementation choices. In other words, there is no generic leakage model. As discussed in [9], even MIA requires a partitioning such that is maximized for the correct key candidate. The extension of MIA in this paper faces a very similar requirement.

Observation 3. On the limits of non-profiled side-channel attacks. Another consequenceof our experiments is to emphasize that, in the context of the dual-rail S-box (Figure 7), none of the non-profiled side-channel attacks could lead to successful key recoveries. Interestingly, the “on-the-fly” stochastic approach fails in this context, even when increasing the size of the basis (e.g. using not only linear, but quadratic, cubic, . . . terms). The failure of a stochastic model using linear base vectors is easily explained by the strongly non-linear nature of the simulated leakages produced by the dual-rail S-box. The unsuccessful results with larger bases just derive from the fact that these large bases allow refining the model for all key candidates (i.e. not only the correct one). In fact, also in this case, it is important that the base vectors are justified by a reasonable physical intuition. For example, in case of linear leakage functions, the regression is easy for the correct key candidate (because provided with a good basis) and difficult for the wrong key candidates (because the regression essentially has to capture the non-linearity of a modified S-box such that , with and the good and a wrong key candidate). But as soon as the base vectors do not have a connection with the actual leakages, the advantage of the correct key candidate in building a good stochastic model vanishes. When combining this dual-rail logic style with masking (in Figure 7 right), we see that only a bivari- 4 This limitation is only due to the application of the stochastic approach in a nonprofiled scenario. In profiled attacks, the stochastic approach remains perfectly sound, as soon as provided with enough base vectors, just as a template attack. ate template attack, similar to the ones in [16], allows recovering keys. In this respect, it is worth noting that a leakage model that is sound in an unprotected setting (e.g. the one based on clustering in Figure 7 left) does not translate into a sound model for the corresponding masked implementation (in Figure 7 right).

Observation 4. MIA versus the new test. Finally, our new distinguisher compares favorably to MIA in all the investigated experiments. We note that the efficiency of MIA could possibly be improved, by exploiting pdf estimation based on Kernels, splines or parametric techniques [10]. However, more than the efficiency of the distinguisher, it is worth to notice that in certain settings, e.g. the masked 65nm CMOS S-boxes in Figures 5 right and 6 right, it allows exploiting a leakage assumption while MIA cannot. It is an open question to determine whether these experiments can be formally confirmed (e.g. are they due to identified limitations as in the example given in [30], Section 3) or are the result of measurement artifacts that would vanish with more intensive measurement efforts.

Заключение и открытые проблемы

Generic distinguishers are a useful tool for evaluating leaking devices. In this paper, we first proposed a new and efficient generic test that is fully non-parametric, based on a natural discriminating criterion, and exploits state-of-the-art statistical tools. It can be useful in all scenarios where the previously introduced MIA shows significant advantages over other non-profiled distinguishers. Next, we discussed the relevance of generic distinguishers in general. Based on experimental validation in different contexts, we put forward that such nonprofiled attacks do not get rid of the need of sound assumptions during the partitioning step in a side-channel analysis. Similarly, when applied “on-thefly”, the stochastic approach of Schindler et al. is only sound when provided with meaningful based vectors, that may not be easy to guess for practical adversaries. This observation suggests that the gap between profiled and non-profiled sidechannel attacks can be huge, when such assumptions are are not available. It reemphasizes the need to consider two aspects in the security analysis of a leaking device, as advocated in [4]. First, the worst case security can only be evaluated with a profiled attack (e.g. using templates), and quantified with an information theoretic metric. Second, different types of non-profiled distinguishers can be compared with a security metric, in order to measure how efficiently they can take advantage of the available information. In this respect, generic tests bring an interesting alternative to more specific (e.g. correlation-based) statistical tools. But they are not immune to model imprecisions, and resisting such attacks is not sufficient to conclude that an implementation is secure. Admittedly, the most critical examples we exhibit in this paper are based on simulations and practical implementations usually show linear dependencies in their leakages. Nevertheless, this discussion underlines that the theoretical limits of present non-profiled attacks have to be properly understood. It also leads to interesting questions for the design and analysis of secure implementations. First, as non-profiled distinguishers published in the literature seem specially affected by non-linear leakage functions, designing hardware logic styles with this criterion in mind appears as an interesting scope for further research. Preliminary experiments reported in [31] suggest that the DDSLL logic style may not be the most suitable for this purpose. Second, the partitioning step of generic distinguishers is made specially easy when non-bijective S-boxes (or components) are used. Hence, such S-boxes should be avoided when designing ciphers to be secured against physical attacks. In the same lines, targeting the output of Mix- Column in an AES implementation could be an interesting topic for further investigation. Depending on the architectures (e.g. 8-bit software or 32-bit hardware), it could also lead to leakage models that are simple to exploit. Eventually, non-profiled security evaluations are typically misleading when randomizationbased countermeasures such as masking are combined with the difficulty to make sound assumptions on the leakage model. Hence, developing new tools to get rid of this limitation, or showing that no such tools actually exist, is an important challenge for evaluating the security of future embedded cryptographic devices.

Рекомендации, список литературы

  1. Paul C. Kocher, Joshua Jaffe, and Benjamin Jun. Differential power analysis. In CRYPTO, pages 388–397, 1999.
  2. 2,0 2,1 Stefan Mangard, Elisabeth Oswald, and Thomas Popp. Power Analysis Attacks: Revealing the Secrets of Smart Cards. Springer, 2007.
  3. 3,0 3,1 Stefan Mangard, Elisabeth Oswald, and Thomas Popp. Power Analysis Attacks: Revealing the Secrets of Smart Cards. Springer, 2007.
  4. 4,0 4,1 4,2 Francois-Xavier Standaert, Tal Malkin, and Moti Yung. A unified framework for the analysis of side-channel key recovery attacks. In Antoine Joux, editor, EU- ROCRYPT, volume 5479 of Lecture Notes in Computer Science, pages 443–461. Springer, 2009.
  5. 5,0 5,1 Eric Brier, Christophe Clavier, and Francis Olivier. Correlation power analysis with a leakage model. In Marc Joye and Jean-Jacques Quisquater, editors, CHES, volume 3156 of Lecture Notes in Computer Science, pages 16–29. Springer, 2004.
  6. 6,0 6,1 Werner Schindler, Kerstin Lemke, and Christof Paar. A stochastic model for dif- ferential side channel cryptanalysis. In Rao and Sunar [22], pages 30–46.
  7. 7,0 7,1 Julien Doget, Emmanuel Prouff, Matthieu Rivain, and Fran ̧cois-Xavier Standaert. Univariate side channel attacks and leakage modeling. In COSADE, pages 1–15, Darmstadt, Germany, February 2011.
  8. 8,0 8,1 8,2 Benedikt Gierlichs, Lejla Batina, Pim Tuyls, and Bart Preneel. Mutual information analysis. In Elisabeth Oswald and Pankaj Rohatgi, editors, CHES, volume 5154 of Lecture Notes in Computer Science, pages 426–442. Springer, 2008.
  9. 9,0 9,1 Nicolas Veyrat-Charvillon and Fran ̧cois-Xavier Standaert. Mutual information analysis: How, when and why? In Christophe Clavier and Kris Gaj, editors, CHES, volume 5747 of Lecture Notes in Computer Science, pages 429–443. Springer, 2009.
  10. 10,0 10,1 10,2 Emmanuel Prouff, Matthieu Rivain, and R ́egis Bevan. Statistical analysis of second order differential power analysis. IEEE Trans. Computers, 58(6):799–811, 2009.
  11. 11,0 11,1 Mathieu Renauld, Franc ̧ois-Xavier Standaert, Nicolas Veyrat-Charvillon, Dina Kamel, and Denis Flandre. A formal study of power variability issues and side- channel attacks for nanoscale devices. In Kenneth G. Paterson, editor, EURO- CRYPT, volume 6632 of Lecture Notes in Computer Science, pages 109–128. Springer, 2011.
  12. Suresh Chari, Charanjit S. Jutla, Josyula R. Rao, and Pankaj Rohatgi. Towards sound approaches to counteract power-analysis attacks. In Michael J. Wiener, editor, CRYPTO, volume 1666 of Lecture Notes in Computer Science, pages 398– 412. Springer, 1999.
  13. Louis Goubin and Jacques Patarin. Des and differential power analysis (the ”du- plication” method). In C ̧etin Kaya Koc ̧ and Christof Paar, editors, CHES, volume 1717 of Lecture Notes in Computer Science, pages 158–172. Springer, 1999.
  14. Thomas S. Messerges. Using second-order power analysis to attack dpa resistant software. In C ̧etin Kaya Koc ̧ and Christof Paar, editors, CHES, volume 1965 of Lecture Notes in Computer Science, pages 238–251. Springer, 2000.
  15. 15,0 15,1 Emmanuel Prouff, Matthieu Rivain, and R ́egis Bevan. Statistical analysis of second order differential power analysis. IEEE Trans. Computers, 58(6):799–811, 2009.
  16. 16,0 16,1 16,2 16,3 16,4 Franc ̧ois-Xavier Standaert, Nicolas Veyrat-Charvillon, Elisabeth Oswald, Benedikt Gierlichs, Marcel Medwed, Markus Kasper, and Stefan Mangard. The world is not enough: Another look on second-order dpa. In Masayuki Abe, editor, ASIACRYPT, volume 6477 of Lecture Notes in Computer Science, pages 112–129. Springer, 2010.
  17. Kerstin Lemke-Rust and Christof Paar. Analyzing side channel leakage of masked implementations with stochastic methods. In Joachim Biskup and Javier Lopez, editors, ESORICS, volume 4734 of Lecture Notes in Computer Science, pages 454– 468. Springer, 2007.
  18. 18,0 18,1 Lejla Batina, Benedikt Gierlichs, Emmanuel Prouff, Matthieu Rivain, Fran ̧cois- Xavier Standaert, and Nicolas Veyrat-Charvillon. Mutual information analysis: a comprehensive study. J. Cryptology, 24(2):269–291, 2011.
  19. BenediktGierlichs,LejlaBatina,BartPreneel,andIngridVerbauwhede.Revisiting higher-order dpa attacks:. In Josef Pieprzyk, editor, CT-RSA, volume 5985 of Lecture Notes in Computer Science, pages 221–234. Springer, 2010.
  20. Alexandre Venelli. E cient entropy estimation for mutual information analysis using b-splines. In Pierangela Samarati, Michael Tunstall, Joachim Posegga, Kon- stantinos Markantonakis, and Damien Sauveron, editors, WISTP, volume 6033 of Lecture Notes in Computer Science, pages 17–30. Springer, 2010.
  21. Roger B. Nelsen. An Introduction to Copulas (Lecture Notes in Statistics).Springer, 1 edition, October 1998.
  22. Carolyn Whitnall and Elisabeth Oswald. A comprehensive evaluation of mutual information analysis using a fair evaluation framework. To appear in the proceed- ings of Crypto 2011, Lecture Notes in Computer Science, vol xxxx, pp yyy-zzz, Santa Barbara, California, USA, August 2011.
  23. Matthieu Rivain, Emmanuelle Dottax, and Emmanuel Prou↵. Block ciphers imple- mentations provably secure against second order side channel analysis. In Kaisa Nyberg, editor, FSE, volume 5086 of Lecture Notes in Computer Science, pages 127–143. Springer, 2008.
  24. Ronald Pyke. Spacings revisited. In Proceedings of the Sixth Berkeley Sympo- sium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. I: Theory of statistics, pages 417–427, Berkeley, Calif., 1972. Univ. California Press.
  25. Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statis- tical Learning, chapter 6. Springer Series in Statistics. Springer New York Inc., New York, NY, USA, 2001.
  26. Ilham Hassoune, Francois Mace, Denis Flandre, and Jean-Didier Legat. Dynamic differential self-timed logic families for robust and low-power security ics. Integration, the VLSI Journal, Volume 40, Issue 3, April 2007, Pages 355-364.
  27. David W Scott. On optimal and data-based histograms. Biometrika, volume 66, issue 3, pp 605-610, 1979.
  28. Stefan Mangard, Norbert Pramstaller, and Elisabeth Oswald. Successfully attack- ing masked aes hardware implementations. In Rao and Sunar [22], pages 157–171.
  29. Carolyn Whitnall. An information theoretic assessment of first-order mia. First year PhD report, University of Bristol, 2010.
  30. Nicolas Veyrat-Charvillon and Franois-Xavier Standaert. Generic side-channel dis- tinguishers: Improvements and limitations. Cryptology ePrint Archive, Report 2011/149, 2011. http://eprint.iacr.org/.
  31. Mathieu Renauld, Dina Kamel, Francois-Xavier Standaert, and Denis Flandre. Scaling trends for dual rail logic styles. Preprint, 2011.