03.babycrypto
2023-09-18 11:10:18 # 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. 完成题目
Prev
2023-09-18 11:10:18 # 19.Paradigm CTF 2021
Next