基于Rowhammer的LWE密钥封装机制实用密钥恢复攻击

### 基于Rowhammer的LWE密钥封装机制实用密钥恢复攻击 #### 1. 引言 后量子密码学（PQC）旨在设计能抵御经典和量子计算机攻击的加密协议与算法。大型量子计算机可利用Shor和Proos - Zalka算法，轻易破坏基于整数分解和椭圆曲线密码学的现有公钥加密方案。因此，用PQC方案取代现有公钥加密方案迫在眉睫。美国国家标准与技术研究院（NIST）已将Kyber密钥封装机制（KEM）和Dilithium、Falcon、SPHINCS + 数字签名方案列为PQC标准。 在广泛部署密码系统前，评估其物理安全性至关重要。数学上安全的密码系统也可能因物理攻击而完全失去安全性。物理攻击主要分为三类： - **被动侧信道攻击（SCA）**：利用实现漏洞，通过功耗、电磁辐射、声学通道等物理通道泄露秘密信息。 - **主动故障攻击（FA）**：通过激光辐射、电源故障等干扰密码方案正常执行，操纵错误执行结果提取密钥。 - **微架构攻击（MA）**：利用密码方案执行平台架构的漏洞或缺陷。与传统SCA和FA主要针对微控制器和物联网设备不同，MA攻击可影响企业服务器、云平台等更广泛的平台，且可远程执行，难以通过简单编码技术缓解。 目前，对PQC的物理攻击研究主要集中在SCA和FA，MA攻击研究较少，且只有Dilithium是PQC标准。因此，研究PQC的MA攻击具有重要意义。本文的主要贡献如下： - 研究基于学习误差（LWE）问题的KEM的MA攻击，特别是Rowhammer攻击。 - 提出改进的明文检查预言机，相比之前的工作，Saber方案的查询次数最多减少39%，Kyber768约减少23%。 - 选择Kyber和Saber两个PQC KEM方案，展示攻击的实用性。 - 提出基于远程软件诱导故障的端到端密钥恢复方法。 - 讨论现有物理攻击对策对本次攻击的影响。 #### 2. 预备知识 - **符号说明**： - \(Z_q\) 表示模 \(q\) 的整数环。 - 小写字母、带杠小写字母和大写字母分别表示 \(Z_q\) 中的元素、向量和矩阵。 - \(R_q = Z_q[x]/(x^n + 1)\) 为多项式环，粗体小写字母表示 \(R_q\) 中的元素。 - \(R_l^q\) 和 \(R_{l×k}^q\) 分别表示 \(l\) 个多项式向量环和 \(l×k\) 个多项式矩阵环。 - \(U\) 表示均匀分布，\(\beta_{\nu}\) 表示标准差为 \(\sqrt{\nu}/2\) 的中心二项分布（CBD）。 - \(\lfloor x \rfloor\) 表示不大于 \(x\) 的最大整数，\(\lfloor x \rceil\) 表示将 \(x\) 四舍五入到最接近的整数。 - \(r \gg x\) 和 \(r \ll x\) 分别表示 \(r\) 右移和左移 \(x\) 位。 - \(|S|\) 表示集合 \(S\) 的基数。 - **学习误差（LWE）问题及其变体**： - **LWE问题**：设 \(A \leftarrow U(Z_{l×k}^q)\)，误差 \(\overline{e} \leftarrow \chi(Z_l^q)\)，秘密 \(\overline{s} \leftarrow \chi(Z_k^q)\)，\(\overline{b} = A\overline{s} + \overline{e} \in Z_l^q\)，\(\overline{b}' \leftarrow U(Z_l^q)\)，区分 \((A, \overline{b})\) 和 \((A, \overline{b}')\) 是困难的，其难度取决于参数 \((n, l, k, q, \chi)\)。 - **环LWE（RLWE）问题**：用 \(R_q = Z_q[X]/(x^n + 1)\) 代替 \(Z_q\)，且 \(l = k = 1\)，给定 \(a \leftarrow U(R_q)\)，\(e, s \leftarrow \chi(R_q)\)，\(b = as + e \in R_q\)，\(b' \leftarrow U(R_q)\)，区分 \((a, b)\) 和 \((a, b')\) 困难，难度取决于参数 \((n, q, \chi)\)。 - **模块LWE（MLWE）问题**：\(A \leftarrow U(R_{l×l}^q)\)，\(\overline{e}, \overline{s} \leftarrow \chi(R_l^q)\)，\(\overline{b} = A\overline{s} + \overline{e} \in R_l^q\)，\(\overline{b}' \leftarrow U(R_l^q)\)，区分 \((A, \overline{b})\) 和 \((A, \overline{b}')\) 困难，难度取决于参数 \((n, l, q, \chi)\)。 - **学习舍入（LWR）问题**：设 \(A \leftarrow U(Z_{l×k}^q)\)，\(s \leftarrow \chi(Z_k^q)\)，\(b = \lfloor \frac{p}{q}(As) \rceil \in Z_l^p\)，\(b' \leftarrow U(Z_l^p)\)，区分 \((A, b)\) 和 \((A, b')\) 困难，难度取决于参数 \((n, l, k, q, \chi)\)。环LWR（RLWR）和模块LWR（MLWR）问题可类似定义。 - **LPR公钥加密**：Lyubashevsky、Peikert和Regev基于RLWE问题提出LPR公钥加密方案（LPR.PKE）。 - **密钥生成（LPR.PKE.KeyGen）**：秘密 \(s \leftarrow \chi(R_q)\)，误差 \(e \leftarrow \chi(R_q)\)，\(a \leftarrow U(Z_q)\)，\(b = as + e \in R_q\)，公钥 \(pk = (a, b)\)，私钥 \(sk = (a, s)\)。 - **加密（LPR.PKE.Enc）**：密文 \(u\) 计算方式与公钥 \(b\) 类似，\(v = br + e_2 + Encode(m)\)，其中 \(Encode(m) = m \cdot \lfloo