学术报告：SHA-256哈希函数的非平凡相关性发现与大规模计算实现

作者及发表信息

本研究由Mellila Bouam（阿尔及利亚高等信息学院）、Charles Bouillaguet（法国索邦大学、CNRS、LIP6实验室）、Claire Delaplace（法国皮卡第儒勒-凡尔纳大学MIS实验室）和Camille Noûs（法国Cogitamus实验室）合作完成，发表于2021年的期刊*Parallel Computing*第106卷，文章编号102804。

学术背景

本研究属于密码学与高性能计算交叉领域，聚焦于安全哈希函数SHA-256的“非预期性质”探索。SHA-256作为美国国家标准与技术研究院（NIST）认证的加密哈希函数，其输出理论上应具备不可区分于随机比特串的特性。然而，研究团队通过“暴力搜索”（brute-force）发现了三个输入字符串，其SHA-256哈希值的前128位异或（XOR）结果为零。这一发现并未利用SHA-256的密码学弱点，而是通过大规模计算实现，属于“广义生日问题”（Generalized Birthday Problem）的实践案例。研究目标包括：
1. 验证128位3XOR问题的实际计算可行性；
2. 探索专用硬件（如比特币矿机）在非货币化计算中的应用；
3. 评估现有3XOR算法在高性能计算环境中的实用性。

研究流程与方法

1. 问题建模与算法选择

研究将3XOR问题定义为寻找三个n位字符串（x, y, z），使得f(x)⊕g(y)⊕h(z)=0，其中f, g, h为随机函数。团队对比了五种算法（见表1），最终选择基于Joux改进的广义算法（Bouillaguet等，2018），因其在时间复杂度和内存需求上的平衡性（时间复杂度O(2^(2n/3)/n)，内存需求O(2^(n/3))）。

2. 硬件加速与数据生成

• 比特币矿机改造：使用两台二手Antminer S7矿机（含BM1385 ASIC芯片），将其改造为SHA-256d（双重SHA-256）计算设备。矿机通过定制化cgminer软件（移除Stratum协议限制）生成前缀固定的76字节数据块，筛选出哈希前33位为零的32位后缀x。
  
• 计算规模：耗时7个月，完成2^67.6次SHA-256压缩函数评估，生成三组各2^32条哈希数据（每组51.5 GB），总数据量155 GB。
  

3. 并行化求解

在IBM BlueGene/Q超算上（65,536个PowerPC A2核心，1.6 GHz）实施分治策略：
- 数据分区：将输入数组按哈希最高位划分为2^15个子问题，每个子问题包含2^17个64位哈希值。
- 核心算法：采用改进的3XOR算法（图3），包括：
- 切片构建（Algorithm S）：通过Lee-Brickell解码算法寻找满足线性方程的哈希子集，减少迭代次数（切片平均大小59，比朴素方法提升30%效率）。
- 哈希连接（Algorithm J）：利用分区哈希表（Cuckoo哈希和线性探测）高效匹配三元组。
- 性能优化：针对BlueGene/Q架构调整参数（如L1缓存利用、多线程负载均衡），最终实现单核33.5秒/子问题的求解速度，较传统二次算法提速5.3倍。

主要结果

1. 128位3XOR解：发现三组输入字符串（图1），其SHA-256哈希前128位异或为零。值得注意的是，其中一个哈希（z）前43位为零，远超预期的33位，但未发现统计偏差。
   
2. 计算效率：共找到62,006组112位以上3XOR三元组（表2），与理论预期（61,440组）吻合。最优结果包括：
   
   • 129位匹配1组（预期0.23组）；
     
   • 127位匹配1组（预期0.94组）。
     
3. 资源消耗：总能耗40 MWh（约144 GJ），相当于煮沸430立方米水的能量；硬件成本约55,000欧元（含矿机和超算资源）。
   

结论与价值

1. 密码学意义：首次通过暴力搜索实现128位碰撞类结果，证明SHA-256在极端计算压力下仍保持安全性，但揭示了专用硬件加速计算的潜力。
   
2. 方法论创新：
   
   • 比特币矿机首次被用于非货币化科学计算，开辟了老旧ASIC设备的再利用途径；
     
   • 提出适应老旧超算的并行化3XOR算法，为其他组合问题提供参考。
     
3. 工程启示：算法的实际性能受硬件约束（如缓存延迟、内存带宽）显著影响，理论最优参数（如k=17）需根据平台调整（实际采用k=19）。
   

研究亮点

1. 规模突破：完成迄今最大的128位3XOR计算（8.7×10^22次整数运算），远超2017年SHA-1碰撞攻击的63.1次哈希评估。
   
2. 硬件创新：首次将比特币矿机转化为通用计算设备，单矿机哈希速度达2^43.1次/秒，比CPU快百万倍。
   
3. 开源贡献：公开全部代码（3700行C程序，GitHub可查），涵盖矿机控制、数据预处理及超算算法。
   

其他价值

研究强调了“理论算法”与“实际实现”的鸿沟：例如，内存需求O(2^(n/2))的算法虽理论高效，但在n≥128时完全不实用。这一发现对密码分析社区优化算法设计具有指导意义。