基于SHA256的问答机制中未知8字节序列S的高效求解方法咨询

先修复代码致命bug #

你提供的示例代码存在低级错误：

memcpy(&input[0],Q,5);  

Q数组仅包含4字节，复制5字节会带入内存后续的垃圾数据，导致所有哈希计算结果完全错误，首先需要将长度参数5改为4。

方案1：代码级性能优化（提速100倍以上） #

原代码的8层嵌套循环、冗余memcpy操作、未优化的SHA256实现浪费了大量性能，优化后单CPU即可将哈希计算速度提升至少两个数量级：

• 用uint64_t类型直接遍历S，去掉8层嵌套循环，单次循环即可覆盖所有S取值
• 预填充input数组的固定部分（Q和后续的SHA256填充位），无需每次循环重复赋值
• 采用优化过的SHA256实现，比如OpenSSL原生实现、或支持AVX2/AVX512指令集的SIMD版本，单核心每秒可轻松完成千万次哈希计算
• 校验匹配时优先校验第一组样本的A，只有匹配成功再校验第二、第三组，99.99%的候选值会在第一关被过滤，几乎不增加额外计算量

方案2：中间相遇攻击（复杂度从2^64降至233，几小时即可出结果） #

利用你拥有3组(Q,A)样本的条件，采用时间内存权衡的中间相遇攻击，将搜索空间从2^{64降低到2*2}32≈86亿次计算，普通PC半天内即可跑完：

1. 将8字节S拆分为前4字节S_a和后4字节S_b，两部分的搜索空间均为2^32≈43亿
2. 遍历所有可能的S_a，对每个S_a计算第一组样本满足SHA256(Q1 || S_a || S_b)前4字节等于A1对应的哈希片段，将(hash片段, S_a)存入哈希表
3. 遍历所有可能的S_b，计算对应哈希值，在哈希表中查找符合条件的组合，得到候选S
4. 用第二、第三组样本验证候选S，唯一通过验证的就是目标S

• 若内存不足，可将S_a的搜索空间拆分成分块处理，每次仅加载一个分块的哈希表到内存，普通16GB内存的PC即可运行。

方案3：GPU加速（最快十几分钟出结果） #

如果有NVIDIA显卡，用CUDA编写SHA256计算核函数，消费级RTX3090/4090每秒可完成10~20亿次哈希计算，86亿次计算仅需十几分钟即可完成。如果S存在字符集限制（比如仅为可打印字符、字母数字等），搜索空间会进一步缩小，几分钟就能跑出结果。

注：SHA256目前没有已知的有效预映射攻击，上述方案已经是理论最优的求解方法。

内容的提问来源于stack exchange，提问作者th3r4t3l