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

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

TPS算法简介

“七剑”通常指梁羽生武侠小说《七剑下天山》中的七把宝剑，其中天瀑剑：象征“无为”，主人武元英，柄芒不分。天瀑剑TPS属于对称加密算法的分支之一中的密码杂凑算法，其整体结构采用了目前较为成熟的海绵结构(SHA3使用的就是海绵结构)，这使得TPS算法的安全性和执行效率可以很好的得到保证。天瀑剑TPS的亮点是使用了安全和性能并驾齐驱的海绵结构和LLLLL系列线性扩散函数和非线性变换SBOX32，海绵结构的执行过程如下图所示：

以下是海绵结构的优缺点：

海绵结构是SHA-3（Keccak）的核心创新，它和传统哈希算法的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比特，容量大小为c=2*l，分组大小r为1024-c，杂凑值长度为l。TPS算法的置换函数为Perm(b,l,12)杂凑值为128比特和Perm(b,l,24)杂凑值为256比特，其中12和24为置换函数的轮数。

TPS算法消息填充和分块

（1）消息填充阶段

将输入的原始消息M按以下规则填充至分组大小r的最小整数倍。

当杂凑值l为128比特，c=256，r=1024-c=768；填充规则如下图所示：

当杂凑值l为256比特，c=512，r=1024-c=512；填充规则如下图所示：

（2）消息分块阶段

类似的，将填充后的消息MM以分组大小r为单位进行分组：

当r=768时，M0M1…Mn-2Mn-1=MM，其中|Mi|=768(i=0,1,…,n-2,n-1)；

当r=512时，M0M1…Mn-2Mn-1=MM，其中|Mi|=512(i=0,1,…,n-2,n-1)。

TPS算法置换函数

根据杂凑值l长度的不同可以将TPS算法置换函数分为两个版本：Perm(1024，128，12)和Perm(1024，256，24)。

其中Perm(1024，128，12)如下图所示：

其中Perm(1024，256，24)如下图所示：

其中SBOX32为4个8比特S盒的并置：

其中8比特S盒的查找表如下图所示：

其中线性扩散函数LLLLL0，LLLLL1，LLLLL2，LLLLL3(均为分支数为4的对合变换)如下图所示：

其中32个常量C如下图所示：

TPS算法消息吸收阶段

内部状态初始值1024比特全部为0。

对于第i个消息分组ri，将ri与内部状态的前768或者512比特进行异或运算，内部状态的后256或者512比特保持不变，然后对整个内部状态执行Perm(1024，128，12)或者Perm(1024，256，24)，若Perm执行完毕，然后处理第i+1个消息分组，以此类推，直至处理完成所有的消息分组。

TPS算法消息挤压阶段

当消息吸收阶段执行完毕(即所有的消息分组处理完毕)，消息挤压阶段开始执行。对整个内部状态执行Perm(1024，128，12)或者Perm(1024，256，24)，然后取输出内部状态的前128或者256比特作为该消息的杂凑值。

TPS128算法执行过程

TPS256算法执行过程

TPS算法总结

天瀑剑TPS算法的核心部分为1024比特的置换函数：

（1）4个字内线性扩散函数LLLLL的使用提供了密码算法必须的扩散性和雪崩效应；

（2）32个32位常量C的使用打破了算法的对称性的同时提高了算法的安全性；

（3）SBOX32提供了密码算法必须的混淆性和非线性复杂度。

（4）线性扩散函数LLLLL和SBOX32以及模加运算相互配合天衣无缝，这使得32位字之间的依赖关系相当复杂以至于整个算法难以分析，安全强度大大提升。