Simple Crypto - 0x09(2023 Lab - signature)
Background
[edu-ctf 2023] week03 - crypto2 - ECDSA
Source code
:::spoiler Source Code
from random import randint
from Crypto.Util.number import *
from hashlib import sha256
from ecdsa import SECP256k1
from ecdsa.ecdsa import Public_key, Private_key, Signature
from secret import FLAG
E = SECP256k1
G, n = E.generator, E.order
d = randint(1, n)
k = randint(1, n)
pubkey = Public_key(G, d*G)
prikey = Private_key(pubkey, d)
print(f'P = ({pubkey.point.x()}, {pubkey.point.y()})')
for _ in range(3):
print('''
1) Request for Signature
2) Check the Permission
3) exit''')
option = input()
if option == '1':
msg = input('What do you want? ')
if msg == 'Give me the FLAG.':
print('No way!')
else:
h = sha256(msg.encode()).digest()
# k = k * 1337 % n
sig = prikey.sign(bytes_to_long(h), k)
print(f'sig = ({sig.r}, {sig.s})')
elif option == '2':
msg = 'Give me the FLAG.'
r = input('r: ')
s = input('s: ')
h = bytes_to_long(sha256(msg.encode()).digest())
verified = pubkey.verifies(h, Signature(int(r), int(s)))
if verified:
print(FLAG)
else:
print('Bad signature')
else:
print("bye~")
break
:::
Recon
這一題主要就是利用上課提到的nonce $k$不隨機的問題，因為$k$只能用一次，也就代表他需要夠隨機，如果像LCG這樣的psudo random generator產生的話，一但被compromise，就會被推導出private key $d$，而這個lab就是有這樣的問題
- 觀察source code會發現不同的nonce $k$之間會產生一個1337倍數的關係，然後如果request
Give me the FLAG.的signature會被拒絕，所以只能自己產生Give me the FLAG.的signature再丟給server檢查，如果過了就可以拿到flag，但重點是要怎麼偽造signature假裝是server簽的?就是要想辦法拿到server產生的private key $d$，可以詳細看一下source code中提到，通常public key都一樣，所以重點是$d$才能產生private key，然後用private key簽署message1
2
3
4
5
6
7E = SECP256k1 G, n = E.generator, E.order d = randint(1, n) pubkey = Public_key(G, d*G) prikey = Private_key(pubkey, d) ↓ sig = prikey.sign(bytes_to_long(h), k) -
已知(題目給的部分) 只要我們給兩次要簽章的message，總共可以得到以下資訊
\[coordinate\ (x_0,\ y_0),\\ hash\ H_1,\ hash\ H_2,\\ signature\ (s_1,\ r_1),\ (s_2,\ r_2)\] -
推導 假設$msg=b’a’$
\[H_1 = H_2 = sha256(msg)\\ \begin{aligned} k_1 &= {s_1}^{-1} \cdot (H_1 + d\cdot r_1)={s_1}^{-1} \cdot H_1 + d\cdot r_1 \cdot {s_1}^{-1}\\ k_2 &= {s_2}^{-1} \cdot (H_2 + d\cdot r_2) = 1337\times k_1=\\ &= {s_2}^{-1} \cdot H_2 + {s_2}^{-1}\cdot d\cdot r_2\\ &= 1337 \cdot {s_1}^{-1} \cdot H_1 + 1337 \cdot d\cdot r_1 \cdot {s_1}^{-1} \end{aligned}\\ \downarrow \\ d\cdot (H_2\cdot {s_2}^{-1} - 1337\cdot H_1\cdot {s_1}^{-1})=1337\cdot r_1\cdot {s_1}^{-1}-r_2\cdot {s_2}^{-1}\\ \hookrightarrow d = {1337\cdot r_1\cdot {s_1}^{-1}-r_2\cdot {s_2}^{-1} \over H_2\cdot {s_2}^{-1} - 1337\cdot H_1\cdot {s_1}^{-1}}\] - 得到原本的private key $d$之後就可以直接選一個亂數nonce $k$，然後重新自己簽署
Give me the FLAG.的signature
Exploit
1 | |
Flag: FLAG{EphemeralKeyShouldBeRandom}