# SIGNATURES PART 2
## 28. Vote for Pedro
### Description:
- If you want my flag, you better vote for Pedro! Can you sign your vote to the server as Alice?
- Connect at `socket.cryptohack.org 13375`
- Challenge code:
```python
#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, long_to_bytes
from utils import listener
FLAG = "crypto{????????????????????}"
class Challenge():
def __init__(self):
self.before_input = "Place your vote. Pedro offers a reward to anyone who votes for him!\n"
def challenge(self, your_input):
if 'option' not in your_input:
return {"error": "You must send an option to this server"}
elif your_input['option'] == 'vote':
vote = int(your_input['vote'], 16)
verified_vote = long_to_bytes(pow(vote, ALICE_E, ALICE_N))
# remove padding
vote = verified_vote.split(b'\00')[-1]
if vote == b'VOTE FOR PEDRO':
return {"flag": FLAG}
else:
return {"error": "You should have voted for Pedro"}
else:
return {"error": "Invalid option"}
listener.start_server(port=13375)
```
### Solution:
- Tất nhiên điều đầu tiên khi giải bài là phải đoán server nhả flag khi nào. Đối với bài này, flag được nhả ra khi thỏa mãn:
```python
vote = int(your_input['vote'], 16)
verified_vote = long_to_bytes(pow(vote, ALICE_E, ALICE_N))
# remove padding
vote = verified_vote.split(b'\00')[-1]
if vote == b'VOTE FOR PEDRO':
return {"flag": FLAG}
```
- Vào file `alice.key` ta lấy được:
```python
ALICE_N = 22266616657574989868109324252160663470925207690694094953312891282341426880506924648525181014287214350136557941201445475540830225059514652125310445352175047408966028497316806142156338927162621004774769949534239479839334209147097793526879762417526445739552772039876568156469224491682030314994880247983332964121759307658270083947005466578077153185206199759569902810832114058818478518470715726064960617482910172035743003538122402440142861494899725720505181663738931151677884218457824676140190841393217857683627886497104915390385283364971133316672332846071665082777884028170668140862010444247560019193505999704028222347577
ALICE_E = 3
```
- Rõ ràng, ta cần chọn `vote` sao cho:
```python
msg = b'VOTE FOR PEDRO' = long_to_bytes(pow(vote, ALICE_E, ALICE_N)).split(b'\00')[-1]
--> bytes_to_long(prefix + b'\00' + msg) = pow(vote, e, n)
--> left ≡ vote ^ 3 (mod n)
```
- Ta cần thay đổi giá trị của `prefix` để tìm `left` là thặng dư bậc ba của `vote` theo modulo `n`. Dễ thấy, các bytes `prefix` sẽ bị bỏ qua vì hàm `split` nên:
```python
prefix = k*256**(15)
#với k bất kì và 15 chính là số bytes của b'\00' + msg
--> left ≡ bytes_to_long(msg) (mod 256**15)
```
- Thực tế thì `n` lớn hơn `256**15` rất nhiều và phép đồng dư `mod n` không còn quan trọng nên phương trình trở thành:
```python
vote ^ 3 ≡ bytes_to_long(msg) (mod 256**15)
```
- Với phương trình này ta có thể sử dụng sage để tính vote dễ dàng:
```python
from Crypto.Util.number import bytes_to_long
msg = b'VOTE FOR PEDRO'
msg = bytes_to_long(msg)
vote = int(mod(msg, 256**15).nth_root(3))
assert (vote**3) % (256**15) == msg
print(vote)
```
- Tính được:
```python
vote = 855520592299350692515886317752220783
```
- Từ đó ta gửi lại vote cho server và lụm flag. Code:
```python
from pwn import *
from json import *
from Crypto.Util.number import long_to_bytes, bytes_to_long
def send(hsh):
return r.sendline(dumps(hsh))
ALICE_N = 22266616657574989868109324252160663470925207690694094953312891282341426880506924648525181014287214350136557941201445475540830225059514652125310445352175047408966028497316806142156338927162621004774769949534239479839334209147097793526879762417526445739552772039876568156469224491682030314994880247983332964121759307658270083947005466578077153185206199759569902810832114058818478518470715726064960617482910172035743003538122402440142861494899725720505181663738931151677884218457824676140190841393217857683627886497104915390385283364971133316672332846071665082777884028170668140862010444247560019193505999704028222347577
ALICE_E = 3
r = remote('socket.cryptohack.org', 13375)
print(r.recv())
vote = 855520592299350692515886317752220783
option = {
'option': 'vote',
'vote': hex(vote)
}
send(option)
get = loads(r.recv())
flag = get['flag']
print(flag)
```
### Flag:
> crypto{y0ur_v0t3_i5_my_v0t3}
### Note:
- Sau đó mình có tham khảo vài cách khác tìm `vote`, bên cạnh cách trong bài, có thể dùng:
```python
from Crypto.Util.number import bytes_to_long
msg = b'VOTE FOR PEDRO'
x = var('x')
f = x**3 - bytes_to_long(msg)
print(solve_mod(f, 256**15))
```
- Cá nhân mình thích cách này hơn vì nó dễ hiểu hơn hàm `mod` và `nth_root` kia :kissing_smiling_eyes:
---
## 29. Let's Decrypt Again
### Description:
- Let's Decrypt was too easy, let's do it again!
- Connect at `socket.cryptohack.org 13394`
- Challenge code:
```python
#!/usr/bin/env python3
import hashlib
import re
import secrets
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime, inverse, isPrime
from pkcs1 import emsa_pkcs1_v15
from utils import listener
# from params import N, E, D
FLAG = b"crypto{????????????????????????????????????}"
BIT_LENGTH = 768
MSG = b'We are hyperreality and Jack and we own CryptoHack.org'
DIGEST = emsa_pkcs1_v15.encode(MSG, BIT_LENGTH // 8)
SIGNATURE = pow(bytes_to_long(DIGEST), D, N)
BTC_PAT = re.compile("^Please send all my money to ([1-9A-HJ-NP-Za-km-z]+)$")
def xor(a, b):
assert len(a) == len(b)
return bytes(x ^ y for x, y in zip(a, b))
def btc_check(msg):
alpha = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
addr = BTC_PAT.match(msg)
if not addr:
return False
addr = addr.group(1)
raw = b"\0" * (len(addr) - len(addr.lstrip(alpha[0])))
res = 0
for c in addr:
res *= 58
res += alpha.index(c)
raw += long_to_bytes(res)
if len(raw) != 25:
return False
if raw[0] not in [0, 5]:
return False
return raw[-4:] == hashlib.sha256(hashlib.sha256(raw[:-4]).digest()).digest()[:4]
PATTERNS = [
re.compile(r"^This is a test(.*)for a fake signature.$").match,
re.compile(r"^My name is ([a-zA-Z\s]+) and I own CryptoHack.org$").match,
btc_check
]
class Challenge():
def __init__(self):
self.shares = [secrets.token_bytes(len(FLAG))
for _ in range(len(PATTERNS) - 1)]
last_share = FLAG
for s in self.shares:
last_share = xor(last_share, s)
self.shares.append(last_share)
self.pubkey = None
self.suffix = None
self.before_input = "This server validates statements we make for you. Present your messages and public key, and if the signature matches ours, you must undoubtably be us. Just do it multiple times to make sure...\n"
def challenge(self, your_input):
if not 'option' in your_input:
return {"error": "You must send an option to this server"}
elif your_input['option'] == 'get_signature':
return {
"N": hex(N),
"E": hex(E),
"signature": hex(SIGNATURE)
}
elif your_input['option'] == 'set_pubkey':
if self.pubkey is None:
pubkey = int(your_input['pubkey'], 16)
if isPrime(pubkey):
return {"error": "Everyone knows RSA keys are not primes..."}
self.pubkey = pubkey
self.suffix = secrets.token_hex(32)
return {"status": "ok", "suffix": self.suffix}
return {"error": "I already had one"}
elif your_input['option'] == 'claim':
if self.pubkey is None:
return {"error": "I need your modulus first, please"}
msg = your_input['msg']
n = self.pubkey
e = int(your_input['e'], 16)
index = your_input['index']
if not (0 <= index < len(PATTERNS)):
return {"error": "invalid index"}
if not msg.endswith(self.suffix):
return {"error": "Invalid message"}
digest = emsa_pkcs1_v15.encode(msg.encode(), BIT_LENGTH // 8)
calculated_digest = pow(SIGNATURE, e, n)
if bytes_to_long(digest) == calculated_digest:
r = PATTERNS[index](msg[:-len(self.suffix)])
if r:
return {"msg": "Congratulations, here's a secret", "secret": self.shares[index].hex()}
else:
return {"msg": "Ownership verified."}
else:
return {"error": "Invalid signature"}
else:
return {"error": "Invalid option"}
listener.start_server(port=13394)
```
### Solution:
- Đọc desc và số điểm thì chắc chắn bài này khó hơn nhiều lần bài `Let's Decrypt`. Mình cần biết server nhả flag khi nào, thực ra đọc xong mình cũng chả biết nó nhả flag ở đâu :penguin:
- Quay lại với bài, chall này giống với chall trước `Let's Decrypt`, cũng yêu cầu mình gửi các số `n` và `e`, cho biết `s` (signature), sao cho `m = pow(s, e, n)`. Ở đây thì `m` thực ra là 3 đoạn, tương ứng như sau:
```=0
index = 0 --> This is a test for a fake signature.
index = 1 --> My name is Zupp and I own CryptoHack.org
index = 2 --> Please send all my money to 88830112005MBBank
```
- vậy mình cần tìm cách tìm lại `e` và `n` thỏa mãn tương ứng. Bên cạnh đó biết `flag` đã được xor với các đoạn secret khác nên mình sẽ gửi lần lượt 3 đoạn `m` lên rồi xor lại để tìm `flag`.
- Nguồn thuật toán tấn công tham khảo ở [đây](http://mpqs.free.fr/corr98-42.pdf#page=11), trên thực tế bài toán sẽ quy về tìm `e` là dlog của `m` trong trường `mod n`.
- Trước tiên mình sẽ khởi tạo hai số `p` và `q`, nhưng thực ra chỉ cần khởi tạo một lần thôi và mũ nhiều lần lên (`n = p^k`) sao cho `p` là smooth prime là được. Lưu ý `p` phải là một số nguyên tố nên mình sẽ chọn `p = 2010103` cho đẹp (thực ra cũng do test nhiều lần bị fail :penguin:) và `k = 50`
- Với các `n` và `p` vừa khởi tạo, chắc chắn sẽ tìm lại được `e` tương ứng, tuy nhiên còn một vấn đề ở `m3` là `btc_check`. Tài khoản phải là một address bitcoin hợp lệ nên mình sẽ tự tạo một địa chỉ bằng [web này](https://spinthewheel.io/bitcoin-address-generator#google_vignette) (`3EovkHLK5kkAbE8Kpe53mkEbyQGjyf8ECw`)
- Giờ thì đem đi giải flag theo đúng quy trình trên là xong:
```python=
from pwn import *
from json import *
from Crypto.Util.number import bytes_to_long
from pkcs1 import emsa_pkcs1_v15
from sage.all import Mod, discrete_log
HOST = 'socket.cryptohack.org'
PORT = 13394
def send(msg):
return r.sendline(dumps(msg).encode())
def cvt(msg):
return bytes_to_long(emsa_pkcs1_v15.encode(msg.encode(), 768 // 8))
r = remote(HOST, PORT)
r.recv()
option = {'option': 'get_signature'}
send(option)
s = int(loads(r.recv())['signature'], 16)
p, k = 2010103, 50
n = p**k
option = {'option': 'set_pubkey', 'pubkey': hex(n)}
send(option)
suffix = loads(r.recv())['suffix']
m1 = 'This is a test for a fake signature.' + suffix
m2 = 'My name is Zupp and I own CryptoHack.org' + suffix
m3 = 'Please send all my money to 3EovkHLK5kkAbE8Kpe53mkEbyQGjyf8ECw' + suffix
msg1, msg2, msg3 = cvt(m1), cvt(m2), cvt(m3)
s = Mod(s, n)
msg1, msg2, msg3 = Mod(msg1, n), Mod(msg2, n), Mod(msg3, n)
e1 = discrete_log(msg1, s)
e2 = discrete_log(msg2, s)
e3 = discrete_log(msg3, s)
assert pow(s, e1, n) == msg1
assert pow(s, e2, n) == msg2
assert pow(s, e3, n) == msg3
option1 = {
'option': 'claim',
'msg': m1,
'index': int(0),
'e': hex(e1)
}
send(option1)
sec1 = bytes.fromhex(loads(r.recv())['secret'])
option2 = {
'option': 'claim',
'msg': m2,
'index': int(1),
'e': hex(e2)
}
send(option2)
sec2 = bytes.fromhex(loads(r.recv())['secret'])
option3 = {
'option': 'claim',
'msg': m3,
'index': int(2),
'e': hex(e3)
}
send(option3)
sec3 = bytes.fromhex(loads(r.recv())['secret'])
flag = xor(sec1, sec2, sec3).decode()
print(flag)
```
### Flag:
> ~~`crypto{let's_decrypt_w4s_t0o_ez_do_1t_ag41n}`~~
### Note:
- Bài được đi osint từ cực nhiều nguồn :penguin:, nhưng hướng đi chính vẫn là dlog các `m` trong trường `mod n`.
Sign in with Wallet
Connect another wallet