Skip to content

Latest commit

 

History

History
368 lines (211 loc) · 15.3 KB

report.md

File metadata and controls

368 lines (211 loc) · 15.3 KB

SanSi

三思而后行。

简介

介绍

三思（SanSi）是一个新型迭代哈希密码，可以接收输入的文件或字符串并将其哈希为 80 位的位串。

不同于传统顺序处理的 Sponge 结构，SanSi 在其基础上引入了更多的复杂性：将顺次线性处理分块的结构改变为树形结构，通过在处理顺序的维度引入更多的复杂性（在每次读入时不直接顺序处理而是在积累了一定数量后以树形结构的方式进行处理，即“三思而后行”）加强了密码，使得长度扩展攻击等攻击方法更加困难。同时，三思还在 f 函数处引入了不同的方法。

小组分工

本算法由刘子君、刘泽禹、庞元喆、徐明启、刘方舟设计、实现并完成评估。

组员 分工
刘子君 文献查阅，生日攻击检测，算法随机性检测，文档撰写
刘泽禹 文献查阅，算法设计，算法实现，效率评估，文档撰写
庞元喆 文献查阅，算法设计，算法实现
徐明启 文献查阅，算法审查
刘方舟（组长） 算法实现，随机路径检测，文档撰写

使用方法

Demo

如果要运行 Demo，可以在文件夹下 make all 并运行下列几种命令：

  1. 文件哈希：./main <arg1>。其中 <arg1> 为一个文件的路径，其哈希值将被打印在标准输出中。
  2. 字符串哈希：
    1. ./main 进入交互模式，在控制台中输入一个字符串，输出该字符串对应的哈希值。
    2. ./main <arg1> <arg2>。其中 <arg1> 与 <arg2> 分别为输入、输出文件地址。输入文件中以换行符分割若干组需要哈希的字符串，输出文件的每行为对应字符串的哈希值。

使用

可以通过在自定义程序中引用 SanSi 算法头文件、并在编译时进行链接进行使用，具体示例如下。

#include "sansi.h"

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main() {
    Sansi crypto; // 实例化 SanSi 哈希计算器
    
    // 情形一: 字符串哈希
    string data = "目标字符串"; // 或者: const char *data = "目标字符串";
    cout << crypto.stringHash(data) << endl; // 输出哈希结果
    ...
    
    // 情形二: 文件哈希
    const char *file = "目标文件路径";
    cout << crypto.fileHash(file) << endl; // 输出哈希结果
    ...
    
    // 情形三: 自定义流式运算
    uint64_t *src;
    int length;
    ...
    crypto.add_block(src); // 每调用一次 add_block(), 可添加一个 1024 位的分块
    ...
    // 当确定输入即将结束时，可以对输入做填充
    length = Sansi::pad(src, length); // 参数 length 为当前输入 src 的[字节]数，返回填充后的[字节]数
    for (int i = 0; i < (length >> 3); i += 16) {
        crypto.add_block(src + i); // 将余下的分组添入 crypto
    }
    cout << crypto.hash() << endl; // 输出哈希结果
    crypto.reset(); // 若之后继续使用该对象，需清空其状态
    ...
    
    return 0;
}

设计理念

在哈希函数密码一类问题中，哈希函数 $h$ 需要将无穷域上的输入映射到固定长度上。因此，多数哈希函数密码采用迭代的方式对此进行处理。传统的迭代结构，如 Merkle-Damgård 结构、Sponge 结构尽管有所不同，但均采用了顺序执行的方式，即依次处理将数据流嵌入状态中，最终再依据状态进行输出。

在这样的背景下，我们考虑在处理顺序的维度上引入更多的复杂性，通过树形结构而非线性结构处理数据。此时，当我们通过黑盒的视角来观察哈希函数 $h$ 和加密的字符串时，其具体结构会更加不可知，并难以被攻击。

在这一想法的基础上，我们的工作集中于：

  • 设计一个合理的计算顺序规则，使得对于不同的字符串输入 $h$ 能够将其以较为混乱的顺序进行处理，并且保证同一个字符串的处理顺序是一定的。
  • 将字符串分块的位置信息内嵌入 f 函数中，使得攻击者无法通过仅仅调换两个分块的顺序找到碰撞。

我们算法设计的最终结果采取了等待输入积累了一定组数的分组后再进行树形合并处理的方式。在我们看来，这一过程就好比“三思而后行”的过程（积累、再执行），与传统迭代结构中“直接行动”的范式相区别。因此，我们将我们的设计理念融入算法的名称当中，命名其为“三思”。

算法组成

算法流程

算法的基本流程如下图。

迭代结构

Sponge 结构的函数主要是由内存状态 $S$、转换函数 $f$ 和填充函数 $P$ 构成的。本算法的树形迭代结构与其有一定的相似之处。在本节中，我们围绕内存状态、树形处理和输出结果三个部分介绍本算法的迭代结构，转换函数 $f$ 和填充函数 $P$ 将在后续章节中进行详细介绍。

内存状态

与采用 Sponge 结构的 SHA-3 类似，SanSi 采用了大小为 1600 比特的内存状态，并将其组织成为一个 $5 \times 5 \times 64$ 的三维张量的形式如下图所示。

在 $S$ 中，我们可以通过三维下标 $s_{x, y, z}$ 对某一位进行索引。约定 $s_{x, y}$ 为一个 64 位的整数 $s_{x, y, 0} \dots s_{x, y, 63}$。

为方便起见，我们约定沿 $x$ 方向为一列、沿 $y$ 方向为一行。

树形处理

分组内嵌

与传统的线性处理结构不同，SanSi 引入了树形处理结构。约定 1024 比特为一个分组，8 个分组为一个大组。

对于每个分组输入，算法首先根据组的奇偶性进行判别：奇数位的组将与全0的内存状态相异或；偶数位的组将与全1的内存状态相异或（异或范围为 $S$ 的前 1024 比特）。异或后运行一次 f 函数进行打乱。

启发值计算

对于每一个输入的块，我们通过其位置和内在信息计算出一个对应的权值作为启发值 $k$ 用于确定树形结构合并的计算顺序。令 $\text{pos}$ 为块在数据流中的位置，则有 $$ k = (\bigoplus \limits_{i = 0}^4 \bigoplus \limits_{j = 0}^4 s_{i, j}) \oplus \text{pos} $$

合并状态

在完成了每个分组的状态内嵌后，我们的算法得到了一系列的内存状态 $S$，此时需要将其进行合并。以 8 个分组为一个大组，每当读入一个完整的大组，依据启发值从大到小将当前的所有内存状态依次进行合并。对于内存状态 $S_1, S_2$，单次合并得到 $S^*$ 的流程为：

  • 更新位置信息： $$ \text{pos}^* = \lfloor \frac{\text{pos}_1 + \text{pos}_2}{2} \rfloor $$

  • 更新内存状态： $$ S^* = S_1 \oplus S_2 $$

  • 进行打乱： $$ S^* = f(S^*) $$

  • 重新计算启发值 $k$。

最终的合并顺序可视化后呈现树形结构。一种可能的合并示意图如下图所示。

输出结果

与 Sponge 结构类似，本算法采用了迭代输出的方式，在共计 20 轮中每轮输出四位 $s_{0, 0, 0} s_{0, 0, 1} s_{0, 0, 2} s_{0, 0, 3}$ 后再运行一次 f 函数。

f 函数

概述

在“设计理念”一节中，我们已经提到，由于树形结构与线性结构的不同，本算法的 f 函数还需要嵌入位置信息以避免攻击者通过简单调换两个分块的位置来制造碰撞。在这一节中，我们会通过介绍 f 函数的具体流程来说明这一目的是如何完成的。

具体而言，本算法的 f 函数中包含两轮，每一轮依次完成 $\sigma, \rho, \pi, \alpha, \chi$ 5个阶段。

$\sigma$ 阶段

$\sigma$（stencil）阶段使得每一位与其上下左右相邻的 6 位相互影响。

在这一阶段中，我们将 $s_{i,j}$ 的 64 位拆分为 4 个 16 位的整数，不妨设为 $t_{i, j, 0}, \dots, t_{i, j, 3}$。

对于任一 8 位整数，我们首先考虑对其进行 7 点模板计算（stencil），即 $$ t_{i, j, k} = g(t_{i - 1, j, k}, t_{i, j - 1, k}, t_{i, j, k - 1}, t_{i, j, k}, t_{i, j, k + 1}, t_{i, j + 1, k}, t_{i + 1, j, k}) $$ 模板计算的内容与CRC校验和的思想类似，即将等式右侧的7个数值相加得到整数 $z$，如果 $z$ 超过 $l = 2^{16} - 1$，则对其进行校验和计算：

while z > l:
	z <- z % l + z / l

为了计算的效率，我们将上述循环简化为固定进行三轮，再对 $l$ 取模（16位截断），即

z <- z % l + z / l
z <- z % l + z / l
z <- z % l + z / l
z <- z % l

设这一过程为函数 $\text{CRC}'(z)$，该过程是非线性的。

同时，在 $\sigma$ 阶段中，我们引入位置信息，即 $$ t_{i, j, k} = \text{CRC}'(t_{i - 1, j, k} + t_{i, j - 1, k} + t_{i, j, k - 1} + t_{i, j, k} + t_{i, j, k + 1} + t_{i, j + 1, k} + t_{i + 1, j, k} + \text{pos} \times c) $$ 其中 $c$ 为一个固定常数：0xB7E1。该值的获取方式：自然常数 e 取小数部分的前 16 位。$c$ 的加入使得位置信息在 $\text{CRC}'$ 的计算中能够得到充分的扩散。

$\rho$ 阶段

$\rho$（rotation）阶段为将 $s_{i, j}$ 的 64 位进行位移轮换。在 SHA-3 算法 $\rho$ 阶段的基础上，我们将位置信息内嵌入了这一阶段。 $$ s_{i, j, k} = s_{i, j, (k - \frac{t(t - 1)}{2} + \text{pos})} $$ 注：此处的加减运算为模 64 意义下的。

$\pi$ 阶段

$\pi$（permutation）阶段为按行列顺序进行打乱。 $$ s_{3i + 2j, i} = s_{i, j} $$

$\alpha$ 阶段

$\alpha$（and）阶段按列进行非线性的“与”运算和“非”运算打乱。每列与其模意义下 $\pm 2$ 的列进行运算，融入一定的非局部特征。 $$ s_{i, j, k} = s_{i, j, k} \oplus ((s_{i + 2, j, k}) \And (\lnot s_{i - 2, j, k})) $$ 注：此处的加减法为模5意义下的加减法。

$\chi$ 阶段

$\chi$（xor）阶段将一个轮常数通过异或的方式嵌入内存状态中。两轮使用的轮常数分别为： $$ r_1=\text{0x243F6A8885A308D3} \quad r_2=\text{0x13198A2E03707344} $$ 这些值的获取方式：圆周率 π 取小数部分的 164 位、65128 位，并以低位在前（小端）格式存储。

填充

为了支持任意长度的输入，有必要对输入进行填充。SanSi 规定任何输入均需经过填充，并选用 $pad10^*1(\cdot)$ 作为填充函数。具体做法为：

  1. 在输入的末尾加入两个比特 $11$。
  2. 在上一步加入的两个 $1$ 之间填入 0~1023 个 $0$，使得输入的长度为分组长度 1024 的整数倍。

算法实现效率

测试方法

由于测试目标是算法实现效率，因此在测试时除去了 IO 时间与生成数据的时间，并且预先进行了两组数据的插入作为预热。

在具体测试框架中，代码使用 SanSi 加密了一个长度为 10000000 * 128 字节的字符串，即处理了 10000000 个分块共 10000000 * 1024 位的数据，并结合运行时间计算出运行效率，具体代码见 performance_test.cpp。

上述流程可在 make all 后运行 ./performance_test 完成。

测试环境

  • 设备：ThinkPad X1 Carbon
    • 处理器：Intel Core i7-10710U CPU
  • 系统：Windows 11
    • WSL 2：Ubuntu 20.04

测试结果

测试结果较为稳定，且程序运行效率约为 436.619 Mbps，在要求的 200 Mbps 以上。

评估结果

随机性检测

使用 NIST 统计学工具包 完成随机性检测。

通过随机改动字节串中随机选取的部分比特，生成相近的多组明文，经过哈希后，获得待检测文件；之后使用 NIST 工具包对文件进行随机性分析。

上述流程可通过命令：

bash test.sh

完成。共生成 128000 组，长度为 256 个字符的随机相近明文，经过 SanSi 算法哈希并转换为 ASCII 编码的 01 串。

将待检测文件分为 10 个比特流，对其进行 NIST 工具包的所有随机性检测项目，结果显示，哈希结果通过了所有的随机性检测项目，如下表所示（具体检测结果文件详见 /result/finalAnalysisReport_test1.txt）：

项目 P Value 通过率
Frequency（频率检验） 0.534146 1/1
BlockFrequency（块内频数检验） 0.911413 1/1
CumulativeSums（累加和检验） 0.350485/0.534146 2/2
Rank（二元矩阵秩检验） 0.534146 1/1
FFT（离散傅里叶变换检验） 0.911413 1/1
Runs（游程检验） 0.350485 1/1
LongestRun（块内最长游程检验） 0.739918 1/1
NonOverlappingTemplate（非重叠模块匹配检验） - 148/148
OverlappingTemplate（重叠模块匹配检验） 0.739918 1/1
Universal（Maurer 的通用统计检验） 0.534146 1/1
ApproximateEntropy（近似熵检验） 0.534146 1/1
RandomExcursions（随机游动检验） - 8/8
RandomExcursionsVariant（随机游动状态频数检验） - 18/18
Serial（序列检验） 0.739918/0.739918 2/2
LinearComplexity（线性复杂度检验） 0.350485 1/1

生日攻击检测

我们对算法进行生日攻击，具体方法为：连续地生成长度为 128 字节的随机字符串，使用 SanSi 计算其哈希值，存储“哈希值-原串”对，直至找到碰撞或者达到最大攻击次数。攻击代码见 birthday_attack.cpp。

由于硬件设施和算力限制，我们最多仅进行到 $2^{26}$ 次哈希没有找到碰撞。

随机路径检测

我们利用 Floyd's Cycle Detection 算法对 SanSi 寻找碰撞，攻击代码见 floyd_cycle.cpp。

Floyd's Cycle Detection 的实现方法为：

  1. 阶段一：生成一个随机字符串作为初始值，并赋给两个字符串，分别称为“快指针”和“慢指针”。在每一轮迭代中，“快指针”对自己进行两次哈希，并将自己更新为该哈希值；“慢指针”对自己进行一次哈希，并将自己更新为该哈希值。不断迭代，直至“慢指针”与“快指针”相等（找到碰撞）或者达到最大攻击次数。
  2. 阶段二：若阶段一找到碰撞，则进入本阶段。将“慢指针”复原到初始值，“快指针”不动。在每一轮迭代中，“慢指针”和“快指针”均对自己进行一次哈希，并将自己更新为该哈希值。不断迭代，直至两个字符串相等。需要注意的是，此阶段需要另外两个字符串保存“慢指针”和“快指针”对自己进行哈希前的原值，当迭代结束时，这两个字符串就具有相同的哈希值，于是我们就找到了一组碰撞。

由于硬件设施和算力限制，我们最多仅进行到 $2^{28}$ 次哈希没有找到碰撞。

参考资料

  1. 算法的结构参考了 SHA-3 的结构。
  2. 算法的软件实现参考了 hash-library 仓库的实现方式。
  3. 算法评估的随机性检测使用了 NIST 统计学工具包。