Cryptography – 499 pts (3 solves) – Chall author: Polymero (me)
“HADIOR will hold the DOOR.”
nc ctf.k3rn3l4rmy.com 2241
Files: hadior.py
This challenge was part of our very first CTF, K3RN3LCTF 2021.
Exploration
Upon connecting with the netcat address we are greeted by HADIOR. Alledgedly HADIOR will hold the DOOR. Well, we will see about that!
|
| Security provided by HADIOR
| _
| _ _____________( )__________
| | | (_____________ _________ \
| | |___________ _| | _____) )
| | ___ ___ | / | | __ /
| | | | | | |__/ /| |___| | \ \
| |_| |_| |_____/ \_____/ \_\
|
| HADIOR will hold the DOOR
|
| Connection established in 2.70 s.
|
| Domain parameters BA.z3tNC6gTFZK-nxqQiEqYA5ICv3HelkDtHy8eFQiXqI9rlKdej0Op6KJKs-g6HFUeWvdy6Wuyz3LAhk4Vsnoi7w
|
|
| [G]enerate user token
| [R]equest access
|
We are provided some domain parameters, and are given two interaction options. The first is generating a login token/cookie for a given username.
|
| >> g
|
| Username: Polymero
|
| Token: eyJ1c2VyIjogIlBvbHltZXJvIiwgImFkbWluIjogZmFsc2UsICJzYWx0IjogIjA3YmJiYmU3In0.YVxZTg.CsYaDu6ht-wHcELocU0IobhQh6y9ax0g1xvAnTbOdj33_awtenARnpvt96vt6m3R8dcafvxWUGC-BnVWErX3zg.JWxNszVszNaAZK6AhN_weVRXNAhy4_b329i6rMS6redvD3S3PI7lvqlU2yZZDKmYn7omyHWFSNPiIWTHVYYO6A
|
Awesome, my very own HADIOR token. Now let me try to access whatever service HADIOR provides.
|
| >> r
|
| User token: eyJ1c2VyIjogIlBvbHltZXJvIiwgImFkbWluIjogZmFsc2UsICJzYWx0IjogIjA3YmJiYmU3In0.YVxZTg.CsYaDu6ht-wHcELocU0IobhQh6y9ax0g1xvAnTbOdj33_awtenARnpvt96vt6m3R8dcafvxWUGC-BnVWErX3zg.JWxNszVszNaAZK6AhN_weVRXNAhy4_b329i6rMS6redvD3S3PI7lvqlU2yZZDKmYn7omyHWFSNPiIWTHVYYO6A
|
|
| WELCOME user Polymero.
|
| There are no new messages for you.
|
|
| Press enter to log out...
|
Okay, that is not as exciting as I was hoping for… That means it is time to dive into the source code.
class HADIOR:
""" HADIOR will hold the DOOR. """
def __init__(self, bits=512):
# Generate *field with large prime order
self.q = 0
while not self.q:
self.p = getPrime(bits)
for k in range(2,128+1):
if (self.p-1) % k == 0 and isPrime((self.p-1)//k):
self.q = (self.p-1) // k
self.g = pow(2,k,self.p)
# Generate keys
self.sk = randbelow(self.q)
self.pk = pow(self.g, self.sk, self.p)
Both the key generation above and the signature scheme below seem to indicate standard DSA practices, with a single exception. Upon calculating the ‘s’-part of the ‘(r,s)’ signature, they raise it to some power ‘d’ over the finite field. This exponent turns out to be the sum of ‘1’ bits of the XOR product between the signed message and the private key! In fact, this operation is more colloquially known as the Hamming distance!
# Signatures
def d(self, x):
if type(x) == bytes:
x = int.from_bytes(x,'big')
x %= self.p
return sum([int(i) for i in list('{:0512b}'.format(x ^ self.sk))])
def h(self, x):
if type(x) == int:
x = x.to_bytes((x.bit_length()+7)//8,'big')
return int.from_bytes(sha256(x).digest(),'big')
def sign(self, m):
k = randbelow(self.q)
r = pow(self.g,k,self.p) % self.q
s = pow( inverse(k,self.q) * (self.h(m) + self.sk * r), self.d(m), self.q)
return r,s
def verify(self, m, r, s):
h = self.h(m)
d = self.d(m)
if d % 2:
s = pow(s, inverse(d, self.q-1), self.q)
u = inverse(s, self.q)
v = ( h * u ) % self.q
w = ( r * u ) % self.q
return r == ( ( pow(self.g,v,self.p) * pow(self.pk,w,self.p) ) % self.p ) % self.q
else:
lst = []
for si in [modular_sqrt(s, self.q), (-modular_sqrt(s, self.q))%self.q]:
sj = pow(si, inverse(d, self.q-1), self.q)
u = inverse(sj, self.q)
v = ( h * u ) % self.q
w = ( r * u ) % self.q
lst += [r == ( ( pow(self.g,v,self.p) * pow(self.pk,w,self.p) ) % self.p ) % self.q]
return any(lst)
The actual cookies are parsed using the following two functions, where bake() creates and signs the cookies, and inspect() reads and validates the cookies.
# Cookies!
def bake(self, username, admin=False):
while True:
salt = os.urandom(4).hex()
data = json.dumps({'user' : username, 'admin' : admin, 'salt' : salt}).encode()
db64 = urlsafe_b64encode(data).rstrip(b'=')
tb64 = urlsafe_b64encode(int(time.time()).to_bytes(4,'big')).rstrip(b'=')
cb64 = db64 + b'.' + tb64
r, s = self.sign(cb64)
if self.verify(cb64, r, s):
return cb64.decode() + '.' + self.tokenify([r, s])
def inspect(self, cookie):
data, t, r, s = cookie.split('.')
r = int.from_bytes(urlsafe_b64decode(r + '==='),'big')
s = int.from_bytes(urlsafe_b64decode(s + '==='),'big')
if not self.verify((data + '.' + t).encode(), r, s):
return 'INSPECT ERROR -- Invalid cookie.'
try:
data = json.loads(urlsafe_b64decode(data + '===').decode())
except:
return 'INSPECT ERROR -- Broken cookie.'
return data
All in all, we have found the following key observations.
- The server uses login tokens/cookies with a DSA-like signature scheme.
- The DSA scheme is altered by raising ‘s’ by the Hamming distance between the plaintext signature and the private key.
- We are allowed to generate valid non-admin cookies for arbitrary usernames.
Let’s see if we can turn this cookie bakery into a Hamming distance oracle! Wait a second… could that be where the name HADIOR comes from?!?
Unintended Shortcut
Soooo, turns out I forgot to check for any trivial input in the verify() function. Yikes! This means that simply using the trivial signature of $(r,s) = (1,0)$ one could verify any arbitrary message. All three solves during the CTF were done using this shortcut. Nice catch!
Intended Exploitation
In order to break this cheeky Hamming distance oracle, our approach will consist of the following steps.
- Farm a large amount of generated valid cookies with varying-length usernames. I used 1000 cookies for better statistics, but fewer might work as well.
- Recover the public key assuming average Hamming distances.
- Recover the real Hamming distances using verification with the recovered public key.
- Recover the private key using known plaintexts and recovered Hamming distances.
- Forge our own admin cookie using the recovered private key!
Step 1 - Cookie Farming
Make sure to use varying-length usernames for the best effect!
Domain parameters BA.g8DwfOcIJRns9e7RRwuNNOtdZatj0sakkbYp-sBm6GTXLQcmwh1OSUw6GEpPhHeRkgSyG_PnEdhRD8WrsxUcow
eyJ1c2VyIjogWyJWIiwgIk8iXSwgImFkbWluIjogZmFsc2UsICJzYWx0IjogIjBkMzY2ZGYxIn0.YcMHxg.LK-1-nzic5MxAfwrdtQU0m6vjv0FjUvqiq_EHGEld9yArgDNWe9Pt3QS04q_q5oVhPemApVlFDg40ldT212XpA.FpaPoXNkb4PgMOsbPRkGHlSZvKUZQckawbCJ8xaoMahjQhCs9NI9HVfC5s0bsu3jiogSxSE3muiuLG74Esv42w
eyJ1c2VyIjogWyI5IiwgInciLCAibSJdLCAiYWRtaW4iOiBmYWxzZSwgInNhbHQiOiAiMTk5YTNjMzYifQ.YcMHxg.FtswN2gY5_LauBmYRAAQE58vnlAtyWhTRZWF0AG7yBAkfnhJ0QakM9uaX1Gpz1zSX0PUQddct03im_vOHYNqkg.Aw2VGI4gD_i5yi-NFmB9JMjcjQwvKx0WfF2WVCmGQW11LyZYZLr0hYE-Yoge-u3p74zrQfYtG4j1rFPHzcQF7Q
eyJ1c2VyIjogWyJGIiwgIm0iXSwgImFkbWluIjogZmFsc2UsICJzYWx0IjogIjIwMzU1M2JjIn0.YcMHxg.Hv9m0kd9V8eCxVqZlBym8WeR8A7UmSvXozhzP2YVIf7At5_52u9co8-VtsTRiLqgmNSUiW4O3fagTZTCgp-oTA.PqxO3rA6y8woNW2KWdjCf8YaNqXbU_ptFDM7d3jmckRId6uqNIflR9w5Llvy2mD_ASOXPuA9yFnXWHi_U17hNw
eyJ1c2VyIjogWyJXIiwgIm4iLCAiVSJdLCAiYWRtaW4iOiBmYWxzZSwgInNhbHQiOiAiYjA1MjNkZTkifQ.YcMHxg.FBcXufqCOk6p3irLDumSxNhJHJGKLr-YuiP81kRExvjh31eyWHXNF2lENH8PZqA2GK2cgWk7qkH9-Sl_V-ACuA.C8uwpmcpc5R4Ab7FSg_pn017Fq_jSypi-zHR62Wfs_UUCdkFAWWd3-PCNvjnJViUYLJylIdG9RNKAG4a61nsYQ
eyJ1c2VyIjogWyJVIiwgIjIiLCAiWSIsICJXIiwgInoiXSwgImFkbWluIjogZmFsc2UsICJzYWx0IjogIjJhMzY5ZjNjIn0.YcMHxg.FXkNJVhrJnbsAyhY3gCBsA2KGA5xoy2ONRiwrjQOOuvEK6_j9aDdny_miYclAQ9EJW_gCXfEftx3CKWiTbQbVQ.Pd3AHoPK3M7twHghttg0LxPLsth7zK8gTln_bZHnzD_xcHxbdZaFcaSxV2te0FkWNbW6iiRrm13lUbkDS-lbXQ
eyJ1c2VyIjogWyJnIl0sICJhZG1pbiI6IGZhbHNlLCAic2FsdCI6ICIxNjJkNDA5YiJ9.YcMHxg.PTvYVTdWaAWxdAVjbilSL6APZHI3SgLzAJvHLjwiMt_Z96alw_HuhB7K4caCOwcenCgtRw47dEWxwTEnLLZ8HQ.DeRzO7RBZ2r7MF5auj1wgPO3iYZlQpn3Enltyu_TK4mGBAzXEYx6OWvaStfyykUYGjeYJIDsRbUNFEBlXfWrGg
eyJ1c2VyIjogWyJRIiwgInkiLCAiQSJdLCAiYWRtaW4iOiBmYWxzZSwgInNhbHQiOiAiMzUzNTlkNGUifQ.YcMHxg.CPhvvPXBxTnSWxpCOGQCiAoD9bDcLqKyN-JieSbeDOBjvuGboTxeSmYn4LwtVcH3F2fJQjtwZWbU5_0qOjvnng.IQQ9XKPJ3NgfBPG484UHoZ6j0A7bIFZteOdd9kjRFbPAi-NTTeNHhIqfnRMwQZjb2Q2TtZNVNum-VMHBasr8Pg
eyJ1c2VyIjogWyJ3IiwgImsiLCAiSiIsICJkIiwgImciLCAiYSIsICJnIiwgIlEiXSwgImFkbWluIjogZmFsc2UsICJzYWx0IjogImUzZTA4NDg3In0.YcMHxg.A6AHNbEXhJuuEtHMq0RPEM6KXFe7l3_KkKoy1YKkM_YSVe6PYV4HWxHDOX9TDVnH8IfNN2Zw2yTAOBgTIx-IEA.JJpe1ZB5awlzgad-Ukrlh_zfGoV4grCKIWtMcdb3lAzZcA6sTFe6a2M7CqnkKie8Rl5QUvHufHU_6cZTV3sbjA
eyJ1c2VyIjogWyJWIiwgInciLCAiSSIsICJFIl0sICJhZG1pbiI6IGZhbHNlLCAic2FsdCI6ICIxZmE4YWViZCJ9.YcMHxg.FHYPSsBS1kcUsEr5Nhx6Jn3_RUMbw4v65hrEwWDl4dKPv7Q7618s-DDxV_egxFcnd9MCOb6WsxR405oXJ8FWFA.LH9WPJ4U3_EwAwX2g3TIZ5HkPg_dMl3VkLeShyZ9XBwyBwypNrGcwqMsu6FrjzKGfE6tEfsJgYn2j3uNyNWWjg
eyJ1c2VyIjogWyI4IiwgIkwiXSwgImFkbWluIjogZmFsc2UsICJzYWx0IjogIjI5OTU1MjdlIn0.YcMHxg.KfqzmWRUUPoVLf5pW4jepKSpEqupcHMtBwSZf9-XyNlqjkFUKVTykKwmgsH4gs1ImFmONj8Gy_BPxm6-cHoh8A.Ez65qH8RuYf-Q_9DY_zVOaMZCDxT-ufquH9looP27Tfw6ORAxy_e9pghjJKhBRezPjs1KUqXDUOGbYOY1CutOQ
Step 2 - Recover Public Key
By looping through some assumed Hamming distances we can potentially recover the public key by dissecting the signature and applying it to the verification equation.
#!/usr/bin/env python3
#
# Polymero
#
# Imports
import base64, json, hashlib
import numpy as np
from Crypto.Util.number import inverse
def H(x):
if type(x) == int:
x = x.to_bytes((x.bit_length()+7)//8,'big')
return int.from_bytes(hashlib.sha256(x).digest(),'big')
# Data import
with open('cookies.txt','r') as f:
data = f.read().split('\n')[2:-1]
f.close()
hadior = data[0]
cookies = data[1:]
print(hadior)
print(len(cookies), len('.'.join(cookies[0].split('.')[:2])))
print()
G, P = [int.from_bytes(base64.urlsafe_b64decode(i+'==='),'big') for i in hadior.split(' ')[2].split('.')]
K = G.bit_length()-1
Q = (P-1) // K
print('P =',P)
print('Q =',Q)
print('K =',K)
print('G =',G)
for k in range(256-10-1,256+10+1,2):
print('\nTrying Hamming distance of', k)
recovered_pks = []
for n,cookie in enumerate(cookies):
if n % (len(cookies)//100) == 0:
print((n*100)//len(cookies),'%!',end='\r',flush=True)
parts = cookie.split('.')
M = parts[0] + '.' + parts[1]
R = int.from_bytes(base64.urlsafe_b64decode(parts[2]+'==='),'big')
S = int.from_bytes(base64.urlsafe_b64decode(parts[3]+'==='),'big')
# Assume a Hamming distance
S = pow(S, inverse(k, Q-1), Q)
u = inverse(S, Q)
v = ( H(int.from_bytes(M.encode(),'big')) * u ) % Q
w = ( R * u ) % Q
mg = inverse(w, P-1)
pk = pow( R * inverse( pow(G, v, P), P ), mg, P )
recovered_pks += [pk]
unis, cnts = np.unique(recovered_pks, return_counts=True)
inds = [i for i in range(len(cnts)) if cnts[i] != 1]
if inds:
for i in inds:
print(cnts[i], unis[i])
else:
print('No public keys founds')
Domain parameters BA.g8DwfOcIJRns9e7RRwuNNOtdZatj0sakkbYp-sBm6GTXLQcmwh1OSUw6GEpPhHeRkgSyG_PnEdhRD8WrsxUcow
1000 82
P = 6900499591590096985463962914666023365087076830846525607369294811386863058113161060020712736008157205901426456930134396329894663935982393514727101645003939
Q = 3450249795795048492731981457333011682543538415423262803684647405693431529056580530010356368004078602950713228465067198164947331967991196757363550822501969
K = 2
G = 4
Trying Hamming distance of 245
7 815603267909877378449906145761747578363446184194830084913713200622632030460623912327197618134717194799903374972945113082629916082980771867210561143644520
8 908278712949839694180158283926746709809100963686253509119795658585994266668985779433871630337991451864055932340361275622802094913802138536114103782017267
Trying Hamming distance of 247
5 815603267909877378449906145761747578363446184194830084913713200622632030460623912327197618134717194799903374972945113082629916082980771867210561143644520
10 908278712949839694180158283926746709809100963686253509119795658585994266668985779433871630337991451864055932340361275622802094913802138536114103782017267
Trying Hamming distance of 249
5 815603267909877378449906145761747578363446184194830084913713200622632030460623912327197618134717194799903374972945113082629916082980771867210561143644520
6 908278712949839694180158283926746709809100963686253509119795658585994266668985779433871630337991451864055932340361275622802094913802138536114103782017267
Trying Hamming distance of 251
18 815603267909877378449906145761747578363446184194830084913713200622632030460623912327197618134717194799903374972945113082629916082980771867210561143644520
11 908278712949839694180158283926746709809100963686253509119795658585994266668985779433871630337991451864055932340361275622802094913802138536114103782017267
Trying Hamming distance of 253
11 815603267909877378449906145761747578363446184194830084913713200622632030460623912327197618134717194799903374972945113082629916082980771867210561143644520
13 908278712949839694180158283926746709809100963686253509119795658585994266668985779433871630337991451864055932340361275622802094913802138536114103782017267
Trying Hamming distance of 255
10 815603267909877378449906145761747578363446184194830084913713200622632030460623912327197618134717194799903374972945113082629916082980771867210561143644520
15 908278712949839694180158283926746709809100963686253509119795658585994266668985779433871630337991451864055932340361275622802094913802138536114103782017267
Trying Hamming distance of 257
11 815603267909877378449906145761747578363446184194830084913713200622632030460623912327197618134717194799903374972945113082629916082980771867210561143644520
11 908278712949839694180158283926746709809100963686253509119795658585994266668985779433871630337991451864055932340361275622802094913802138536114103782017267
Trying Hamming distance of 259
11 815603267909877378449906145761747578363446184194830084913713200622632030460623912327197618134717194799903374972945113082629916082980771867210561143644520
11 908278712949839694180158283926746709809100963686253509119795658585994266668985779433871630337991451864055932340361275622802094913802138536114103782017267
Trying Hamming distance of 261
12 815603267909877378449906145761747578363446184194830084913713200622632030460623912327197618134717194799903374972945113082629916082980771867210561143644520
11 908278712949839694180158283926746709809100963686253509119795658585994266668985779433871630337991451864055932340361275622802094913802138536114103782017267
Trying Hamming distance of 263
5 815603267909877378449906145761747578363446184194830084913713200622632030460623912327197618134717194799903374972945113082629916082980771867210561143644520
8 908278712949839694180158283926746709809100963686253509119795658585994266668985779433871630337991451864055932340361275622802094913802138536114103782017267
Trying Hamming distance of 265
6 815603267909877378449906145761747578363446184194830084913713200622632030460623912327197618134717194799903374972945113082629916082980771867210561143644520
9 908278712949839694180158283926746709809100963686253509119795658585994266668985779433871630337991451864055932340361275622802094913802138536114103782017267
For this specific run, it seems that
908278712949839694180158283926746709809100963686253509119795658585994266668985779433871630337991451864055932340361275622802094913802138536114103782017267
is most likely to be the public key of the HADIOR service.
Step 3 - Recover Hamming Distances
With the public key in our possession, we can recover the exact Hamming distance of each signed cookie by simply checking for which value it succesfully verifies.
#!/usr/bin/env python3
#
# Polymero
#
# Imports
import base64, json, hashlib
import numpy as np
from Crypto.Util.number import inverse
def H(x):
if type(x) == int:
x = x.to_bytes((x.bit_length()+7)//8,'big')
return int.from_bytes(hashlib.sha256(x).digest(),'big')
def legendre_symbol(a, p):
ls = pow(a, (p - 1) // 2, p)
return -1 if ls == p - 1 else ls
def modular_sqrt(a, p):
if legendre_symbol(a, p) != 1:
return 0
elif a == 0:
return 0
elif p == 2:
return 0
elif p % 4 == 3:
return pow(a, (p + 1) // 4, p)
s = p - 1
e = 0
while s % 2 == 0:
s //= 2
e += 1
n = 2
while legendre_symbol(n, p) != -1:
n += 1
x = pow(a, (s + 1) // 2, p)
b = pow(a, s, p)
g = pow(n, s, p)
r = e
while True:
t = b
m = 0
for m in range(r):
if t == 1:
break
t = pow(t, 2, p)
if m == 0:
return x
gs = pow(g, 2 ** (r - m - 1), p)
g = (gs * gs) % p
x = (x * gs) % p
b = (b * g) % p
r = m
# Data import
with open('cookies.txt','rb') as f:
data = f.read().split(b'\n')[2:-1]
f.close()
hadior = data[0]
cookies = data[1:]
print(hadior)
print(len(cookies), len(b'.'.join(cookies[0].split(b'.')[:2])))
print()
G, P = [int.from_bytes(base64.urlsafe_b64decode(i+b'==='),'big') for i in hadior.split(b' ')[2].split(b'.')]
K = G.bit_length()-1
Q = (P-1) // K
print('P =',P)
print('Q =',Q)
print('K =',K)
print('G =',G)
PK = int(input('PK: '))
def verify(m, r, s, d):
h = H(m)
if d % 2:
s = pow(s, inverse(d, Q-1), Q)
u = inverse(s, Q)
v = ( h * u ) % Q
w = ( r * u ) % Q
return r == ( ( pow(G,v,P) * pow(PK,w,P) ) % P ) % Q
else:
lst = []
for si in [modular_sqrt(s, Q), (-modular_sqrt(s, Q))%Q]:
sj = pow(si, inverse(d, Q-1), Q)
u = inverse(sj, Q)
v = ( h * u ) % Q
w = ( r * u ) % Q
lst += [r == ( ( pow(G,v,P) * pow(PK,w,P) ) % P ) % Q]
return any(lst)
hamdists = []
NUM = 512*2
for k,cookie in enumerate(cookies[:NUM]):
print(k, end='\r', flush=True)
parts = cookie.split(b'.')
M = parts[0] + b'.' + parts[1]
R = int.from_bytes(base64.urlsafe_b64decode(parts[2]+b'==='),'big')
S = int.from_bytes(base64.urlsafe_b64decode(parts[3]+b'==='),'big')
for d in range(201,320):
if verify(M, R, S, d):
hamdists += [d]
break
print(len(hamdists) == len(cookies[:NUM]))
print(hamdists)
b'Domain parameters BA.g8DwfOcIJRns9e7RRwuNNOtdZatj0sakkbYp-sBm6GTXLQcmwh1OSUw6GEpPhHeRkgSyG_PnEdhRD8WrsxUcow'
1000 82
P = 6900499591590096985463962914666023365087076830846525607369294811386863058113161060020712736008157205901426456930134396329894663935982393514727101645003939
Q = 3450249795795048492731981457333011682543538415423262803684647405693431529056580530010356368004078602950713228465067198164947331967991196757363550822501969
K = 2
G = 4
PK: 908278712949839694180158283926746709809100963686253509119795658585994266668985779433871630337991451864055932340361275622802094913802138536114103782017267
True
[261, 253, 262, 267, 251, 275, 246, 262, 257, 250, 258, 274, 253, 238, 267, 277, 278, 267, 274, 261, 241, 238, 281, 269, 274, 269, 246, 261, 279, 241, 250, 243, 246, 259, 250, 269, 245, 246, 251, 249, 249, 231, 269, 270, 242, 253, 278, 269, 265, 269, 258, 238, 277, 235, 269, 259, 255, 270, 257, 259, 265, 278, 255, 259, 266, 277, 261, 266, 267, 257, 251, 257, 255, 277, 263, 274, 239, 278, 275, 241, 257, 269, 259, 266, 279, 254, 258, 273, 257, 242, 267, 253, 259, 275, 265, 267, 247, 258, 255, 255, 266, 245, 279, 253, 238, 243, 278, 265, 261, 257, 238, 278, 267, 265, 257, 266, 273, 254, 243, 265, 237, 266, 262, 255, 279, 239, 259, 253, 258, 273, 247, 278, 250, 257, 270, 275, 265, 259, 278, 269, 245, 246, 262, 243, 255, 254, 269, 265, 242, 257, 251, 262, 271, 251, 278, 271, 255, 257, 259, 247, 257, 254, 277, 279, 277, 266, 242, 261, 262, 271, 261, 251, 246, 262, 259, 238, 269, 246, 281, 259, 279, 262, 255, 255, 269, 254, 259, 278, 277, 242, 266, 275, 281, 250, 242, 275, 270, 255, 261, 246, 255, 269, 267, 257, 250, 267, 245, 255, 253, 279, 250, 271, 243, 261, 269, 253, 275, 251, 250, 274, 245, 237, 249, 278, 243, 274, 261, 237, 243, 245, 263, 273, 246, 262, 266, 253, 261, 266, 253, 281, 261, 245, 233, 277, 249, 250, 277, 251, 259, 273, 251, 267, 263, 271, 257, 253, 254, 281, 247, 282, 251, 253, 261, 257, 269, 253, 235, 254, 267, 234, 235, 263, 253, 238, 245, 247, 261, 267, 250, 265, 257, 262, 246, 285, 261, 282, 241, 269, 250, 251, 253, 241, 273, 261, 251, 271, 285, 278, 262, 229, 279, 262, 269, 267, 283, 275, 255, 247, 286, 271, 265, 239, 243, 262, 247, 258, 258, 249, 269, 269, 279, 257, 225, 251, 289, 247, 278, 287, 233, 258, 253, 273, 253, 281, 266, 253, 249, 241, 267, 246, 245, 253, 279, 245, 259, 262, 253, 279, 241, 275, 266, 277, 267, 257, 249, 253, 263, 251, 257, 251, 275, 218, 273, 255, 273, 275, 257, 262, 277, 257, 273, 254, 251, 274, 251, 270, 251, 249, 263, 262, 238, 250, 257, 251, 246, 241, 263, 275, 242, 255, 281, 246, 271, 259, 277, 270, 263, 261, 250, 241, 281, 246, 251, 243, 266, 243, 250, 251, 235, 265, 261, 253, 247, 245, 255, 265, 254, 273, 255, 255, 273, 262, 249, 262, 270, 254, 258, 271, 265, 255, 279, 265, 262, 263, 249, 247, 229, 258, 235, 255, 270, 247, 254, 231, 253, 259, 255, 277, 250, 251, 258, 247, 242, 247, 255, 250, 243, 262, 230, 251, 267, 254, 270, 278, 245, 277, 254, 273, 258, 251, 255, 259, 237, 238, 269, 269, 249, 274, 273, 278, 254, 247, 243, 269, 246, 277, 250, 267, 267, 258, 237, 263, 274, 283, 265, 255, 249, 255, 269, 255, 259, 271, 262, 247, 269, 251, 257, 278, 258, 270, 246, 238, 265, 263, 246, 271, 273, 237, 271, 274, 270, 266, 285, 254, 261, 246, 271, 257, 243, 255, 275, 241, 267, 245, 257, 262, 261, 238, 247, 246, 266, 251, 278, 245, 253, 249, 253, 259, 271, 238, 239, 263, 249, 263, 267, 277, 281, 230, 242, 278, 265, 275, 255, 249, 274, 266, 265, 270, 250, 253, 249, 259, 237, 253, 266, 247, 258, 261, 277, 270, 259, 245, 261, 257, 275, 247, 266, 251, 261, 259, 269, 262, 265, 234, 267, 261, 242, 254, 245, 243, 246, 265, 255, 245, 257, 255, 238, 275, 275, 263, 242, 251, 254, 253, 274, 245, 245, 261, 267, 259, 263, 257, 267, 242, 253, 277, 257, 242, 267, 258, 254, 250, 259, 255, 270, 250, 254, 233, 254, 254, 263, 263, 241, 259, 259, 261, 246, 253, 265, 273, 247, 254, 255, 262, 275, 242, 247, 257, 242, 253, 273, 259, 251, 259, 237, 251, 259, 263, 243, 271, 249, 245, 258, 242, 275, 283, 255, 270, 258, 274, 271, 269, 242, 253, 246, 259, 245, 242, 282, 251, 245, 278, 275, 275, 253, 243, 285, 261, 261, 243, 257, 283, 247, 254, 261, 250, 259, 253, 258, 242, 259, 245, 238, 261, 257, 258, 271, 259, 265, 253, 255, 233, 275, 243, 281, 250, 241, 283, 243, 249, 246, 265, 229, 286, 263, 275, 269, 269, 247, 242, 258, 257, 278, 269, 257, 246, 275, 287, 277, 274, 251, 257, 246, 259, 253, 271, 265, 251, 262, 258, 263, 287, 239, 265, 283, 246, 263, 250, 266, 263, 281, 247, 250, 253, 279, 262, 262, 266, 277, 282, 255, 253, 263, 258, 246, 279, 258, 235, 253, 235, 251, 259, 259, 277, 254, 254, 258, 254, 273, 243, 246, 234, 275, 246, 247, 262, 246, 261, 262, 279, 255, 255, 255, 243, 247, 262, 251, 275, 259, 241, 275, 245, 262, 273, 282, 270, 234, 245, 253, 283, 241, 261, 254, 261, 282, 254, 249, 253, 283, 245, 251, 262, 241, 243, 266, 237, 283, 254, 275, 282, 255, 263, 259, 245, 251, 233, 230, 261, 282, 250, 253, 254, 257, 254, 283, 246, 259, 243, 262, 245, 257, 253, 259, 255, 253, 246, 243, 270, 246, 255, 271, 251, 261, 289, 274, 265, 247, 249, 242, 263, 271, 243, 277, 271, 257, 250, 265, 242, 262, 250, 269, 277, 263, 259, 242, 258, 246, 271, 265, 259, 255, 247, 274, 246, 263, 259, 249, 274, 262, 265, 249, 271, 251, 238, 262, 269, 251, 265, 269, 261, 246, 257, 275, 282, 262, 278, 257, 254, 245, 250, 275, 239, 287, 275, 278, 230, 249, 249, 270, 263, 249, 253, 253, 282, 263, 267, 245, 259, 287, 267, 263, 274, 253, 239, 279, 261, 254, 275, 242, 251, 250, 262, 250, 247, 253, 253, 254, 279, 243, 253, 257, 234, 235, 279, 254, 251, 258, 261, 282, 253, 277, 249, 266, 251, 234, 265, 257, 273, 277, 255]
Now that we have found the Hamming distances of each cookie, we can start to recover the private key used by the HADIOR service.
Step 4 - Recover Private Key
In order to recover the private key we can simply set up an augmented matrix containing the ‘x’ values (used in the Hamming distance calculation) and the resulting Hamming distances. If we then apply gaussian elimination (row reduction) we end up with a 512-length vector containing ‘1’s and ‘254’s. I am not 100% as to why (mathematically speaking), but if we turn the ‘1’s into ‘0’s and the ‘254’s into ‘1’s we seem to end up with the private key quite consistently!
#!/usr/bin/env python3
#
# Polymero
#
# Imports
import base64, json, hashlib
import numpy as np
from Crypto.Util.number import inverse
from sage.all import Matrix, Integers
# Data import
with open('cookies.txt','rb') as f:
data = f.read().split(b'\n')[2:-1]
f.close()
hadior = data[0]
cookies = data[1:]
print(hadior)
print(len(cookies), len(b'.'.join(cookies[0].split(b'.')[:2])))
print()
G, P = [int.from_bytes(base64.urlsafe_b64decode(i+b'==='),'big') for i in hadior.split(b' ')[2].split(b'.')]
K = G.bit_length()-1
Q = (P-1) // K
print('P =',P)
print('Q =',Q)
print('K =',K)
print('G =',G)
with open('hadior_pk.txt','r') as f:
PK = int(f.read())
f.close()
with open('hamdists.txt','r') as f:
Hs = [int(i) for i in f.read().split(', ')]
f.close()
cookies = cookies[:len(Hs)]
INTS = [int.from_bytes( b'.'.join(cookie.split(b'.')[:2]), 'big') % P for cookie in cookies]
#print(INTS)
print(max([i.bit_length() for i in INTS]))
BITS = [[int(j) for j in list('{:0512b}'.format(i))] for i in INTS]
DMAT = Matrix(Integers(), Hs).T
QMAT = Matrix(Integers(), BITS)
print(DMAT.T)
print(QMAT.rank())
AUG = QMAT.augment(DMAT)
ECH = AUG.echelon_form()
print(ECH.row(0))
print(ECH.column(-1))
REC_SK = int(''.join(['0' if i == 1 else '1' for i in ECH.column(-1).list()[:512]]),2)
print('{:0512b}'.format(REC_SK))
print(REC_SK)
b'Domain parameters BA.g8DwfOcIJRns9e7RRwuNNOtdZatj0sakkbYp-sBm6GTXLQcmwh1OSUw6GEpPhHeRkgSyG_PnEdhRD8WrsxUcow'
1000 82
P = 6900499591590096985463962914666023365087076830846525607369294811386863058113161060020712736008157205901426456930134396329894663935982393514727101645003939
Q = 3450249795795048492731981457333011682543538415423262803684647405693431529056580530010356368004078602950713228465067198164947331967991196757363550822501969
K = 2
G = 4
512
[261 253 262 267 251 275 246 262 257 250 258 274 253 238 267 277 278 267 274 261 241 238 281 269 274 269 246 261 279 241 250 243 246 259 250 269 245 246 251 249 249 231 269 270 242 253 278 269 265 269 258 238 277 235 269 259 255 270 257 259 265 278 255 259 266 277 261 266 267 257 251 257 255 277 263 274 239 278 275 241 257 269 259 266 279 254 258 273 257 242 267 253 259 275 265 267 247 258 255 255 266 245 279 253 238 243 278 265 261 257 238 278 267 265 257 266 273 254 243 265 237 266 262 255 279 239 259 253 258 273 247 278 250 257 270 275 265 259 278 269 245 246 262 243 255 254 269 265 242 257 251 262 271 251 278 271 255 257 259 247 257 254 277 279 277 266 242 261 262 271 261 251 246 262 259 238 269 246 281 259 279 262 255 255 269 254 259 278 277 242 266 275 281 250 242 275 270 255 261 246 255 269 267 257 250 267 245 255 253 279 250 271 243 261 269 253 275 251 250 274 245 237 249 278 243 274 261 237 243 245 263 273 246 262 266 253 261 266 253 281 261 245 233 277 249 250 277 251 259 273 251 267 263 271 257 253 254 281 247 282 251 253 261 257 269 253 235 254 267 234 235 263 253 238 245 247 261 267 250 265 257 262 246 285 261 282 241 269 250 251 253 241 273 261 251 271 285 278 262 229 279 262 269 267 283 275 255 247 286 271 265 239 243 262 247 258 258 249 269 269 279 257 225 251 289 247 278 287 233 258 253 273 253 281 266 253 249 241 267 246 245 253 279 245 259 262 253 279 241 275 266 277 267 257 249 253 263 251 257 251 275 218 273 255 273 275 257 262 277 257 273 254 251 274 251 270 251 249 263 262 238 250 257 251 246 241 263 275 242 255 281 246 271 259 277 270 263 261 250 241 281 246 251 243 266 243 250 251 235 265 261 253 247 245 255 265 254 273 255 255 273 262 249 262 270 254 258 271 265 255 279 265 262 263 249 247 229 258 235 255 270 247 254 231 253 259 255 277 250 251 258 247 242 247 255 250 243 262 230 251 267 254 270 278 245 277 254 273 258 251 255 259 237 238 269 269 249 274 273 278 254 247 243 269 246 277 250 267 267 258 237 263 274 283 265 255 249 255 269 255 259 271 262 247 269 251 257 278 258 270 246 238 265 263 246 271 273 237 271 274 270 266 285 254 261 246 271 257 243 255 275 241 267 245 257 262 261 238 247 246 266 251 278 245 253 249 253 259 271 238 239 263 249 263 267 277 281 230 242 278 265 275 255 249 274 266 265 270 250 253 249 259 237 253 266 247 258 261 277 270 259 245 261 257 275 247 266 251 261 259 269 262 265 234 267 261 242 254 245 243 246 265 255 245 257 255 238 275 275 263 242 251 254 253 274 245 245 261 267 259 263 257 267 242 253 277 257 242 267 258 254 250 259 255 270 250 254 233 254 254 263 263 241 259 259 261 246 253 265 273 247 254 255 262 275 242 247 257 242 253 273 259 251 259 237 251 259 263 243 271 249 245 258 242 275 283 255 270 258 274 271 269 242 253 246 259 245 242 282 251 245 278 275 275 253 243 285 261 261 243 257 283 247 254 261 250 259 253 258 242 259 245 238 261 257 258 271 259 265 253 255 233 275 243 281 250 241 283 243 249 246 265 229 286 263 275 269 269 247 242 258 257 278 269 257 246 275 287 277 274 251 257 246 259 253 271 265 251 262 258 263 287 239 265 283 246 263 250 266 263 281 247 250 253 279 262 262 266 277 282 255 253 263 258 246 279 258 235 253 235 251 259 259 277 254 254 258 254 273 243 246 234 275 246 247 262 246 261 262 279 255 255 255 243 247 262 251 275 259 241 275 245 262 273 282 270 234 245 253 283 241 261 254 261 282 254 249 253 283 245 251 262 241 243 266 237 283 254 275 282 255 263 259 245 251 233 230 261 282 250 253 254 257 254 283 246 259 243 262 245 257 253 259 255 253 246 243 270 246 255 271 251 261 289 274 265 247 249 242 263 271 243 277 271 257 250 265 242 262 250 269 277 263 259 242 258 246 271 265 259 255 247 274 246 263 259 249 274 262 265 249 271 251 238 262 269 251 265 269 261 246 257 275 282 262 278 257 254 245 250 275 239 287 275 278 230 249 249 270 263 249 253 253 282 263 267 245 259 287 267 263 274 253 239 279 261 254 275 242 251 250 262 250 247 253 253 254 279 243 253 257 234 235 279 254 251 258 261 282 253 277 249 266 251 234 265 257 273 277 255]
512
(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
(1, 1, 254, 254, 1, 1, 254, 254, 254, 254, 1, 254, 1, 254, 1, 254, 254, 1, 254, 254, 1, 254, 254, 1, 1, 254, 254, 254, 254, 254, 254, 1, 254, 1, 254, 1, 254, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 254, 254, 1, 1, 254, 1, 1, 254, 1, 1, 254, 254, 1, 1, 1, 1, 1, 1, 1, 254, 1, 1, 254, 254, 254, 254, 254, 254, 1, 1, 1, 254, 1, 1, 1, 254, 1, 1, 1, 1, 1, 254, 254, 254, 254, 254, 1, 1, 1, 254, 254, 1, 1, 254, 254, 254, 1, 254, 254, 254, 1, 1, 254, 1, 254, 254, 254, 254, 254, 254, 1, 254, 254, 254, 254, 1, 254, 1, 1, 1, 254, 254, 1, 1, 1, 1, 1, 254, 254, 254, 254, 254, 254, 254, 1, 1, 1, 1, 254, 1, 254, 1, 254, 1, 254, 1, 254, 254, 1, 1, 1, 254, 1, 254, 254, 254, 254, 1, 254, 254, 254, 254, 1, 1, 254, 1, 1, 254, 1, 1, 254, 1, 254, 254, 1, 1, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 1, 1, 1, 254, 1, 254, 1, 1, 1, 254, 1, 254, 1, 1, 254, 1, 254, 254, 254, 1, 1, 254, 254, 1, 254, 1, 254, 1, 254, 1, 254, 1, 254, 254, 1, 254, 254, 1, 254, 1, 254, 254, 254, 254, 1, 1, 1, 254, 1, 1, 1, 1, 254, 254, 1, 254, 1, 254, 1, 1, 1, 254, 254, 1, 1, 1, 254, 1, 1, 254, 1, 254, 254, 1, 1, 1, 254, 1, 254, 1, 1, 1, 1, 254, 254, 254, 254, 1, 254, 254, 254, 1, 1, 254, 254, 1, 1, 254, 1, 1, 254, 1, 1, 254, 1, 1, 254, 1, 254, 1, 254, 254, 254, 1, 254, 1, 254, 1, 1, 1, 1, 254, 254, 1, 254, 254, 1, 254, 254, 1, 254, 1, 1, 254, 254, 1, 254, 1, 1, 254, 254, 254, 1, 1, 254, 1, 1, 254, 1, 254, 254, 254, 254, 254, 1, 1, 254, 254, 254, 1, 1, 1, 254, 254, 1, 254, 254, 1, 1, 1, 1, 1, 1, 254, 1, 1, 1, 254, 254, 1, 1, 1, 254, 1, 254, 254, 1, 1, 254, 1, 1, 254, 1, 1, 254, 254, 1, 1, 1, 254, 254, 254, 1, 254, 254, 1, 1, 1, 254, 254, 254, 1, 1, 1, 254, 1, 254, 1, 254, 254, 254, 1, 254, 1, 1, 1, 254, 1, 1, 1, 1, 254, 254, 254, 254, 254, 1, 254, 254, 254, 254, 1, 1, 1, 1, 254, 1, 254, 1, 254, 254, 1, 1, 254, 254, 254, 1, 1, 1, 1, 254, 254, 254, 254, 1, 1, 1, 254, 254, 1, 1, 254, 254, 254, 254, 1, 254, 1, 254, 1, 1, 1, 254, 1, 254, 1, 1, 1, 1, 254, 254, 1, 1, 254, 1, 1, 254, 254, 254, 254, 1, 254, 254, 254, 1, 1, 1, 1, 254, 1, 1, 1, 254, 254, 254, 1, 254, 1, 254, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
00110011110101011011011001111110101010000000000110010010011000000010011111100010001000001111100011001110111001011111101111010001100000111111100001010101011000101111011110010010010110011111111110001010001010010111001101010101011011010111100010000110101000110001001011000101000011110111001100100100100101011101010000110110110100110100111001001011111001110001101100000010001100010110010010011000111011000111000101011101000100001111101111000010101100111000011110001100111101010001010000110010011110111000010001110101
2714809592408365173561798468377108576556134124467482620133310294822610721051485049792433567888185309833419530709674617232790797270508135778250760826618997
Private key secured 
!
Step 5
Having recovered all of the Server’s parameters, we can easily forge a signature directly using the server code. It will tell us we have a single unread message, the FLAG!
Ta-da!
flag{th3s3_c00k13s_m4y_c0nt41n_tr4c3s_0f_h4m_SEFESU9S}
Is this the most elegant solution? No. Is this the fastest solution? No. If you have found another way to exploit HADIOR, please let me know ~ ! ^w^
Note that due to the many involved steps and altered algorithms/implementation, there might be unknown solution shortcuts present.
Thanks for reading! <3
~ Polymero