密码杂凑算法七大神剑之青干剑QGS设计原理详解

密码杂凑算法七大神剑之青干剑QGS设计原理详解

QGS算法简介

七剑”通常指梁羽生武侠小说《七剑下天山》中的七把宝剑，其中青干剑：象征“防守”，主人杨云聪，游龙剑克星。青干剑QGS属于对称加密算法的分支之一中的密码杂凑算法，其整体结构采用了目前较为成熟的海绵结构(SHA3使用的就是海绵结构)，这使得QGS算法的安全性和执行效率可以很好的得到保证。青干剑QGS的亮点是使用了安全和性能并驾齐驱的海绵结构和SBOX160系列大S盒，海绵结构的执行过程如下图所示：

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

海绵结构是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普及不如预期的一个现实原因。

QGS算法参数

QGS算法的输入为相当长的一段消息M(长度不大于2^256比特)，输出为固定长度的杂凑值Hash(128比特和256比特)。QGS算法的内部状态b大小为800比特，容量大小为c=2*l，分组大小r为800-c，杂凑值长度为l。QGS算法的置换函数为Perm(b,l,14)杂凑值为128比特和Perm(b,l,28)杂凑值为256比特，其中14和28为置换函数的轮数。

QGS算法消息填充和分块

（1）消息填充阶段

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

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

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

（2）消息分块阶段

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

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

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

QGS算法置换函数

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

其中Perm(800，128，14)如下图所示：

其中Perm(800，256，28)如下图所示：

其中基于ARX结构的5个160比特大S盒分别如下图所示：

其中SBOX5为32个并行的5比特S盒，如下图所示：

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

QGS算法消息吸收阶段

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

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

QGS算法消息挤压阶段

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

QGS128算法执行过程

QGS256算法执行过程

QGS算法总结

青干剑QGS算法的核心部分为800比特的置换函数：

（1）5个字间非线性扩散函数(基于ARX结构的160比特大S盒)SBOX160A，SBOX160B，SBOX160C，SBOX160D，SBOX160E的使用提供了密码算法必须的混淆性，扩散性和雪崩效应；

（2）5比特字间非线性扩散函数(5比特S盒)SBOX5提供了密码算法必须的混淆性，扩散性和雪崩效应；

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

（4）行变换使得行内的5个32位字相互依赖和影响，列变换使得列内的5个32位字相互依赖和影响，多轮之后25个32位字相互依赖和影响，牵一发而动全身(输入数据的细微变换会导致输出数据翻天覆地的变化)。