03.babycrypto
2023-08-10 17:17:27 # 19.Paradigm CTF 2021

babycrypto

分析

1.全局观

只有一个python文件和依赖,因为需要用到sha3,也就是pysha3库,因此用python3.5

2.任务

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
from random import SystemRandom
from ecdsa import ecdsa
import sha3
import binascii
from typing import Tuple
import uuid
import os

# 定义生成密钥对的函数 : 这个函数生成一个 ECDSA 密钥对,其中包括私钥 priv 和对应的公钥 pub
def gen_keypair() -> Tuple[ecdsa.Private_key, ecdsa.Public_key]:
"""
generate a new ecdsa keypair
"""
# 选择椭圆曲线参数 secp256k1
g = ecdsa.generator_secp256k1
# 随机生成私钥 d,范围在 [1, g.order()) 内
d = SystemRandom().randrange(1, g.order())
# 计算公钥 pub = g * d
pub = ecdsa.Public_key(g, g * d)
priv = ecdsa.Private_key(pub, d)
return priv, pub

# 定义生成会话密钥的函数: 这个函数生成一个随机的 32 字节会话密钥
def gen_session_secret() -> int:
"""
generate a random 32 byte session secret
"""
# 使用 /dev/urandom 生成随机数据
with open("/dev/urandom", "rb") as rnd:
seed1 = int(binascii.hexlify(rnd.read(32)), 16)
seed2 = int(binascii.hexlify(rnd.read(32)), 16)
return seed1 ^ seed2

# 定义哈希消息的函数: 这个函数将输入的字符串消息哈希为一个整数,用于签名
def hash_message(msg: str) -> int:
"""
hash the message using keccak256, truncate if necessary
"""
k = sha3.keccak_256()
k.update(msg.encode("utf8"))
d = k.digest()
n = int(binascii.hexlify(d), 16)
olen = ecdsa.generator_secp256k1.order().bit_length() or 1
dlen = len(d)
n >>= max(0, dlen - olen)
return n


if __name__ == "__main__":
# 获取标志信息或设置默认标志
# 这里获取环境变量中的 FLAG 值作为标志信息,如果环境变量中没有设置,则使用默认的占位标志
flag = os.getenv("FLAG", "PCTF{placeholder}")

# 生成 ECDSA 密钥对和会话密钥
# 通过调用之前定义的 gen_keypair() 函数生成 ECDSA 密钥对,然后调用 gen_session_secret() 函数生成会话密钥。
priv, pub = gen_keypair()
session_secret = gen_session_secret()

# 在这个循环中,程序四次要求用户输入消息,然后对消息进行哈希处理。
# 接着,使用 priv.sign() 方法对哈希值进行签名,其中 priv 是之前生成的私钥,
# session_secret 是会话密钥。签名后,程序打印出签名的 r 和 s 值。
for _ in range(4):
message = input("message? ")
hashed = hash_message(message)
sig = priv.sign(hashed, session_secret)
print(f"r=0x{sig.r:032x}")
print(f"s=0x{sig.s:032x}")

# 生成测试哈希值并验证签名
# 首先,程序生成一个随机的测试哈希值并打印出来。然后,程序等待用户输入 r 和 s 值。
test = hash_message(uuid.uuid4().hex)
print(f"test=0x{test:032x}")

r = int(input("r? "), 16)
s = int(input("s? "), 16)

# 程序使用公钥 pub 对测试哈希值进行验证,检查用户输入的签名是否有效。
# 如果验证失败,程序输出一条失败消息并退出
# 这就意味着,我们需要获得产生这个公钥的私钥,然后拿这个私钥签名一个信息(就是这里的test)
# 获得这个信息的r和s
if not pub.verifies(test, ecdsa.Signature(r, s)):
print("better luck next time")
exit(1)

print(flag)

任务是:提供r和s,然后对信息test进行验签成功。

3.详细分析

想要验签成功,就必须拿到私钥,然后对test进行签名才能拿到正确的r和s,问题是我们没有私钥。

没有思路的时候,就随便跑一下程序,发现无论输入什么message,输出的r都是一样的

问题就出来了,r相同导致私钥泄露,和capturetheether这题原理一样。

思路1

因此,我们可以通过相同的r来还原出私钥(似乎下面的脚本无法根据相同的r还原出私钥,但是可以签名信息,但也是用相同的私钥签名的):

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
from random import SystemRandom
from ecdsa import ecdsa
import sha3
import binascii
from typing import Tuple
import uuid
import os
import math

def hash_message(msg: str) -> int:
"""
hash the message using keccak256, truncate if necessary
"""
k = sha3.keccak_256()
k.update(msg.encode("utf8"))
d = k.digest()
n = int(binascii.hexlify(d), 16)
olen = ecdsa.generator_secp256k1.order().bit_length() or 1
dlen = len(d)
n >>= max(0, dlen - olen)
return n

def modInverse(b,m):
g = math.gcd(b, m)
if (g != 1):
return -1
else:
return pow(b, m - 2, m)

# Function to compute a/b under modulo m
def modDivide(a,b,m):
a = a % m
inv = modInverse(b,m)
if(inv == -1):
print("Division not defined")
else:
return (inv*a) % m

if __name__ == "__main__":
msg1 = input("message_01: ")
msg1_hashed = hash_message(msg1)
msg2 = input("message_02: ")
msg2_hashed = hash_message(msg2)
r1 = int(input("message_01_r1: "), 16)
s1 = int(input("message_01_s1: "), 16)
s2 = int(input("message_02_rs: "), 16)

g = ecdsa.generator_secp256k1
n = g.order()

k = modDivide((msg1_hashed - msg2_hashed), (s1 - s2), n)

d = modDivide(((s1 * k) - msg1_hashed), r1, n)

test = int(input("your message's hash to sign: "), 16)

pub = ecdsa.Public_key(g, g * d)
priv = ecdsa.Private_key(pub, d)

sig = priv.sign(test, k)
# 将结果输出为16进制
print("your message's r=0x{:032x}".format(sig.r))
print("your message's s=0x{:032x}".format(sig.s))

思路2

通过下面的脚本,可以获得私钥,然后再用私钥进行签名,然后得到r和s即可

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
from ecdsa import ecdsa, SigningKey
from ecdsa.numbertheory import inverse_mod
from hashlib import sha1

# g: chal.py使用的特定加密曲线算法。
# r: 相同的r值
# sA,sB: 输入message, 然后chal.py输出的s
# hashA,hashB: 输入的message的hash值

g = ecdsa.generator_secp256k1
publicKeyOrderInteger = g.order()

r = "e430b3a398f2320556eef81c1c523ea5ae0a920f493c8376eafcb0dc9cd75b89" # 相同的r值

sA = "bbfb7b34c31f025bddb8724a53dae7dd5a17c489587b881b8ed0dc5453c07e87" # 消息`</3`的s
sB = "43d8ec82d7b6b1f3c8ed41b0ba682d5291f6d4a922a57729fa716dccd0f237d6" # 消息`no`的s

hashA = "45951261090588542051596130132754692813999860320220484796045003839994507210350" # `</3`的hash值
hashB = "56710668495515998944273818574660611208941006033402527734960197520384934694586" # `no`的哈希值

r1 = int(r, 16)
s1 = int(sA, 16)
s2 = int(sB, 16)

L1 = int(hashA, 10)
L2 = int(hashB, 10)

numerator = (((s2 * L1) % publicKeyOrderInteger) - ((s1 * L2) % publicKeyOrderInteger))
denominator = inverse_mod(r1 * ((s1 - s2) % publicKeyOrderInteger), publicKeyOrderInteger)

privateKey = numerator * denominator % publicKeyOrderInteger

print(privateKey)

解题

思路1

  1. 随便输入4个message
  2. 打印出test=的内容,将此内容作为参数输入我们的脚本,得到r和s
  3. 再将r和s输入回题目的python脚本,完成

下面是得到r和s的脚本例子:

1
2
3
4
5
6
7
8
9
PS E:\BlockChainCTF\Paradigm 2021> & d:/environment/python305/python305.exe "e:/BlockChainCTF/Paradigm 2021/src/03.babycrypto/test.py"
msg1? test
msg2? test1
r1? 67301546230259439644359053584721379568919080569085179252685698636483892629289
s1? 73622799527434127903940560943498995649761922715977926009361268130333681085387
s2? 20463651075801853238185465293923791885297838446287006594323104600372328967360
test? `输入题目脚本给出的test内容`
solved r=xxxxx
solved s=xxxxx

思路2

  1. 跑脚本得到私钥
  2. 用私钥对chal.py提供的hash进行签名
  3. 将签名分解出r和s
  4. 完成题目