从部分信息中恢复加密密钥(通过一些例子)

发布于 2022-02-07  1027 次阅读






从部分信息中恢复加密密钥(通过一些例子)

从部分信息中恢复加密密钥(通过一些例子)(Recovering cryptographic keys from partial information, by example)

[TOC]

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: 公钥加密系统密钥恢复方法的可视化目录
    table1

2 动机

虽然本教程主要是在更高的数学抽象层次上操作,而不是我们预想的侧通道攻击,但我们将给出一些示例来说明攻击者如何得到有关密钥的剩余部分信息。

模幂运算。我们讨论的所有公钥密码算法都涉及对值进行模幂运算或者椭圆曲线标量加法运算。对于RSA签名,受害者需要计算,其中是私钥指数。对于DSA签名受害者需要计算每个签名的密钥,并计算,其中是公钥对。对于DH密钥交换,受害者生成一个密钥指数,并计算公钥交换值,其中是公钥对。

朴素的模幂运算算法,如平方和乘法,对指数的位进行逐位运算:每次迭代将执行一次平方运算,如果指数的该位为 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算法获得了更好的逼近因子 [NS06]。事实上,LLL 算法将返回格的整个基,其向量很好地近似于格的连续最小值。 就我们的目的而言,我们需要知道的是这些向量非常短,并且对于随机晶格,它们将接近相同的长度。 LLL 算法的当前实现可以很容易地在几百维的格上运行。

为了计算比 LLL 更接近最短向量的近似值,可以使用 BKZ 算法 [Sch87, SE94]。 该算法在块大小中按时间指数运行,这是确定近似因子质量的算法参数。 该算法的理论依据难以表达; 就我们的目的而言,我们只需要知道对于维度低于 100 左右的格,我们可以很容易地计算出,使用 BKZ 算法的启发式随机格中的最短向量,并且通常可以找到最短向量,或者通过使用较小的块大小,“足够好”的近似值。 理论上,LLL 算法等价于使用块大小为 2 的 BKZ。

4 对于RSA的密钥恢复方法

4.1 RSA初步

参数生成。要生成 RSA 密钥对,实现通常从选择公钥指数开始。 到目前为止,最常见的选择是简单地固定。一些实现使用像 3 或 17 这样的小素数。几乎没有实现使用大于 32 位的公钥指数。这意味着涉及小于的暴力破解值的攻击在实践中通常是可行的。

下一步,实现生成两个随机素数,使得互素。公共模数为。私钥指数为

公钥对为,理论上私钥对是,但是实际上很多实现将密钥存储在数据结构中,这就包括了更多信息。例如PKCS#1中,私钥格式包括字段,用CRT来加速加密过程。

加密和签名。在教科书里的 RSA 中,Alice 通过计算将消息加密给 Bob。实际上,消息不是“原始”消息,而是首先使用填充方案从内容转换而来。 网络协议中最常见的加密填充方案是 PKCS#1v1.5,但有时也会在协议中使用或指定 OAEP [BR95]。 为了解密加密的密文,Bob 计算 并验证 m 具有正确的填充。

为了生成数字签名,Bob 首先使用 PKCS#1v1.5 签名填充(最常见)或 PSS(不太常见)等填充方案对他希望签名的消息进行哈希和填充;令是这种形式的哈希和填充消息。 然后 Bob 生成签名为。Alice 可以通过计算值 并验证 是正确的哈希和填充值来验证签名。

由于加密和签名验证只使用公钥,解密和签名生成过程就成为侧信道攻击的典型目标。

RSA-CRT。为了加速解密过程,避免直接计算,实现通常使用中国剩余定理(CRT)。RSA-CRT把分为两个部分,其中

为了在解密中使用CRT,Alice 将计算。消息可以借助预先计算的值 通过计算下式恢复:

这个式子被称为加纳公式(Garner’s formula)[Gar59]。

RSA密钥元素之间的关系。 为了密钥的恢复,我们通常假设攻击者知道公钥。

RSA 密钥具有许多数学结构,我们可以将公钥和私钥的不同组成部分联系在一起,用于密钥恢复算法。 RSA 公钥和私钥是相互关联的:

这个模等式可以通过引入新变量 ,来获得整数关系:

我们知道,于是。虽然攻击者不知道 的值,但是因为通常,所以在实际上暴力枚举所有可能的 值是有效的。

对于针对CRT系数的​攻击,我们可以获得类似的关系:对于某些整数

暴力破解两个独立的 16 位值可能会很麻烦,但我们可以将 关联如下:重新整理这两个关系,我们得到

相乘得到 (原paper这里几个式子的符号有误)

对上式模

因此,给定 的值,我们可以求解 的唯一值,于是对于需要暴力破解 值的应用程序,我们只需要暴力破解最多 对。

乘数 k 也与这些值也有很好的关系。将等式 1 中的关系相乘,我们有

进行替换,同时对式子模 ,我们就可以将系数表示成:

当公钥 已知时,任何密钥值 都足以计算所有其他值。

计算其他值很简单。对于小的 可以从 计算得到分解:

乘数 可以通过 舍入来恢复。一旦 已知,等式 3 就可以变形用于求解 知道后,我们就有 ,于是 就可以通过计算 分解。

很小时, 可以从 ​ 计算得到(其中 可以从 1 到 枚举得到)

未知且太大而无法枚举,那么对于任意的 ,有

通过 分解更为复杂。 如 [HS09] 中所述, 满足 ,并且可以使用 Coppersmith 方法恢复 ,如下所述。

4.2 已知连续位的 RSA 密钥恢复

本节将介绍在已知密钥的大部分连续位时恢复 RSA 私钥的方法。 在这种情况下使用的主要方法是格基规约。

对于本节中的密钥恢复问题,我们通常可以恢复未知密钥值( )的一大块未知位。 我们通常假设攻击者知道公钥 但没有任何其他辅助信息(例如,

在涉及噪声测量的侧信道中,不太可能出现密钥的大量连续部分信息。但在从内存中读取密钥,并在可识别区域损坏的情况下,可能会出现这类情况。 如果为恢复已知位付出了巨大代价,它们还可以帮助提高攻击效率。

4.2.1 热身:对具有不良填充的低指数 RSA 的格攻击

用于连续位 RSA 密钥恢复的主要算法是通过找到整数模多项式的小根来描述问题,然后使用格基规约来解决这个问题。

为了介绍使用格基规约来求多项式根的主要工具,我们将从一个说明性示例开始,以说明使用已知填充攻击小指数 RSA 的具体应用。 在后面的部分中,我们将说明如何优化这种方法,以涵盖不同的 RSA 密钥恢复场景。

这个问题的最初表述是由 Coppersmith [Cop96] 提出的。 Howgrave-Graham [HG97] 给出了一种我们发现更容易阐释并更容易实现的方法。 May 的研究 [May10] 包含了对 Coppersmith/Howgrave-Graham 算法的详细描述。

为了解决这个问题,我们假设有一个整数 和一个 次多项式 ,其有根 ,即 。我们希望找到这样的 。 找到多项式的根就可以有效地模素数 [LLL82],所以如果 是素数或 的素数分解已知,这个问题很容易解决。 当 N 的素数分解未知时,Coppersmith/Howgrave-Graham 方法很有趣:它提供了一种有效的算法来寻找未知分解的模数 的所有小根(如果它们存在)。

问题设定。 对于我们的简单示例,我们将使用96位RSA模数

。考虑一个损坏的 PKCS#1v1.5-esque RSA 加密填充方案,它将消息 m 填充为

现在假设我们得到了一个密文

我们希望恢复未知消息

  • Figure 1

    图1:低指数 RSA 消息恢复攻击条件的图示。 攻击者在加密之前知道模数 、密文 和填充在未知消息 之前的填充 。 攻击者希望恢复

将问题转换为找到多项式的根。

为已知的填充字符串(偏移到正确的字节位置)。我们也知道消息的长度;在这种情况下,。因此我们对于某个未知的 ,有 。令 ;由于我们已经设定了系数,所以我们希望找到一个多项式小根满足 ,多项式化简如下

(这里已经对所有系数模

构造格。 的系数为 。 设 是根 ​ 大小的上限。 我们构造矩阵

然后我们将 LLL 算法应用于矩阵。 规约基的最短向量是

从格中提取多项式并找到它的根。 然后我们构造多项式

多项式 有一个整数根 0x42,这就是 的解。

这种特定的 4 × 4 格结构可以找到最大为 的根。对于我们在示例中使用的小密钥,它仅为16位,但由于求解值直接与模数大小成比例,相同的格结构足以用1024位RSA模数得到170比特的消息,或者用2048位RSA模数得到341比特的消息。当然,4×4格基上的格基规约是非常快的。

更详细的阐释。 为什么能解出结果? 该矩阵的行对应于多项式的系数向量 。我们知道,在 处计算的这些多项式中的每一个都将模 余0。每一列都按 的幂进行缩放,因此该格中任何向量的1 - 范数都是在 处计算的相应(未缩放)多项式值的上界。对于格中向量 ,对任意

我们已经构造了格子,因此我们从中提取的每个多项式 都具有 的性质。我们还构造了格子,使得在约简基中的最短向量的长度将小于 。 能让 小于 的唯一整数倍数是 0,因此通过构造,对应于这个短向量的多项式在整数上满足 ,而不仅仅是模 。由于找到多项式的根(整数,有理数, 实数和复数)可以在多项式时间内完成,我们可以计算这个多项式的根,并检查其中哪一个是我们想要的解。

如果格子构造正确,此方法始终有效。 也就是说,我们需要确保简化的基将包含一个长度小于 的向量。对于这个例子, 。于是,LLL算法将会找到一个向量,其 2 - 范数为 。我们赞数忽略 这个因数,以及 2 - 范数和 1 - 范数之间的差异。那么我们希望满足的条件就是

例如,我们有 。不等式对 求解,我们得到 。在上面的例子中, 为96比特, 为16比特,因此条件满足。

这个条件可以被扩展为 ,其中 是在使用更高维的格后多项式 的指数。Howgrave-Graham 的论文 [HG] 和 May 的研究 [May10] 对这种方法进行了详细的阐释和改进。

4.2.2 已知 的连续位进行因式分解。

在本节中,我们将说明:如果已知一个因数的大部分连续位(不失一般性 ),如何使用格来分解 RSA 模数

  • 图2

    图 2:已知 的连续高位,对 进行因式分解。

Coppersmith 在 [Cop96] 中解决了这个问题,但我们发现 Howgrave-Graham 将其重新表述为“近似整数公约数”[HG01]后,更易于应用,我们将在此处给出构造。

问题设定。 是具有相同比特的 ​ 的 RSA 模数。 为了适合页面显示,选择一个足够小数字,我们有一个 240 位 RSA 模数

假设 已知,假设我们知道 的大量连续 比特高位,因此 ,其中 未知,但是我们知道 。这里我们令 是未知比特,或者等价于已知位的左移量。

我们知道 很小,并且特别的,对于某个已知界 ,有,这里

构造格。 我们可以构造格基如下

然后对格基 使用LLL算法。令 是规约基的最短向量。在我们的例子中,我们得到向量

从格中提取多项式并找到它的根。 我们构造多项式 。在我们的例子中

我们可以计算 的根,在此例子中,它有一个整数根 ,然后我们可以重写 并验证 的因数。

这个 3 × 3 格子适用于任何 ,并随着 的增加直接减小。 在我们的例子中,我们选择120位的 ,而 有 30 位。 但是,同样的格可以从 1024 位 RSA 模数的 512 位因数中恢复 170 位,或从 2048 位 RSA 模数的 1024 位因数中恢复 341 位。

更详细的阐释。 该矩阵的行对应于多项式的系数向量 。我们知道当 时 计算这些多项式的值都是模 余0,因此每个多项式对应的向量都有这个性质。 与前面的例子一样,每一列都按 的幂进行缩放,因此该格中任何向量的 1 - 范数都是在 处计算的相应(未缩放)多项式的值的上限。

如果我们可以在格中找到一个长度小于 的向量,那么它对应的多项式 ,必须满足 。 因为通过构造,我们有,于是 是整数解。

我们计算格的行列式,来验证它是否包含这样小的向量。对于本例,,这就说明我们需要 。对 qiujie ,得到条件 。对于一个RSA模数我们有 ,所以有

该方法通过增加格的维度,在极限处达到 。 这是通过取 的更高倍数来实现的。有关如何操作的详细信息,请参阅 Howgrave-Graham 的论文 [HG] 和 May 的研究 [May10]。

4.2.3 从 的最低有效位恢复 RSA 密钥

采用上面的方法,来处理 的最低有效位中的未知位块也很简单:如果块从第 位开始,则输入多项式为 。多项式可以乘以 ,然后完全按照上面的方法求解。

  • 图3

    图3:已知 的最低有效位,对