做硬件密码实现的朋友应该都体会过一件烦心事AES的加密通路调通后一看解密逻辑的面积心凉了半截。S盒要逆的列混合要逆的轮密钥加法虽然不用逆但整套逆变换摆在版图上硬生生多出一块芯片面积。更烦的是时序和功耗的平衡解密这条路径不是白送的它是拿工程师的头发换的。所以当我第一次读到ICEBERG这个分组加密算法的论文时第一反应是还有这种操作它把一个在数学里很出名、但在密码工程里不太常用的性质——对合结构——用到了极致让解密电路和加密电路共用同一套轮函数逻辑。简单说加密和解密对ICEBERG来说几乎是同一个操作只是子密钥的流动方向变了。这篇东西我会从对合概念讲起把ICEBERG的轮函数构造、子密钥编排、硬件面积账、安全权衡一次性聊透。适合三类人读做嵌入式安全或RFID芯片的硬件工程师对分组密码设计感兴趣的进阶学习者以及在轻量级密码算法里做选型的技术负责人。读完你至少能明白为什么有些密码天生解密便宜以及数学性质换来工程优势这件事在密码设计里到底怎么落地。1. 对合结构到底是个啥不搞懂这个性质后面都没法聊1.1 对合的定义一个函数是自己逆函数这件事对合involution的定义其实特别简单一个函数 (f)如果对定义域里的任意 (x)都有 (f(f(x)) x)那 (f) 就是对合函数。说白了这个函数就是它自己的逆函数同一个函数用两遍所有东西恢复原样。生活里的例子很多。镜子就是最典型的现实里的你照一次镜子镜像里出现一个反向的你再照一次这个反向的反向又变回正向。数学上取负号 (f(x) -x) 也是负负得正。翻书页、拧瓶盖再拧回去、把口袋内衬翻出来再翻回去全都符合这个模式。密码学里最常见的对合操作是异或(f(x) x \oplus K)连续异或同一个密钥两次(x) 原封不动地回来了。这个性质是分组密码里轮密钥加法的基石——没有它密钥加法这一层在解密的时候就要重新设计一套逻辑。但要注意对合是个全局性质和局部性质要分清的概念。两个对合函数复合在一起结果不一定还是对合。举个简单例子(f(x) -x) 是对合(g(x) 1-x) 也是对合但 (f(g(x)) x - 1) 用两遍得到的是 (x - 2)不是 (x)。所以设计一个整体对合的密码算法比简单地把几个对合操作叠起来要难得多你必须处理层与层之间的相互作用。这一点后面讲ICEBERG的轮函数构造时是理解它的关键。1.2 从Feistel到SPN分组密码里的对合家族史分组密码的两大经典骨架——Feistel结构和SPN结构——在对合这件事上的待遇截然不同。Feistel结构的代表是DES。它的每一次迭代只改分组的一半另一半原样拿着做轮函数输入。这个结构有一个非常著名的数学性质不管轮函数 (F) 本身是什么整个Feistel网络天然是对合的只要把子密钥的使用顺序反过来。这就是为什么DES的解密可以直接复用加密的硬件数据通路只是密钥调度的读序不同。Feistel是天生就对合解密路径白送。SPN结构的代表是AES。它的每一轮同时对整个分组做替换和扩散扩散效率比Feistel高得多——每一轮里所有比特都能互相关联上。但代价就是轮函数里的S盒、行移位、列混合这些操作都必须单独构造逆操作。AES的解密需要逆S盒、逆行移位、逆列混合一套完整的反向轮函数。虽然工程上有技巧可以让正逆变换共用一部分电路但本质上SPN的加解密路径是不对称的解密就是要比加密贵。这个矛盾就是ICEBERG出现的背景能不能造一个既保留SPN优秀扩散性能、又让解密路径像Feistel一样白送的算法对合结构就是这个问题的答案。1.3 解密免费的工程红利比省面积更值钱很多人第一次听到对合结构第一反应是解密省电路。对这是最直观的好处但不是全部。我实际做项目之后发现加解密路径完全一致这件事在工程上的连锁收益比想象中多得多。首先是掩码方案可以复用。搞侧信道防护的同学都知道做一套掩码masking设计的验证工作量有多大。如果加密和解密是两套数据通路掩码就得做两遍每个中间值都要重新算掩码表示。ICEBERG这种对合结构掩码变换在加解密两边是同一套逻辑验证工作量直接减半。其次是设计周期。一次实现两遍功能综合、布局布线、时序收敛都只需要做一遍。在项目工期紧的时候这一个优势可能比省那几千个门电路还关键。最后是个容易被忽略的点加解密路径的功耗对称性。很多侧信道攻击会利用加密和解密过程中功耗曲线的差异来校准模板攻击的模板特征。如果加解密走的是同一条物理路径攻击者能用来做区分的信息维度就少了一个。这不是安全证明但确实在实践中让某些攻击路径变得更麻烦。2. 在SPN里塞进对合结构ICEBERG的轮函数与密钥编排2.1 先把参数底牌亮出来ICEBERG是2004年前后由几位韩国学者提出的分组加密算法目标平台从一开始就是低成本硬件。它的基本参数如下分组长度64比特密钥长度128比特轮数16轮结构SPN结构S盒4比特S盒两个交替使用扩散层基于Hadamard矩阵/线性码构造的二元矩阵核心卖点加密路径与解密路径共用同一套轮函数这个参数组合放在今天看并不惊艳甚至有点复古。64比特分组在现代密码学标准里已经不够看了得需要至少128比特分组才能抗住生日攻击。但在它提出的那个年代RFID标签和传感器节点的计算资源极其有限64比特分组配合轻量级的轮函数换来的是电路面积和功耗的可控性。理解一个算法的设计目标一定要把它放回当时的历史场景里看而不是用今天的标准去审判它。2.2 轮函数三层拆解每一层都努力做对合层ICEBERG的轮函数由三个子层复合而成密钥加层、S盒替换层、线性扩散层。我们来逐一拆解每个子层是怎么处理对合性问题的。密钥加层最简单就是异或轮子密钥。异或天然对合加了一次再加密钥就回到原位这一层零成本满足对合。S盒替换层是第一个技术难点。ICEBERG用的是4比特S盒而不是AES那种8比特S盒。4比特S盒的好处是面积极小一个盒只有4个输入比特组合逻辑非常省但代价是4比特S盒的差分均匀度和线性逼近优势可能不如8比特S盒所以需要从代数构造上多花心思。ICEBERG的论文里设计了两个不同的4比特对合S盒每个S盒都满足自己是自己的逆映射。这两个S盒在一轮内部交替使用——比如奇数位置用S1偶数位置用S2——既保证了每一层的对合性又通过混用两个代数表达式的替换来抑制简单S盒在连续迭代中的代数规律。那么4比特对合S盒怎么构造我记得论文里的思路是从有限域上做文章。在一个特征为2的有限域里取一个元素的乘法逆元这个映射本身是逆运算而逆运算的逆运算是它自己所以直接把 (x \mapsto x^{-1}) 这个映射拿来用天然就是自逆的。再在这个基础上复合一些保序的仿射变换只要仿射变换选取得当整个S盒仍然能保持对合。这种构造方式和AES的S盒同源AES也是用有限域逆加仿射变换构造的只不过AES没有刻意去保持对合性ICEBERG在设计取舍里把自逆当成了硬约束。线性扩散层是第二个技术难点。ICEBERG的扩散层用了基于Hadamard矩阵构造的二元矩阵。这类矩阵的好处在于合适的Hadamard矩阵天然满足矩阵乘自己等于单位阵或者转置等于自己的性质。意思是一个比特的变化经过这一层扩散能同时影响多个输出比特扩散性能好而且这个线性变换的逆变换恰好就是它自己对合性满足。所以从单层角度看ICEBERG的三个子层全部是对合的。但前面已经说过两个对合函数的复合不一定对合。如果只是简单地对合S盒 对合扩散矩阵 异或密钥层叠加解密的时候密钥加层的顺序、S盒与扩散层的交互都会出问题整体结构依然没法直接复用加密电路。ICEBERG真正的工程巧思在于它用子密钥编排的对称性解决了层与层之间的对合复合问题。2.3 子密钥编排的镜像对称解决复合对合的真正钥匙ICEBERG的密钥编排据我看到的设计思路是先通过非线性的密钥扩展算法从128比特主密钥生成一个中间密钥相关的量再从中间量派生出16轮子密钥。最关键的地方在于第1轮到第8轮的子密钥序列与第9轮到第16轮的子密钥序列围绕整个调度表的中心呈镜像对称关系。这个设计解决了一个看似绕不开的难题如果轮函数整体对合解密时数据流反向流动每一轮遇到的子密钥应该和加密时对应位置的子密钥是什么关系答案在普通SPN里是要用逆子密钥在Feistel里是把子密钥倒序但ICEBERG因为子密钥序列本身镜像对称解密时不需要重新生成一套反序的子密钥序列只需要改变子密钥轮数的读取方向——硬件上就是改了一个指针或者计数器。更深一层看为什么要用镜像对称而不是更简单的完全对称或完全独立因为如果16轮子密钥完全一样安全性会出大问题轮间独立性不足如果完全独立解密时数据通路虽然能用但密钥调度器必须支持反向生成那就得要么把所有子密钥都存储下来费寄存器要么在硬件里再实现一套反向调度逻辑费电路。镜像对称正好卡在中间既保证了前后轮子密钥不同又让调度器只需一套硬件就能正反两向供钥。这个前后轮子密钥不同但是对称的思路本质上是用代数上的弱约束换工程上的强收益是理解ICEBERG设计哲学的钥匙。2.4 加密与解密对照一张表看清哪里一样、哪里不一样我用一张表来总结ICEBERG加解密时的各个操作操作步骤加密流程解密流程硬件是否共用S盒替换用S1/S2交替替换同样用S1/S2交替替换因为S盒对合完全共用同一套查表电路线性扩散Hadamard矩阵乘法同一个Hadamard矩阵乘法矩阵自逆完全共用同一套组合逻辑密钥加层与第i轮子密钥异或同样与第i轮子密钥异或异或自逆完全共用同一套XOR门子密钥生成正向读取轮密钥反向读取轮密钥同一套密钥调度逻辑仅读序改变如果你把加密轮函数和解密轮函数的所有模块名称摆在一起对比会发现模块列表一模一样唯一的区别是子密钥的读取顺序和数据的流向。这就是对合结构带来的最大工程红利——不是省了某个模块而是整个反向轮函数逻辑根本不存在。3. 解密免费硬件实现里的面积账、功耗账和时序账3.1 一个真实对比AES加解密实现里的面积税要说清楚ICEBERG省了什么得先知道普通SPN密码比如AES在同时支持加解密时付出了什么代价。假设你在ASIC上实现一个AES核心加密需要SubBytes、ShiftRows、MixColumns、AddRoundKey四个操作。如果只做加密S盒查找表或组合逻辑一套MixColumns矩阵乘一套面积是很紧凑的。但一旦要支持解密事情就变了InvSubBytes是逆S盒要么单独做一套查找表要么对S盒查找表做反向索引后者延迟更大InvMixColumns是一套完全不同的矩阵乘法和MixColumns不能共用只能单独画逻辑虽然ShiftRows的逆操作只是换了个移位方向但那也得有额外的布线或Mux控制。我记得业界给过一个粗略的估算一个同时支持加解密的AES核心面积大约比纯加密核心多出20%到30%。别小看这二三十个百分点的面积税对于一颗小尺寸RFID芯片来说这可能就卡在产品能不能塞进指定封装的关键线上。3.2 ICEBERG把面积省在哪几个具体环节ICEBERG的对合结构几乎把上面提到的每一条面积税都规避掉了S盒面积省一半普通SPN正逆S盒各一套ICEBERG只放一套因为正逆是同一个映射。4比特S盒虽然单价比8比特S盒便宜但省掉一套的含义是一样的。扩散层面积省一套Hadamard矩阵自逆加密和解密用的是同一个矩阵乘法组合逻辑只画一遍。反过来想如果一个SPN算法的扩散矩阵不是自逆的解密就得额外挂一套逆矩阵乘法的逻辑这就是纯面积开销。密钥调度面积省一套ICEBERG子密钥镜像对称硬件上只需要正向生成参数反向读取时只需要控制读序。很多普通SPN密码解密时要么预先存好全部轮密钥要一堆寄存器放着要么调度器里再实现一套反向扩展逻辑面积翻倍。ICEBERG两种坑都避开了。控制逻辑保持极简加解密切换就相当于数据从这头进还是从那头进的方向切换控制状态机简单得多。我记得论文里给出的ICEBERG硬件实现面积和同期的轻量级密码在同时支持加解密的条件下做对比非常有竞争力数量级上比AES那种完整加解密内核要省不少。具体数字这些年我已经记不太清建议以论文报告为准但趋势肯定是明确的对合结构在面积指标上确实能换来实打实的收益。3.3 面积之外的三笔隐性收益除了面积我在实际工程里还尝到了另外三个甜头。第一个是时序收敛变简单了。解密路径共享加密路径后关键路径只有一条综合工具不需要同时约束两条路径的时序时钟频率的收敛难度显著下降。对于追求低功耗的芯片来说这意味着可以在更低的电压下跑功耗还能再省一笔。第二个是验证成本大幅降低。加解密共用一个数据通路功能验证只需要证明正向走一遍再反向走一遍能回到原文比分别验证两套独立逻辑的等价性要省事得多。在密码模块的安全性验证比如抗故障注入验证里这个优势更明显——需要覆盖的攻击路径少了一半。第三个是硬件随机掩码的实现更顺畅。前面提到过掩码方案在加解密两边共用时中间值的随机化表达是一致的。我曾经在一个嵌入式安全项目里切过算法原来用普通SPN时加解密掩码逻辑要做好几套变体换成对合结构后掩码生成、掩码更新、掩码移除的逻辑直接统一了代码量肉眼可见地缩水。3.4 什么场景最吃这个特性坦白说如果你只想做单方向的加密比如存数据的时候算个校验密文、或者做一次哈希式操作那对合结构的好处不大。ICEBERG这类算法的甜区在于双向通信和资源受限同时成立的场景。RFID标签是最经典的例子标签要响应读写器的查询加密回数据解密命令加解密都得有。同时标签芯片的面积和功耗受到严格限制很多RFID标签连电池都没有靠射频场供电每一纳安功耗都在预算表里。ICEBERG这类对合结构算法在标签里实现一套硬件搞定双向加解密面积和功耗都省下来了。传感器网络、智能卡、NFC支付模块、物流溯源芯片这些场景的逻辑一样低成本设备既要加密发出去又要解密收进来对成本极其敏感。每次我看到讨论轻量级密码选型的文章都爱提AES-128的最小面积能压到多少门却很少提同一颗芯片还要把解密做进去这半个隐性需求。ICEBERG的思路提醒我们有时候更聪明的做法不是把单方向做小而是让另外一个方向直接归零。4. 对合不是免费的午餐安全代价与设计权衡4.1 密码设计的一条铁律结构越规整攻击面越顺手密码算法设计有个绕不开的悖论为了让硬件好做、面积小、功耗低你希望结构整齐、对称、规律强但攻击者最喜欢的就是整齐、对称、规律强的东西。对合结构相当于给算法强加了一套全局代数对称性。攻击者看到加密路径等于解密路径第一反应就是那我可以把正反两个方向的差分特征连起来用。典型的两类攻击就来了。一类是飞去来器boomerang攻击。这类攻击的基本操作就是把明文加密一段做修改再解密回来利用的是顶半段和底半段的独立差分特征。如果算法加解密路径对称攻击者的差分特征设计空间会更宽裕因为下半段的特征可以直接借用上半段路径的性质来构造。另一类是代数攻击。对合结构本质上是给代数方程组添加了冗余约束攻击者在构建布尔多项式系统时这些冗余约束可能让方程求解变得更容易。这就是为什么很多密码算法论文里光说结构巧妙是不够的你还得证明这些巧妙的结构不会给攻击者送子弹。4.2 ICEBERG怎么应对轮数、S盒交替和扩散强度ICEBERG对安全性的应对从我读过的公开分析来看主要靠三根支柱第一根是足够的轮数。ICEBERG是16轮。对比一下AES-128的标准轮数是10轮PRESENT是31轮但PRESENT的轮函数极其简单ICEBERG选16轮说明设计者很清楚对合结构的规整性需要用更多的迭代轮数来稀释。多几轮意味着差分特征和线性逼近的传播路径更长单轮特征再好也较难拼出一条覆盖全轮的实用路径。第二根是双S盒交替混用。前面提到S1和S2在每一轮交替排列。这不仅仅是给对合性服务的它更大的安全意义在于两个不同代数结构的S盒交替使用会让攻击者试图用统一的代数表达式描述整个替换层时遇到非齐次的痛苦。对于基于代数攻击和插值攻击的判断来说这种交替设计能明显提高分析难度。第三根是Hadamard扩散层的扩散速度。ICEBERG的扩散层一次能影响多个输出比特单个比特的扰动经过一两轮就能覆盖整个分组。对于不可能差分攻击和飞去来器攻击来说扩散快的算法意味着要构造一条长路径的差分特征更难因为中间截断的比特位置会迅速蔓延开很难维持截断差异的清晰结构。从我看到的公开文献记录来看ICEBERG在提出之后并没有出现实质性的、可复现的全轮攻击结果。它是安全的但也别因此就把安全当成它的最大卖点——它的最大卖点始终是对合结构带来的工程优势。4.3 用约束条件下的最优解眼光评价ICEBERG如果拿ICEBERG和AES拼每轮安全性强度ICEBERG会输拿它和现代轻量级算法拼软件实现速度它也不占优。但拿它和一个默认前提比——低成本硬件上加密解密都得做面积预算在几千门级别——它就呈现出一种我说不清道不明的优雅感。我见过不少人评价ICEBERG时把它当做一个失败的AES挑战者这让我有点哭笑不得。ICEBERG从来没打算跟AES在通用处理器上抢地盘。它是带着特定的工程约束出场的它的价值不是取代谁而是证明了在SPN结构里也能实现对合路径这个设计思路是走得通的。5. 站在ICEBERG肩膀上轻量级密码的对称路径传承5.1 同时代的省钱密码各显神通2000年代中后期轻量级密码设计迎来了一波井喷。各家算法省钱的方向不太一样可以拉一个表直观对比算法分组/密钥轮数结构省钱核心思路ICEBERG64/12816对合SPN加解密共用轮函数解密路径近乎免费PRESENT64/80或12831SPN4位S盒查表极小置换层布线省电轮函数简单HIGHT64/12832ARX纯异或、加法、循环移位无S盒查表面积极小PRINCE64/12812对称轮结构FX构造解密加密固定常量操作路径几乎完全对称你看ICEBERG不是唯一一个往对称路径方向使劲的。PRINCE更是把这个理念推到了极致——它的解密实现只需要加密实现加一个固定的alpha常量处理轮函数部分完全共用。这进一步验证了ICEBERG当初选对合结构作为核心设计约束是踩在了一个正确的技术方向上。5.2 解密路径也省的设计思想在后续算法里越走越远晚近一点的轻量级算法里你可以明显看到对合思想的变体在延续。比如Midori和SkINNY这类面向深度低功耗场景设计的算法都在刻意追求解密轮函数与加密轮函数尽量同构。SkINNY的官方文档里甚至直接把这一条列为设计目标之一。更广义地说很多AEAD认证加密方案的硬件实现里底层的分组密码如果天然对合或者加解密路径对称认证加密的整体电路就会紧凑得多。因为认证加密在解密方向上本来就要同时做解密和认证两个操作底层分组密码的解密代价越低整个方案的硬件成本就越可控。我甚至见过一些做白盒密码和混淆实现的团队会优先考虑加解密路径对称的底层密码因为对称路径可以让加解密变换的嵌入表示保持一致从而减小混淆表的总规模。这说明对合结构的应用范围早就超出了RFID芯片省钱密码这个小圈层。5.3 从ICEBERG里我学到的三件密码工程之外的事第一件数学性质是有工程价格的。对合、自逆矩阵、有限域逆映射这些词听起来像是纯数学对象但它们背后直接对应的是芯片上省掉的一堆逻辑门。做密码工程的人如果能多从代数结构层面理解算法很多性能问题其实在算法选择阶段就可以避免。第二件评估一个密码不能脱离它的目标场景。ICEBERG跟你说我安全是没意义的你要问的是在面积预算两千克门、加密解密都要、功耗不能超过多少微瓦的前提下ICEBERG是网安全性和成本之间最好的折中吗把约束条件列清楚选择自然就浮出水面了。第三件对称性在密码学里是双刃剑。对合结构给了你面积和功耗的优惠券但也给了攻击者代数结构上的抓手。设计者必须用轮数、S盒多样性、扩散强度这些手段把安全漏洞补回去。看到任何一个免费性质第一反应应该是这个免费背后谁买单。最后说点我自己的体会我对ICEBERG的兴趣从第一眼看到它的轮函数图就产生了——十几年前第一次在FPGA上复现它的时候代码量比我预想的小得多因为加解密真的只有一套逻辑。我记得当时在仿真波形里看到解密出来的明文和原始明文完全对上的那一刻觉得一个看似抽象的数学性质对合变成芯片上实实在在的面积优势这个转化链路的魅力是很多复杂算法给不了的。如果你也想深入研究这个算法我建议别光读论文亲手去写一轮加解密的实现。ICEBERG的轮函数结构足够简洁用任何一门语言写一个软件验证模型都不难。等你写完加密再把解密函数写出来你会发现解密函数几乎可以复制粘贴——区别只有子密钥的读序。那一下的触动比看十篇论文摘要都管用。密码设计的精妙之处往往不是多了什么而是恰到好处地少了一样东西。
解密电路零成本？ICEBERG用对合结构实现加解密硬件共用
做硬件密码实现的朋友应该都体会过一件烦心事AES的加密通路调通后一看解密逻辑的面积心凉了半截。S盒要逆的列混合要逆的轮密钥加法虽然不用逆但整套逆变换摆在版图上硬生生多出一块芯片面积。更烦的是时序和功耗的平衡解密这条路径不是白送的它是拿工程师的头发换的。所以当我第一次读到ICEBERG这个分组加密算法的论文时第一反应是还有这种操作它把一个在数学里很出名、但在密码工程里不太常用的性质——对合结构——用到了极致让解密电路和加密电路共用同一套轮函数逻辑。简单说加密和解密对ICEBERG来说几乎是同一个操作只是子密钥的流动方向变了。这篇东西我会从对合概念讲起把ICEBERG的轮函数构造、子密钥编排、硬件面积账、安全权衡一次性聊透。适合三类人读做嵌入式安全或RFID芯片的硬件工程师对分组密码设计感兴趣的进阶学习者以及在轻量级密码算法里做选型的技术负责人。读完你至少能明白为什么有些密码天生解密便宜以及数学性质换来工程优势这件事在密码设计里到底怎么落地。1. 对合结构到底是个啥不搞懂这个性质后面都没法聊1.1 对合的定义一个函数是自己逆函数这件事对合involution的定义其实特别简单一个函数 (f)如果对定义域里的任意 (x)都有 (f(f(x)) x)那 (f) 就是对合函数。说白了这个函数就是它自己的逆函数同一个函数用两遍所有东西恢复原样。生活里的例子很多。镜子就是最典型的现实里的你照一次镜子镜像里出现一个反向的你再照一次这个反向的反向又变回正向。数学上取负号 (f(x) -x) 也是负负得正。翻书页、拧瓶盖再拧回去、把口袋内衬翻出来再翻回去全都符合这个模式。密码学里最常见的对合操作是异或(f(x) x \oplus K)连续异或同一个密钥两次(x) 原封不动地回来了。这个性质是分组密码里轮密钥加法的基石——没有它密钥加法这一层在解密的时候就要重新设计一套逻辑。但要注意对合是个全局性质和局部性质要分清的概念。两个对合函数复合在一起结果不一定还是对合。举个简单例子(f(x) -x) 是对合(g(x) 1-x) 也是对合但 (f(g(x)) x - 1) 用两遍得到的是 (x - 2)不是 (x)。所以设计一个整体对合的密码算法比简单地把几个对合操作叠起来要难得多你必须处理层与层之间的相互作用。这一点后面讲ICEBERG的轮函数构造时是理解它的关键。1.2 从Feistel到SPN分组密码里的对合家族史分组密码的两大经典骨架——Feistel结构和SPN结构——在对合这件事上的待遇截然不同。Feistel结构的代表是DES。它的每一次迭代只改分组的一半另一半原样拿着做轮函数输入。这个结构有一个非常著名的数学性质不管轮函数 (F) 本身是什么整个Feistel网络天然是对合的只要把子密钥的使用顺序反过来。这就是为什么DES的解密可以直接复用加密的硬件数据通路只是密钥调度的读序不同。Feistel是天生就对合解密路径白送。SPN结构的代表是AES。它的每一轮同时对整个分组做替换和扩散扩散效率比Feistel高得多——每一轮里所有比特都能互相关联上。但代价就是轮函数里的S盒、行移位、列混合这些操作都必须单独构造逆操作。AES的解密需要逆S盒、逆行移位、逆列混合一套完整的反向轮函数。虽然工程上有技巧可以让正逆变换共用一部分电路但本质上SPN的加解密路径是不对称的解密就是要比加密贵。这个矛盾就是ICEBERG出现的背景能不能造一个既保留SPN优秀扩散性能、又让解密路径像Feistel一样白送的算法对合结构就是这个问题的答案。1.3 解密免费的工程红利比省面积更值钱很多人第一次听到对合结构第一反应是解密省电路。对这是最直观的好处但不是全部。我实际做项目之后发现加解密路径完全一致这件事在工程上的连锁收益比想象中多得多。首先是掩码方案可以复用。搞侧信道防护的同学都知道做一套掩码masking设计的验证工作量有多大。如果加密和解密是两套数据通路掩码就得做两遍每个中间值都要重新算掩码表示。ICEBERG这种对合结构掩码变换在加解密两边是同一套逻辑验证工作量直接减半。其次是设计周期。一次实现两遍功能综合、布局布线、时序收敛都只需要做一遍。在项目工期紧的时候这一个优势可能比省那几千个门电路还关键。最后是个容易被忽略的点加解密路径的功耗对称性。很多侧信道攻击会利用加密和解密过程中功耗曲线的差异来校准模板攻击的模板特征。如果加解密走的是同一条物理路径攻击者能用来做区分的信息维度就少了一个。这不是安全证明但确实在实践中让某些攻击路径变得更麻烦。2. 在SPN里塞进对合结构ICEBERG的轮函数与密钥编排2.1 先把参数底牌亮出来ICEBERG是2004年前后由几位韩国学者提出的分组加密算法目标平台从一开始就是低成本硬件。它的基本参数如下分组长度64比特密钥长度128比特轮数16轮结构SPN结构S盒4比特S盒两个交替使用扩散层基于Hadamard矩阵/线性码构造的二元矩阵核心卖点加密路径与解密路径共用同一套轮函数这个参数组合放在今天看并不惊艳甚至有点复古。64比特分组在现代密码学标准里已经不够看了得需要至少128比特分组才能抗住生日攻击。但在它提出的那个年代RFID标签和传感器节点的计算资源极其有限64比特分组配合轻量级的轮函数换来的是电路面积和功耗的可控性。理解一个算法的设计目标一定要把它放回当时的历史场景里看而不是用今天的标准去审判它。2.2 轮函数三层拆解每一层都努力做对合层ICEBERG的轮函数由三个子层复合而成密钥加层、S盒替换层、线性扩散层。我们来逐一拆解每个子层是怎么处理对合性问题的。密钥加层最简单就是异或轮子密钥。异或天然对合加了一次再加密钥就回到原位这一层零成本满足对合。S盒替换层是第一个技术难点。ICEBERG用的是4比特S盒而不是AES那种8比特S盒。4比特S盒的好处是面积极小一个盒只有4个输入比特组合逻辑非常省但代价是4比特S盒的差分均匀度和线性逼近优势可能不如8比特S盒所以需要从代数构造上多花心思。ICEBERG的论文里设计了两个不同的4比特对合S盒每个S盒都满足自己是自己的逆映射。这两个S盒在一轮内部交替使用——比如奇数位置用S1偶数位置用S2——既保证了每一层的对合性又通过混用两个代数表达式的替换来抑制简单S盒在连续迭代中的代数规律。那么4比特对合S盒怎么构造我记得论文里的思路是从有限域上做文章。在一个特征为2的有限域里取一个元素的乘法逆元这个映射本身是逆运算而逆运算的逆运算是它自己所以直接把 (x \mapsto x^{-1}) 这个映射拿来用天然就是自逆的。再在这个基础上复合一些保序的仿射变换只要仿射变换选取得当整个S盒仍然能保持对合。这种构造方式和AES的S盒同源AES也是用有限域逆加仿射变换构造的只不过AES没有刻意去保持对合性ICEBERG在设计取舍里把自逆当成了硬约束。线性扩散层是第二个技术难点。ICEBERG的扩散层用了基于Hadamard矩阵构造的二元矩阵。这类矩阵的好处在于合适的Hadamard矩阵天然满足矩阵乘自己等于单位阵或者转置等于自己的性质。意思是一个比特的变化经过这一层扩散能同时影响多个输出比特扩散性能好而且这个线性变换的逆变换恰好就是它自己对合性满足。所以从单层角度看ICEBERG的三个子层全部是对合的。但前面已经说过两个对合函数的复合不一定对合。如果只是简单地对合S盒 对合扩散矩阵 异或密钥层叠加解密的时候密钥加层的顺序、S盒与扩散层的交互都会出问题整体结构依然没法直接复用加密电路。ICEBERG真正的工程巧思在于它用子密钥编排的对称性解决了层与层之间的对合复合问题。2.3 子密钥编排的镜像对称解决复合对合的真正钥匙ICEBERG的密钥编排据我看到的设计思路是先通过非线性的密钥扩展算法从128比特主密钥生成一个中间密钥相关的量再从中间量派生出16轮子密钥。最关键的地方在于第1轮到第8轮的子密钥序列与第9轮到第16轮的子密钥序列围绕整个调度表的中心呈镜像对称关系。这个设计解决了一个看似绕不开的难题如果轮函数整体对合解密时数据流反向流动每一轮遇到的子密钥应该和加密时对应位置的子密钥是什么关系答案在普通SPN里是要用逆子密钥在Feistel里是把子密钥倒序但ICEBERG因为子密钥序列本身镜像对称解密时不需要重新生成一套反序的子密钥序列只需要改变子密钥轮数的读取方向——硬件上就是改了一个指针或者计数器。更深一层看为什么要用镜像对称而不是更简单的完全对称或完全独立因为如果16轮子密钥完全一样安全性会出大问题轮间独立性不足如果完全独立解密时数据通路虽然能用但密钥调度器必须支持反向生成那就得要么把所有子密钥都存储下来费寄存器要么在硬件里再实现一套反向调度逻辑费电路。镜像对称正好卡在中间既保证了前后轮子密钥不同又让调度器只需一套硬件就能正反两向供钥。这个前后轮子密钥不同但是对称的思路本质上是用代数上的弱约束换工程上的强收益是理解ICEBERG设计哲学的钥匙。2.4 加密与解密对照一张表看清哪里一样、哪里不一样我用一张表来总结ICEBERG加解密时的各个操作操作步骤加密流程解密流程硬件是否共用S盒替换用S1/S2交替替换同样用S1/S2交替替换因为S盒对合完全共用同一套查表电路线性扩散Hadamard矩阵乘法同一个Hadamard矩阵乘法矩阵自逆完全共用同一套组合逻辑密钥加层与第i轮子密钥异或同样与第i轮子密钥异或异或自逆完全共用同一套XOR门子密钥生成正向读取轮密钥反向读取轮密钥同一套密钥调度逻辑仅读序改变如果你把加密轮函数和解密轮函数的所有模块名称摆在一起对比会发现模块列表一模一样唯一的区别是子密钥的读取顺序和数据的流向。这就是对合结构带来的最大工程红利——不是省了某个模块而是整个反向轮函数逻辑根本不存在。3. 解密免费硬件实现里的面积账、功耗账和时序账3.1 一个真实对比AES加解密实现里的面积税要说清楚ICEBERG省了什么得先知道普通SPN密码比如AES在同时支持加解密时付出了什么代价。假设你在ASIC上实现一个AES核心加密需要SubBytes、ShiftRows、MixColumns、AddRoundKey四个操作。如果只做加密S盒查找表或组合逻辑一套MixColumns矩阵乘一套面积是很紧凑的。但一旦要支持解密事情就变了InvSubBytes是逆S盒要么单独做一套查找表要么对S盒查找表做反向索引后者延迟更大InvMixColumns是一套完全不同的矩阵乘法和MixColumns不能共用只能单独画逻辑虽然ShiftRows的逆操作只是换了个移位方向但那也得有额外的布线或Mux控制。我记得业界给过一个粗略的估算一个同时支持加解密的AES核心面积大约比纯加密核心多出20%到30%。别小看这二三十个百分点的面积税对于一颗小尺寸RFID芯片来说这可能就卡在产品能不能塞进指定封装的关键线上。3.2 ICEBERG把面积省在哪几个具体环节ICEBERG的对合结构几乎把上面提到的每一条面积税都规避掉了S盒面积省一半普通SPN正逆S盒各一套ICEBERG只放一套因为正逆是同一个映射。4比特S盒虽然单价比8比特S盒便宜但省掉一套的含义是一样的。扩散层面积省一套Hadamard矩阵自逆加密和解密用的是同一个矩阵乘法组合逻辑只画一遍。反过来想如果一个SPN算法的扩散矩阵不是自逆的解密就得额外挂一套逆矩阵乘法的逻辑这就是纯面积开销。密钥调度面积省一套ICEBERG子密钥镜像对称硬件上只需要正向生成参数反向读取时只需要控制读序。很多普通SPN密码解密时要么预先存好全部轮密钥要一堆寄存器放着要么调度器里再实现一套反向扩展逻辑面积翻倍。ICEBERG两种坑都避开了。控制逻辑保持极简加解密切换就相当于数据从这头进还是从那头进的方向切换控制状态机简单得多。我记得论文里给出的ICEBERG硬件实现面积和同期的轻量级密码在同时支持加解密的条件下做对比非常有竞争力数量级上比AES那种完整加解密内核要省不少。具体数字这些年我已经记不太清建议以论文报告为准但趋势肯定是明确的对合结构在面积指标上确实能换来实打实的收益。3.3 面积之外的三笔隐性收益除了面积我在实际工程里还尝到了另外三个甜头。第一个是时序收敛变简单了。解密路径共享加密路径后关键路径只有一条综合工具不需要同时约束两条路径的时序时钟频率的收敛难度显著下降。对于追求低功耗的芯片来说这意味着可以在更低的电压下跑功耗还能再省一笔。第二个是验证成本大幅降低。加解密共用一个数据通路功能验证只需要证明正向走一遍再反向走一遍能回到原文比分别验证两套独立逻辑的等价性要省事得多。在密码模块的安全性验证比如抗故障注入验证里这个优势更明显——需要覆盖的攻击路径少了一半。第三个是硬件随机掩码的实现更顺畅。前面提到过掩码方案在加解密两边共用时中间值的随机化表达是一致的。我曾经在一个嵌入式安全项目里切过算法原来用普通SPN时加解密掩码逻辑要做好几套变体换成对合结构后掩码生成、掩码更新、掩码移除的逻辑直接统一了代码量肉眼可见地缩水。3.4 什么场景最吃这个特性坦白说如果你只想做单方向的加密比如存数据的时候算个校验密文、或者做一次哈希式操作那对合结构的好处不大。ICEBERG这类算法的甜区在于双向通信和资源受限同时成立的场景。RFID标签是最经典的例子标签要响应读写器的查询加密回数据解密命令加解密都得有。同时标签芯片的面积和功耗受到严格限制很多RFID标签连电池都没有靠射频场供电每一纳安功耗都在预算表里。ICEBERG这类对合结构算法在标签里实现一套硬件搞定双向加解密面积和功耗都省下来了。传感器网络、智能卡、NFC支付模块、物流溯源芯片这些场景的逻辑一样低成本设备既要加密发出去又要解密收进来对成本极其敏感。每次我看到讨论轻量级密码选型的文章都爱提AES-128的最小面积能压到多少门却很少提同一颗芯片还要把解密做进去这半个隐性需求。ICEBERG的思路提醒我们有时候更聪明的做法不是把单方向做小而是让另外一个方向直接归零。4. 对合不是免费的午餐安全代价与设计权衡4.1 密码设计的一条铁律结构越规整攻击面越顺手密码算法设计有个绕不开的悖论为了让硬件好做、面积小、功耗低你希望结构整齐、对称、规律强但攻击者最喜欢的就是整齐、对称、规律强的东西。对合结构相当于给算法强加了一套全局代数对称性。攻击者看到加密路径等于解密路径第一反应就是那我可以把正反两个方向的差分特征连起来用。典型的两类攻击就来了。一类是飞去来器boomerang攻击。这类攻击的基本操作就是把明文加密一段做修改再解密回来利用的是顶半段和底半段的独立差分特征。如果算法加解密路径对称攻击者的差分特征设计空间会更宽裕因为下半段的特征可以直接借用上半段路径的性质来构造。另一类是代数攻击。对合结构本质上是给代数方程组添加了冗余约束攻击者在构建布尔多项式系统时这些冗余约束可能让方程求解变得更容易。这就是为什么很多密码算法论文里光说结构巧妙是不够的你还得证明这些巧妙的结构不会给攻击者送子弹。4.2 ICEBERG怎么应对轮数、S盒交替和扩散强度ICEBERG对安全性的应对从我读过的公开分析来看主要靠三根支柱第一根是足够的轮数。ICEBERG是16轮。对比一下AES-128的标准轮数是10轮PRESENT是31轮但PRESENT的轮函数极其简单ICEBERG选16轮说明设计者很清楚对合结构的规整性需要用更多的迭代轮数来稀释。多几轮意味着差分特征和线性逼近的传播路径更长单轮特征再好也较难拼出一条覆盖全轮的实用路径。第二根是双S盒交替混用。前面提到S1和S2在每一轮交替排列。这不仅仅是给对合性服务的它更大的安全意义在于两个不同代数结构的S盒交替使用会让攻击者试图用统一的代数表达式描述整个替换层时遇到非齐次的痛苦。对于基于代数攻击和插值攻击的判断来说这种交替设计能明显提高分析难度。第三根是Hadamard扩散层的扩散速度。ICEBERG的扩散层一次能影响多个输出比特单个比特的扰动经过一两轮就能覆盖整个分组。对于不可能差分攻击和飞去来器攻击来说扩散快的算法意味着要构造一条长路径的差分特征更难因为中间截断的比特位置会迅速蔓延开很难维持截断差异的清晰结构。从我看到的公开文献记录来看ICEBERG在提出之后并没有出现实质性的、可复现的全轮攻击结果。它是安全的但也别因此就把安全当成它的最大卖点——它的最大卖点始终是对合结构带来的工程优势。4.3 用约束条件下的最优解眼光评价ICEBERG如果拿ICEBERG和AES拼每轮安全性强度ICEBERG会输拿它和现代轻量级算法拼软件实现速度它也不占优。但拿它和一个默认前提比——低成本硬件上加密解密都得做面积预算在几千门级别——它就呈现出一种我说不清道不明的优雅感。我见过不少人评价ICEBERG时把它当做一个失败的AES挑战者这让我有点哭笑不得。ICEBERG从来没打算跟AES在通用处理器上抢地盘。它是带着特定的工程约束出场的它的价值不是取代谁而是证明了在SPN结构里也能实现对合路径这个设计思路是走得通的。5. 站在ICEBERG肩膀上轻量级密码的对称路径传承5.1 同时代的省钱密码各显神通2000年代中后期轻量级密码设计迎来了一波井喷。各家算法省钱的方向不太一样可以拉一个表直观对比算法分组/密钥轮数结构省钱核心思路ICEBERG64/12816对合SPN加解密共用轮函数解密路径近乎免费PRESENT64/80或12831SPN4位S盒查表极小置换层布线省电轮函数简单HIGHT64/12832ARX纯异或、加法、循环移位无S盒查表面积极小PRINCE64/12812对称轮结构FX构造解密加密固定常量操作路径几乎完全对称你看ICEBERG不是唯一一个往对称路径方向使劲的。PRINCE更是把这个理念推到了极致——它的解密实现只需要加密实现加一个固定的alpha常量处理轮函数部分完全共用。这进一步验证了ICEBERG当初选对合结构作为核心设计约束是踩在了一个正确的技术方向上。5.2 解密路径也省的设计思想在后续算法里越走越远晚近一点的轻量级算法里你可以明显看到对合思想的变体在延续。比如Midori和SkINNY这类面向深度低功耗场景设计的算法都在刻意追求解密轮函数与加密轮函数尽量同构。SkINNY的官方文档里甚至直接把这一条列为设计目标之一。更广义地说很多AEAD认证加密方案的硬件实现里底层的分组密码如果天然对合或者加解密路径对称认证加密的整体电路就会紧凑得多。因为认证加密在解密方向上本来就要同时做解密和认证两个操作底层分组密码的解密代价越低整个方案的硬件成本就越可控。我甚至见过一些做白盒密码和混淆实现的团队会优先考虑加解密路径对称的底层密码因为对称路径可以让加解密变换的嵌入表示保持一致从而减小混淆表的总规模。这说明对合结构的应用范围早就超出了RFID芯片省钱密码这个小圈层。5.3 从ICEBERG里我学到的三件密码工程之外的事第一件数学性质是有工程价格的。对合、自逆矩阵、有限域逆映射这些词听起来像是纯数学对象但它们背后直接对应的是芯片上省掉的一堆逻辑门。做密码工程的人如果能多从代数结构层面理解算法很多性能问题其实在算法选择阶段就可以避免。第二件评估一个密码不能脱离它的目标场景。ICEBERG跟你说我安全是没意义的你要问的是在面积预算两千克门、加密解密都要、功耗不能超过多少微瓦的前提下ICEBERG是网安全性和成本之间最好的折中吗把约束条件列清楚选择自然就浮出水面了。第三件对称性在密码学里是双刃剑。对合结构给了你面积和功耗的优惠券但也给了攻击者代数结构上的抓手。设计者必须用轮数、S盒多样性、扩散强度这些手段把安全漏洞补回去。看到任何一个免费性质第一反应应该是这个免费背后谁买单。最后说点我自己的体会我对ICEBERG的兴趣从第一眼看到它的轮函数图就产生了——十几年前第一次在FPGA上复现它的时候代码量比我预想的小得多因为加解密真的只有一套逻辑。我记得当时在仿真波形里看到解密出来的明文和原始明文完全对上的那一刻觉得一个看似抽象的数学性质对合变成芯片上实实在在的面积优势这个转化链路的魅力是很多复杂算法给不了的。如果你也想深入研究这个算法我建议别光读论文亲手去写一轮加解密的实现。ICEBERG的轮函数结构足够简洁用任何一门语言写一个软件验证模型都不难。等你写完加密再把解密函数写出来你会发现解密函数几乎可以复制粘贴——区别只有子密钥的读序。那一下的触动比看十篇论文摘要都管用。密码设计的精妙之处往往不是多了什么而是恰到好处地少了一样东西。
