从部分信息中恢复加密密钥(通过一些例子)(Recovering cryptographic keys from partial information, by example)
0 写在前面
0.1 综述
针对密码学的侧信道攻击可能仅泄露有关密钥的部分或间接信息。 本篇文献中有多种技术可用于从部分信息中恢复密钥。 在本文中,我们研究了RSA,(EC)DSA 和 (EC)Diffie-Hellman(当今常用的公钥密码系统)的几个主要部分密钥恢复算法家族。 我们根据攻击者收集到的信息结构对已知的攻击方式进行分类,并为每种攻击方式提供简化示例以说明其背后思想。
0.2 译者想说的
这篇paper目前在国内还没有翻译文本,我自己在翻译之前大致看了一遍这篇paper,感觉和上次翻译的二十年内RSA攻击综述类型相同,都是一篇文章汇总了很多的攻击方式,其中一些攻击方式在最近的CTF比赛中也有出现过,所以就打算翻译这篇paper。当然由于本人能力有限,翻译水平不高,借鉴了一部分机翻,也会在原文的基础上写上一点点自己的看法什么的,各位师傅在阅读的时候如有疑惑或感觉不妥的地方,还请批评教正。原文链接:1506.pdf (iacr.org)
1 引入
- You are dangling in a rope sling hung from the ceiling of a data center in an undisclosed location, high above the laser tripwires crisscrossing the floor. You hold an antenna over the target’s computer, watching the bits of their private key appear one by one on your smartwatch display. Suddenly you hear a scuffling at the door, the soft beep of keypad presses. You’d better get out of there! You pull your emergency release cable and retreat back to the safety of the ventilation 2 duct. Drat! You didn’t have time to get all the bits! Mr. Bond is going to be very disappointed in you. Whatever are you going to do?
(上面是一个很幽默的场景描述,写了一个特工去数据中心窃取私钥时的突发状况,这里翻译了就没内味儿了)
在侧信道攻击中,攻击者利用计算或存储的副作用来窃取表面上的秘密信息。 许多侧信道攻击源于计算机是现实世界中的物理对象这一事实,因此计算可能需要不同的时间 [Koc96],导致功耗变化 [KJJ99],产生电磁辐射 [QS01],或 产生声音 [GST14]、光线 [FH08] 或温度 [HS14] 波动。 泄露信息的具体特征取决于算法的顶层和底层的实现细节,通常还取决于计算机硬件本身:分支条件、错误条件、内存缓存收回行为或电容器放电的具体情况。
已发表文献中关于侧信道攻击的第一项工作并未直接针对密码学 [EL85],但自从 Kocher 在 90 年代开展时序和功率分析方面的工作 [Koc96, KJJ99] 以来,密码学已成为侧信道工作的热门对象。然而,攻击者很少能通过侧信道简单地读取完整的密码密钥。 许多侧信道攻击所揭示的信息通常是间接的或不完整的,甚至可能包含错误。
因此,为了充分了解给定漏洞的性质,侧信道分析师通常需要使用额外的密码分析技术。在这种情况下,密码分析者的主要目标通常是:“我获得了以下类型的关于密钥的不完整信息,它能不能让我可以高效地恢复剩下的密钥?” 不幸的是,没有一个万能的答案:它取决于所使用的特定算法,以及已得到信息的性质。
这项工作的目标是在一个地方收集该领域中一些最有用的技术,并为实践中最常见的场景提供一个合理全面的分类。 也就是说,这是一个非详尽的研究和一个带有引导性例子的具体教程。 该领域的许多算法论文都给出了完全通用的结构,这有时会模糊读者对方法为何有效的直觉。 在这里,我们的目标是提供最少的工作示例来说明每种算法用于简单但不平凡的情况。 我们将重点放在公钥密码学上,特别是目前广泛使用的算法(因此也是最流行的攻击目标):RSA,(EC)DSA 和 (EC)Diffie-Hellman。
在整篇文章中,我们将用如下方式表示已知信息:
本次研究的分类情况见表1。
- Table 1: 公钥加密系统密钥恢复方法的可视化目录
2 动机
虽然本教程主要是在更高的数学抽象层次上操作,而不是我们预想的侧通道攻击,但我们将给出一些示例来说明攻击者如何得到有关密钥的剩余部分信息。
模幂运算。我们讨论的所有公钥密码算法都涉及对值进行模幂运算或者椭圆曲线标量加法运算。对于RSA签名,受害者需要计算
朴素的模幂运算算法,如平方和乘法,对指数的位进行逐位运算:每次迭代将执行一次平方运算,如果指数的该位为 1,则将执行一次乘法运算。 更复杂的模幂运算算法使用非相邻形式(non-adjacent form) (NAF)、窗口非相邻形式(windowed non-adjacent form) (wNAF) [Möl03]、滑动窗口(sliding windows)或Booth recoding [Boo51]进行预先计算,然后对预计算的数字表示进行操作。 [Gor98]。
对模幂的缓存攻击。缓存定时攻击是学术文献 [Pag02, TTMH02, TSS 03, Per05, Ber05, OST06] 中最常被利用的侧信道攻击家族之一。这些攻击有许多变体,但它们都有一个共同点,即攻击者能够在与受害进程位于同一位置并共享 CPU 缓存上的执行代码。当受害者代码执行时,攻击者测量从缓存中的地址加载信息所需的时间,从而推断出受害进程在执行期间,加载到这些缓存地址的数据的信息。在上面讨论的模幂运算或标量加法算法的语境下,如果攻击者可以检测到执行乘法指令的代码是否已加载到其中,那么对易受攻击的实现发起缓存攻击,就可能会反应乘法运算是否在特定比特位置执行缓存。或者,对于一个数的预计算数字表示,攻击者可能用缓存攻击来观察被访问的数字值 [ASK07, AS08, BvSY14]。
对模幂的其他攻击。现在还有一些其他侧信道攻击家族已经用于分析易受攻击的模幂实现,其中就包括功率分析和差分功率分析攻击 [KJJ99, KJJR11]、电磁辐射 [QS01]、声发射 [GST14]、原始时序 [Koc96]、光子发射 [ FH08] 和温度 [HS14]。 这些攻击同样利用代码或电路,其执行因密钥而异。
冷启动和内存攻击。一种完全不同类别的侧信道攻击(可以针对密钥泄露部分信息)包括可能泄露内存内容的攻击。 这其中包括冷启动攻击 [HSH 08]、DMA (Direct Memory Access)(直接内存访问)、Heartbleed 和 Spectre/Meltdown [LSG+18,KHF+19]。 虽然这些攻击可能会泄露不完整的信息,因此可以作为我们讨论的某些算法的理论动机,但这类攻击中的大多数漏洞都可以简单地用于读取任意内存(以几乎完美的精度),并且很少需要密码分析算法。
依赖于长度的攻击。最后一个漏洞类是实现的行为取决于密钥的长度,因此行为的变化可能会泄露有关密钥中高位零的数量信息。 一个简单的例子是将密钥复制到缓冲区中,以显示密钥的位长度。 在另一个例子中,Raccoon 攻击观察到 TLS 版本 1.2 及以下版本在应用密钥派生函数之前从Diffie-Hellman共享密钥中去除高位零,从而导致时间差异取决于密钥长度所需的哈希输入块的数量。 [MBA 20]
3 数学背景
格和格规约算法。我们提出的几种算法都使用格和格算法。我们将陈述一些关于格的事实,但尽量避免过于正式。
出于本文的目的,我们将通过给出一个基矩阵
在几何上,格类似于n维空间中的离散的、可能倾斜的点网格。 这种离散性确保了格中存在最短的向量:格中的向量有一个非无穷小的最小长度,并且至少有一个向量
任意格中的最短向量要想精确计算是 NP困难的,但是 LLL 算法 [LLL82] 能在多项式时间内计算这个最短向量的指数近似值:在最坏的情况下,它将返回一个向量
为了计算比 LLL 更接近最短向量的近似值,可以使用 BKZ 算法 [Sch87, SE94]。 该算法在块大小中按时间指数运行,这是确定近似因子质量的算法参数。 该算法的理论依据难以表达; 就我们的目的而言,我们只需要知道对于维度低于 100 左右的格,我们可以很容易地计算出,使用 BKZ 算法的启发式随机格中的最短向量,并且通常可以找到最短向量,或者通过使用较小的块大小,“足够好”的近似值。 理论上,LLL 算法等价于使用块大小为 2 的 BKZ。
4 对于RSA的密钥恢复方法
4.1 RSA初步
参数生成。要生成 RSA 密钥对,实现通常从选择公钥指数
下一步,实现生成两个随机素数
公钥对为
加密和签名。在教科书里的 RSA 中,Alice 通过计算
为了生成数字签名,Bob 首先使用 PKCS#1v1.5 签名填充(最常见)或 PSS(不太常见)等填充方案对他希望签名的消息进行哈希和填充;令
由于加密和签名验证只使用公钥,解密和签名生成过程就成为侧信道攻击的典型目标。
RSA-CRT。为了加速解密过程,避免直接计算
为了在解密中使用CRT,Alice 将计算
这个式子被称为加纳公式(Garner’s formula)[Gar59]。
RSA密钥元素之间的关系。 为了密钥的恢复,我们通常假设攻击者知道公钥。
RSA 密钥具有许多数学结构,我们可以将公钥和私钥的不同组成部分联系在一起,用于密钥恢复算法。 RSA 公钥和私钥是相互关联的:
这个模等式可以通过引入新变量
我们知道
对于针对CRT系数的
暴力破解两个独立的 16 位值可能会很麻烦,但我们可以将
相乘得到 (原paper这里几个式子的符号有误)
对上式模
因此,给定
乘数 k 也与这些值也有很好的关系。将等式 1 中的关系相乘,我们有
用
当公钥
从
乘数
当
当
通过
4.2 已知连续位的 RSA 密钥恢复
本节将介绍在已知密钥的大部分连续位时恢复 RSA 私钥的方法。 在这种情况下使用的主要方法是格基规约。
对于本节中的密钥恢复问题,我们通常可以恢复未知密钥值(
在涉及噪声测量的侧信道中,不太可能出现密钥的大量连续部分信息。但在从内存中读取密钥,并在可识别区域损坏的情况下,可能会出现这类情况。 如果为恢复已知位付出了巨大代价,它们还可以帮助提高攻击效率。
4.2.1 热身:对具有不良填充的低指数 RSA 的格攻击
用于连续位 RSA 密钥恢复的主要算法是通过找到整数模多项式的小根来描述问题,然后使用格基规约来解决这个问题。
为了介绍使用格基规约来求多项式根的主要工具,我们将从一个说明性示例开始,以说明使用已知填充攻击小指数 RSA 的具体应用。 在后面的部分中,我们将说明如何优化这种方法,以涵盖不同的 RSA 密钥恢复场景。
这个问题的最初表述是由 Coppersmith [Cop96] 提出的。 Howgrave-Graham [HG97] 给出了一种我们发现更容易阐释并更容易实现的方法。 May 的研究 [May10] 包含了对 Coppersmith/Howgrave-Graham 算法的详细描述。
为了解决这个问题,我们假设有一个整数
问题设定。 对于我们的简单示例,我们将使用96位RSA模数
令
现在假设我们得到了一个密文
我们希望恢复未知消息
-
图1:低指数 RSA 消息恢复攻击条件的图示。 攻击者在加密之前知道模数
、密文 和填充在未知消息 之前的填充 。 攻击者希望恢复 。
将问题转换为找到多项式的根。 令
为已知的填充字符串(偏移到正确的字节位置)。我们也知道消息的长度;在这种情况下,
(这里已经对所有系数模
构造格。 令
然后我们将 LLL 算法应用于矩阵。 规约基的最短向量是
从格中提取多项式并找到它的根。 然后我们构造多项式
多项式
这种特定的 4 × 4 格结构可以找到最大为
更详细的阐释。 为什么能解出结果? 该矩阵的行对应于多项式的系数向量
我们已经构造了格子,因此我们从中提取的每个多项式
如果格子构造正确,此方法始终有效。 也就是说,我们需要确保简化的基将包含一个长度小于
例如,我们有
这个条件可以被扩展为
4.2.2 已知 的连续位进行因式分解。
在本节中,我们将说明:如果已知一个因数的大部分连续位(不失一般性
-
图 2:已知
的连续高位,对 进行因式分解。
Coppersmith 在 [Cop96] 中解决了这个问题,但我们发现 Howgrave-Graham 将其重新表述为“近似整数公约数”[HG01]后,更易于应用,我们将在此处给出构造。
问题设定。 令
假设
我们知道
构造格。 我们可以构造格基如下
然后对格基
从格中提取多项式并找到它的根。 我们构造多项式
我们可以计算
这个 3 × 3 格子适用于任何
更详细的阐释。 该矩阵的行对应于多项式的系数向量
如果我们可以在格中找到一个长度小于
我们计算格的行列式,来验证它是否包含这样小的向量。对于本例,
该方法通过增加格的维度,在极限处达到
4.2.3 从 的最低有效位恢复 RSA 密钥
采用上面的方法,来处理