A Vulnerability in RSA Implementations Due to Instruction Cache Analysis and Its Demonstration on OpenSSL
A Vulnerability in RSA Implementations Due to Instruction Cache Analysis and Its Demonstration on OpenSSL
复制标题
DOI：
10.1007/978-3-540-79263-5_16
复制
发表时间：
2008-04
期刊：
影响因子：
5.9
通讯作者：
O. Aciiçmez;W. Schindler
中科院分区：
文献类型：
--
作者：
O. Aciiçmez;W. Schindler
微体系结构分析（MA）技术，更具体地说是简单分支预测分析（SBPA）和指令缓存分析，具有揭示软件实现的密码系统的整个执行流程的潜力（[5，2]）。在本文中，我们将证明，即使最安全的配置已经到位，也可以在原始的未修补OpenSSL版本（v.0.9.8e）中完全破解RSA，包括针对侧通道和微体系结构分析的所有对策（特别是基础盲化）。我们还讨论了（已知的）对策，防止这种攻击。在第一步中，我们应用指令缓存攻击，以揭示哪些蒙哥马利操作需要额外的减少。为了利用这些信息，我们模拟的随机过程的模幂算法的时序行为。它的分析提供了最佳猜测策略，该策略揭示了秘密密钥（modp 1），并最终揭示了RSA模n =p1p2的因式分解。对于指令缓存攻击，我们应用了一个嵌入在目标进程（OpenSSL）中的间谍进程，这显然有利于实验部分。这种简化并没有使我们的结果无效，因为在缓存攻击中，来自嵌入式间谍进程和（适当实现的）独立间谍进程的经验结果彼此非常接近[16]，此外，我们的猜测策略是容错的。有趣的是，我们的攻击的第二步与智能卡上的特定组合功率和定时攻击有关[23]（另请参见[27，22]）。在我们发布我们的结果[1]之前，我们通知了OpenSSL开发团队，他们将补丁包含到v.0.9.7e的稳定分支（[31，32]）和CERT中，并通知了软件供应商（[33，34，35]）。特别是，此对策包含在当前版本0.9.8f中。我们只分析了OpenSSL，因此我们目前不知道其他加密库的强度。
MicroArchitectural Analysis (MA) techniques, more specifically Simple Branch Prediction Analysis (SBPA) and Instruction Cache Analysis, have the potential of disclosing the entire execution flow of a software-implemented cryptosystem ([5,2]). In this paper we will show that one can completely break RSA in the originalunpatchedOpenSSL version (v.0.9.8e) even if the most secure configuration is in place, including all countermeasures against side-channel and MicroArchitectural analysis (in particular, base blinding). We also discuss (known) countermeasures that prevent this attack.In a first step we apply an instruction cache attack to reveal which Montgomery operations require extra reductions. To exploit this information we model the timing behavior of the modular exponentiation algorithm by a stochastic process. Its analysis provides the optimal guessing strategy, which reveals the secret key (modp1) and finally the factorization of the RSA modulusn=p1p2. For the instruction cache attack we applied a spy process that was embedded in the target process (OpenSSL), which clearly facilitates the experimental part. This simplification yet does not nullify our results since in cache attacks empirical results from embedded spy processes and (suitably implemented) stand-alone spy processes are very close to each other [16] and, moreover, our guessing strategy is fault-tolerant. Interestingly, the second step of our attack is related to that of a particular combined power and timing attack on smart cards [23] (see also [27,22]).Before we published our result [1] we informed the OpenSSL development team who included a patch into the stable branch of v.0.9.7e ([31,32]) and CERT which informed software vendors ([33,34,35]). In particular, this countermeasure is included in the current version 0.9.8f. We have only analyzed OpenSSL, thus we currently do not know the strength of other cryptographic libraries.