密码杂凑算法七大神剑之天瀑剑TPS设计原理详解

密码杂凑算法七大神剑之天瀑剑TPS设计原理详解TPS算法简介“七剑”通常指梁羽生武侠小说《七剑下天山》中的七把宝剑其中天瀑剑象征“无为”主人武元英柄芒不分。天瀑剑TPS属于对称加密算法的分支之一中的密码杂凑算法其整体结构采用了目前较为成熟的海绵结构(SHA3使用的就是海绵结构)这使得TPS算法的安全性和执行效率可以很好的得到保证。天瀑剑TPS的亮点是使用了安全和性能并驾齐驱的海绵结构和LLLLL系列线性扩散函数和非线性变换SBOX32海绵结构的执行过程如下图所示以下是海绵结构的优缺点海绵结构是SHA-3Keccak的核心创新它和传统哈希算法的Merkle-Damgård结构思路完全不同。下面来看它的优缺点。海绵结构的优点极强的抗碰撞性这源于它内部状态非常大例如SHA3-256的状态是1600位远大于256位的输出。攻击者无法通过输出直接推算内部状态抵抗长度扩展攻击、原像攻击等的能力很强。可灵活调节安全等级同一套算法通过调整“容量”和“输出长度”两个参数就能平衡安全性和速度。容量越大安全性越高输出长度可以任意定制这叫作“全能哈希函数”一套算法就能实现SHA3-224到SHA3-512的全部变体。天生免疫长度扩展攻击传统SHA-2等算法的核心弱点在于可以从H(m)推算出H(m || padding || new_data)。而海绵结构的“吸收-挤出”两阶段设计以及最后截断输出的方式使其天然免疫此类攻击所以SHA-3可以直接用作消息认证码MAC。结构简洁便于安全分析海绵结构本身不定义具体的压缩函数只定义工作模式。你可以把它和内部的置换函数f分开分析。这种模块化设计降低了设计和实现的复杂度理论上也更健壮甚至可以用在硬件资源极少的场景。海绵结构的缺点软件性能相对较慢这是它最实际的短板。相比AES-NI等硬件指令集深度优化的SHA-2纯软件实现的SHA-3通常要慢不少因为它的内部置换操作更复杂。在一些没有硬件加速的老旧或低功耗设备上这一点很明显。初始化时存在“空跑”开销吸收第一块数据前需要先处理一大块全是0的状态这在处理短消息时会造成冗余计算导致短消息哈希速度不理想。并行计算不友好其内部置换是顺序执行的无法像SHA-2或BLAKE2那样将多个数据块的计算并行化单个数据流的哈希速度有先天瓶颈。大状态消耗更多资源1600位的内部状态意味着需要更多的寄存器、内存和功耗。在资源极度受限的硬件如RFID芯片上这反而成了劣势。历史生态惯性SHA-2已有几十年的安全运行历史和广泛的软硬件基础设施迁移到SHA-3的动力不足。在大多数场景下SHA-2尤其是带硬件加速的SHA-256依然是更快的选择这也是SHA-3普及不如预期的一个现实原因。TPS算法参数TPS算法的输入为相当长的一段消息M(长度不大于2^256比特)输出为固定长度的杂凑值Hash(128比特和256比特)。TPS算法的内部状态b大小为1024比特容量大小为c2*l分组大小r为1024-c杂凑值长度为l。TPS算法的置换函数为Perm(b,l,12)杂凑值为128比特和Perm(b,l,24)杂凑值为256比特其中12和24为置换函数的轮数。TPS算法消息填充和分块1消息填充阶段将输入的原始消息M按以下规则填充至分组大小r的最小整数倍。当杂凑值l为128比特c256r1024-c768填充规则如下图所示当杂凑值l为256比特c512r1024-c512填充规则如下图所示2消息分块阶段类似的将填充后的消息MM以分组大小r为单位进行分组当r768时M0M1…Mn-2Mn-1MM其中|Mi|768(i0,1,…,n-2,n-1)当r512时M0M1…Mn-2Mn-1MM其中|Mi|512(i0,1,…,n-2,n-1)。TPS算法置换函数根据杂凑值l长度的不同可以将TPS算法置换函数分为两个版本Perm(102412812)和Perm(102425624)。其中Perm(102412812)如下图所示其中Perm(102425624)如下图所示其中SBOX32为4个8比特S盒的并置其中8比特S盒的查找表如下图所示其中线性扩散函数LLLLL0LLLLL1LLLLL2LLLLL3(均为分支数为4的对合变换)如下图所示其中32个常量C如下图所示TPS算法消息吸收阶段内部状态初始值1024比特全部为0。对于第i个消息分组ri将ri与内部状态的前768或者512比特进行异或运算内部状态的后256或者512比特保持不变然后对整个内部状态执行Perm(102412812)或者Perm(102425624)若Perm执行完毕然后处理第i1个消息分组以此类推直至处理完成所有的消息分组。TPS算法消息挤压阶段当消息吸收阶段执行完毕(即所有的消息分组处理完毕)消息挤压阶段开始执行。对整个内部状态执行Perm(102412812)或者Perm(102425624)然后取输出内部状态的前128或者256比特作为该消息的杂凑值。TPS128算法执行过程TPS256算法执行过程TPS算法总结天瀑剑TPS算法的核心部分为1024比特的置换函数14个字内线性扩散函数LLLLL的使用提供了密码算法必须的扩散性和雪崩效应232个32位常量C的使用打破了算法的对称性的同时提高了算法的安全性3SBOX32提供了密码算法必须的混淆性和非线性复杂度。4线性扩散函数LLLLL和SBOX32以及模加运算相互配合天衣无缝这使得32位字之间的依赖关系相当复杂以至于整个算法难以分析安全强度大大提升。