后量子密码Dilithium签名验证算法的故障攻击分析与对策

### 后量子密码Dilithium签名验证算法的故障攻击分析与对策 #### 1. 引言 Shor算法的出现凸显了后量子密码学（PQC）的紧迫性。美国国家标准与技术研究院（NIST）第三轮评选确定了四种新的后量子公钥方案，预计2024年标准化。在选定的三种数字签名方案中，有两种基于结构化格上的难题。本文聚焦于NIST推荐的量子安全数字签名标准CRYSTALS - Dilithium（简称Dilithium）。 虽然Dilithium设计上能抵抗时序攻击，但实际实现可能泄露秘密信息。故障攻击对密码系统安全构成重大威胁，本文着重分析Dilithium验证算法对故障攻击的敏感性，提出伪造签名的方法，并给出相应的对策。 #### 2. 预备知识 ##### 2.1 Dilithium概述 Dilithium是基于Fiat - Shamir带中止原理的格基签名方案，其安全性源于解决模块学习误差（M - LWE）和SelfTargetMSIS问题的难度。它有三个安全级别，签名算法有确定性和随机化两种变体。为提高效率，使用了诸如Power2Round、Decompose等舍入子函数，并通过打包和解包函数存储多项式。 - **密钥生成**：通过ExpandA函数从公共种子ρ扩展矩阵A，采样随机秘密向量s1和s2，计算t = A s1 + s2，仅公开t的高位t1，低位t0保密。最后计算tr并添加到私钥中。 ```plaintext Algorithm 1. KeyGen Output: pk = (ρ, t1), sk = (ρ, K, tr, s1, s2, t0) 1 ζ ←{0, 1}256 2 (ρ, ρ′, K) ∈{0, 1}256 × {0, 1}512 × {0, 1}256 := H(ζ) 3 A ∈Rk×l_q := ExpandA(ρ) 4 (s1, s2) ∈Sl_η × Sk_η := ExpandS(ρ′) 5 t := A s1 + s2 6 (t1, t0) := Power2Roundq(t, d) 7 tr ∈{0, 1}256 := H(ρ || t1) 8 return pk = (ρ, t1), sk = (ρ, K, tr, s1, s2, t0) ``` - **签名**：签名过程包含拒绝采样循环，生成签名直到满足安全和正确性属性。生成掩码向量y，计算w = Ay，压缩w为高位w1和低位w0，哈希消息和w1采样挑战c，计算潜在签名z = y + c s1，包含向量h记录w1高位溢出的系数。 ```plaintext Algorithm 2. Sign Input: sk = (ρ, K, tr, s1, s2, t0) Output: σ = (˜c, z, h) 1 A ∈Rk×l_q := ExpandA(ρ) 2 μ ∈{0, 1}512 := H(tr || M) 3 κ := 0, (z, h) :=⊥ 4 ρ′ ∈{0, 1}512 := H(K || μ) 5 while (z, h) =⊥do 6 y ∈˜Sl_γ1 := ExpandMask(ρ′, κ) 7 w := A y 8 w1 = HighBitsq(w, 2 γ2) 9 ˜c ∈{0, 1}256 := H(μ || w1) 10 c ∈Bτ := SampleInBall(˜c) 11 z := y + c s1 12 r0 := LowBitsq(w - cs2, 2 γ2) 13 if ∥z∥∞≥γ1 - β or ∥r0∥∞≥γ2 - β then 14 (z, h) :=⊥ 15 else 16 h := MakeHintq(−c t0, w - cs2 + c t0, 2 γ2) 17 if ||c t0||∞≥γ2 or |h|hj=1 > ω then 18 (z, h) :=⊥ 19 return σ = (˜c, z, h) ``` - **签名验证**：验证算法使用签名和公钥计算A z - c t1 2d的高位，通过提示向量h校正结果。若签名正确，结果等于w1，可重新计算挑战c。最后检查z的系数小于γ1 - β，h中的提示数小于ω。 ```plaintext Algorithm 3. Verify Input: pk = (ρ, t1), σ = (˜c, z, h) Output: True or False 1 A ∈Rk×l_q := ExpandA(ρ) 2 μ ∈{0, 1}512 := H(H(ρ || t1) || M) 3 c := SampleInBall(˜c) 4 w′_1 := UseHintq(h, Az - ct1 2d, 2γ2) 5 return ||z||∞< γ1 - β and ˜c = H(μ || w′_1) and |h|hj=1 ≤ω ``` ##### 2.2 故障模型 过去二十年，故障注入攻击成为破坏设备安全的有力手段。攻击技术包括激光束和电磁（EM）脉冲，可精确控制时空。常见的故障模型有： - **跳过故障**：故意跳过程序中的选定代码行，可通过CPU时钟或电压毛刺、EM脉冲注入或激光束实现。 - **测试反转故障**：反转条件分支结果，可通过反转条件或破坏相关指令实现。 - **随机