2025 NepCTF nepsign
这题比较简单，很多人都出了。
题目
#!/usr/bin/python3
# 导入必要的库
from gmssl import sm3 # SM3哈希算法库
from random import SystemRandom # 系统随机数生成器
from ast import literal_eval # 安全的字符串字面值求值
import os
# 从环境变量获取flag
# flag = os.environ["FLAG"]
flag = "123"
def SM3(data):
"""
SM3哈希函数封装
将输入数据转换为字节列表并计算SM3哈希值
"""
d = [i for i in data]
h = sm3.sm3_hash(d)
return h
def SM3_n(data, n=1, bits=256):
"""
执行n次SM3哈希运算
Args:
data: 输入数据
n: 哈希轮数，默认为1
bits: 输出位数，默认为256位
Returns:
截取指定位数的十六进制哈希值
"""
for _ in range(n):
data = bytes.fromhex(SM3(data))
return data.hex()[: bits // 4]
class Nepsign:
"""
Nepsign数字签名算法实现类
基于SM3哈希函数的自定义签名方案
"""
def __init__(self):
self.n = 256 # 密钥长度参数
self.hex_symbols = "0123456789abcdef" # 十六进制字符集
self.keygen() # 初始化时生成密钥对
def keygen(self):
"""
生成公私钥对
私钥：48个32字节的随机数
公钥：对私钥进行255轮SM3哈希运算的结果
"""
rng = SystemRandom()
# 生成48个32字节的私钥
self.sk = [rng.randbytes(32) for _ in range(48)]
# 通过255轮哈希生成对应的公钥
self.pk = [SM3_n(self.sk[_], 255, self.n) for _ in range(48)]
return self.sk, self.pk
def sign(self, msg, sk=None):
"""
对消息进行数字签名
Args:
msg: 待签名的消息（字节形式）
sk: 私钥（可选，默认使用实例的私钥）
Returns:
签名结果列表（48个元素）
"""
sk = sk if sk else self.sk
# 计算消息的SM3哈希值
m = SM3(msg)
# 将哈希值转换为256位二进制字符串
m_bin = bin(int(m, 16))[2:].zfill(256)
# 将二进制字符串按8位分组，转换为整数数组（32个字节）
a = [int(m_bin[8 * i : 8 * i + 8], 2) for i in range(self.n // 8)]
step = [0] * 48 # 存储哈希轮数
qq = [0] * 48 # 存储签名结果
# 对前32个私钥进行处理（基于消息字节值）
for i in range(32):
step[i] = a[i] # 使用消息哈希的第i个字节作为哈希轮数
qq[i] = SM3_n(sk[i], step[i]) # 对私钥进行step[i]轮哈希
# if step[i] == 0, qq[i] = sk[i].hex()
# 对后16个私钥进行处理（基于哈希值中十六进制字符的位置统计）
sum = [0] * 16
for i in range(16):
sum[i] = 0
# 统计哈希值前64位中第i个十六进制字符出现的位置总和
for j in range(1, 65):
if m[j - 1] == self.hex_symbols[i]:
sum[i] += j
step[i + 32] = sum[i] % 255 # 对255取模作为哈希轮数
qq[i + 32] = SM3_n(sk[i + 32], step[i + 32])
# if step[i + 32] == 0, qq[i + 32] = sk[i + 32].hex()
return [i for i in qq]
def verify(self, msg, qq, pk=None):
"""
验证数字签名
Args:
msg: 原始消息（字节形式）
qq: 签名值列表
pk: 公钥（可选，默认使用实例的公钥）
Returns:
验证结果（True/False）
"""
# 将签名值从十六进制字符串转换为字节
qq = [bytes.fromhex(i) for i in qq]
pk = pk if pk else self.pk
# 计算消息的SM3哈希值
m = SM3(msg)
# 将哈希值转换为256位二进制字符串
m_bin = bin(int(m, 16))[2:].zfill(256)
# 将二进制字符串按8位分组，转换为整数数组（32个字节）
a = [int(m_bin[8 * i : 8 * i + 8], 2) for i in range(self.n // 8)]
step = [0] * 48 # 存储哈希轮数
pk_ = [0] * 48 # 存储重构的公钥
# 验证前32个签名（基于消息字节值）
for i in range(32):
step[i] = a[i] # 使用消息的第i个字节作为哈希轮数
# 对签名进行(255-step[i])轮哈希，应该得到公钥
pk_[i] = SM3_n(qq[i], 255 - step[i])
# 验证后16个签名（基于哈希值中十六进制字符的位置统计）
sum = [0] * 16
for i in range(16):
sum[i] = 0
# 统计哈希值前64位中第i个十六进制字符出现的位置总和
for j in range(1, 65):
if m[j - 1] == self.hex_symbols[i]:
sum[i] += j
step[i + 32] = sum[i] % 255 # 对255取模作为哈希轮数
# 对签名进行(255-step[i+32])轮哈希，应该得到公钥
pk_[i + 32] = SM3_n(qq[i + 32], 255 - step[i + 32])
# 比较重构的公钥与原公钥是否一致
return True if pk_ == pk else False
# 初始化签名系统
print("initializing...")
Sign = Nepsign()
# 主程序循环
while 1:
match int(input("> ")):
case 1:
# 选项1：对用户输入的消息进行签名
msg = bytes.fromhex(input("msg: "))
# 禁止对目标消息进行签名（防止直接获取所需签名）
if msg != b"happy for NepCTF 2025":
print(Sign.sign(msg))
else:
print("You can't do that")
case 2:
# 选项2：验证签名，如果验证成功则输出flag
qq = literal_eval(input("give me a qq: "))
# 验证目标消息的签名
if Sign.verify(b"happy for NepCTF 2025", qq):
print(flag)
签名算法分析
这个Nepsign算法并不是Lamport签名，而是一个自定义的基于哈希链的签名方案。
算法原理：
- 私钥：48个32字节的随机数
- 公钥：每个私钥经过255轮SM3哈希的结果
- 签名过程：根据消息哈希值确定每个私钥需要进行的哈希轮数，然后输出对应的哈希结果
具体来说：
- 前32个私钥：哈希轮数 = 消息SM3哈希值对应字节的值 (0-255)
- 后16个私钥：哈希轮数 = 消息哈希值中对应十六进制字符位置总和 % 255
验证时通过继续哈希到255轮来恢复公钥进行验证。
漏洞点
关键漏洞在于私钥泄露：当哈希轮数为0时，签名直接返回私钥本身。
- 前32位：当消息哈希的某个字节值为0时，对应位置的签名就是私钥
- 后16位：当某个十六进制字符的位置总和为255的倍数时，对应位置的签名就是私钥
通过构造特定消息使得哈希轮数为0，可以直接获取私钥，然后用这些私钥伪造任意消息的签名。
攻击思路
攻击分为两个阶段：
阶段1：寻找泄露私钥的消息
目标是找到48个消息，使得签名时对应的哈希轮数为0：
- 前32个私钥：寻找消息使得其SM3哈希值的第i个字节为0
- 后16个私钥：寻找消息使得其SM3哈希值中第i个十六进制字符的位置总和为255的倍数
阶段2：泄露私钥并伪造签名
- 用找到的消息获取对应位置的私钥
- 计算目标消息"happy for NepCTF 2025"的签名参数
- 用泄露的私钥计算对应的签名值
- 提交伪造的签名获取flag
攻击脚本
由于需要暴力搜索大量消息来找到合适的哈希值，Python版本速度较慢，因此使用Rust并行搜索。
use rayon::prelude::*;
use sm3::{Digest, Sm3};
use std::sync::{Arc, Mutex};
fn sm3_hash(data: &[u8]) -> String {
let mut hasher = Sm3::new();
hasher.update(data);
let result = hasher.finalize();
hex::encode(result)
}
fn analyze_message(i: u32) -> Vec<(usize, u32)> {
// 将整数转换为字节（按Python的bytes(i)逻辑）
let msg_bytes = if i <= 255 {
vec![i as u8]
} else {
// 对于大于255的数，转换为大端字节序
let mut bytes = Vec::new();
let mut val = i;
while val > 0 {
bytes.insert(0, (val & 0xff) as u8);
val >>= 8;
}
bytes
};
// 计算SM3哈希
let hash_str = sm3_hash(&msg_bytes);
// 将完整的哈希转换为256位二进制
// 需要处理完整的64字符哈希字符串
let mut m_bin = String::new();
for chunk in hash_str.chars().collect::<Vec<char>>().chunks(2) {
let hex_str: String = chunk.iter().collect();
if let Ok(byte_val) = u8::from_str_radix(&hex_str, 16) {
m_bin.push_str(&format!("{:08b}", byte_val));
}
}
let mut zero_positions = Vec::new();
// 检查前32个8位组是否为0
for key in 0..32 {
let start = key * 8;
let end = start + 8;
if start < m_bin.len() && end <= m_bin.len() {
if let Ok(val) = u8::from_str_radix(&m_bin[start..end], 2) {
if val == 0 {
zero_positions.push((key, i));
}
}
}
}
zero_positions
}
fn find_leak_positions_parallel(max_range: u32, num_threads: usize) -> Vec<Option<u32>> {
println!(
"开始多线程搜索，范围: 0-{}, 线程数: {}",
max_range, num_threads
);
let leak_pos = Arc::new(Mutex::new(vec![None; 32]));
let found_count = Arc::new(Mutex::new(0));
// 使用并行迭代器处理范围
(0..max_range)
.into_par_iter()
.chunks(1000)
.for_each(|chunk| {
for i in chunk {
// 检查是否已经找到所有位置
{
let count = found_count.lock().unwrap();
if *count >= 32 {
break;
}
}
let zero_positions = analyze_message(i);
if !zero_positions.is_empty() {
let mut leak_pos_guard = leak_pos.lock().unwrap();
let mut count_guard = found_count.lock().unwrap();
for (key, msg_id) in zero_positions {
if leak_pos_guard[key].is_none() {
leak_pos_guard[key] = Some(msg_id);
*count_guard += 1;
println!(
"发现位置 {} 的泄露消息: {} (十六进制: {:02x})",
key, msg_id, msg_id
);
}
}
if *count_guard >= 32 {
println!("已找到所有32个位置的泄露消息！");
break;
}
}
// 定期报告进度
if i % 10000 == 0 {
let count = found_count.lock().unwrap();
println!("进度: 已检查 {} 个消息, 找到 {}/32 个位置", i, *count);
}
}
});
let final_result = leak_pos.lock().unwrap().clone();
final_result
}
fn main() {
println!("Nepsign 私钥泄露搜索工具 (Rust多线程版本)");
println!("========================================");
// 设置搜索范围和线程数
let max_range = 100000; // 搜索前10万个消息
let num_threads = num_cpus::get().max(4);
println!("使用 {} 个线程", num_threads);
rayon::ThreadPoolBuilder::new()
.num_threads(num_threads)
.build_global()
.unwrap();
let start_time = std::time::Instant::now();
let leak_positions = find_leak_positions_parallel(max_range, num_threads);
let elapsed = start_time.elapsed();
println!("\n搜索完成！用时: {:?}", elapsed);
println!("泄露位置结果:");
println!("=============");
let mut found_count = 0;
for (i, pos) in leak_positions.iter().enumerate() {
match pos {
Some(msg_id) => {
println!("位置 {:2}: 消息 {} (0x{:02x})", i, msg_id, msg_id);
found_count += 1;
}
None => {
println!("位置 {:2}: 未找到", i);
}
}
}
println!("\n统计信息:");
println!("找到泄露位置: {}/32", found_count);
println!(
"搜索效率: {:.2} 消息/秒",
max_range as f64 / elapsed.as_secs_f64()
);
// 输出Python脚本可用的格式
println!("\nPython字典格式:");
println!("leak_messages = {{");
for (i, pos) in leak_positions.iter().enumerate() {
if let Some(msg_id) = pos {
// 确保输出的十六进制字符串是偶数长度
let hex_str = format!("{:x}", msg_id);
let padded_hex = if hex_str.len() % 2 == 1 {
format!("0{}", hex_str)
} else {
hex_str
};
println!(" {}: \"{}\", # 泄露sk[{}]", i, padded_hex, i);
}
}
println!("}}");
// 输出利用脚本
println!("\n可直接用于exploit的消息列表:");
let mut exploit_messages = Vec::new();
for (i, pos) in leak_positions.iter().enumerate() {
if let Some(msg_id) = pos {
// 确保输出的十六进制字符串是偶数长度
let hex_str = format!("{:x}", msg_id);
let padded_hex = if hex_str.len() % 2 == 1 {
format!("0{}", hex_str)
} else {
hex_str
};
exploit_messages.push(padded_hex);
}
}
println!("messages = {:?}", exploit_messages);
}
use rayon::prelude::*;
use sm3::{Digest, Sm3};
use std::sync::{Arc, Mutex};
fn sm3_hash(data: &[u8]) -> String {
let mut hasher = Sm3::new();
hasher.update(data);
let result = hasher.finalize();
hex::encode(result)
}
fn analyze_hex_positions(i: u32) -> Vec<(usize, u32)> {
// 将整数转换为字节（按Python的bytes(i)逻辑）
let msg_bytes = if i <= 255 {
vec![i as u8]
} else {
// 对于大于255的数，转换为大端字节序
let mut bytes = Vec::new();
let mut val = i;
while val > 0 {
bytes.insert(0, (val & 0xff) as u8);
val >>= 8;
}
bytes
};
// 计算SM3哈希
let hash_str = sm3_hash(&msg_bytes);
// 十六进制字符集，对应server.py中的self.hex_symbols
let hex_symbols = "0123456789abcdef";
let mut zero_positions = Vec::new();
// 对每个十六进制字符（0-15），检查位置总和是否为255的倍数
for hex_idx in 0..16 {
let target_char = hex_symbols.chars().nth(hex_idx).unwrap();
let mut sum = 0;
// 统计哈希值前64位中该字符出现的位置总和
// j从1开始（对应Python中的range(1, 65)）
for j in 1..=64 {
if let Some(hash_char) = hash_str.chars().nth(j - 1) {
if hash_char == target_char {
sum += j;
}
}
}
// 检查sum % 255 == 0（对应step[hex_idx + 32] = 0）
if sum % 255 == 0 {
zero_positions.push((hex_idx + 32, i)); // 位置32-47对应后16个私钥
println!(
"消息 {} (0x{:x}): 字符 '{}' 位置和={}, 泄露sk[{}]",
i,
i,
target_char,
sum,
hex_idx + 32
);
}
}
zero_positions
}
fn find_hex_leak_positions_parallel(max_range: u32, num_threads: usize) -> Vec<Option<u32>> {
println!(
"开始搜索后16个私钥的泄露消息，范围: 0-{}, 线程数: {}",
max_range, num_threads
);
let leak_pos = Arc::new(Mutex::new(vec![None; 48])); // 0-47，但我们只关心32-47
let found_count = Arc::new(Mutex::new(0));
// 使用并行迭代器处理范围
(0..max_range)
.into_par_iter()
.chunks(1000)
.for_each(|chunk| {
for i in chunk {
// 检查是否已经找到所有后16个位置
{
let count = found_count.lock().unwrap();
if *count >= 16 {
break;
}
}
let zero_positions = analyze_hex_positions(i);
if !zero_positions.is_empty() {
let mut leak_pos_guard = leak_pos.lock().unwrap();
let mut count_guard = found_count.lock().unwrap();
for (key, msg_id) in zero_positions {
if key >= 32 && key < 48 && leak_pos_guard[key].is_none() {
leak_pos_guard[key] = Some(msg_id);
*count_guard += 1;
println!(
"发现位置 {} 的泄露消息: {} (十六进制: {:x})",
key, msg_id, msg_id
);
}
}
if *count_guard >= 16 {
println!("已找到所有16个后位置的泄露消息！");
break;
}
}
// 定期报告进度
if i % 10000 == 0 {
let count = found_count.lock().unwrap();
println!("进度: 已检查 {} 个消息, 找到 {}/16 个后位置", i, *count);
}
}
});
let final_result = leak_pos.lock().unwrap().clone();
final_result
}
fn main() {
println!("Nepsign 后16个私钥泄露搜索工具");
println!("===================================");
// 设置搜索范围和线程数
let max_range = 500000; // 搜索前50万个消息
let num_threads = num_cpus::get().max(4);
println!("使用 {} 个线程", num_threads);
rayon::ThreadPoolBuilder::new()
.num_threads(num_threads)
.build_global()
.unwrap();
let start_time = std::time::Instant::now();
let leak_positions = find_hex_leak_positions_parallel(max_range, num_threads);
let elapsed = start_time.elapsed();
println!("\n搜索完成！用时: {:?}", elapsed);
println!("后16个位置的泄露结果:");
println!("========================");
let mut found_count = 0;
for i in 32..48 {
match leak_positions[i] {
Some(msg_id) => {
println!("位置 {:2}: 消息 {} (0x{:x})", i, msg_id, msg_id);
found_count += 1;
}
None => {
println!("位置 {:2}: 未找到", i);
}
}
}
println!("\n统计信息:");
println!("找到后16个泄露位置: {}/16", found_count);
println!(
"搜索效率: {:.2} 消息/秒",
max_range as f64 / elapsed.as_secs_f64()
);
// 输出Python脚本可用的格式（仅后16个位置）
println!("\nPython字典格式（后16个私钥）:");
println!("hex_leak_messages = {{");
for i in 32..48 {
if let Some(msg_id) = leak_positions[i] {
// 确保输出的十六进制字符串是偶数长度
let hex_str = format!("{:x}", msg_id);
let padded_hex = if hex_str.len() % 2 == 1 {
format!("0{}", hex_str)
} else {
hex_str
};
println!(" {}: \"{}\", # 泄露sk[{}]", i, padded_hex, i);
}
}
println!("}}");
}
python的攻击脚本
from pwn import *
from gmssl import sm3
context.log_level = "debug"
# context.log_level = "info"
LOCAL = False
if LOCAL:
p = process(["python3", "./server.py"])
else:
p = remote("nepctf32-ncuk-bxts-ld1y-ivwodb1uj620.nepctf.com", 443, ssl=True)
def get_signature(msg_hex):
"""获取消息的签名"""
p.sendline(b"1")
p.recvuntil(b"msg: ")
p.sendline(msg_hex.encode())
# 接收完整的返回数据，直到下一个提示符
result = p.recvuntil(b"> ").decode()
# 提取签名列表部分（去除提示符）
signature_line = result.split("\n")[0].strip()
return eval(signature_line)
# 等待服务器初始化
p.recvuntil(b"initializing...")
# p.interactive()
# 使用Rust工具找到的泄露消息（更新版本，确保偶数长度）
leak_messages = {
0: "9088",
1: "61ce",
2: "c3e6",
3: "465b",
4: "2f43",
5: "4655",
6: "2ef0",
7: "2f28",
8: "61be",
9: "c37f",
10: "15",
11: "c36b",
12: "2f4e",
13: "c36e",
14: "2f18",
15: "4667",
16: "6229",
17: "61cf",
18: "c35f",
19: "c35e",
20: "61ba",
21: "4661",
22: "c363",
23: "c374",
24: "c419",
25: "15",
26: "61ed",
27: "2f40",
28: "c355",
29: "c363",
30: "c378",
31: "2f4f",
}
# 后16个私钥的泄露消息
hex_leak_messages = {
32: "f235",
33: "01e856",
34: "01e85c",
35: "f230",
36: "01e84e",
37: "00",
38: "03d093",
39: "01e85c",
40: "01",
41: "01e858",
42: "016b49",
43: "08",
44: "0f",
45: "f23a",
46: "f236",
47: "7927",
}
leaked_sk = {}
# 泄露前32个私钥（基于消息字节值）
for i, msg_hex in leak_messages.items():
try:
signature = get_signature(msg_hex)
# 当step[i] = 0时，signature[i] = sk[i].hex()
leaked_sk[i] = signature[i]
except Exception as e:
print(f"泄露sk[{i}]失败: {e}")
# 泄露后16个私钥（基于十六进制字符位置统计）
for i, msg_hex in hex_leak_messages.items():
try:
signature = get_signature(msg_hex)
# 当step[i] = 0时，signature[i] = sk[i].hex()
leaked_sk[i] = signature[i]
except Exception as e:
print(f"泄露sk[{i}]失败: {e}")
print(f"\n成功泄露了 {len(leaked_sk)}/48 个私钥!")
print(leaked_sk)
# 如果成功泄露了足够的私钥，尝试伪造目标消息的签名
if len(leaked_sk) >= 48:
print("\n开始伪造目标消息签名...")
# 目标消息: "happy for NepCTF 2025"
target_msg = b"happy for NepCTF 2025"
# 计算目标消息的SM3哈希
def SM3(data):
d = [i for i in data]
h = sm3.sm3_hash(d)
return h
def SM3_n(data, n=1, bits=256):
for _ in range(n):
data = bytes.fromhex(SM3(data))
return data.hex()[: bits // 4]
# 重构签名算法
m = SM3(target_msg)
m_bin = bin(int(m, 16))[2:].zfill(256)
a = [int(m_bin[8 * i : 8 * i + 8], 2) for i in range(32)]
hex_symbols = "0123456789abcdef"
forged_signature = []
# 计算前32个签名
for i in range(32):
step_i = a[i]
sk_i_hex = leaked_sk[i]
sk_i = bytes.fromhex(sk_i_hex)
signature_i = SM3_n(sk_i, step_i)
forged_signature.append(signature_i)
# 计算后16个签名
for i in range(16):
sum_i = 0
# 统计哈希值前64位中第i个十六进制字符出现的位置总和
for j in range(1, 65):
if m[j - 1] == hex_symbols[i]:
sum_i += j
step_i = sum_i % 255
sk_i_hex = leaked_sk[i + 32]
sk_i = bytes.fromhex(sk_i_hex)
signature_i = SM3_n(sk_i, step_i)
forged_signature.append(signature_i)
print("伪造的签名:", forged_signature)
# 发送伪造的签名获取flag
print("\n发送伪造签名获取flag...")
p.sendline(b"2")
p.recvuntil(b"give me a qq: ")
p.sendline(str(forged_signature).encode())
# 接收结果
result = p.recvline().decode().strip()
print("服务器响应:", result)
else:
print(f"私钥泄露不完整，只获得了 {len(leaked_sk)}/48 个")
p.interactive()