A Comprehensive Evaluation of Mutual Information Analysis Using a Fair Evaluation Framework
Carolyn Whitnall and Elisabeth Oswald
University of Bristol, Department of Computer Science, Merchant Venturers Building, Woodland Road Bristol, UK
Abstract： The resistance of cryptographic implementations to sidechannel analysis is a matter of considerable interest to those concerned with information security. It is particularly desirable to identify the attack methodology (e.g. differential power analysis using correlation or distance-of-means as the distinguisher) able to produce the best results. Such attempts are complicated by the many and varied factors contributing to attack success: the device power consumption characteristics, an attackerrsquo;s power model, the distinguisher by which measurements and model predictions are compared, the quality of the estimations, and so on. Previous work has delivered partial answers for certain restricted scenarios. In this paper we assess the effectiveness of mutual informationbased differential power analysis within a generic and comprehensive evaluation framework. Complementary to existing work, we present several notions/characterisations of attack success with direct implications for the amount of data required. We are thus able to identify scenarios in which mutual information offers performance advantages over other distinguishers. Furthermore we observe an interesting feature—unique to the mutual information based distinguisher—resembling a type of stochastic resonance, which could potentially enhance the effectiveness of such attacks over other methods in certain noisy scenarios.
Keywords: side channel analysis, mutual information.
1 Introduction
Side-channel analysis (SCA) refers to a collection of cryptanalytic techniques for extracting secret information from the physical leakage of a device as it executes a cryptographic algorithm. Of the various types, one of the most popularly studied is differential power analysis (DPA); it involves applying some type of statistic (the distinguisher ) to identify a correct hypothesis about (part of) the secret key from the set of all possible hypotheses about this key. Popular distinguisher choices are the Pearson correlation coefficient and the distance-of-means test. Mutual information (MI) measures the total dependency between two random variables, and was first proposed for use in DPA at CHES 2008 [6]. A priori it was expected to display certain advantages over other distinguishers, loosely summarized by three (informal) conjectures:
1. By comprehensively exploiting all of the information contained within trace measurements it could have an efficiency advantage over existing side-channel distinguishers such as correlation (which measures linear dependencies only).
2. By capturing total dependency between the true device leakage and the modeled leakage it could prove effective in scenarios where an accurate model for the data-dependent leakage of the device is not known, thereby serving as a lsquo;genericrsquo; distinguisher.
3. By natural extension to multivariate statistics it might be adapted to the context of higher-order attacks against (for example) protected implementations. Existing distinguishers operate on univariate data only and therefore require trace data to be pre-processed, resulting in loss of information.
Subsequent investigations such as [1,17,20,23] have found little evidence of the first two expectations being met in practice (there is rather more support for the third—see, for example, [1,5,17]). However, the literature has not been comprehensive in explaining why this might be. We must bear in mind that many factors influence DPA outcomes: not only the choice of distinguisher, but also the target intermediate function, the form of the data-dependent device leakage and how well this can be modeled, and the precision with which the distinguishing vector can be estimated using the resources and capabilities available. It is often unclear whether the observed underperformance of MI-based DPA is an inherent theoretical weakness of the distinguisher, a result of sub-optimal estimation procedures, or simply a failure to identify scenarios (i.e. combinations of target functions and power consumption patterns) where it offers a useful advantage: see Batina et al. [1] for an overview of these issues.
In this paper we introduce a framework for assessing and comparing DPA attacks in any given scenario on a theoretical basis, abstracting away from the problem of practical estimation. We use this to gain fresh insight into the findings of the existing literature and to clarify when and in what sense the a priori intuition regarding MI-based DPA does hold. Moreover, we are able to identify and describe attack scenarios in which MI-based DPA is theoretically successful whilst other distinguishers fail, or in which it displays a theoretic advantage large enough to potentially translate to a practical advantage. Further, we demonstrate that the (standardised) MI-based distinguishing vector exhibits the property of stochastic resonance as the noise levels in the power consumption vary. This feature, which is not shared by correlation-based DPA, could potentially be exploited to enhance MI-based attacks via noise injection.
In what follows, we first give the relevant preliminary information on DPA attacks, including details of particular distinguishers and a discussion of previous work in Sect. 2. In Sect. 3 we describe our methodology, whilst Sect. 4 reports on our findings as they relate to various attack scenarios. We conclude in Sect. 5.
2 DPA Attacks
We consider a lsquo;standard DPA attackrsquo; scenario such as defined in [13]: The power consumption L of the target device depends on some internal value (or state) fklowast; (x): a function of some part of the plaintext x isin; X, as well as some part
剩余内容已隐藏，支付完成后下载完整资料
利用公平评估框架综合评估互信息分析
卡罗琳惠特纳和伊丽莎白奥斯瓦尔德
英国布里斯托尔伍德兰路商业风险投资大厦布里斯托大学计算机科学系
摘要：密码实现对侧道分析的阻力对于与信息安全有关的人来说是非常感兴趣的问题。特别需要确定攻击方法(例如，使用相关性或远程手段作为区分方法的差异功率分析)能够产生最好的结果。这样的尝试是复杂的，因为许多因素导致了攻击成功:设备的功耗特征，攻击者的动力模型，通过测量和模型预测来比较的区别，估计的质量，等等。之前的工作已经为某些受限的场景提供了部分答案。本文在一个通用的综合评价框架中，评估了基于信息的差异功率分析的有效性。对现有工作的补充，我们提出了一些关于攻击成功的概念/特征，并直接影响所需的数据量。因此，我们能够识别出在哪些情况下，互信息比其他信息提供了性能优势。此外，我们还观察到一种有趣的特性，这种特性是基于相互信息的，类似于一种随机共振，这可能会在某些噪声环境下提高对其他方法的攻击的有效性。
关键词：侧通道分析 互信息
介绍
侧通道分析(SCA)指的是一种密码分析技术，用于从设备的物理泄漏中提取秘密信息，因为它执行一种加密算法。在各种类型中，最常见的研究之一是差分功率分析(DPA);它涉及应用某种统计量(区分者)来确定关于这个关键的所有可能假设集合中的一个正确的假设(部分)。流行的区分选择是比尔森相关系数和距离均值检验。互信息(MI)测量两个随机变量之间的总依赖关系，并首次提出在2008年的DPA中使用[6]。预计它将显示出比其他区别更大的优势，粗略地总结为三个(非正式)推测:
1．通过综合利用跟踪测量中包含的所有信息，它可以比现有的边通道区分(仅度量线性依赖关系)具有效率优势。
2．通过捕获真正的设备泄漏和模型泄漏之间的完全依赖关系，可以证明在不知道设备的数据依赖泄漏的精确模型的情况下是有效的，从而充当“通用”的区别。
3．通过对多变量统计的自然扩展，它可以适应针对(例如)受保护的实现的高阶攻击的上下文。现有的区分只对单变量数据进行操作，因此需要对跟踪数据进行预处理，从而导致信息的丢失。
随后的调查，如[1,17,20,23]，几乎没有发现在实践中遇到的前两种期望(例如，对第三类的支持更多，例如，[1,5,17])。然而，文献并没有全面解释为什么会这样。我们必须记住,许多因素影响分区结果:不仅器材的选择,而且目标中间函数,视设备泄漏的形式和如何建模,这和区分向量的精度可以使用可用的资源与能力的估计。我们通常不清楚的是，基于互信息的DPA的表现是一个明显的理论弱点，这是不合理的评估过程的结果，或者仅仅是一个错误的结果，它提供了一个有用的优势，即目标函数和能量消费模式的组合，它提供了一个有用的优势，这就是对这些问题的概述。
本文介绍了一种基于理论基础的在任意给定场景中对DPA攻击进行评估和比较的框架，并从实际估计的问题上进行了抽象。我们利用这一点来获得对现有文献的发现的新见解，并在什么时候和什么意义上阐明基于互信息的DPA的先验直觉是成立的。此外，我们能够识别和描述基于互信息的DPA在理论上成功的攻击场景，而其他的区分失败，或者它显示了足够大的理论上的优势，从而有可能转化为实际的优势。此外，我们还证明了(标准化的)基于互信息的区分向量具有随机共振的性质，因为能量消耗的噪声水平各不相同。这一特性不被基于关联的DPA共享，可能被利用来通过噪声注入增强基于互信息的攻击。
在接下来的内容中，我们首先给出了有关DPA攻击的相关的初步信息，包括具体的区分者的详细信息，以及对以前工作的讨论。在第3节中，我们描述了我们的方法，而第4节则是关于我们的发现的报告，因为它们与各种攻击场景有关。我们在第5节结束。
DPA攻击
我们考虑一个“标准DPA攻击”的场景,如[13]中定义:目标设备的功耗L取决于一些内部价值(或状态) fklowast; (x):一个函数的明文isin;x的一部分,以及一些秘密密钥的一部分klowast;isin;k .因此,我们有t L = L ◦ fklowast; (x) ε, L是一些函数描述了视组件和ε由剩下的功耗,可以建模为独立的随机噪声。攻击者有N个功率测量相应的N已知明文的加密xiisin;X, i= 1,hellip;hellip;,N和希望恢复密钥klowast;。攻击者可以准确地计算出内部的值将在每个关键假设 {fk(xi)}N i=1, k isin; K 和使用他具有的真正的泄漏函数L构造一个模型M的任何信息。
DPA利用了一个事实，即与正确的关键假设相对应的建模的电源跟踪应该更像真实的电源跟踪，而不是与不正确的假设相对应的模型跟踪。因此，攻击者关注于量化和比较每个关键假设的真实和建模跟踪之间的相似性程度。有一系列的比较工具——“区分者”——是可用的，其中相互信息和皮尔逊相关系数都是很受欢迎的例子。我们将在本节的其余部分中更详细地介绍这些内容。我们使用速记CPA和MIA来分别指代基于关联和基于互信息的DPA攻击。
DPA攻击的成功和效率的推理。
以前的工作已经取得了一些进展，为DPA攻击的“成功”和“效率”提供了有意义和实际的相关定义。Standaert的作品将“键恢复成功”的概念形式化了(相应的，成功率)，这是我们为我们的目的所采用的:理论攻击的区别在于当明文输入X根据已知的分布(通常是一致的)在X中取值时D = {D(k)}kisin;K = {D(L ◦ fklowast; (X) ε, M ◦ fk(X))} kisin;K。如果D(klowast;)gt; D(k)lowast;forall;k = k我们能说这次袭击理论上是成功的。
由于我们对L对攻击结果的影响特别感兴趣，所以我们希望从噪声的影响和估计过程中抽象出来。如果在理论上成功的无噪声的情况下，我们定义了一个区分者。
理想的成功因此取决于目标中间函数,视设备泄漏的形式,集sube;X的明文加密,和权力的选择模型和器材。理论进一步成功是取决于噪声的大小和分布ε而实用的成功还取决于选择器材及估计量的跟踪测量的数量n,给定一个攻击,理论上区分正确的键(一定规模的比例),实际结果将由攻击者是否有足够的资源来估计Dcirc;足够精确地检测不同的大小。
DPA攻击的区别
Standaert等提供了一个很好的概述，从DPA在20世纪90年代末首次引入以来，在文献中使用了许多不同的区别。在本文中，我们将重点放在相互信息上，并将其与另一个感兴趣的区别:Pearson的相关系数。
在最近的研究中，Mangard等人已经表明，在标准的DPA攻击的场景中，三种最受欢迎的区分方法，Pearson相关性，方法的距离，以及Bayes，都同样成功。在附加的、强有力的假设条件下，MI可以被估计为高斯混合，它们甚至能够证明基于关联的和基于MI的区分之间的映射。我们的工作涉及更广泛的分布假设。
互信息
互信息以比特度量，两个随机变量X和Y之间共享的信息。最直观的表达方式是通过Shannon的公式:I(X;Y)= H(X)minus;H(X | Y)。
相互信息是概率分布的函数，而估计是一个研究较多的问题，没有简单的答案[3,8,14,19,22]。所有的估计量都是偏置的，而且不存在“理想”的估计量;根据数据的底层结构，不同的估计器执行方式不同。
通常的方法是先估计底层的边缘和条件密度，然后通过一个“插件”的离散熵估计器将它们代入香农的公式。有许多不同的方法来估计密度，因此对MI的结果估计量的质量对所选择的方法和参数非常敏感。如果我们对底层的分布有一个很好的理解，我们可以使用一个参数模型，比如高斯混合。然而，由于MIA已经被提议用于我们通常的假设不存在的场景中，我们通常对非参数方法更感兴趣，而非参数方法对用户方法有些敏感，并且在估算成本方面会引起开销。实际上，由于大样本空间和小数据集，我们通常通过空间的m-bin正则化来估计密度。通过一个重要的数据处理不平等，这意味着我们总是在评估相互信息的下界，当binning或mesh变得更精细时，估计从下面单调地接近真实的相互信息。
在安全评估中，我们通常希望能够谈论攻击成功所需的跟踪数量。这就要求在合理的假设下，要知道区分者的抽样分布。不幸的是，对于MI的估计数不像其他统计数据那样“表现良好”(如相关系数，见下文);事实上，没有统一的收敛速率，所以无论我们选择什么估计量，我们总能找到一个分布，误差会任意地慢慢消失。
在存在噪声的情况下，理想MI和理论MI之间的关系是复杂的(例如，[11])。特别是,当I(X ε;I(Y)le;X;Y)(X,ε独立),然而I(X;Y)minus;I(X ε;Y)=I(X,Z)minus;(X ε;Z)。因此，理论上的MIA向量的元素受到不同的影响，因此理想的结果不能直接在噪声存在的情况下对理论结果进行概括。
皮尔森相关系数
Pearson的相关系数测量了两个随机变量X和Y之间的总线性依赖关系。它被定义为rho;(X,Y)= X(X,Y)sigma;Xsigma;Y。它取从-1到1的值，和互信息一样，当X和Y是独立的时，它是零。然而，反过来却不是真的;也就是说，X和Y可能是(非线性的)依赖于(线性)0的相关关系。
通过样本相关系数:r(X, Y) = N i=1(xi X) N i=1(xi X)2 N i=1(yi Y)2。这是一个一致的估计量(X, Y)，而且，如果X和Y有一个联合正态分布，它是渐近无偏和有效的。在相同的假设条件下，我们甚至可以近似于抽样分布，从而得出“nice”的结果，例如攻击所需的跟踪测量的数量。
在噪声存在时，理想相关性与理论相关性之间的关系是直接的。事实上,正如6.3章,rho;(L ε,Mk)=rho;(L,Mk)1 sigma;2εVar(L)。因此，噪声越大，相关性越小。但是，分母不依赖于关键假设;因此，理论上的区别向量是按比例缩放的，从而保留了排名和其他相关特征。这并不意味着实际的CPA攻击对噪声是免疫的:当估计量的样本方差增加时，达到足够精确水平所需的跟踪量也会增加。
3综合评价框架
我们对理想/理论的CPA和MIA向量进行了计算和检验，得到了一个广泛的可能的泄漏场景，其中真实的泄漏L是未知的，通过汉明重(HW)或目标函数输出的原始值(ID)来建模。对于注册会计师,这是一样的假设漏成正比的HW或ID的目标,而对于米娅一样这是允许泄漏为每个不同HW或ID值是不同的,没有任何限制该依赖的特性(例如,它不必是一个单调关系)。这些向量提供了对区分者的相对优势和弱点的洞察。我们特别感兴趣的是，米娅对CPA有一个理想的/理论的优势，因为我们希望一个足够大的理论优势可以转化为一个实际的优势。要做到这一点，我们需要制定一个适当的“优势”概念。
安全评估的一个非常理想的指标是攻击成功所需的跟踪数量。我们可以用统计功率分析的方法来计算给定的估计值，如果抽样分布可以近似，但这在一般情况下是不可能实现的(见第2.2节)，而且我们还在寻求避免与估计相关的比较。我们的解决方案是基于理论向量的这些特征来选择度量方法，它们对实际攻击的跟踪效率具有最大的影响:
1正确的键排序:按不同的值排列正确的键的位置。如果正确的键是并列第一，排序顺序是键共享位置1的数量，因此，按o的排序顺序进行攻击是理论上的成功，如第2.1节中定义的那样。与实际效率的关系是显而易见的:不是一阶成功的攻击将不能唯一地提取正确的密钥。
2平均识别分数:高于(或低于)的标准偏差的数量，与正确的键对应的区别值的平均值。这与“DPA信噪比”的描述相匹配，并指出了隔离正确密钥的攻击的敏感性:一种非常敏感的攻击可能只在少量的跟踪测量中获得成功，因为即使是不精确的估计也能探测到很大的差异。理论上的“不成功”攻击可能仍然能够返回一个小的候选子集，如果平均识别能力很高，则包含正确的密钥。
3最接近竞争对手的区分值: 距离“最近的竞争对手”(即正确的关键区别值和最高等级的替代值之间的差值)，由标准偏差标准化。这代表着，比一般的区分能力更直接，被实际攻击所发现的边缘。
通过计算上述统一绘制的纯文本的方法。Xlarr;unif(X),我们能够比较理论提供完整信息时的攻击行为。我们建议通过检查理想/理论上的攻击向量来减少明文空间的子集，从而探索攻击对受限信息的敏感性。这些向量不仅依赖于大小，还取决于输入集的组成;我们不能对可能子集的整个空间进行详尽的计算(它太大了)，但是通过不断增加大小的随机抽取，我们可以估计攻击成功所需的平均支持大小。因此，我们将以下的措施作为“有多少追溯”问题的进一步线索:
5。平均最小支持:平均而言，攻击所需的输入分布的支持大小，以实现订单成功(o是排名顺序)。
6。支持x%的成功率:成功的成功率(适当的顺序)的支持大小至少是x%。
我们的标准最好是结合在一起，而不是孤立地看待，它们之间的权衡将与实际考虑不同。例如，一种只实现o订单成功(o gt; 1)的方法，如果能够更精确地和/或有效地估计出不同的向量，则可能更适合于实现一阶的成功。同样，在高噪音的情况下，与平均最小支持相比，最接近的可分辨能力可能更重要。
在本研究的某些部分中，更可取的方法是测量一组场景中攻击的平均行为，而不是描述特定场景下的结果。这是相关的，例如，当考虑到足够的任意性的功能时，我们不能详尽地详细说明每一种情况。在这种情况下，如分析限制输入支持，我们使用随机抽样的例子来估计平均行为(注意区分向量本身仍然是计算的，而不是估计的)。
我们承认，数据复杂性并不是成本的唯一衡量标准，计算复杂性等考虑因素也在决定攻击的实用性方面发挥了作用。一项正式的研究超出了本文的范围，但我们确实试图在适当的地方发表评论。
理想/理论与实际的攻击。
回想一下，我们定义了理论上的(以及理想的，即无噪声的)攻击，以从估算过程(和噪声)的影响中抽象出来。因此，理论上的结果依赖于目标中间函数，设备的泄漏(包括有多少噪声)，作为输入的
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[22632]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
