1. 项目概述当公钥加密遇上轻量级块密码最近在密码学安全分析领域一个挺有意思的交叉研究方向引起了我的注意那就是将公钥加密PKE方案中的分析思想应用到像LowMC这样的轻量级块密码的高阶差分分析上。这个方向听起来有点跨界但仔细琢磨内核逻辑是相通的都是在处理“噪声”或“误差”并试图从中提取出决定性的信息。公钥加密里我们常面对的是由随机性引入的“学习误差”而在对LowMC这类采用部分非线性层S-box层稀疏的密码进行高阶差分分析时我们处理的则是经过多轮加密后那些非线性操作产生的、难以线性逼近的“高阶误差”。把前者的数学工具和建模思路借鉴过来往往能给后者带来新的分析视角和更高效的攻击路径。这不仅仅是两个术语的简单拼接而是一种方法论上的迁移与融合。对于从事密码设计、密码分析或者对前沿密码学进展感兴趣的朋友来说理解这个交叉点非常有必要。它不仅能帮你更深刻地把握LowMC这类后量子时代热门密码的结构特性也能让你领略到现代密码分析中“它山之石可以攻玉”的巧妙。本文我将结合自己的理解拆解“基于指数学习误差的公钥加密与LowMC块密码高阶分析”这个命题聊聊背后的核心思想、技术实现的关键步骤以及在实际操作中需要绕开的那些“坑”。2. 核心思想拆解误差学习与高阶差分的内在联系2.1 公钥加密中的“指数学习误差”是什么在基于格Lattice的公钥加密方案特别是那些基于学习有误Learning With Errors, LWE问题及其变种的方案中“学习误差”是一个核心概念。简单来说在LWE问题中攻击者或分析者面对的是形如b A * s e的方程组其中A是公开的矩阵s是秘密向量e是一个小的随机误差向量。这里的“误差”e就是“学习误差”。之所以叫“学习”是因为问题可以理解为给定A和b去“学习”或恢复出秘密s而这个过程被误差e所干扰。“指数学习误差”则是对这种误差分布或误差引入方式的一种特定刻画或假设。它可能指的是误差服从某种指数衰减的分布如离散高斯分布也可能指在安全性归约中区分“有误差的样本”和“完全均匀随机样本”的困难性是指数级的。其核心在于这个误差是小的、有界的但又不可或缺正是它提供了方案的计算安全性。分析这类加密方案很大程度上就是在分析误差e如何掩盖了秘密信息s以及多大的误差仍然能保证攻击者无法有效学习s。2.2 LowMC块密码与高阶差分分析挑战LowMC是近年来为后量子密码学特别是多方计算MPC、全同态加密FHE等场景设计的一族轻量级块密码。它的一个显著特点是采用了非常稀疏的非线性层——每一轮只使用极少数的S-box例如3比特S-box其余部分均为线性变换。这种设计使得它在保持必要安全性的同时在布尔电路中的计算深度很浅非常适合上述复杂密码协议。然而这种稀疏非线性设计也给传统的密码分析带来了新挑战同时也创造了新机会。高阶差分分析是一种强大的选择明文攻击方法它通过追踪高阶差分即多个明文差分之间的运算结果在密码函数中的传播来构建有效的区分器或恢复密钥。对于非线性组件密集的密码高阶差分会随着轮数增加迅速变得复杂而不可用。但LowMC的稀疏S-box层意味着在多数比特路径上数据只是经历了线性处理这在一定程度上“保持”了差分的某些代数结构。挑战在于尽管线性层多但那些零星分布的S-box就像电路中的“非线性噪声源”会破坏差分的高阶线性关系。经过多轮迭代后这些局部非线性效应累积起来构成了分析中需要处理的“高阶误差”。这个“误差”与LWE中的误差e在概念上扮演了相似的角色它们都是使得从输出反推输入或密钥变得困难的“干扰项”。2.3 思想迁移用误差学习的框架看待密码分析那么如何将两者联系起来呢关键洞察在于建模的转化。将密码算法视为一个“带噪声的函数”在对LowMC进行高阶差分分析时我们可以尝试将经过r轮加密后的某个比特或一组比特的函数值表达为一个关于明文差分和密钥的多元多项式。其中线性操作密钥加、线性层贡献了多项式的主体线性/仿射部分而稀疏的S-box操作则引入了高阶项如二次项、三次项。这些高阶项相对于我们想构建的线性区分器而言就是“误差”。定义“分析误差”我们可以定义一个“分析误差”项它包含了所有由S-box引入的、阶数高于我们当前分析所考虑阶数的差分效应。理想情况下如果我们能完全精确建模这个误差应为零。但实际上由于S-box的非线性和迭代这个误差是存在且复杂的。借鉴LWE的分析范式在LWE分析中我们研究需要多少样本即多少个(A, b)对才能以显著概率从误差e中“学习”到s。类似地在LowMC的高阶分析中我们可以研究需要多少选择明文对对应样本才能使得高阶差分统计量能够以显著概率“区分”出密码算法和一个随机置换尽管存在由稀疏S-box产生的“分析误差”。这里的“分析误差”类似于LWE中的e而密钥信息或算法的非随机性特征则类似于s。指数级安全性的类比在安全的公钥加密方案中区分真实密文和随机串的优势advantage通常被证明是忽略不计的或者更理想的是攻击者的成功概率随安全参数呈指数级下降。当我们说“基于指数学习误差”时可能暗示我们试图证明对于LowMC的某种高阶差分攻击随着轮数增加或S-box数量调整攻击者成功构建有效区分器的概率或优势也呈指数级下降。这就将密码算法的具体安全性与一个抽象的、已被深入研究的计算困难问题带误差学习的难度联系了起来提供了一种形式化或半形式化的安全论证思路。这种思想迁移的价值在于它允许我们利用格密码和LWE问题中成熟的复杂性理论工具和证明技术来量化评估LowMC这类特定结构密码对抗高阶差分分析的安全性。我们不再仅仅依靠具体的攻击实验和复杂度估算而是可以尝试建立更一般的、基于计算困难假设的安全边界。3. 技术实现路径从理论框架到具体分析步骤将上述思想落地需要进行一系列具体的建模、计算和实验步骤。下面我以一个简化的研究流程为例说明如何操作。3.1 第一步精确建模LowMC的差分传播首先需要对目标LowMC实例特定的参数集如块大小、S-box数量及位置、线性层矩阵、轮数等进行精确的代数描述。状态表示将每一轮的内部状态表示为比特向量。设状态长度为n。轮函数分解明确每一轮的三个子步骤AddRoundKey密钥加通常是异或、SboxLayer稀疏S-box应用、LinearLayer矩阵乘法。其中S-box层只作用于少数几个比如k个特定的比特位置。差分表示对于选择明文攻击我们考虑一组明文并计算它们在某些特定比特位置上的差分通常是异或差分。设我们关注一个d阶差分即涉及2^d个明文。追踪差分经过线性层线性变换异或和矩阵乘法对差分的处理是线性的可以直接通过矩阵运算推导出输出差分。这是模型中“干净”的、可预测的部分。处理S-box引入的非线性这是关键也是难点。每个3比特S-box是一个非线性函数。当差分传播经过S-box时输出差分不再是输入差分的确定性函数而是一个分布差分分布表DDT。在构建确定性区分器时我们通常寻找概率为1的差分特征。但在高阶差分分析中我们更关心的是经过S-box后某个高阶差分例如所有2^d个明文经过S-box输出值的异或总和是否恒为0。对于某些低阶输入差分和特定的S-box这个和可能恒为0这被称为高阶差分的“零和”性质。注意LowMC使用的S-box通常经过精心挑选具有好的密码学性质但针对高阶差分“零和”的性质需要单独验证。这是分析的基础需要查阅该LowMC实例的具体设计文档或进行预计算。3.2 第二步构建带“误差”的高阶差分等式我们的目标是构建一个关于最终密文状态某些比特的、涉及高阶差分的等式这个等式在密码算法下以高概率成立或高概率不成立而在随机置换下以不同的概率成立。选择目标比特和差分路径基于第一步的传播分析选择密文状态的若干比特作为观测点。同时选择明文差分模式即哪些比特位置参与构造高阶差分使得差分路径尽可能多地通过线性部分减少经过S-box的次数。推导理想等式假设所有S-box对高阶差分的传播都是“理想”的例如总是保持某种线性关系或零和特性我们可以推导出一个理论上的等式。例如SUM over all plaintexts in the delta-set (Ciphertext_bit_i) 0其中求和是异或和。这个等式在“无误差”的理想模型中应始终成立。引入“误差项”现在将每个S-box在差分传播中可能破坏上述理想等式的因素建模为一个布尔变量或一个小概率事件。这个破坏因素就是我们的“分析误差”。由于S-box稀疏误差项的数量是可控的。最终我们得到形如理想等式 XOR (误差项1 OR 误差项2 OR ...) 0的实际预测。也就是说只有当所有相关S-box都没有引入破坏时理想等式才成立。误差的概率化分析计算每个“误差项”发生的概率。这需要对每个涉及的S-box分析其在高阶差分输入下的输出和分布。这个概率通常取决于S-box的DDT和具体的输入差分值。将所有误差项的影响综合起来可以得到实际等式成立的概率p_cipher。3.3 第三步应用“指数学习误差”框架进行分析在这一步我们将第二步的概率结果放入一个类似LWE问题分析的框架中。定义区分游戏攻击者可以查询一个“黑盒”黑盒要么是目标LowMC实例使用随机密钥要么是一个真正的随机置换。攻击者的目标是区分两者。构建区分器攻击者使用我们构造的高阶差分等式。他准备一个特定的d阶差分明文集合查询黑盒得到密文然后计算等式是否成立。计算区分优势对于真正的LowMC等式成立的概率是p_cipher我们计算出的通常明显偏离0.5。对于一个随机置换任何基于固定比特位置的、非平凡的布尔函数等式其成立的概率期望是0.5或非常接近0.5取决于等式具体形式。攻击者通过多次独立实验使用不同的差分基底或密钥可以检验等式成立的概率是否显著偏离0.5。这个偏离的程度就是区分优势。关联到“学习误差”我们可以将|p_cipher - 0.5|视作一个“信号强度”。而攻击者从有限次查询中准确估计出p_cipher的过程类似于从带有“噪声”的样本中学习一个参数。这里的“噪声”来源于1当黑盒是随机置换时其本身输出的随机性2即使黑盒是LowMC由于“误差项”的存在等式成立与否也是概率性的。样本复杂度与安全参数基于统计学习理论或LWE问题分析中常用的引理如Chernoff bound, Hoeffding inequality我们可以估算出为了以接近1的概率成功区分攻击者需要多少组查询即样本量或选择明文量。这个样本复杂度N应该是1 / (p_cipher - 0.5)^2的量级。如果随着LowMC轮数r增加|p_cipher - 0.5|呈指数级衰减例如2^{-cr}那么所需的样本量N就呈指数级增长2^{2cr}。这就将LowMC的安全性与一个“指数学习误差”问题联系了起来攻击者需要指数级多的样本才能从指数级小的偏差中学习到足够的信息进行区分。这为LowMC抵抗高阶差分分析提供了形式化的安全论据只要p_cipher以足够快的指数速度趋近于0.5那么任何实际可行的攻击者其查询量有上限的区分优势都是可以忽略不计的。3.4 第四步工具辅助与实验验证理论分析需要工具和实验的支撑。符号计算工具使用如SageMath、Python的sympy库或专门的密码分析框架如CryptoMiniSat的代数接口对小型参数如状态n较小轮数r较少的LowMC进行精确的代数建模。这可以帮助我们验证高阶差分等式的推导并精确计算小规模实例下的p_cipher。概率模拟对于参数较大的实例精确符号计算可能不可行。可以采用蒙特卡洛模拟方法随机生成大量密钥和符合差分模式的明文集运行LowMC加密统计等式成立的概率以此估算p_cipher。验证指数衰减通过模拟不同轮数下的p_cipher绘制其与轮数r的关系曲线通常在对数坐标下。如果观察到接近线性的下降则支持了偏差指数衰减的假设从而佐证了基于指数学习误差的安全论证。4. 实操要点与避坑指南在实际操作这个分析流程时有几个关键点需要特别注意它们直接决定了分析的可行性和结论的可靠性。4.1 要点一S-box高阶差分性质的精确预计算这是整个分析的基石绝对不能想当然。LowMC使用的3比特S-box虽然小但其高阶差分性质特别是针对“零和”性质必须逐一验算。操作对于选定的S-box枚举所有可能的低阶输入差分例如1阶、2阶差分对于每一种输入差分计算所有可能输入值在该差分下的输出集合然后检查输出值的异或总和即高阶差分是否为0。工具可以写一个简单的脚本来自动化这个过程。输入S-box的查找表输出一个字典或表格记录哪些输入差分能保证输出高阶差分为0。避坑不要只检查S-box本身的零和性质还要检查在具体差分路径中S-box的输入是否确实是你预计算的那些“友好”差分。由于线性层的扩散到达S-box的输入差分可能是多个明文差分位的线性组合这可能超出你预计算的简单差分情况。必须根据具体的线性层矩阵进行反向推导。4.2 要点二误差项的独立性假设与处理在第三步的概率分析中我们常常需要假设不同的“误差项”即不同S-box破坏等式的事件是相互独立的这样才能方便地将它们的概率相乘或相加。风险这个假设不一定成立。由于密码算法的迭代结构不同轮的S-box输入可能通过线性层相关联导致误差事件之间存在相关性。处理保守估计在无法证明独立性的情况下采用最坏情况假设即所有误差事件完全相关。那么整体失败的概率就是单个最大误差概率的上界。这会导致估算出的p_cipher更接近0.5从而给出一个更保守更安全的安全边界。深入分析相关性对于小型实例可以通过符号计算或详尽的模拟来直接估算多个误差事件联合发生的概率避免独立性假设。利用结构特性LowMC的线性层通常是最大距离可分MDS或具有良好扩散性的这有助于在几轮之后使状态比特充分混合从而可能使得不同位置的误差在统计上趋近于独立。但这需要论证。4.3 要点三区分优势的统计估计与样本量即使理论计算出了p_cipher在实际区分攻击中如何用有限样本做出可靠判断也是个技术活。假设检验这本质上是一个假设检验问题。零假设H0: 黑盒是随机置换 (p0.5)备择假设H1: 黑盒是LowMC (pp_cipher)。确定样本量N给定我们希望达到的区分优势成功概率和可接受的错误概率第一类错误α第二类错误β可以利用统计公式如基于正态近似的公式反推出需要的样本量N。N与(p_cipher - 0.5)^2成反比。当p_cipher非常接近0.5时N会变得巨大攻击在实践中不可行。避坑不要仅仅因为一次实验中等式成立/不成立就下结论。必须进行足够多次的独立实验并采用严格的统计检验如计算p-value。否则很容易被随机波动所误导。4.4 要点四寻找最优的差分路径与观测点分析的成功与否和效率极大程度上取决于第一步中差分路径和密文观测点的选择。策略这通常是一个搜索优化问题。目标是让差分路径尽可能少地通过S-box减少误差源同时让最终的观测等式尽可能敏感即|p_cipher - 0.5|尽可能大。自动化搜索可以尝试使用混合整数线性规划MILP或可满足性模理论SMT等工具将差分传播的规则线性层确定性传播S-box概率性/确定性传播约束建模为约束条件以最小化激活S-box数量或最大化理论偏差为目标进行搜索。经验通常选择那些从明文差分位开始经过线性层能“绕过”许多S-box直接传播到密文某些位的路径。观测点也常选择在状态的最后几轮因为那里的非线性累积效应更复杂可能产生更独特的统计特征。5. 案例推演对一个简化LowMC模型的攻击模拟为了让大家更有体感我们设想一个极度简化的模型请勿用于真实设计。假设一个微型LowMC变种4比特状态每轮使用1个3比特S-box作用于前3比特线性层是一个4x4的随机可逆矩阵但固定共3轮。我们的目标是构造一个2阶差分区分器。建模我们选择明文的第0、1比特参与构造2阶差分4个明文。通过跟踪我们发现由于线性层的特性在第三轮S-box的输入中来自第0比特差分的影响被抵消了因此第三轮的S-box输入差分恒为0对于这个特定的差分模式。这意味着对于这个差分集合第三轮的S-box实际上没有引入任何非线性效应输出差分也为0。构建等式我们选择密文状态的所有4个比特作为观测。由于第三轮S-box无误差且之前轮次的S-box影响可以通过线性层推导我们最终得到一个理论预测对于这个特定的2阶差分明文集4个密文比特的异或和始终为0。即p_cipher 1。分析对于随机置换4个比特异或和为0的概率是0.5。因此我们有一个完美的区分器 (|1-0.5| 0.5)。样本复杂度只需要1组4个明文查询就能以100%的概率区分。这显然是不安全的。现实意义这个例子展示了如果差分路径能完全避开S-box的非线性即“误差”为0攻击会非常高效。真实LowMC的设计会通过更复杂的线性层和更多的轮数来避免这种简单路径的存在确保任何非平凡的高阶差分路径都会激活足够多的S-box从而使p_cipher快速指数趋近于0.5。6. 高阶分析中的常见问题与排查在实际研究过程中你可能会遇到以下典型问题问题现象可能原因排查思路与解决方案理论推导的等式在模拟中成立概率远低于预期p_cipher太小。1. S-box的高阶差分性质计算有误。2. 误差项的独立性假设过于乐观实际相关性很强。3. 差分路径中存在未考虑到的S-box激活。1. 重新检查并验证S-box的零和性质计算脚本。2. 对小型参数进行穷举或大量模拟直接测量联合概率检验独立性假设。3. 使用更精确的符号计算工具如Sage跟踪特定差分集合的具体传播路径确认每个S-box的输入差分。模拟结果显示p_cipher接近0.5无法构建有效区分器。1. 选择的轮数过多偏差已指数衰减到可忽略范围。2. 差分路径或观测点选择不佳信号太弱。3. 线性层设计使得差分快速扩散过早激活了大量S-box。1. 尝试减少轮数验证偏差是否随着轮数减少而增大确认安全边际。2. 使用自动化搜索工具MILP寻找更优的差分模式。3. 分析线性层的扩散特性尝试选择能延迟S-box激活的差分输入模式。统计区分实验所需的样本量N巨大远超计算能力。p_cipher - 0.5在不同密钥下等式成立概率p_cipher波动很大。推导的等式可能依赖于密钥的某些特定值即“弱密钥”性质。在一般密钥假设下等式可能不总是高概率成立。检查等式推导过程是否隐含了密钥必须满足某个线性条件。真正的密钥无关区分器其概率应对几乎所有密钥都成立。需要重新推导一个密钥无关的统计特征。7. 延伸思考方法论的局限与未来方向基于指数学习误差的框架为分析LowMC等高阶差分安全性提供了有力的理论工具但它也有其适用范围和局限。局限模型简化将复杂的S-box非线性传播抽象为独立的“误差事件”是一个强简化。实际的相关性可能更复杂导致安全估计过于乐观或悲观。寻找路径的难度对于全参数规模的LowMC自动化搜索最优高阶差分路径本身就是一个计算难题。当前工具MILP/SMT在处理多轮、多S-box时可能遇到状态爆炸问题。其他攻击向量该方法专注于高阶差分分析。LowMC还可能面临其他类型的攻击如代数攻击、立方攻击、积分攻击等。一个全面的安全分析需要多角度评估。未来方向更精确的误差建模发展更精细的概率模型来刻画S-box误差项之间的相关性例如使用马尔可夫链或更复杂的随机过程。结合机器学习利用机器学习方法自动学习差分传播的模式甚至直接预测高阶差分等式的有效性辅助或替代部分搜索过程。形式化验证将整个分析过程从差分传播规则到概率计算用形式化验证工具如EasyCrypt, CryptoVerif进行编码和验证确保推导过程无漏洞安全边界可靠。应用于其他密码将此框架推广到其他具有稀疏非线性层的轻量级密码或密码组件如ARX结构中的模加运算可视为一种非线性的安全性分析中。在我个人看来这种跨领域的思路融合是密码学研究的魅力所在。把公钥密码中深刻的计算复杂性思想用来剖析对称密码的具体结构往往能照亮那些单纯依靠传统对称密码分析难以看清的角落。虽然具体操作起来满是细节和计算但当你看到通过这种建模能够为一段精巧的密码算法勾勒出一个清晰的安全边界时那种感觉是非常扎实和满足的。最后一个小建议是动手做的时候一定要从最小的、可完全验证的实例开始把每一步的中间结果都打印出来核对确保你的建模和代码与算法的实际行为严丝合缝这是避免在复杂分析中迷失方向的最有效方法。
公钥加密误差学习思想在LowMC高阶差分分析中的应用
发布时间：2026/6/24 21:32:57
1. 项目概述当公钥加密遇上轻量级块密码最近在密码学安全分析领域一个挺有意思的交叉研究方向引起了我的注意那就是将公钥加密PKE方案中的分析思想应用到像LowMC这样的轻量级块密码的高阶差分分析上。这个方向听起来有点跨界但仔细琢磨内核逻辑是相通的都是在处理“噪声”或“误差”并试图从中提取出决定性的信息。公钥加密里我们常面对的是由随机性引入的“学习误差”而在对LowMC这类采用部分非线性层S-box层稀疏的密码进行高阶差分分析时我们处理的则是经过多轮加密后那些非线性操作产生的、难以线性逼近的“高阶误差”。把前者的数学工具和建模思路借鉴过来往往能给后者带来新的分析视角和更高效的攻击路径。这不仅仅是两个术语的简单拼接而是一种方法论上的迁移与融合。对于从事密码设计、密码分析或者对前沿密码学进展感兴趣的朋友来说理解这个交叉点非常有必要。它不仅能帮你更深刻地把握LowMC这类后量子时代热门密码的结构特性也能让你领略到现代密码分析中“它山之石可以攻玉”的巧妙。本文我将结合自己的理解拆解“基于指数学习误差的公钥加密与LowMC块密码高阶分析”这个命题聊聊背后的核心思想、技术实现的关键步骤以及在实际操作中需要绕开的那些“坑”。2. 核心思想拆解误差学习与高阶差分的内在联系2.1 公钥加密中的“指数学习误差”是什么在基于格Lattice的公钥加密方案特别是那些基于学习有误Learning With Errors, LWE问题及其变种的方案中“学习误差”是一个核心概念。简单来说在LWE问题中攻击者或分析者面对的是形如b A * s e的方程组其中A是公开的矩阵s是秘密向量e是一个小的随机误差向量。这里的“误差”e就是“学习误差”。之所以叫“学习”是因为问题可以理解为给定A和b去“学习”或恢复出秘密s而这个过程被误差e所干扰。“指数学习误差”则是对这种误差分布或误差引入方式的一种特定刻画或假设。它可能指的是误差服从某种指数衰减的分布如离散高斯分布也可能指在安全性归约中区分“有误差的样本”和“完全均匀随机样本”的困难性是指数级的。其核心在于这个误差是小的、有界的但又不可或缺正是它提供了方案的计算安全性。分析这类加密方案很大程度上就是在分析误差e如何掩盖了秘密信息s以及多大的误差仍然能保证攻击者无法有效学习s。2.2 LowMC块密码与高阶差分分析挑战LowMC是近年来为后量子密码学特别是多方计算MPC、全同态加密FHE等场景设计的一族轻量级块密码。它的一个显著特点是采用了非常稀疏的非线性层——每一轮只使用极少数的S-box例如3比特S-box其余部分均为线性变换。这种设计使得它在保持必要安全性的同时在布尔电路中的计算深度很浅非常适合上述复杂密码协议。然而这种稀疏非线性设计也给传统的密码分析带来了新挑战同时也创造了新机会。高阶差分分析是一种强大的选择明文攻击方法它通过追踪高阶差分即多个明文差分之间的运算结果在密码函数中的传播来构建有效的区分器或恢复密钥。对于非线性组件密集的密码高阶差分会随着轮数增加迅速变得复杂而不可用。但LowMC的稀疏S-box层意味着在多数比特路径上数据只是经历了线性处理这在一定程度上“保持”了差分的某些代数结构。挑战在于尽管线性层多但那些零星分布的S-box就像电路中的“非线性噪声源”会破坏差分的高阶线性关系。经过多轮迭代后这些局部非线性效应累积起来构成了分析中需要处理的“高阶误差”。这个“误差”与LWE中的误差e在概念上扮演了相似的角色它们都是使得从输出反推输入或密钥变得困难的“干扰项”。2.3 思想迁移用误差学习的框架看待密码分析那么如何将两者联系起来呢关键洞察在于建模的转化。将密码算法视为一个“带噪声的函数”在对LowMC进行高阶差分分析时我们可以尝试将经过r轮加密后的某个比特或一组比特的函数值表达为一个关于明文差分和密钥的多元多项式。其中线性操作密钥加、线性层贡献了多项式的主体线性/仿射部分而稀疏的S-box操作则引入了高阶项如二次项、三次项。这些高阶项相对于我们想构建的线性区分器而言就是“误差”。定义“分析误差”我们可以定义一个“分析误差”项它包含了所有由S-box引入的、阶数高于我们当前分析所考虑阶数的差分效应。理想情况下如果我们能完全精确建模这个误差应为零。但实际上由于S-box的非线性和迭代这个误差是存在且复杂的。借鉴LWE的分析范式在LWE分析中我们研究需要多少样本即多少个(A, b)对才能以显著概率从误差e中“学习”到s。类似地在LowMC的高阶分析中我们可以研究需要多少选择明文对对应样本才能使得高阶差分统计量能够以显著概率“区分”出密码算法和一个随机置换尽管存在由稀疏S-box产生的“分析误差”。这里的“分析误差”类似于LWE中的e而密钥信息或算法的非随机性特征则类似于s。指数级安全性的类比在安全的公钥加密方案中区分真实密文和随机串的优势advantage通常被证明是忽略不计的或者更理想的是攻击者的成功概率随安全参数呈指数级下降。当我们说“基于指数学习误差”时可能暗示我们试图证明对于LowMC的某种高阶差分攻击随着轮数增加或S-box数量调整攻击者成功构建有效区分器的概率或优势也呈指数级下降。这就将密码算法的具体安全性与一个抽象的、已被深入研究的计算困难问题带误差学习的难度联系了起来提供了一种形式化或半形式化的安全论证思路。这种思想迁移的价值在于它允许我们利用格密码和LWE问题中成熟的复杂性理论工具和证明技术来量化评估LowMC这类特定结构密码对抗高阶差分分析的安全性。我们不再仅仅依靠具体的攻击实验和复杂度估算而是可以尝试建立更一般的、基于计算困难假设的安全边界。3. 技术实现路径从理论框架到具体分析步骤将上述思想落地需要进行一系列具体的建模、计算和实验步骤。下面我以一个简化的研究流程为例说明如何操作。3.1 第一步精确建模LowMC的差分传播首先需要对目标LowMC实例特定的参数集如块大小、S-box数量及位置、线性层矩阵、轮数等进行精确的代数描述。状态表示将每一轮的内部状态表示为比特向量。设状态长度为n。轮函数分解明确每一轮的三个子步骤AddRoundKey密钥加通常是异或、SboxLayer稀疏S-box应用、LinearLayer矩阵乘法。其中S-box层只作用于少数几个比如k个特定的比特位置。差分表示对于选择明文攻击我们考虑一组明文并计算它们在某些特定比特位置上的差分通常是异或差分。设我们关注一个d阶差分即涉及2^d个明文。追踪差分经过线性层线性变换异或和矩阵乘法对差分的处理是线性的可以直接通过矩阵运算推导出输出差分。这是模型中“干净”的、可预测的部分。处理S-box引入的非线性这是关键也是难点。每个3比特S-box是一个非线性函数。当差分传播经过S-box时输出差分不再是输入差分的确定性函数而是一个分布差分分布表DDT。在构建确定性区分器时我们通常寻找概率为1的差分特征。但在高阶差分分析中我们更关心的是经过S-box后某个高阶差分例如所有2^d个明文经过S-box输出值的异或总和是否恒为0。对于某些低阶输入差分和特定的S-box这个和可能恒为0这被称为高阶差分的“零和”性质。注意LowMC使用的S-box通常经过精心挑选具有好的密码学性质但针对高阶差分“零和”的性质需要单独验证。这是分析的基础需要查阅该LowMC实例的具体设计文档或进行预计算。3.2 第二步构建带“误差”的高阶差分等式我们的目标是构建一个关于最终密文状态某些比特的、涉及高阶差分的等式这个等式在密码算法下以高概率成立或高概率不成立而在随机置换下以不同的概率成立。选择目标比特和差分路径基于第一步的传播分析选择密文状态的若干比特作为观测点。同时选择明文差分模式即哪些比特位置参与构造高阶差分使得差分路径尽可能多地通过线性部分减少经过S-box的次数。推导理想等式假设所有S-box对高阶差分的传播都是“理想”的例如总是保持某种线性关系或零和特性我们可以推导出一个理论上的等式。例如SUM over all plaintexts in the delta-set (Ciphertext_bit_i) 0其中求和是异或和。这个等式在“无误差”的理想模型中应始终成立。引入“误差项”现在将每个S-box在差分传播中可能破坏上述理想等式的因素建模为一个布尔变量或一个小概率事件。这个破坏因素就是我们的“分析误差”。由于S-box稀疏误差项的数量是可控的。最终我们得到形如理想等式 XOR (误差项1 OR 误差项2 OR ...) 0的实际预测。也就是说只有当所有相关S-box都没有引入破坏时理想等式才成立。误差的概率化分析计算每个“误差项”发生的概率。这需要对每个涉及的S-box分析其在高阶差分输入下的输出和分布。这个概率通常取决于S-box的DDT和具体的输入差分值。将所有误差项的影响综合起来可以得到实际等式成立的概率p_cipher。3.3 第三步应用“指数学习误差”框架进行分析在这一步我们将第二步的概率结果放入一个类似LWE问题分析的框架中。定义区分游戏攻击者可以查询一个“黑盒”黑盒要么是目标LowMC实例使用随机密钥要么是一个真正的随机置换。攻击者的目标是区分两者。构建区分器攻击者使用我们构造的高阶差分等式。他准备一个特定的d阶差分明文集合查询黑盒得到密文然后计算等式是否成立。计算区分优势对于真正的LowMC等式成立的概率是p_cipher我们计算出的通常明显偏离0.5。对于一个随机置换任何基于固定比特位置的、非平凡的布尔函数等式其成立的概率期望是0.5或非常接近0.5取决于等式具体形式。攻击者通过多次独立实验使用不同的差分基底或密钥可以检验等式成立的概率是否显著偏离0.5。这个偏离的程度就是区分优势。关联到“学习误差”我们可以将|p_cipher - 0.5|视作一个“信号强度”。而攻击者从有限次查询中准确估计出p_cipher的过程类似于从带有“噪声”的样本中学习一个参数。这里的“噪声”来源于1当黑盒是随机置换时其本身输出的随机性2即使黑盒是LowMC由于“误差项”的存在等式成立与否也是概率性的。样本复杂度与安全参数基于统计学习理论或LWE问题分析中常用的引理如Chernoff bound, Hoeffding inequality我们可以估算出为了以接近1的概率成功区分攻击者需要多少组查询即样本量或选择明文量。这个样本复杂度N应该是1 / (p_cipher - 0.5)^2的量级。如果随着LowMC轮数r增加|p_cipher - 0.5|呈指数级衰减例如2^{-cr}那么所需的样本量N就呈指数级增长2^{2cr}。这就将LowMC的安全性与一个“指数学习误差”问题联系了起来攻击者需要指数级多的样本才能从指数级小的偏差中学习到足够的信息进行区分。这为LowMC抵抗高阶差分分析提供了形式化的安全论据只要p_cipher以足够快的指数速度趋近于0.5那么任何实际可行的攻击者其查询量有上限的区分优势都是可以忽略不计的。3.4 第四步工具辅助与实验验证理论分析需要工具和实验的支撑。符号计算工具使用如SageMath、Python的sympy库或专门的密码分析框架如CryptoMiniSat的代数接口对小型参数如状态n较小轮数r较少的LowMC进行精确的代数建模。这可以帮助我们验证高阶差分等式的推导并精确计算小规模实例下的p_cipher。概率模拟对于参数较大的实例精确符号计算可能不可行。可以采用蒙特卡洛模拟方法随机生成大量密钥和符合差分模式的明文集运行LowMC加密统计等式成立的概率以此估算p_cipher。验证指数衰减通过模拟不同轮数下的p_cipher绘制其与轮数r的关系曲线通常在对数坐标下。如果观察到接近线性的下降则支持了偏差指数衰减的假设从而佐证了基于指数学习误差的安全论证。4. 实操要点与避坑指南在实际操作这个分析流程时有几个关键点需要特别注意它们直接决定了分析的可行性和结论的可靠性。4.1 要点一S-box高阶差分性质的精确预计算这是整个分析的基石绝对不能想当然。LowMC使用的3比特S-box虽然小但其高阶差分性质特别是针对“零和”性质必须逐一验算。操作对于选定的S-box枚举所有可能的低阶输入差分例如1阶、2阶差分对于每一种输入差分计算所有可能输入值在该差分下的输出集合然后检查输出值的异或总和即高阶差分是否为0。工具可以写一个简单的脚本来自动化这个过程。输入S-box的查找表输出一个字典或表格记录哪些输入差分能保证输出高阶差分为0。避坑不要只检查S-box本身的零和性质还要检查在具体差分路径中S-box的输入是否确实是你预计算的那些“友好”差分。由于线性层的扩散到达S-box的输入差分可能是多个明文差分位的线性组合这可能超出你预计算的简单差分情况。必须根据具体的线性层矩阵进行反向推导。4.2 要点二误差项的独立性假设与处理在第三步的概率分析中我们常常需要假设不同的“误差项”即不同S-box破坏等式的事件是相互独立的这样才能方便地将它们的概率相乘或相加。风险这个假设不一定成立。由于密码算法的迭代结构不同轮的S-box输入可能通过线性层相关联导致误差事件之间存在相关性。处理保守估计在无法证明独立性的情况下采用最坏情况假设即所有误差事件完全相关。那么整体失败的概率就是单个最大误差概率的上界。这会导致估算出的p_cipher更接近0.5从而给出一个更保守更安全的安全边界。深入分析相关性对于小型实例可以通过符号计算或详尽的模拟来直接估算多个误差事件联合发生的概率避免独立性假设。利用结构特性LowMC的线性层通常是最大距离可分MDS或具有良好扩散性的这有助于在几轮之后使状态比特充分混合从而可能使得不同位置的误差在统计上趋近于独立。但这需要论证。4.3 要点三区分优势的统计估计与样本量即使理论计算出了p_cipher在实际区分攻击中如何用有限样本做出可靠判断也是个技术活。假设检验这本质上是一个假设检验问题。零假设H0: 黑盒是随机置换 (p0.5)备择假设H1: 黑盒是LowMC (pp_cipher)。确定样本量N给定我们希望达到的区分优势成功概率和可接受的错误概率第一类错误α第二类错误β可以利用统计公式如基于正态近似的公式反推出需要的样本量N。N与(p_cipher - 0.5)^2成反比。当p_cipher非常接近0.5时N会变得巨大攻击在实践中不可行。避坑不要仅仅因为一次实验中等式成立/不成立就下结论。必须进行足够多次的独立实验并采用严格的统计检验如计算p-value。否则很容易被随机波动所误导。4.4 要点四寻找最优的差分路径与观测点分析的成功与否和效率极大程度上取决于第一步中差分路径和密文观测点的选择。策略这通常是一个搜索优化问题。目标是让差分路径尽可能少地通过S-box减少误差源同时让最终的观测等式尽可能敏感即|p_cipher - 0.5|尽可能大。自动化搜索可以尝试使用混合整数线性规划MILP或可满足性模理论SMT等工具将差分传播的规则线性层确定性传播S-box概率性/确定性传播约束建模为约束条件以最小化激活S-box数量或最大化理论偏差为目标进行搜索。经验通常选择那些从明文差分位开始经过线性层能“绕过”许多S-box直接传播到密文某些位的路径。观测点也常选择在状态的最后几轮因为那里的非线性累积效应更复杂可能产生更独特的统计特征。5. 案例推演对一个简化LowMC模型的攻击模拟为了让大家更有体感我们设想一个极度简化的模型请勿用于真实设计。假设一个微型LowMC变种4比特状态每轮使用1个3比特S-box作用于前3比特线性层是一个4x4的随机可逆矩阵但固定共3轮。我们的目标是构造一个2阶差分区分器。建模我们选择明文的第0、1比特参与构造2阶差分4个明文。通过跟踪我们发现由于线性层的特性在第三轮S-box的输入中来自第0比特差分的影响被抵消了因此第三轮的S-box输入差分恒为0对于这个特定的差分模式。这意味着对于这个差分集合第三轮的S-box实际上没有引入任何非线性效应输出差分也为0。构建等式我们选择密文状态的所有4个比特作为观测。由于第三轮S-box无误差且之前轮次的S-box影响可以通过线性层推导我们最终得到一个理论预测对于这个特定的2阶差分明文集4个密文比特的异或和始终为0。即p_cipher 1。分析对于随机置换4个比特异或和为0的概率是0.5。因此我们有一个完美的区分器 (|1-0.5| 0.5)。样本复杂度只需要1组4个明文查询就能以100%的概率区分。这显然是不安全的。现实意义这个例子展示了如果差分路径能完全避开S-box的非线性即“误差”为0攻击会非常高效。真实LowMC的设计会通过更复杂的线性层和更多的轮数来避免这种简单路径的存在确保任何非平凡的高阶差分路径都会激活足够多的S-box从而使p_cipher快速指数趋近于0.5。6. 高阶分析中的常见问题与排查在实际研究过程中你可能会遇到以下典型问题问题现象可能原因排查思路与解决方案理论推导的等式在模拟中成立概率远低于预期p_cipher太小。1. S-box的高阶差分性质计算有误。2. 误差项的独立性假设过于乐观实际相关性很强。3. 差分路径中存在未考虑到的S-box激活。1. 重新检查并验证S-box的零和性质计算脚本。2. 对小型参数进行穷举或大量模拟直接测量联合概率检验独立性假设。3. 使用更精确的符号计算工具如Sage跟踪特定差分集合的具体传播路径确认每个S-box的输入差分。模拟结果显示p_cipher接近0.5无法构建有效区分器。1. 选择的轮数过多偏差已指数衰减到可忽略范围。2. 差分路径或观测点选择不佳信号太弱。3. 线性层设计使得差分快速扩散过早激活了大量S-box。1. 尝试减少轮数验证偏差是否随着轮数减少而增大确认安全边际。2. 使用自动化搜索工具MILP寻找更优的差分模式。3. 分析线性层的扩散特性尝试选择能延迟S-box激活的差分输入模式。统计区分实验所需的样本量N巨大远超计算能力。p_cipher - 0.5在不同密钥下等式成立概率p_cipher波动很大。推导的等式可能依赖于密钥的某些特定值即“弱密钥”性质。在一般密钥假设下等式可能不总是高概率成立。检查等式推导过程是否隐含了密钥必须满足某个线性条件。真正的密钥无关区分器其概率应对几乎所有密钥都成立。需要重新推导一个密钥无关的统计特征。7. 延伸思考方法论的局限与未来方向基于指数学习误差的框架为分析LowMC等高阶差分安全性提供了有力的理论工具但它也有其适用范围和局限。局限模型简化将复杂的S-box非线性传播抽象为独立的“误差事件”是一个强简化。实际的相关性可能更复杂导致安全估计过于乐观或悲观。寻找路径的难度对于全参数规模的LowMC自动化搜索最优高阶差分路径本身就是一个计算难题。当前工具MILP/SMT在处理多轮、多S-box时可能遇到状态爆炸问题。其他攻击向量该方法专注于高阶差分分析。LowMC还可能面临其他类型的攻击如代数攻击、立方攻击、积分攻击等。一个全面的安全分析需要多角度评估。未来方向更精确的误差建模发展更精细的概率模型来刻画S-box误差项之间的相关性例如使用马尔可夫链或更复杂的随机过程。结合机器学习利用机器学习方法自动学习差分传播的模式甚至直接预测高阶差分等式的有效性辅助或替代部分搜索过程。形式化验证将整个分析过程从差分传播规则到概率计算用形式化验证工具如EasyCrypt, CryptoVerif进行编码和验证确保推导过程无漏洞安全边界可靠。应用于其他密码将此框架推广到其他具有稀疏非线性层的轻量级密码或密码组件如ARX结构中的模加运算可视为一种非线性的安全性分析中。在我个人看来这种跨领域的思路融合是密码学研究的魅力所在。把公钥密码中深刻的计算复杂性思想用来剖析对称密码的具体结构往往能照亮那些单纯依靠传统对称密码分析难以看清的角落。虽然具体操作起来满是细节和计算但当你看到通过这种建模能够为一段精巧的密码算法勾勒出一个清晰的安全边界时那种感觉是非常扎实和满足的。最后一个小建议是动手做的时候一定要从最小的、可完全验证的实例开始把每一步的中间结果都打印出来核对确保你的建模和代码与算法的实际行为严丝合缝这是避免在复杂分析中迷失方向的最有效方法。
