WOTS介绍

  • WOTS全称为Winternitz one-time signature scheme，翻译过来就被叫做Winternitz 一次性签名方案，该数字签名为Robert Winternitz提出的。
  • WOTS这个数字签名是基于哈希的签名算法，该签名是Lamport签名的改进算法，通过时间换空间的思路，减少了签名的体积。
  • 应用场景：
    • 作为XMSS、SPHINCS等现代化哈希签名体系的核心组件。
    • 适合在抗练字密码学中作为安全的签名方案
    • 由于WOTS是一次性签名，通常配合Merkle树扩展成多次使用的签名体系。

WOTS算法过程

  • 对于这个算法来说，主要包括的还是密钥生成、签名、数字签名的验证三个算法，所以WOTS算法过程主要就是分为密钥生成、签名、数字签名的验证三个过程
  • 注意：这个数字签名算法需要多看几遍才能看明白，而且第一次看的时候会有点懵，需要从整体把握这样才能明白每一步为什么要这样选取数据。

密钥生成

确定同时签名的位数：首先需要先选取一个ω≥2\omega\ge2，ω\omega表示要同时签名的位数，并且还控制着公钥的哈希次数。

  • 这里例举一个例子帮助理解：比如：要签名a->01100001，如果选取w=2w=2，那么签名的时候对于a->01100001就会将它的二进制位，按照俩个一组进行组合，将组合后的数据进行哈希计算h(01)、h(10)、h(00)、h(01)。
  • 注意：一般来说ω=8\omega=8，因为8位是一个字节刚好可以一个字节同时进行数字签名。

选取一个哈希函数：确定哈希函数的消息摘要长度是256位，还是128位将会影响后续公钥和私钥的长度。这边选取目前最常用的sha2-256。即哈希摘要长度为256位，转换为字节数就是32字节。

私钥的选取：要确定私钥的个数，私钥的大小。

  • 私钥的个数由俩个部分组成：

    • 第一个部分t1t_1：由同时签名的位数ω\omega与哈希函数的消息摘要长度决定，即哈希摘要的位数256/ω256/\omega，这里t1=32t_1=32

    • 第二个部分t2t_2：由同时签名的位数ω\omega与后面校验和的长度决定，根据下面的校验和长度，选择t2=2t_2=2

  • 私钥的生成的大小其实就是在xi∈[0,2256),i=1,2,..,t−1x_i\in[0,2^{256}),i=1,2,..,t-1这个范围内，而这个256其实就是选取哈希函数消息摘要的位数。这样就形成了一个私钥。

Sk=(xt−1,...,x1,x0),t=t1+t2Sk=(x_{t-1},...,x_1,x_0),t=t_1+t_2

公钥的计算：公钥的计算其实比较简单，就是将私钥进行一定次数的哈希计算，形成哈希链。而哈希的次数是由ω\omega决定的。

yi=h2ω−1(xi)=h256(xi),0≤i≤t−1Pk=(yt−1,...,y1,y0)y_i=h^{2^{\omega}-1}(x_i)=h^{256}(x_i),0\le i \le t-1\\ Pk=(y_{t-1},...,y_1,y_0)

  • 由于ω=8\omega=8，哈希的次数为255，哈希的次数比较合适（太多会导致运算时间太高，太少导致容易被破解）。

签名

  • 假设消息是m，首先需要通过一次哈希，将消息m映射到固定的长度，这里选取sha2-256，所以消息m会被映射成256位。接下来就需要对这个256位的哈希值进行分组操作，将这个256位的哈希值分成ω\omega位一组，这里也就是8位一组。

h(m)=bt1−1∣∣...∣∣b0h(m) = b_{t_1-1}||...||b_0

  • 接下来需要对分组的bib_i计算一个校验和，具体的计算方式如下：

c=∑i=0t1−1(2ω−bi)c = \sum_{i=0}^{t_1-1}(2^{\omega}-b_i)

  • 求得校验和c后，需要将c转换为比特串，将转换成的比特串继续按照ω\omega位一组进行分组，一共可以分得t2t_2组，而这个t2t_2就是前面私钥的个数t=t1+t2t=t_1+t_2中的t2t_2，而通过计算这里的t2=2t_2=2

c=bt2−1∣∣...∣∣b0c=b_{t_2-1}||...||b_0

  • 这里将h(m)和c组合起来得到d：

d=c∣∣h(m)=dt−1∣∣...∣∣dt−t2−1∣∣....d0d=c||h(m)=d_{t-1}||...||d_{t-t_2-1}||....d_0

  • 最终就需要对消息的哈希值与校验和进行签名得到最终的签名V，最坏的情况需要执行2ω−12^{\omega-1}次的哈希函数运算：

vi=hdi(ski),i=0,1,...,t−1V=(vt−1,...,t1,t0)v_i =h^{d_i}(sk_i),i=0,1,...,t-1\\ V = (v_{t-1},...,t_1,t_0)

验签算法

  • 验证签名的运算其实就是将哈希链的计算次数达到255次并判断是否与公钥相等。也就是先进行哈希函数的运算：

vi′=h255−di(vi)V′=(vt−1′,...,v1′,v0′)v'_i = h^{255-d_i}(v_i)\\ V'=(v'_{t-1},...,v'_{1},v'_0)

  • 最后判断pkipk_i是否与vi′v'_i相等，如果存在有一个数据不相等就说明签名验证不成功，说明消息或者某些数据被更改了。

注意：这是一次性数字签名方案，说明如果重复使用同一个私钥对不同消息进行数字签名，很可能就能伪造数字签名了。所以一次性数字签名在可能会存在重复使用私钥的情况。

代码实现

  • 实现的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
from hashlib import sha256
from Crypto.Util.number import long_to_bytes
import random
# 使用sha2-256进行哈希链的计算
def hash_chain(m,x):
    t = m
    for i in range(x):
        t = sha256(t).digest()
    return t

# 创建公钥和私钥
def key_gen():
    omega,t1,t2 = 8, 32, 2
    sk = [random.randint(0,2**(omega * 32)) for _ in range(t1+t2)] # 生成私钥
    pk = [hash_chain(long_to_bytes(m),255) for m in sk] # 生成公钥
    return sk,pk

# 进行签名操作m表示需要签名的消息,sk表示用于签名的私钥
def sign(m,sk):
    # 计算消息的哈希值
    m_ = sha256(m).digest()
    # V用于存储签名的结果
    V = []

    # 签名消息
    for index, item in enumerate(m_):
        V.append(hash_chain(long_to_bytes(sk[index]),item))
    sigma = long_to_bytes(sum(list(m_)))

    # 签名校验和
    for index, item in enumerate(sigma):
        V.append(hash_chain(long_to_bytes(sk[index+32]),item))

    return V

# 进行数字签名的验证
def verify(m,V,pk):
    m_ = sha256(m).digest()
    V_ = []
    # 计算剩余的哈希链
    for index, item in enumerate(m_):
        V_.append(hash_chain(V[index],255-item))

    c = long_to_bytes(sum(list(m_)))
    # 计算校验和部分的剩余哈希链
    for index,item in enumerate(c):
        V_.append(hash_chain(V[index+32],255-item))

    # 判断计算出来的哈希链是否与公钥pk相等
    for i in range(len(V_)):
        if pk[i] != V_[i]:
            return False
    return True



if __name__ == '__main__':
    sk, pk = key_gen()
    m = b'AAAA'
    V = sign(m,sk)
    # 当 m 没被修改时进行认证
    result = verify(m,V,pk)
    print(f"m没被修改={result}")
    # 当 m 被修改过时进行认证
    result2 = verify(b'AAA',V,pk)
    print(f'm被修改过进行认证={result2}')

例题-nepctf2025_nepsign

  • 题目附件如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
from gmssl import sm3
from random import SystemRandom
from ast import literal_eval
import os
flag = os.environ["FLAG"]
def SM3(data):
    d = [i for i in data]
    h = sm3.sm3_hash(d)  
    return h

# SM3和SM3_n是一块的,实现的就是哈希值计算,所以此题使用的就是SM3作为哈希函数
def SM3_n(data, n=1, bits=256):
    for _ in range(n):
        data = bytes.fromhex(SM3(data))
    return data.hex()[:bits // 4]


class Nepsign():
    # 构造方法, 初始化n = 256 , hex_symbols = '012....' ,调用keygen函数
    # 从sign()函数中可以看出,omega = 8
    # 从公钥的生成可以看出哈希链也是哈希了255次
    
    def __init__(self): 
        self.n = 256
        self.hex_symbols = '0123456789abcdef'
        self.keygen()

    # 密钥生成方式类似于WOTS(Winternitz one-time signature scheme)
    def keygen(self): 
        rng = SystemRandom()   
        self.sk = [rng.randbytes(32) for _ in range(48)] 			  # 生成私钥sk,生成48组
        self.pk = [SM3_n(self.sk[_], 255, self.n) for _ in range(48)] # 生成公钥pk,生成48组
        return self.sk, self.pk # 返回数据及其哈希值

    def sign(self, msg, sk=None): 	# 签名操作
        sk = sk if sk else self.sk  # 获取私钥
        m = SM3(msg) 				# 计算消息msg的哈希值,结果为m
        m_bin = bin(int(m, 16))[2:].zfill(256) # 将哈希值转换为二进制比特填充,填充到256位
        a = [int(m_bin[8 * i: 8 * i + 8], 2) for i in range(self.n // 8)] # 8位一组,8位一组的取出来
        step = [0] * 48 			# 初始化,保存a数组的值
        qq = [0] * 48 				# 初始化,保存hash值
        
        for i in range(32):			# 计算哈希链,哈希次数为step[i],哈希的数据为sk[i]
            step[i] = a[i]
            qq[i] = SM3_n(sk[i], step[i]) 
        
        # 这里相当于自定义了一个校验和,这个校验和是统计m消息的哈希值的16进制字符表示中0~f的索引和
        # 比如m[0]='0',m[16]='0',那么sum[0] = 0 + 16
        sum = [0] * 16
        for i in range(16):
            sum[i] = 0
            for j in range(1, 65):
                if m[j - 1] == self.hex_symbols[i]: 
                    sum[i] += j     				
            step[i + 32] = sum[i] % 255 				 # 将sum[i]模上255
            qq[i + 32] = SM3_n(sk[i + 32], step[i + 32]) # 计算校验和部分的哈希链
        
        return [i for i in qq] # 相当于返回qq列表,qq列表长度为

    def verify(self, msg, qq, pk=None): 	# 验证过程
        qq = [bytes.fromhex(i) for i in qq] #
        pk = pk if pk else self.pk
        m = SM3(msg)
        m_bin = bin(int(m, 16))[2:].zfill(256)
        a = [int(m_bin[8 * i: 8 * i + 8], 2) for i in range(self.n // 8)]
        step = [0] * 48
        pk_ = [0] * 48
        for i in range(32):
            step[i] = a[i]
            pk_[i] = SM3_n(qq[i], 255 - step[i]) # 关键点一共会进行255次哈希,抓住这一点去伪造qq
        sum = [0] * 16
        for i in range(16):
            sum[i] = 0
            for j in range(1, 65):
                if m[j - 1] == self.hex_symbols[i]:
                    sum[i] += j
            step[i + 32] = sum[i] % 255
            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是输入消息,消息不等于happy for NepCTF 2025就会对输入的消息进行签名,但是这里存在一个私钥复用的漏洞点,通过特殊构造其实就可以得到qq列表
            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:
            qq = literal_eval(input('give me a qq: ')) # 输入qq使得使得qq满足对happy for NepCTF 2025这个消息的签名
            if Sign.verify(b'happy for NepCTF 2025', qq):
                print(flag)

  • 通过解读代码其实就发现本题其实可以得到，最关键的利用点就是要想办法获取消息b'happy for NepCTF 2025'，签名过后的qq数组。
  • 其实使用题目中现成的函数，可以得到消息b'happy for NepCTF 2025'的哈希值以及校验和的具体值,也就是上面代码中的step的值，而step的值代表着私钥哈希的次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from pwn import *
from gmssl import sm3
import os
from random import SystemRandom

def SM3(data):
    d = [i for i in data]
    h = sm3.sm3_hash(d)  # 应该是计算一个hash值
    return h

def SM3_n(data, n=1, bits=256):
    for _ in range(n):
        data = bytes.fromhex(SM3(data))
    return data.hex()[:bits // 4]
# 首先计算出对消息b'happy for NepCTF 2025'来说,它的step的状态
msg = b'happy for NepCTF 2025'
def c_step(msg):
    m = SM3_n(msg)
    m_bin = bin(int(m, 16))[2:].zfill(256)
    step = [0]*48
    a = [int(m_bin[8 * i: 8 * i + 8], 2) for i in range(256 // 8)]
    hex_symbols = '0123456789abcdef'
    for i in range(32):
        step[i] = a[i]
    sum = [0] * 16
    for i in range(16):
        sum[i] = 0
        for j in range(1, 65):
            if m[j - 1] == hex_symbols[i]:  # 如果消息的哈希值对应索引符合hex_symbols中的某一个
                sum[i] += j  # sum就会加上索引
        step[i + 32] = sum[i] % 255
    return step

step_des = c_step(b'happy for NepCTF 2025')
print(step_des)

image-20250901222946617

  • 通过观察代码就会发现，每次使用选择1的签名操作时，都使用的是同一个私钥进行签名，由于消息b'happy for NepCTF 2025'的step值是已知的。所以我们只要发送特殊的消息，使得该消息的step1[i]<=step[i]

    • 当step1[i]<step[i]的时候，其实可以使用返回的qq1[i]，继续哈希step[i]-step1[i]次就能得到消息b'happy for NepCTF 2025'对应的qq[i]的值
    • 当step1[i]=step[i]的时候，qq1[i]==qq[i]
    • 这样通过有限次的对不同的特殊消息进行签名，就可以得到pp这个列表的值。

  • 接下来使用下面这一串代码可以生成符合要求的消息，也就是满足step1[i]<=step[i]的消息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from pwn import *
from gmssl import sm3
import os
from random import SystemRandom

def SM3(data):
    d = [i for i in data]
    h = sm3.sm3_hash(d)  # 应该是计算一个hash值
    return h

def SM3_n(data, n=1, bits=256):
    for _ in range(n):
        data = bytes.fromhex(SM3(data))
    return data.hex()[:bits // 4]

# 首先计算出对消息b'happy for NepCTF 2025'来说,它的step的状态
msg = b'happy for NepCTF 2025'

def c_step(msg):
    m = SM3_n(msg)
    m_bin = bin(int(m, 16))[2:].zfill(256)
    step = [0]*48
    a = [int(m_bin[8 * i: 8 * i + 8], 2) for i in range(256 // 8)]
    hex_symbols = '0123456789abcdef'
    for i in range(32):
        step[i] = a[i]
    sum = [0] * 16
    for i in range(16):
        sum[i] = 0
        for j in range(1, 65):
            if m[j - 1] == hex_symbols[i]:  # 如果消息的哈希值对应索引符合hex_symbols中的某一个
                sum[i] += j  # sum就会加上索引
        step[i + 32] = sum[i] % 255
    return step

step_des = c_step(b'happy for NepCTF 2025')
print(step_des)
candidate = []
for i in range(48):
    while True:
        x = os.urandom(5)
        step = c_step(x)
        if step[i] <= step_des[i]:
            candidate.append(x.hex())
            break
print(candidate)
"""
candate = ['e528ac746f', 'ad694be518', '12e5f725da', 'f38b0675a8', 'd126dd5379', 'e1bcffc062', 'f54fb14599', '9e4ce2c549', '42bb777a69', '37773f0771', '605fc06b20', '3dd0ba0a5b', 'f01e1de8f1', '651d6251d5', '07e90c3714', '2e70224c66', 'cd73d66284', 'dd270bb39b', '0afbbf91bb', '21954ad626', '53c6e4b606', 'cb6632070b', '25e43397f6', 'd6f54113c6', '0f1dbf213f', '8a71fbbcef', '1e484654d5', 'c0cce89280', '720c8fde3a', 'b42e82218b', '8fb6002d72', 'fa4804f1af', 'ff05854709', '0e83a61727', 'd087fccce3', '08958c158a', '5bc77069ea', 'b1173ddd72', 'f0bf6f2b4f', 'b144583404', '8ebc7c5eb8', 'dd82f6435d', '903377a152', 'f31923e8d1', '58ab6aac57', '6bc744f37c', '4ca8b192b1', '9f22cebc5f']
"""
  • 最后使用candidate中的消息泄露消息b'happy for NepCTF 2025'的qq数组的值，最后再使用选项2认证即可。最终exp如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
from pwn import *
from gmssl import sm3
import os
from random import SystemRandom
context.log_level = 'debug'
def SM3(data):
    d = [i for i in data]
    h = sm3.sm3_hash(d)  # 应该是计算一个hash值
    return h

def SM3_n(data, n=1, bits=256):
    for _ in range(n):
        data = bytes.fromhex(SM3(data))
    return data.hex()[:bits // 4]

# 首先计算出对消息b'happy for NepCTF 2025'来说,它的step的状态
msg = b'happy for NepCTF 2025'

def c_step(msg):
    m = SM3_n(msg)
    m_bin = bin(int(m, 16))[2:].zfill(256)
    step = [0]*48
    a = [int(m_bin[8 * i: 8 * i + 8], 2) for i in range(256 // 8)]
    hex_symbols = '0123456789abcdef'
    for i in range(32):
        step[i] = a[i]
    sum = [0] * 16
    for i in range(16):
        sum[i] = 0
        for j in range(1, 65):
            if m[j - 1] == hex_symbols[i]:  # 如果消息的哈希值对应索引符合hex_symbols中的某一个
                sum[i] += j  # sum就会加上索引
        step[i + 32] = sum[i] % 255
    return step

step_des = c_step(b'happy for NepCTF 2025')
print(step_des)
"""
candate = []
for i in range(48):
    while True:
        x = os.urandom(5)
        step = c_step(x)
        if step[i] <= step_des[i]:
            candate.append(x.hex())
            break
print(candate)
"""

candate = ['e528ac746f', 'ad694be518', '12e5f725da', 'f38b0675a8', 'd126dd5379', 'e1bcffc062', 'f54fb14599', '9e4ce2c549', '42bb777a69', '37773f0771', '605fc06b20', '3dd0ba0a5b', 'f01e1de8f1', '651d6251d5', '07e90c3714', '2e70224c66', 'cd73d66284', 'dd270bb39b', '0afbbf91bb', '21954ad626', '53c6e4b606', 'cb6632070b', '25e43397f6', 'd6f54113c6', '0f1dbf213f', '8a71fbbcef', '1e484654d5', 'c0cce89280', '720c8fde3a', 'b42e82218b', '8fb6002d72', 'fa4804f1af', 'ff05854709', '0e83a61727', 'd087fccce3', '08958c158a', '5bc77069ea', 'b1173ddd72', 'f0bf6f2b4f', 'b144583404', '8ebc7c5eb8', 'dd82f6435d', '903377a152', 'f31923e8d1', '58ab6aac57', '6bc744f37c', '4ca8b192b1', '9f22cebc5f']

#host = "nepctf30-tjtu-vam0-ewpd-crfw4njdv208.nepctf.com"
#port = '443'
#p = remote(host, port, ssl=True, sni=host)
p = process(['python3.10','server.py'])
hash_list = []
qq = []

for i in range(len(candate)):
    p.sendlineafter(b'>',b'1')
    p.sendlineafter(b'msg',candate[i].encode())
    hash = p.recvuntil(b']').decode()[3:-1]
    hash = hash.split(',')
    hash_ = []
    for j in range(len(hash)):
        if j == 0:
            hash_.append(hash[j][1:-1])
        else:
            hash_.append(hash[j][2:-1])
    step = c_step(bytes.fromhex(candate[i]))
    t = step_des[i] - step[i]
    #print(hash_)
    qq.append(SM3_n(bytes.fromhex(hash_[i]),t))
    #print(qq)
print(qq)
p.sendlineafter(b'>',b'2')
p.sendlineafter(b'give me a qq:',str(qq).encode())
p.interactive()

image-20250901225954934