# mc_frontend

**Repository Path**: qturing/mc_frontend

## Basic Information

- **Project Name**: mc_frontend
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2026-01-06
- **Last Updated**: 2026-09-16

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# mc_frontend — 基于DFG的密码算法识别系统

## 项目简介

本项目实现了一套基于编译器中间表示（LLVM IR）的密码算法自动识别系统。通过自定义 LLVM Pass 提取算法的数据流图（Data Flow Graph, DFG），利用 VF3 子图同构算法与预计算的签名模板进行匹配，从而自动识别目标程序的密码算法类型。

## 软件架构

```
mc_frontend/
├── alg-analy/
│   ├── llvm_DFGPass/          # LLVM DFG 提取 Pass（C++/CMake）
│   │   ├── DFG/
│   │   │   ├── DFGPass.cpp        # 主 DFG 提取 Pass
│   │   │   ├── ConstantExtractor.cpp  # 常量提取辅助 Pass
│   │   │   └── LoopAnalyzer.cpp      # 循环分析辅助 Pass
│   │   ├── build/                 # 构建输出
│   │   ├── dfg_gen.sh             # DFG 生成脚本
│   │   ├── autobuild.sh           # 自动编译脚本
│   │   └── build_passes.sh        # Pass 编译脚本
│   ├── vf3lib/                # VF3 子图同构匹配库（C++）
│   ├── DFG_Signature/         # 算法签名模板
│   │   ├── grf/                   # .grf 格式签名文件
│   │   └── dot/                   # .dot 格式签名文件
│   ├── cryptography/          # 密码算法参考实现（C）
│   │   ├── aes128/            # AES-128
│   │   ├── aes192/            # AES-192
│   │   ├── aes256/            # AES-256
│   │   ├── des/               # DES / 3DES
│   │   ├── 3des/              # 3DES (EDE, 基于 hashcat 实现移植)
│   │   ├── md5/               # MD5
│   │   ├── office07/          # Office 2007 加密 (AES+SHA1)
│   │   ├── office10/          # Office 2010 加密
│   │   ├── present/           # PRESENT-80
│   │   ├── sha1/              # SHA-1
│   │   ├── sha224/            # SHA-224
│   │   ├── sha256/            # SHA-256
│   │   ├── sha3-224/          # SHA3-224
│   │   ├── sha3-256/          # SHA3-256
│   │   ├── sha3-384/          # SHA3-384
│   │   ├── sha3-512/          # SHA3-512
│   │   ├── sha384/            # SHA-384
│   │   ├── sha512/            # SHA-512
│   │   ├── sm3/               # SM3
│   │   ├── sm4/               # SM4
│   │   ├── 7zip/              # 7-Zip (7zAES: SHA-256 KDF + AES-256-CBC)
│   │   └── winzip/            # WinZip 加密 (SHA1)
│   ├── scripts/               # Python 工具脚本
│   │   └── dot_to_grf.py      # DOT → GRF 格式转换
│   ├── match.py               # 算法识别主程序（v1）
│   └── match_v2.py            # 算法识别主程序（v2）
```

## 环境依赖

| 依赖 | 版本要求 | 用途 |
|------|----------|------|
| LLVM | 18.x / 4.0.2+ | 生成 IR 并运行 DFG 提取 Pass |
| CMake | 3.16+ | 编译 LLVM Pass 和 VF3 库 |
| GCC / Clang | 支持 C++17 | 编译 C/C++ 代码 |
| Graphviz | 任意版本 | 可视化 DFG 图 |
| Python | 3.x | 运行脚本和匹配程序 |

### 一键安装

```bash
# Ubuntu/Debian
sudo apt install llvm-18 llvm-18-dev clang-18 cmake graphviz python3

# 创建 llvm-config 软链接（如需要）
sudo ln -s /usr/bin/llvm-config-18 /usr/local/bin/llvm-config
```

## 快速开始

### 1. 编译 LLVM Pass

```bash
cd alg-analy/llvm_DFGPass
./autobuild.sh
```

编译生成以下 Pass 动态库：
- `build/DFG/libDFGPass.so` — 主 DFG 提取 Pass
- `build/DFG/libConstantExtractorPass.so` — 常量提取 Pass
- `build/DFG/libLoopAnalyzerPass.so` — 循环分析 Pass

### 2. 编译 VF3 匹配库

```bash
cd alg-analy/vf3lib
make
```

### 3. 生成算法的 DFG 图

```bash
cd alg-analy/llvm_DFGPass

# 编辑 dfg_gen.sh，将 INPUT 变量指向目标 .c 文件，然后运行：
./dfg_gen.sh
```

脚本会依次执行：
1. Clang 编译 C 代码生成 LLVM IR（`.ll`）
2. 运行 DFGPass 从 IR 提取数据流图（`.dot`）
3. 运行 ConstantExtractor 和 LoopAnalyzer 提取辅助信息（`constants.json`, `loops.json`）

### 4. 转换 DOT 为 GRF 格式

```bash
cd alg-analy
python3 scripts/dot_to_grf.py <input.dot>
# 示例
python3 scripts/dot_to_grf.py llvm_DFGPass/sha256.dot
```

### 5. 运行算法识别

```bash
cd alg-analy

# v1 — 基于 VF3 子图同构匹配
python3 match.py ./DFG_Signature/grf/ <target_alg_dir>

# v2 — 改进版匹配逻辑
python3 match_v2.py
```

## 支持的算法签名

系统预置了以下算法的 DFG 签名模板（`DFG_Signature/grf/`）：

### 已验证（match_v2.py 三层识别）

| 算法 | 结构签名 | init 签名 | fshl | 分组 | 匹配结果 | 识别准确率 |
|------|----------|-----------|------|------|----------|-----------|
| MD5 | md5_sig4.grf | — | 64 | high | 64 | 100% |
| SHA-1 | sha1_sig1.grf | — | 9 | low | 4 | 100% |
| SHA-224 | sha256_sig1.grf | sha224_init_sig.grf | 16 | mid | 4 + init | 100% |
| SHA-256 | sha256_sig1.grf | sha256_init_sig.grf | 16 | mid | 4 + init | 100% |
| SHA-384 | sha256_sig1.grf | sha384_init_sig.grf | 16 | mid | 4 + init | 100% |
| SHA-512 | sha256_sig1.grf | sha512_init_sig.grf | 16 | mid | 4 + init | 100% |
| SM3 | sm3_sig1.grf | — | 24 | mid | 6 | 100% |
| AES-128 | aes128_sig2.grf | — | 0 | low | 160 | 100% |
| AES-192 | aes128_sig2.grf | — | 0 | low | 192 (阈值区分) | 100% |
| AES-256 | aes128_sig2.grf | — | 0 | low | 224 (阈值区分) | 100% |
| DES | des_sig3.grf | — | 0 | low | 1 | 100% |
| 3DES | 3des_sig1.grf + 3des_sig2.grf | — | 2 | low | 核心+调用链 | 100% |
| PRESENT-80 | present80_sig1.grf | — | 1 | low | 2 | 100% |
| SM4 | sm4_sig1.grf | — | 0 | low | 1 | 100% |
| 7-Zip (7zAES) | sha256_sig1.grf + aes128_sig2.grf | — | — | 全目录扫描 | SHA256+AES 共存 | 100% |
| Office 2007 | office_aes_sig.grf + office07_sig.grf | — | — | 全目录扫描 | T表AES+轮数常量 | 100% |
| Office 2010 | office_aes_sig.grf + office10_sig.grf | — | — | 全目录扫描 | T表AES+轮数常量 | 100% |
| SHA3-224 | sha3_sig1.grf | sha3_224_init_sig.grf | ~30 | high | 6M+ + init | 100% |
| SHA3-256 | sha3_sig1.grf | sha3_256_init_sig.grf | ~30 | high | 6M+ + init | 100% |
| SHA3-384 | sha3_sig1.grf | sha3_384_init_sig.grf | ~30 | high | 6M+ + init | 100% |
| SHA3-512 | sha3_sig1.grf | sha3_512_init_sig.grf | ~30 | high | 6M+ + init | 100% |
| SHAKE128 | sha3_sig1.grf + shake_final_sig.grf | shake128_init_sig.grf | ~30 | high | 域分隔符 0x1F + init | 100% |
| SHAKE256 | sha3_sig1.grf + shake_final_sig.grf | —（rate 0x88 复用 opcode 70） | ~30 | high | 域分隔符 0x1F + init | 100% |

> **init 签名**：SHA-224/256、SHA-384/512、SHA3-224/256/384/512 分别共享压缩函数。init 签名通过匹配 init 函数中的 IV/rate 常量值精确区分同族算法变体。SHAKE128/256 与 SHA3 家族共享 Keccak-f 结构签名，先由 final 中的域分隔符 0x1F 特征（`detect_shake()`）确认 SHAKE，再按 init 中 rate 常量区分变体（0xA8→SHAKE128，0x88→SHAKE256）。

### 预置签名（待集成/开发中）

| 算法 | 签名文件 | 状态 |
|------|----------|------|
| SHA-512/224 | sha512_224_sig1~3.grf | 待集成（与 SHA-512 结构相同，需 init 签名区分） |
| SHA-512/256 | sha512_256_sig1~3.grf | 待集成（与 SHA-512 结构相同，需 init 签名区分） |
| WinZip | 待生成 | 待生成签名（已有参考实现，SHA1 复合） |

> **说明**：AES-192/256 与 AES-128 共用 aes128_sig2 签名，通过 VF3 匹配数阈值区分（160/192/224，对应 10/12/14 轮）。

## 工作原理

### DFG 提取

LLVM Pass 遍历函数的 IR 指令，构建数据流图：

- **节点**：每条 IR 指令为一个节点，标注操作码（add、xor、shl、fshl 等）
- **边**：表示指令执行顺序（前驱指令 → 后继指令）
- **特殊处理**：
  - `fshl`/`fshr` — LLVM 循环移位 intrinsic，识别为独立操作码（34/35），用于区分不同算法
  - **常量编码** — 加密常量立即数（≥ 0x100）创建为带值标签的节点（如 `k_0x6A09E667`），在 GRF 中分配专属 opcode（36-74，含 Office 2007/2010 KDF 轮数常量 73/74），用于区分同族算法
  - 循环结构 — 通过 LoopAnalyzer 分析循环体中的操作模式

### 签名匹配（match_v2.py 三层架构）

**第一层 — fshl 粗筛**：统计主循环图中 fshl 节点数量，将目标算法归入 `low/mid/high/very_high` 分组。

**第二层 — 结构签名匹配**：在对应分组内使用 VF3 子图同构匹配特异性签名。例如 `sha256_sig1.grf`（5 节点 `fshl→fshl→xor→fshl→xor`）识别所有 SHA-2 变体的 sigma 函数。

**第三层 — init 签名区分**：对于结构相同但 IV 不同的同族算法（SHA-224 vs SHA-256、SHA-384 vs SHA-512），使用 init 函数中的 IV 常量签名精确区分：

**3DES 专项检测**：3DES 与 DES 参考实现的轮函数风格不同（前者移植自 hashcat，后者为 BITNUM 位操作风格），仅靠主函数签名无法区分。在 low 分组内对目标目录全部 GRF 做特征扫描：同时命中 DES 轮函数核心签名（3des_sig1）和 EDE 三次调用链签名（3des_sig2）时判定为 3DES（`detect_3des()`）。

**7-Zip 专项检测**：7zAES 是复合算法（SHA-256 迭代 KDF + AES-256-CBC），主函数启发式会选中 sha256_proc 而误判为 sha256。在 fshl 分组之前对目标目录全部 GRF 扫描：SHA-256 压缩结构（sha256_sig1）与 AES 轮结构（aes128_sig2）同时存在时判定为 7zip（`detect_7zip()`）。与 office07/10（AES+SHA1）、winzip（PBKDF2-SHA1）天然互斥。

**Office 2007/2010 专项检测**：Office 是复合算法（SHA-1 迭代 KDF + T 表 AES-128）。在 fshl 分组之前对全目录扫描：先匹配 T 表 AES 查表链签名（office_aes_sig：`lshr→and→zext→xor`，corpus 内为 Office 独有），命中后再按 KDF 迭代轮数常量区分版本——50000（`k_0xC350→icmp`，office07_sig）为 Office 2007，100000（`k_0x186A0→icmp`，office10_sig）为 Office 2010（`detect_office()`）。

**SHAKE 专项检测**：SHAKE128/256 与 SHA3 家族共享 Keccak-f 置换结构（sha3_sig1 同时命中），主函数结构签名无法区分；区别在于 final 的域分隔符——SHAKE 为 0x1F（≥0x10，编码为 opcode 76 的常量节点），SHA3 为 0x06（低于编码阈值，不入图）。在 sha3 init 消歧之前运行 `detect_shake()`：全目录扫描命中 `shake_final_sig.grf`（`k_0x1f→xor→store`）即判定为 SHAKE，再按 init 中的 rate 常量区分变体（`shake128_init_sig.grf`：`k_0xA8→store`，rate=168 为 SHAKE128；rate=136 与 SHA3-256 相同，为 SHAKE256）。

```
sha256_init_sig.grf:  k_0x510E527F → store   (SHA-256 IV[4])
sha224_init_sig.grf:  k_0xFFC00B31 → store   (SHA-224 IV[4])
sha512_init_sig.grf:  k_0x6A09E667F3BCC908 → store  (SHA-512 IV[0])
sha384_init_sig.grf:  k_0xCBBB9D5DC1059ED8 → store  (SHA-384 IV[0])
sha3_224_init_sig.grf: k_0x00000090 → store  (SHA3-224 rate=144)
sha3_256_init_sig.grf: k_0x00000088 → store  (SHA3-256 rate=136)
sha3_384_init_sig.grf: k_0x00000068 → store  (SHA3-384 rate=104)
sha3_512_init_sig.grf: k_0x00000048 → store  (SHA3-512 rate=72)
shake128_init_sig.grf: k_0x000000A8 → store  (SHAKE128 rate=168)
shake_final_sig.grf:   k_0x0000001F → xor → store  (SHAKE 域分隔符 0x1F)
```

### 识别策略

不同算法具有独特的 DFG 结构特征：

- **SHA-2 家族**: `fshl → fshl → xor → fshl → xor` sigma 函数模式（sha256_sig1），通过 init IV 常量值区分具体变体
- **SHA-3 家族**: Keccak 置换结构（sha3_sig1），通过 init 函数中 rate 常量值区分具体变体
- **SHAKE128/256**: 与 SHA-3 家族共享 Keccak 置换结构；`detect_shake()` 在 sha3 init 消歧前扫描 final 中的域分隔符 0x1F 特征（shake_final_sig：`k_0x1f→xor→store`），命中后按 init rate 常量区分（168→SHAKE128，136→SHAKE256）
- **SHA-1**: `fshl → add → icmp` 结构（sha1_sig1）
- **SM3**: `fshl → fshl → fshl` 三重循环移位（sm3_sig1）
- **MD5**: `fshl → add` 模式，通过数量阈值判断（md5_sig4）
- **AES-128**: SubBytes/ShiftRows/MixColumns 组合（aes128_sig2），fshl=0
- **DES**: Feistel 网络结构（des_sig3），fshl=0
- **3DES**: hashcat 风格 DES 轮函数核心（3des_sig1：`fshl→xor→lshr→and`）+ EDE 三次调用链（3des_sig2：`call→call→call`），low 组内全目录扫描，两者同时命中才判定
- **7-Zip (7zAES)**: 复合算法（SHA-256 迭代 KDF + AES-256-CBC），无单一主函数图；在 fshl 分组前对全目录扫描，SHA-256 压缩结构（sha256_sig1）与 AES 轮结构（aes128_sig2）同时存在才判定（`detect_7zip()`）
- **PRESENT-80**: S-box 置换层（present80_sig1），fshl=1
- **SM4**: S-box + 线性变换（sm4_sig1），fshl=0

## 添加新算法

1. 在 `alg-analy/cryptography/` 下创建新目录，编写算法的 C 参考实现
2. 编译 C → LLVM IR: `clang-18 -O3 -emit-llvm -S algo.c -o algo.ll`
3. 运行 DFGPass 生成 DOT: `opt-18 -load-pass-plugin=libDFGPass.so -passes=DFGPass algo.ll`
4. 转换 DOT → GRF: `python3 scripts/dot_to_grf.py algo_func.dot`
5. 将代表性 GRF 作为签名模板放入 `DFG_Signature/grf/`（文件名需匹配 `match_v2.py` 中的配置）
6. 在 `match_v2.py` 的 `SIGNATURES` 字典中添加新算法条目，确定所属 fshl 分组

## 已知问题

- LLVM 18 生成的 DFG 中，循环移位操作为 `fshl`/`fshr` intrinsic，与早期版本的 `shl+lshr+or` 组合模式不同
- SHA-512/224、SHA-512/256、WinZip 的 init 常量签名尚未生成
- Shell 脚本中的路径引用为硬编码，迁移到新环境时需更新

## 参与贡献

1. Fork 本仓库
2. 新建 `Feat_xxx` 分支
3. 提交代码
4. 新建 Pull Request