The aliens attacked our territory and stole our necessary supplies and kept them in a secure manner. We can get them back, but it requires a lot of data samples. Fortunately, we have some stuff to get back what we need. But, are we lucky enough?!
Information
Challenge: signup
Category: Crypto
Difficulty: Medium
Files: signup.zip 15.4 Kb
output.txt 35 KB
app.py 3 KB
Environment: Remnux VM
My Recommendations
Download it from hackthebox and verify it with:
sha256sum /path/to/signup.zipSHA256SUM:
fe7ec89c8e5ba71b20b84a03fe410292c177fde4ce5cb0288ec98887cb39051e
Walkthrough
1. Code Analysis
app.py
So this is a ECDSA/ElGamal (??) signature algorithm. At first glance, nothing crazy seems to be occurring. In the sign function, k is a random value which is what (should) make it safe. On top of that, the messages are hashed with SHA-512, again, another feature that makes it ‘safe’.
The flag is xored with private key x, which is unkown to us.
The out.txt file contains p,q,g,y and 100 plaintext messages and their corresponding signatures.
from Crypto.Util.number import getPrime, getRandomRange, isPrime, inverse, long_to_bytes, bytes_to_long
from hashlib import sha512
from random import SystemRandom
from FLAG import flag
L = 2048
N = 256
def repeating_xor_key(message, key):
repeation = 1 + (len(message) // len(key))
key = key * repeation
key = key[:len(message)]
msg = bytes([c ^ k for c, k in zip(message, key)])
return msg
def domain_params_generation():
q = getPrime(N)
print(f"[+] q condition is satisfied : {N} bit")
print(q)
p = 0
while not (isPrime(p) and len(bin(p)[2:]) == L):
factor = getRandomRange(2**(L-N-1), 2**(L-N))
p = factor*q + 1
print(f"[+] p condition is satisfied : {L} bit")
print(p)
g = 1
while g == 1:
h = getRandomRange(2, p-2)
g = pow(h, factor, p)
print(f"[+] g condition is satisfied ")
print(g)
return(p, q, g)
def key_generation(p, q, g):
x = getRandomRange(1, q-1)
y = pow(g, x, p)
# print(f"[+] private key : {x}")
print(f"[+] public key : {y}")
return(x, y)
def sign(message, private_key, parameters):
p, q, g = parameters
k = getRandomRange(1, q-1)
r = 0
while r == 0:
r = pow(g, k, p) % q
s = 0
while s == 0:
Hm = int(sha512(message.encode('utf-8')).hexdigest(), 16)
s = (inverse(k, q) * (Hm + private_key*r)) % q
return (r, s)
def verify(message, signature, public_key, parameters):
p, q, g = parameters
r, s = signature
if 0 < r < q and 0 < s < q:
w = inverse(s, q)
Hm = int(sha512(message.encode('utf-8')).hexdigest(), 16)
u1 = (Hm * w) % q
u2 = (r * w) % q
v = ( (pow(g, u1, p) * pow(public_key, u2, p)) % p ) % q
if v == r:
print(f"[+] Valid signature")
return True
else:
print("[!] Invalid signature")
return False
parameters = domain_params_generation()
p, q, g = parameters
keys = key_generation(p, q, g)
x, y = keys
print()
print("=============================================================================================")
print("===================================== Let's signup ==========================================")
print("=============================================================================================")
print()
with open('./messages', 'r') as o:
messages = o.readlines()
for message in messages:
message = message.rstrip()
print("********************************************************************************")
print(f"message : {message}")
signature = sign(message, x, parameters)
r, s = signature
print(f"signature: {signature}")
# verify(message, signature, y, parameters)
o.close()
key = long_to_bytes(x)
ctf = repeating_xor_key(flag, key)
print()
print("[+] Cipher Text Flag (CTF) : ")
print(hex(bytes_to_long(ctf))[2:])
2. Signature Analysis
Let’s load the data in python:
from Crypto.Util.number import getPrime, getRandomRange, isPrime, inverse, long_to_bytes, bytes_to_long
from hashlib import sha512
from random import SystemRandom
with open("output.txt", "r") as f:
data =[]
for line in f.readlines():
data.append(line.strip())
q,p,g,y = int(data[1]),int(data[3]),int(data[5]),int(data[6].replace('[+] public key :',''))
flag = bytes.fromhex(data[-1])
def clean_list(data):
delim = data[12]
filtered = [i for i in data[13:-3] if i != delim]
clean = []
for i in range(0,len(filtered),2):
msg = filtered[i].replace('message : ', '')
sig = filtered[i+1].replace('signature: ', '')
clean.append({"message": msg, "signature": eval(sig)})
return clean
signed_values = clean_list(data)
So we can check for two potential vulnerabilities identical messages, and identical signatures:
len(set([i['message'] for i in signed_values]))
#100 so there are no identical messages
len(set([i['signature'] for i in signed_values]))
#100, again no identical signatures
len(set([i['signature'][0] for i in signed_values]))
#99 ha! there are two identical r values. We can isolate the signatures like this:
rvalues = [i['signature'][0] for i in signed_values]
dupes = [i for i in signed_values if i['signature'][0] == [i for i in rvalues if rvalues.count(i)>1][0]]
If two r values are equal, then it means a nonce (k) was reused. We can recover it with a Nonce Reuse Attack.
3. Nonce Reuse Attack
The code for the attack is from here.
def attack(v1,v2,q,p,g):
L1 = int(sha512(v1['message'].encode('utf-8')).hexdigest(), 16)
L2 = int(sha512(v2['message'].encode('utf-8')).hexdigest(), 16)
s1 = v1['signature'][1]
r1 = v1['signature'][0]
s2 = v2['signature'][1]
r2 = v2['signature'][0]
candidates = (s1 - s2,s1 + s2,-s1 - s2,-s1 + s2)
z = L1 - L2
for candidate in candidates:
k = (z * pow(candidate,-1, q)) % p
if pow(g, k, p) % q == r1:
return k
key = attack(dupes[0],dupes[1],q,p,g)
Next, we need to recover the x value. We know that x is used in the sign function, and generates s:
s = (pow(key,-1, q) * (Hm1 + private_key*r)) % q
where r = pow(g, key, p) % q
So we can recover x likeso:
assert pow(g,(((s1 * key - Hm1) % p) * inverted_r) % q,p) == y
inverted_r = pow(r1,-1,q)
xval = (((s1 * key -Hm1) % p) * inverted_r) % q
assert pow(g, xval, p) == y
def check_sign(message, private_key, k):
r = 0
while r == 0:
r = pow(g, k, p) % q
s = 0
while s == 0:
Hm = int(sha512(message.encode('utf-8')).hexdigest(), 16)
s = (inverse(k, q) * (Hm + private_key*r)) % q
return (r, s)
assert check_sign(dupes[0]['message'], xval, key) == dupes[0]['signature']
assert check_sign(dupes[1]['message'], xval, key) == dupes[1]['signature']
4. Flag Recovery
The process from now is super straight forward, we convert the key to bytes and xor it to the encrypted cipher:
def repeating_xor_key(message, key):
repeation = 1 + (len(message) // len(key))
key = key * repeation
key = key[:len(message)]
msg = bytes([c ^ k for c, k in zip(message, key)])
return msg
key = long_to_bytes(xval)
ctf = repeating_xor_key(flag, key)
print(ctf.decode())
#You did a shared and known job, here is the flag :
#HTB{Sh4r3d_K_1s_n0t_A_g00d_S1gninG_Id3a}
#best wishes good luck!!
