正交格攻击 :Orthogonal Lattice Attack (简记为 OL 攻击)是一类重要的格相关攻击。可用于近似公约数问题 (Approximate Common Divisor abbr. ACD)、隐藏子集和问题(Hidden Subset Sum Problem abbr. HSSP)等困难问题的求解,在密码分析方向有广泛的应用。
正交格攻击
正交格的本质就是核空间(kernel space),求某个(或者多个)向量 的核空间 ,在核空间中进行格规约(LLL 或者 BKZ),从而筛选出具有某种特征的向量组成一个核空间子格的 basis,记为 ,在新的 里面再求核空间回去得到 的一组基,做 BKZ 或者 LLL 规约,恢复目标向量。
OL 攻击方法可以应用在许多密码分析场景下,下面简单阐述 ACD 和 HSSP 场景下 OL 攻击的应用。
近似公约数问题
近似公约数问题(Approximate Common Divisor Problem),记为 ,定义如下,给定一个 -bit 奇数 以及足够多的下面的样例 :
我们想要恢复出 。
部分近似公约数问题,记为 ,区别在于此时 的某个精确的整数倍是给出的,即额外已知 。我们仅考虑 OL 攻击在 上的应用。以下攻击参考论文 Revisiting Orthogonal Lattice Attacks on Approximate Common Divisor Problems and their Applications。
OL 攻击其一
ACD 问题的第一类 OL 攻击,由 van Dijk, Gentry, Halevi 和 Vaikuntanathan 等人提出。给定一个 问题,记已知输出样例为 ,未知的系列参数为 和 ,格 是一个 的矩阵,如下
其中 是一个足够大的数,这样 LLL 或者 BKZ 规约后能够保证短向量的第一维度为 0,即核空间。记 为规约后的基, 足够大,因此在规约后的基中的向量 ,多数( )都满足, 。又 ,也就意味着 , 因此如果我们再筛选出长度比较短的核向量 ,使得 ,也就意味着 在整数环上也成立,进而得到 。也就是说,此时 是正交于 。于是,神奇的事情出现了,我们通过在 的核空间进行筛选,居然能够得到未知向量 和 的正交向量,也就是得到了线性关系。
那么,通过筛选出足够多这样的线性关系,我们能否恢复出 或者 呢?首先注意到。我们寻找的短向量 需要满足下面条件:
- 向量 与向量 垂直。
- 向量 与向量 垂直(足够短即可)。
同时满足上面条件就能满足 和 垂直,因为 是线性相关的。我们寻找的是与向量组 正交的核空间,也就是说最多能够筛选出 个线性无关的向量,它们构成了 的一组基。在 上求核空间回去,能够得到两个向量 ,容易知道 在格空间 中,且 是一个短向量,LLL 或者 BKZ 能够恢复向量 ,进一步恢复出参数 。
Remarks
实际上第一步构造的格 ,就是在整数环上求 ,维度为 ,然后对矩阵 做 LLL 或者 BKZ 规约。
OL 攻击其二
第一种 OL 攻击略显复杂,不够直接,因为我们寻找的是 , 也就是 的核空间,那么利用 的结构,能否直接求 的核空间呢?
基于上述考虑,van Dijk, Gen- try, Halevi 和 Vaikuntanathan 等人提出了第二种 OL 攻击。给定一个 问题,记已知输出样例为 ,未知的系列参数为 和 ,格 是一个 的矩阵,如下
上述格的核心思想就是搜索向量 , 使得它垂直于 , 即有 ,从而 。
格 能找到正交于 向量是因为 ,如果规约得到短向量,意味着 本身会很短(决定 后 维), 从而第一维度不可能含有 的项,也就要求 。否则假设 ,第一维度为 ,因为 都远远小于 ,从而第一维远远大于其他维度的值,这是不太可能的。
至于 里的 ,是为了使得我们的目标向量更加平衡,质量更好,更容易规约得到目标解。
一般来说,对 进行 LLL 规约,得到一组 basis ,我们能够从这组 basis 中取到 组线性无关的短向量 组成 ,它们是正交于向量 的完整核空间。对这 组向量再求核空间,得到的 恰好只有一组向量,即 ,这里有一个前提要求是 的最大公约数为 1,这在 比较大,随机生成的情况下是大概率满足的,否则我们得到的是 。
OL 攻击其三
针对 第三类 OL 攻击和第二类 OL 攻击的核心思路是一样的。记已知输出样例为 ,未知的系列参数为 和 ,格 是一个 的矩阵,如下
此时我们规约得到的目标向量为 ,我们想要向量 正交于 ,因为这意味着 ,将 代入,得到 ,即 是正交于 的向量。
我们简单分析格 为什么能够找到上述短向量, 最后一个行向量里的 本质是作为模数的作用,而由于 ,并且 远远小于 和 ,上面的格本质可以换成 :
在 足够小的情况下下,目标向量 大概率可以视为 。后续求解向量 和第二类 OL 攻击类似。
OL 的优化
针对第三类 OL 攻击的 的优化,额外给出 ,可以定义如下格(参考论文 Fully Homomorphic Encryption over the Integers with Shorter Public Keys 6.2 节,原论文这里应该是有 typo)
其中 表示取模运算。
第一类 OL 攻击的格在论文 Revisiting Orthogonal Lattice Attacks on Approximate Common Divisor Problems and their Applications 3.3 节中提到的优化为:
隐藏子集和问题
Nguyen 和 Stern 在 1999 年美密会上提出了隐藏子集和问题(Hidden Subset Sum Problem),可以用于一些密码算法的分析,并且提出了 Nguyen-Stern 算法,求解 HSSP,并且后续破解了一系列签名、加密算法,。
定义 :令 是一个整数, 为 上的随机整数, 是 m-维随机向量。 满足:
给出 ,恢复出隐藏数集 和对应的向量 。
值得注意的是,对于每个 ,都对应一个大小为 的子集和问题。因此上面的向量给出了 个在相同数集 上的子集和问题,但是数集 也是未知的,因此称为隐藏子集和问题。
HSSP 的 OL 攻击
Nguyen-Stern 算法使用了正交格的思想求解 HSSP 问题。我们考虑在 上正交于向量 的核空间,假设 与 正交,即:
这也就意味着 和向量 在模 意义上垂直。 我们寻找足够短的向量 ,由于 ,这就会导致 很短。我们知道在模 意义下与 正交的核空间中,存在最短的向量,记这个核空间中的最短向量模长为 。此时如果 向量很短,模长远远小于 ,从而 也远远小于 ,即 的模长小于 并且和 正交,那么只能满足 。因此,我们得到的 会在整数环上正交于所有的 向量 。
在 上求向量 的核空间的格如下 (其中 选取得足够大)
假设能够上面的格中得到 个足够小的向量 使得 ,再对 求核空间,得到 的一组 basis ,对这组 basis 做 LLL 或者 BKZ 规约 ,就能恢复出所有的 向量,从而也能恢复出 。
Nguyen-Stern 算法
本节给出标准的 Nguyen-Stern 算法。记:
一个简单算法流程如下:
- 首先在 计算 的一组 LLL-reduced 基 。
- 在这组基中选取最短的 组向量 ,这组基将恰好是 的一组生成基。
- 在整数环上计算 的核空间, 。 ,计算 的一组基 。
- 对这组基 计算 BKZ-reduced 基,筛选这些基,直至满足所有基向量都是二元的,即恢复了 向量。
下图是 Nguyen-Stern 算法中 OL 攻击的部分(即上面的 step1-3,图源自论文 A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem):
Optimized Nguyen-Stern 算法
Jean-S´ebastien Coron 和 Agnese Gini 在论文 A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem 给出了 HSSP 的优化解法。其优化步骤与 OL 攻击无关,而在于最后一步如何恢复 。
Nguyen-Stern 算法恢复 向量并不是简单的。因为 不是其中最短的向量,而是它们的线性组合,比如 就可能比 短。规约得到的向量里的元素会大概率落在 中,而我们的目标向量 向量里的元素只会落在 中。因此 Nguyen-Stern 算法提出将格 转换成 , 其中 ,这意味着元素落入 的向量 ,它在新的格里面对应的短向量是 (加减若干个 不能减少模长),其元素落入 中,而元素只落入 中的向量 ,它在新的格里面对应的短向量 ,其元素会落入 中,有很大概率比前面的向量要短。因此,在新的格 中,我们能够恢复出原始的 向量,而不是它的线性组合。
Jean-S´ebastien Coron 和 Agnese Gini 对 Nguyen-Stern 算法最后 BKZ 规约以恢复 向量的部分进行了修改,即使用线性化、多变元的思想解方程恢复目标向量 。在 Nguyen-Stern 算法中,我们只需要大概 个隐藏子集和样例即可求解, 但是优化后的算法至少需要 个隐藏子集和样例才能解多变元方程。
因此一个现实的问题是,我们不能用算法一直接求 LLL 得到 ,在 时, , 此时维度太大,LLL 的性能极差。甚至在 不是素数,难以分解的时候,核空间的求解都是比较困难的。于是 Jean-S´ebastien Coron 和 Agnese Gini 提出了一个比较巧妙的办法去求解这种非常高维度场景下的 ,每次只对大小为 的格进行 LLL-reduce ,得到完整的 basis 在对应维度上的投影 , 然后选定前 个维度(固定住),把其他各个维度都进行简单转换计算,这样就能以比较简单的方式将多次计算的结果进行合并,得到最后的 。一个概念性的计算流程图如下 :
假设 , ,其中 。每次都使用算法 1 对 这个子向量进行计算 在对应维度的投影,得到 ,但是我们保证每次前 个维度都固定投影为 ,后续就可以将 的 basis 在各个维度的投影组合起来了。将算法 1 的作用表示为一个函数,记为 。则针对 情况下的正交格攻击算法如下:
后续第二步的攻击算法与 OL 攻击无关,由于 都是二元的,即全部元素都落入 中,则有 。然后转换为多变元二次方程组的求解,注意到一般的多变元二次方程组的求解是 NP 困难的,但是利用线性化的思想就能转换为线性方程组求解,因此是简单的,Jean-S´ebastien Coron 和 Agnese Gini 工作的最大贡献就是把 Nguyen-Stern 算法第二步原本指数级别复杂度的 BKZ 算法替换成了多项式时间内可解的问题。感兴趣的读者可以阅读原论文 A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem 第 4.2 节。
OL 攻击总结
OL 攻击应用的基本思路是在已知向量的核空间去筛选足够短的向量,从而得到一些未知向量的核空间,筛选出这些未知向量的核空间的 basis ,就能再求一次正交,进而得到包含未知向量的格空间的 basis ,进而恢复未知向量。
OL 攻击中一个关键的步骤就是求核空间(kernel space),对于任意 个向量 。
在整环 上 的核空间 LLL-reduced 基可以由下面的格得到( 足够大):
在模环 上 的核空间的 LLL-reduced 基可以由下面的格得到( 足够大):
一些参考
一些用到了 OL 攻击技巧的 CTF 赛题:
- Zer0pts CTF 2022 Karen : HSSP 求解。
- D3CTF 2023 d3pack : AHSSP 求解。
- HITCON CTF 2022 Chimera : HSSP 问题的变体。
一些 OL 攻击的论文推荐 :
- Revisiting Orthogonal Lattice Attacks on Approximate Common Divisor Problems and their Applications : OL 攻击综述性质的论文。
- A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem : HSSP, AHSSP 求解算法, OL 攻击的应用。
- Lattice Attacks on the DGHV Homomorphic Encryption Scheme : ACD, PACD 问题的求解,OL 攻击的应用。