signup
6 minutes to read
We are given the Python source code to encrypt the flag (app.py
):
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:])
Moreover, we have the output of the script (output.txt
):
[+] q condition is satisfied : 256 bit
82349764091980216703243528787846721157571379253101971061732427939554681522787
[+] p condition is satisfied : 2048 bit
22597614376179368541927291014351181151227386315855982530475290304066480549601872481125000412312232411854471891135859606462198144416258790805203892259557432117585853522644532244043882866950543772453962473369978828348563267281282352402870551728874298860312184560283971631533453430210347478794479982659822354364676170461394200151617927348650724770337556315374296708920869883704844016422867256502854967833552352244354161923370938186895496059235837548125257119775236437293842236838420824347387394024112360489719718482356279060719080630335848636921250967340335457343005624222097640480295331833551512059471129216303573167509
[+] g condition is satisfied
1522212929726315022276463307120954560926577974082882818811797965963142559037271005677110576098054722157527674127902562772533441779935566082403254092732974888203331702770403906546118095393659134079664766399608052006354212408035095060235607110586791971501473747663375215625574865706205289870455822949113508277054039439561937834562865074493156250996591912564352116714825726533396169890605271470775008065174813981767038809048518345994705536020788635479039463106099323099699225053825245500316037480436011003338091199884975066597695902083102085310246580054607257558459623691521498166469718547232285924180800892984387501802
[+] public key : 10301551349126329107088362265646928131049491442403482867496980836175873288506342576259707854365987702240527285572213439531723683002024146579359208402373918640506155640001430423630072829735081526301031527635977510509965942632354962864260004282149309957641462890526767244115715946314304320419688533957853639652278917522214541525010449214567907170562229712395613781822381944931215562795920884762599015541122869232934183665333423423899053585371134224417264749221110182731383922695086302701203378645475314119934887765168566160180674997559835947912322992312116118206408320274722250233256553213251576546136974127152356743543
=============================================================================================
===================================== Let's signup ==========================================
=============================================================================================
********************************************************************************
message : AUSSMKJVUNUPKBQ9X10U15409YQT79I6XNF7U0K5YI1568Q42L
signature: (56550035924113170505830328735387144247082155512866957659656089559388264283806, 81360207435150401587545818478565496253332501404776627654827674339875574853292)
********************************************************************************
message : TXNJSIVFXYVZL7SO393MU20XJAK9TN75M0VV29RYI1TMORLJB3
signature: (59454243776673042612495706274074683779593162173045377254234644102590461254174, 69901126149177379418089041430016833757460549835486806478242279543570064790515)
********************************************************************************
...
********************************************************************************
message : 4L0A5NHNMJAS3GJT0AWR1EPAL3R6YTMYAFIWK8SEIBFKUWH98V
signature: (23656285267672134853079913256893925874990475097287627360940184092061316722900, 60259462838850060842954111630590641393950384980094248092524544563470754722439)
********************************************************************************
message : VRE2H23VMQ2ORK8WNRTLBEASQF3GY9VK05CEYQ74KGO44B8QJK
signature: (4221419519268981734259482267401150235000986484722820856700522542664903741971, 39042686015475285979469968400043348530602713981922607759813976003431964156934)
[+] Cipher Text Flag (CTF) :
caaa08c4332e5701a9105ab701cc830b9ddbe18f6612c999f82a344bdc597819fba00f81772e4001bc584cff06d287089d8085a3123bdca5e7706612d7641f66a2b6228a67336c60975719ef04e1b55edad4e6850126ee92bc25692bd15e274db3b214973f224001af5f46bb40d2930cd69bae
We have some parameters for a Digital Signature Algorithm (DSA) implementation, a long list of messages and signatures and finally the encrypted flag. The flag is encrypted using XOR and the DSA private key
DSA implementation
The code for the DSA is correct (more information here):
- It generates prime numbers
and (such that for some integer ) - Then public values
and - And private values
and
In order to sign messages, it uses SHA512 as hash function and computes:
And the output is the pair
Helper functions
First of all, we can use this Python script to parse the contents of output.txt
:
def get_number(pattern: str, res: str) -> int:
return int(re.findall(pattern, res)[0])
def main():
with open('output.txt') as o:
res = o.read()
q = get_number(r'\[\+\] q condition is satisfied : 256 bit\n(\d+)', res)
p = get_number(r'\[\+\] p condition is satisfied : 2048 bit\n(\d+)', res)
g = get_number(r'\[\+\] g condition is satisfied \n(\d+)', res)
y = get_number(r'\[\+\] public key : (\d+)', res)
m_i = re.findall(r'message : (.+)', res)
signatures = re.findall(r'signature: \((\d+?), (\d+?)\)', res)
signatures = list(map(lambda s: list(map(int, s)), signatures))
r_i = list(map(lambda rs: rs[0], signatures))
s_i = list(map(lambda rs: rs[1], signatures))
ctf = re.findall(r'\[\+\] Cipher Text Flag \(CTF\) : \n(.+)', res)[0]
ctf = bytes.fromhex(ctf)
The security flaw
DSA can be compromised when the nonce values are not chosen randomly or they are used more than once. This time we have a total of 100 messages and signatures. However, if we list the number of distint values of getRandomRange
):
print(f'{len(r_i) = }, {len(set(r_i)) = }')
same_k = (-1, -1)
$ python3 solve.py
len(r_i) = 100, flen(set(r_i)) = 99
Since
same_k = (-1, -1)
for i, r in enumerate(r_i):
if r in r_i[i + 1:]:
same_k = (i, r_i.index(r, i + 1))
break
print(f'{same_k = }')
$ python3 solve.py
len(r_i) = 100, len(set(r_i)) = 99
same_k = (29, 74)
So, we have message
Therefore, we have
If we subtract both equations, we get
So we can find
Then
Python implementation
Let’s program the above equations in Python:
m29, r, s29 = m_i[same_k[0]], r_i[same_k[0]], s_i[same_k[0]]
m74, r, s74 = m_i[same_k[1]], r_i[same_k[1]], s_i[same_k[1]]
k_inv = (s29 - s74) * pow(h(m29) - h(m74), -1, q) % q
k = pow(k_inv, -1, q)
x = (s29 * k - h(m29)) * pow(r, -1, q) % q
print(f'{x = }')
key = long_to_bytes(x)
flag = repeating_xor_key(ctf, key)
print()
print(flag.decode())
Flag
If we run the script, we will find the flag:
$ python3 solve.py
len(r_i) = 100, len(set(r_i)) = 99
same_k = (29, 74)
You did a shared and known job, here is the flag :
HTB{Sh4r3d_K_1s_n0t_A_g00d_S1gninG_Id3a}
best wishes good luck!!
The full script can be found in here: solve.py
.