Skip to content

Latest commit

 

History

History
113 lines (86 loc) · 3.31 KB

README.md

File metadata and controls

113 lines (86 loc) · 3.31 KB

md5fastcoll Python

基于 Marc Stevens Fast Collision Attack on MD5 的可复现实现，强调一步一验证。

目标

  • 生成与 HashClash md5_fastcoll 一致的两块碰撞文件对
  • 提供纯 Python 引擎，不需要 make
  • 提供可验证的中间状态，便于调试与学习

依赖

  • Python 3.11 或更高
  • 纯 Python 引擎依赖
    • pip install -U numpy numba

引擎说明

fastcoll 子命令支持三种引擎

  • python
    • 只使用 Python 与 pip 安装的依赖
    • 不使用 tools/md5_fastcoll_lib_wrap.cpp
    • 同一 IHV seed prefixfile 下输出与 HashClash md5_fastcoll 一致
    • 首次运行会触发 Numba 编译，后续会使用磁盘缓存
  • ctypes
    • 通过 ctypes 调用共享库 md5_fastcoll_lib
    • build-native-lib 会使用 tools/md5_fastcoll_lib_wrap.cpp 并编译 HashClash 源码
    • 需要本机有 C++ 编译器
  • native
    • 直接运行 HashClash 可执行文件 md5_fastcoll
    • build-native 会拉取 HashClash 源码并编译
    • 需要本机有 make 与 autotools 工具链

性能

基准配置

  • seed: 123
  • IHV: 0123456789abcdeffedcba9876543210
  • prefixfile: 无

环境

  • OS: Darwin 23.6.0
  • 体系结构: arm64
  • Python: 3.11.12
  • NumPy: 1.26.4
  • Numba: 0.59.1

结果

引擎 wall time 秒 相对 native
native 4.80 1.00
python 17.25 3.59

说明

  • python 引擎首次运行可能更慢，因为需要 JIT 编译

快速开始

  • 校验核心 MD5 与 hashlib 一致
    • python -m md5fastcoll.cli verify-core
  • 生成 fastcoll 兼容碰撞文件对
    • python -m md5fastcoll.cli fastcoll --engine python --seed 123 -q -o msg1.bin msg2.bin
  • 带前缀生成
    • python -m md5fastcoll.cli fastcoll --engine python --prefixfile prefix.bin -q -o msg1.bin msg2.bin

搜索命令

  • Block1 搜索
    • python -m md5fastcoll.cli search-block1 --restarts 50
  • Block2 搜索
    • python -m md5fastcoll.cli search-block2 --restarts 500 --ihv 0xC4DA537C 0x1051DD8E 0x42867DB3 0x0D67B366
    • 该命令是概率搜索，restarts 50 常见会失败
  • 固定随机种子复现
    • python -m md5fastcoll.cli search-block2 --seed 42 --restarts 500 --ihv 0xC4DA537C 0x1051DD8E 0x42867DB3 0x0D67B366

脚本

  • 准确性检查
    • python scripts/accuracy.py
  • 性能与吞吐基准
    • python scripts/perf.py --trials 20 --budget 4096
  • 论文一致性检查
    • python scripts/test_paper_compliance.py --skip-search

说明

  • fastcoll 前缀按 64 字节块零填充，与 HashClash md5_fastcoll 行为一致
  • seed 为 0 时 HashClash 的 rng64 可能进入全零退化状态，md5fastcoll 会自动将 seed2 置为 0x12345678
  • tables/block1.txt 与 tables/block2.txt 为论文附录 A 条件表的转录
  • I/J/K 表示同一未知位，K 与 I 相同

来源

  • Marc Stevens Fast Collision Attack on MD5
  • HashClash 源码仓库
  • Python fastcoll 引擎主要移植自 HashClash 的 src/md5fastcoll 目录
    • md5.cpp
    • block0.cpp
    • block1wang.cpp
    • block1stevens00.cpp
    • block1stevens01.cpp
    • block1stevens10.cpp
    • block1stevens11.cpp
  • tools/md5_fastcoll_lib_wrap.cpp 用于 ctypes 引擎
    • build-native-lib 会编译该 wrapper 并链接 HashClash 源码以导出 md5fastcoll_find_blocks