For the past five days, I have been competing solo in the Cyber Apocalypse CTF 2023. During this time, I was able to solve all of the pwn challenges and 10 out of the 11 crypto challenges. In this writeup, I will be sharing my solutions for some of the crypto challenges that I solved. If you’re interested in reading about the pwn challenges, check out my other post.
Crypto
Multipage Recyclings
Description
As your investigation progressed, a clue led you to a local bar where you met an undercover agent with valuable information. He spoke of a famous astronomy scientist who lived in the area and extensively studied the relic. The scientist wrote a book containing valuable insights on the relic’s location, but encrypted it before he disappeared to keep it safe from malicious intent. The old man disclosed that the book was hidden in the scientist’s house and revealed two phrases that the scientist rambled about before vanishing.
Initial Analysis
For this challenge, we were given two file called source.py and output.txt. Let’s take a look at the source.py first.
Based on the given source code, the main logic for the code is as follows:
Concatenate the flag with itself 4 times.
Pad the flag so that it can be split into multiple 16-bytes block
Encrypt it with AES
Provide some leaks
Let’s try to understand the encrypt method first. If you read it, it is actually an implementation of AES-CFB.
So, now we know the AES type, let’s take a look at what the leak that the source generates is. It turns out that the given leak was two decrypted blocks that exist in the ciphertext. Therefore, given the leaks, our target is to somehow recover our flag.
Solution
Please refer to the image above. As you can see, to decrypt the plaintext, what AES-CFB does is actually like this,
$$
p_i = C(c_{i-1}) \oplus c_{i}
$$
where $C$ is the block cipher encryption, $c$ is the ciphertext, and $p$ is the plaintext. Notice that the leak is actually the $C(c_{i-1})$ result, where $i$ is random. Additionally, the given leak is always two consecutive blocks, and if we have the $C(c_{i-1})$ and $C(c_{i})$, we can actually get the plaintext block for at least two blocks. After testing to XOR the blocks one by one, I found that the leak is $C(c_3)$ and $C(c_4)$. By XORing them with $c_4$ and $c_5$, respectively, we were able to obtain the flag.
As you deciphered the Matrix, you discovered that the astronomy scientist had observed that certain stars were not real. He had created two 5x5 matrices with values based on the time the stars were bright, but after some time, the stars stopped emitting light. Nonetheless, he had managed to capture every matrix until then and created an algorithm that simulated their generation. However, he could not understand what was hidden behind them as he was missing something. He believed that if he could understand the stars, he would be able to locate the secret tombs where the relic was hidden.
Initial Analysis
For this challenge, we were given a file called server.py. Let’s check that.
fromsage.all_cmdlineimport*# from utils import ascii_printimportosFLAG=b"HTB{????????????????????}"assertlen(FLAG)==25classBook:def__init__(self):self.size=5self.prime=Nonedefparse(self,pt:bytes):pt=[bforbinpt]returnmatrix(GF(self.prime),self.size,self.size,pt)defgenerate(self):key=os.urandom(self.size**2)returnself.parse(key)defrotate(self):self.prime=random_prime(2**6,False,2**4)defencrypt(self,message:bytes):self.rotate()key=self.generate()message=self.parse(message)ciphertext=message*keyreturnciphertext,keydefmenu():print("Options:\n")print("[L]ook at page")print("[T]urn page")print("[C]heat\n")option=input("> ")returnoptiondefmain():book=Book()ciphertext,key=book.encrypt(FLAG)page_number=1whileTrue:option=menu()ifoption=="L":# ascii_print(ciphertext, key, page_number)print(ciphertext,key,page_number)elifoption=="T":ciphertext,key=book.encrypt(FLAG)page_number+=2print()elifoption=="C":print(f"\n{list(ciphertext)}\n{list(key)}\n")else:print("\nInvalid option!\n")if__name__=="__main__":try:main()exceptExceptionase:print(f"An error occurred: {e}")
Reading through the code, there are three menus that we can interact with:
L, which prints the ciphertext, key, and page_number
T, which encrypts the FLAG and stores the encryption result to ciphertext and key
C, which is the same as L, but prints it as a list format.
The encryption scheme is as follows:
Parse the FLAG to a matrix 5x5 under GF(prime).
prime is randomized from range ($2^4$ - $2^6$)
Generate random key and parse it to matrix 5x5 under GF(P).
Do matrix multiplication between parsed FLAG and the parsed key.
Return the encryption result and the key itself.
Note that the server doesn’t return the value of prime. Therefore, the task for this challenge is to recover the flag given an encrypted flag and a key.
Solution
Because we know the key value, we actually can just simply multiple the encrypted flag with the inverse of key. Take a look on the below equations,
$$
\begin{align*}
c = mk \\
mkk^{-1} = ck^{-1} \\
m = ck^{-1}\\
\end{align*}
$$
where $m$ is message, $c$ is encryted message, and $k$ is the key. To do the above equation, we need to know the prime value first. Notice that the range is actually small, so we can actually just bruteforce it. The possible primes that is used in this encryption scheme is actually only [17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]. So, by bruteforcing the prime, we can recover the matrix of the parsed FLAG.
However, there is a problem with this one. Notice that the parsed matrix elements was reduced with modulo of the chosen prime. The prime is small, which means that the parsed matrix of FLAG each element’s value is actually not the original value of the FLAG char. So, we need to think on how to recover this.
The answer is we can use Chinese Remainder Theorem to recover the original FLAG. Notice that if we recover three pairs of ciphertext and key with different prime, after we recover the $m$, we actually can rearrange the value as follows,
where $x_{i,j}$ is the original element of FLAG char on the matrix $m[i][j]$, $m_{1,i,j}, m_{2,i,j}, m_{3,i,j}$ is the messages recovered from the three pairs, and $p_1, p_2, p_3$ is the recovered primes. The above setup can be solved with Chinese Remainder Theorem, where the recovered $x$ will be the original char of the FLAG.
To summarize, what we need to do to solve this challenge:
Recover three reduced messages (in form of matrix) from the three pairs of (ct, key) from the server
For each element in the recovered messages, perform CRT.
frompwnimport*# Based on `self.prime = random_prime(2**6, False, 2**4)`possible_primes=[17,19,23,29,31,37,41,43,47,53,59,61]whileTrue:print(f'Try to bruteforce...')# r = remote(b'159.65.86.238', int(32021))r=process(['python3','server.py'])# Collect 3 pair of cts and keys with hope that all of them are unique.# If not unique, just reconnect.cts=[]keys=[]foriinrange(3):r.sendlineafter(b'> ',b'C')r.recvline()ct=eval(r.recvline().strip())key=eval(r.recvline().strip())cts.append(ct)keys.append(key)r.sendlineafter(b'> ',b'T')# We will bruteforce the possible primesforp0inpossible_primes:forp1inpossible_primes:forp2inpossible_primes:ifp0==p1orp0==p2orp1==p2:continueprimes=[p0,p1,p2]msgs=[]foriinrange(3):try:# Try to calculate msg by doing ct*key^-1mat_ct=Matrix(GF(primes[i]),cts[i])mat_key=Matrix(GF(primes[i]),keys[i])msgs.append(mat_ct*mat_key.inverse())except:# If failed, that means the inverse is failed,# which mean we used the wrong primepassiflen(msgs)<3:# Continue to bruteforce the correct primescontinue'''
Now, we have this equations
x = msgs[0][i][j] mod primes[0]
x = msgs[1][i][j] mod primes[1]
x = msgs[2][i][j] mod primes[2]
Do CRT to retrieve x, which is the character of the flag
'''test_m_arr=[]forchr_idxinrange(25):test_m=[]formsg_idxinrange(len(msgs)):i=chr_idx//5j=chr_idx%5test_m.append(int(msgs[msg_idx][i][j]))test_m_arr.append(test_m)flag=''fortest_mintest_m_arr:flag_char=crt(test_m,primes)flag+=chr(flag_char)if'HTB'inflag:# We found the flagprint(flag)exit()
Flag: HTB{l00k_@t_7h3_st4rs!!!}
Elliptic Labyrinth
Description
As you navigate through the labyrinth inside the tomb, you encounter GPS inaccuracies that make it difficult to determine the correct path to the exit. Can you overcome the technical issues and use your instincts to find your way out of the maze?
Initial Analysis
For this challenge, we were given a file called server.py. The provided code is shown below.
importos,jsonfromhashlibimportsha256fromrandomimportrandintfromCrypto.Util.numberimportgetPrime,long_to_bytesfromCrypto.CipherimportAESfromCrypto.Util.Paddingimportpadfromsage.all_cmdlineimport*# from secret import FLAGFLAG=b'flag{fake_flag}'classECC:def__init__(self,bits):self.p=getPrime(bits)self.a=randint(1,self.p)self.b=randint(1,self.p)defgen_random_point(self):returnEllipticCurve(GF(self.p),[self.a,self.b]).random_point()defmenu():print("1. Get parameters of path")print("2. Get point in path")print("3. Try to exit the labyrinth")option=input("> ")returnoptiondefmain():ec=ECC(512)print(f'{ec.p= }')print(f'{ec.a= }')print(f'{ec.b= }')whileTrue:choice=menu()ifchoice=='1':r=randint(ec.p.bit_length()//3,2*ec.p.bit_length()//3)print(json.dumps({'p':hex(ec.p),'a':hex(ec.a>>r),'b':hex(ec.b>>r)}))elifchoice=='2':A=ec.gen_random_point()print(json.dumps({'x':hex(A[0]),'y':hex(A[1])}))elifchoice=='3':iv=os.urandom(16)key=sha256(long_to_bytes(pow(ec.a,ec.b,ec.p))).digest()[:16]cipher=AES.new(key,AES.MODE_CBC,iv)flag=pad(FLAG,16)print(json.dumps({'iv':iv.hex(),'enc':cipher.encrypt(flag).hex()}))else:print('Bye.')exit()if__name__=='__main__':main()
Upon analyzing the given code, we can deduce that this is an ECC (Elliptic Curve) challenge. When we connect to the server, we are presented with three menus:
The first one is used to dump some information related to the ECC parameters, which includes:
$p$
$a_{msb}$ (a >> r) where r is a random number within the range of p.bit_length()/3 until 2*p.bit_length()/3
$b_{msb}$ (b >> r)
The second menu allows us to generate a random point on the curve.
The third menu allows us to dump the encrypted flag (with AES), where the AES key is encrypted with the key sha256(long_to_bytes(pow(ec.a, ec.b, ec.p))).digest()[:16].
Therefore, based on our initial analysis, our objective in this challenge is to recover the ECC parameters (a, b, p).
Solution
Well, we can recover p from the first menu as it is provided. Now, we need to recover a and b. It’s important to remember that the equation for the ECC curve is as follows:
$$
y^2 = x^3 + ax + b \mod p
$$
Now, remember that from the second menu, we can generate many points that reside on the curve. As you can see, if we have two points, it becomes two equations with two unknown variables, which are solvable (and for this challenge, we actually don’t need the leak of a and b at all!).
So, to recover the a and b, we just need to recover two points, and then subtract it to remove a. See below equations:
$$
\begin{align}
y_1^2 = x_1^3 + ax_1 + b \mod p \\
y_2^2 = x_2^3 + ax_2 + b \mod p \\
\end{align}
$$
If we subtract the above equations, we will get a new equation as follows
$$
\begin{align}
(y_1^2 - y_2^2) = (x_1^3 -x_2^3) + a(x_1-x_2) \mod p \\
((y_1^2 - y_2^2) - (x_1^3 -x_2^3))(x_1-x_2)^{-1} = a \mod p \\
\end{align}
$$
Now that we can recover a from the above equation, recovering b becomes trivial.
$$
b = y^2 - x^3 - a*x
$$
Once we have recovered a and b, we can retrieve the AES key and use it to decrypt the encrypted flag. The following is the solver that can be used to do that (sage script):
frompwnimport*importos,jsonfromhashlibimportsha256fromrandomimportrandintfromCrypto.Util.numberimportgetPrime,long_to_bytesfromCrypto.CipherimportAESfromCrypto.Util.Paddingimportpadr=remote(b'167.71.143.44',int(31762))r.sendlineafter(b'> ',b'1')out=json.loads(r.recvline().strip())p=int(out['p'],16)partial_a=int(out['a'],16)partial_b=int(out['b'],16)xy_data=[]foriinrange(2):r.sendlineafter(b'> ',b'2')xy_out=json.loads(r.recvline().strip())xy_data.append([int(xy_out['x'],16),int(xy_out['y'],16)])r.sendlineafter(b'> ',b'3')enc_out=json.loads(r.recvline().strip())iv=bytes.fromhex(enc_out['iv'])enc=bytes.fromhex(enc_out['enc'])'''
y1^2 = x1^3 + a*x1 + b mod p
y2^2 = x2^3 + a*x2 + b mod p
----------------------------- subtract
(y1^2 - y2^2) = (x1^3 -x2^3) + a*(x1-x2) mod p
((y1^2 - y2^2) - (x1^3 -x2^3))*(x1-x2)^-1 = a mod p
'''x1,y1=xy_data[0]x2,y2=xy_data[1]sol_a=(((y1^2-y2^2)-(x1^3-x2^3))*inverse_mod(x1-x2,p))%psol_b=(y1^2-x1^3-sol_a*x1)%pprint(f'{sol_a= }')print(f'{sol_b= }')key=sha256(long_to_bytes(pow(int(sol_a),int(sol_b),p))).digest()[:16]cipher=AES.new(key,AES.MODE_CBC,iv)print(f'Flag: {cipher.decrypt(enc)}')
Flag: HTB{d3fund_s4v3s_th3_d4y!}
Elliptic Labyrinth Revenge
Description
As you navigate through the labyrinth inside the tomb, you encounter GPS inaccuracies that make it difficult to determine the correct path to the exit. Can you overcome the technical issues and use your instincts to find your way out of the maze?
Initial Analysis
This is the revenge of the previous challenge. The only difference is that in the previous challenge, we could retrieve multiple points, but for this challenge, we can only retrieve one point.
importos,jsonfromhashlibimportsha256fromrandomimportrandintfromCrypto.Util.numberimportgetPrime,long_to_bytesfromCrypto.CipherimportAESfromCrypto.Util.Paddingimportpadfromsage.all_cmdlineimport*FLAG=b'flag{fake_flag}'classECC:def__init__(self,bits):self.p=getPrime(bits)self.a=randint(1,self.p)self.b=randint(1,self.p)defgen_random_point(self):returnEllipticCurve(GF(self.p),[self.a,self.b]).random_point()defmenu():print("1. Get parameters of path")print("2. Try to exit the labyrinth")option=input("> ")returnoptiondefmain():ec=ECC(512)print(f'{ec.p= }')print(f'{ec.a= }')print(f'{ec.b= }')A=ec.gen_random_point()print("This is the point you calculated before:")print(json.dumps({'x':hex(A[0]),'y':hex(A[1])}))whileTrue:choice=menu()ifchoice=='1':r=randint(ec.p.bit_length()//3,2*ec.p.bit_length()//3)print(json.dumps({'r':r,'p':hex(ec.p),'a':hex(ec.a>>r),'b':hex(ec.b>>r)}))elifchoice=='2':iv=os.urandom(16)key=sha256(long_to_bytes(pow(ec.a,ec.b,ec.p))).digest()[:16]cipher=AES.new(key,AES.MODE_CBC,iv)flag=pad(FLAG,16)print(json.dumps({'iv':iv.hex(),'enc':cipher.encrypt(flag).hex()}))else:print('Bye.')exit()if__name__=='__main__':main()
However, it’s important to remember that we actually have a leak for the a and b parameters, which are their most significant bits (MSBs). Thus, we can use that leak to retrieve them.
Notice that the p.bit_length() is 512. Therefore, the range of r is from 170 to 340, which can be bruteforced. It is important to remember that the ECC equation is as follows:
$$
y^2 = x^3 + ax + b \mod p
$$
And with our leak, the equation can be rearranged as follows:
$$
y^2 = x^3 + (2^ra_{leaked} + c) + {2^rb_{leaked} + d} \mod p
$$
Notice that the value of r is bruteforce-able, and the values of $c$ and $d$ are small compared to the other values ($y^2$, $x^3$, and $2^r$). In this type of challenge, we can try to retrieve the values of $c$ and $d$ value with Coppersmith.
We can reuse the defund implementation of coppersmith to perform the coppersmith attack on the equation.
After retrieving the value $c$ and $d$, we will be able to recover the values of $a$ and $b$.
frompwnimport*importos,jsonfromhashlibimportsha256fromrandomimportrandintfromCrypto.Util.numberimportgetPrime,long_to_bytesfromCrypto.CipherimportAESfromCrypto.Util.Paddingimportpadimportitertoolsdefsmall_roots(f,bounds,m=1,d=None):ifnotd:d=f.degree()R=f.base_ring()N=R.cardinality()f/=f.coefficients().pop(0)f=f.change_ring(ZZ)G=Sequence([],f.parent())foriinrange(m+1):base=N^(m-i)*f^iforshiftsinitertools.product(range(d),repeat=f.nvariables()):g=base*prod(map(power,f.variables(),shifts))G.append(g)B,monomials=G.coefficient_matrix()monomials=vector(monomials)factors=[monomial(*bounds)formonomialinmonomials]fori,factorinenumerate(factors):B.rescale_col(i,factor)B=B.dense_matrix().LLL()B=B.change_ring(QQ)fori,factorinenumerate(factors):B.rescale_col(i,1/factor)H=Sequence([],f.parent().change_ring(QQ))forhinfilter(None,B*monomials):H.append(h)I=H.ideal()ifI.dimension()==-1:H.pop()elifI.dimension()==0:roots=[]forrootinI.variety(ring=ZZ):root=tuple(R(root[var])forvarinf.variables())roots.append(root)returnrootsreturn[]r=remote(b'165.232.100.46',int(31844))# Retrieve x yr.recvuntil(b':\n')xy_out=json.loads(r.recvline().strip())x,y=int(xy_out['x'],16),int(xy_out['y'],16)# Retrieve partial_a and partial_br.sendlineafter(b'> ',b'1')out=json.loads(r.recvline().strip())p=int(out['p'],16)partial_a=int(out['a'],16)partial_b=int(out['b'],16)r.sendlineafter(b'> ',b'2')enc_out=json.loads(r.recvline().strip())iv=bytes.fromhex(enc_out['iv'])enc=bytes.fromhex(enc_out['enc'])'''
f(x) = x^3 - y^2 + (partial_a*2^r + c)*x + (partial_b*2^r + d) mod p
c and d is small, r is bruteforceable
bounds = [2^r, 2^r]
'''print(f'{p= }')forguess_rinrange(p.bit_length()//3,2*p.bit_length()//3):P.<c,d>=PolynomialRing(Zmod(p))bound=2^(guess_r)print(f'{guess_r= }')f=x^3-y^2+x*(partial_a*2^guess_r+c)+(partial_b*2^guess_r+d)bounds=(bound,bound)sols=small_roots(f,bounds,m=7,d=3)iflen(sols)>0:forsolinsols:sol_a=int(sol[0])+partial_a*2^guess_rsol_b=int(sol[1])+partial_b*2^guess_rkey=sha256(long_to_bytes(pow(int(sol_a),int(sol_b),p))).digest()[:16]cipher=AES.new(key,AES.MODE_CBC,iv)print(f'Flag: {cipher.decrypt(enc)}')exit()
Flag: HTB{y0u_5h0u1d_h4v3_u53d_c00p325m17h}
Colliding Heritage
Description
As you arrive at the location of the relic, you discover an ancient tomb that appears to have no visible entrance. However, a scan of the area reveals the presence of unusual RF signals coming from a specific location. With the help of your team, you manage to create an interface to communicate with the signal-emitting device. Unfortunately, the device only grants access to descendants of the pharaoh’s left hand. Can you find a way to enter the tomb?
Initial Analysis
For this challenge, we were given a file called server.py. Below is its code:
#!/usr/bin/env python3importsignalfromsecretsimportrandbelowfromhashlibimportmd5fromCrypto.Util.numberimportisPrime,getPrime,long_to_bytes,bytes_to_longFLAG="HTB{???????????????????????????}"classMD5chnorr:def__init__(self):# while True:# self.q = getPrime(128)# self.p = 2*self.q + 1# if isPrime(self.p):# breakself.p=0x16dd987483c08aefa88f28147702e51ebself.q=(self.p-1)//2self.g=3self.x=randbelow(self.q)self.y=pow(self.g,self.x,self.p)defH(self,msg):returnbytes_to_long(md5(msg).digest())%self.qdefsign(self,msg):k=self.H(msg+long_to_bytes(self.x))print(f'{k= }')r=pow(self.g,k,self.p)%self.qe=self.H(long_to_bytes(r)+msg)s=(k-self.x*e)%self.qreturn(s,e)defverify(self,msg,sig):s,e=sigifnot(0<s<self.q):returnFalseifnot(0<e<self.q):returnFalserv=pow(self.g,s,self.p)*pow(self.y,e,self.p)%self.p%self.qev=self.H(long_to_bytes(rv)+msg)returnev==edefmenu():print('[S]ign a message')print('[V]erify a signature')returninput('> ').upper()[0]defmain():md5chnorr=MD5chnorr()print('g:',md5chnorr.g)print('y:',md5chnorr.y)print('p:',md5chnorr.p)for_inrange(3):choice=menu()ifchoice=='S':msg=bytes.fromhex(input('Enter message> '))ifb'I am the left hand'inmsg:print('No!')else:sig=md5chnorr.sign(msg)print('Signature:',sig)elifchoice=='V':msg=bytes.fromhex(input('Enter message> '))s=int(input('Enter s> '))e=int(input('Enter e> '))ifmd5chnorr.verify(msg,(s,e)):ifmsg==b'I am the left hand':print(FLAG)else:print('Valid signature!')else:print('Invalid signature!')else:print('Invalid choice...')if__name__=='__main__':signal.alarm(30)main()
So, we were given a server that implements a signature scheme with the Schnorr signature algorithm. The details of the algorithm can be read on Wikipedia. The challenge shares the public key of the signature scheme (g, y, and p), and gives us three chances to use the available menus:
S, which is a menu to sign any message that we provide.
There is a restriction that disallows messages containing the string I am the left hand.
We get the s and e values as well, which are the signature.
V, which is a menu to validate our signature of the message.
If the signature is valid and the message is I am the left hand, it will print the flag.
Therefore, the objective of this challenge is to retrieve the private key with two signatures that we obtain from the server so that we can sign the message I am the left hand, send it to the server, and retrieve the flag.
Solution
Notice that in this kind of signature scheme, the vulnerability usually lies in the way it generates the k (nonce) value. The k generation cannot be weak because it can be used to retrieve the private key (x).
As mentioned in the Wikipedia page that I shared before, reusing a nonce is disallowed in this kind of signature scheme. The reason is that we can recover the private key (x) if we use the same k during signing two different messages. Let’s take a look at the signing equations below to understand why we can recover k if it is being reused to sign different messages:
If we subtract the above equation, retrieving the value of $x$ becomes very easy because we know the value of $s_1$, $s_2$, $e_1$, $e_2$ and $q$. We can rearrange those two equations to retrieve $x$.
$$
\begin{align}
(s_1 - s_2) = k - k - x(e_1e_2) \mod q \\
x = -(s_1 - s_2)(e_1e_2)^{-1} \mod q \\
\end{align}
$$
So, if we sign two different messages with the same k, we will be able to recover x and sign the required message.
Now that we know that we need to somehow sign two different messages with the same k value, let’s take a look at how the k is generated.
Notice that the generation of k (nonce) is basically just md5(msg || x). As mentioned in many articles, it is easy to generate a hash collision with md5. Reading through this article helped me understand why the way this challenge generates k is weak. It is easy to generate a md5 hash collision, which means we can sign two different messages with the same k value due to the collision.
After reading that article, I realized that it is pretty simple to exploit the weakness of md5. We just need to grab two strings that have md5 collisions and use that as our messages to be signed. However, we need to be careful because the msg that we send will be appended by the x as well. Therefore, we can’t send the raw msg to the server. As mentioned in the previous article, md5 pads the msg first with some bytes during hashing. Thus, we need to send the padded message to the server instead of raw msg. This ensures that before the md5 process the bytes of appended x, both of the messages that we sent will have the same md5 state. So, when the md5 algorithm tries to process the block of the appended x, the state will be the same, which means it will produce the same hash.
Once we are able to produce the md5 collision, we can retrieve the private key x based on the previous equations that I explained because the k value is reused.
Below is my full script to recover the flag (sage script):
frompwnimport*fromhashlibimportmd5fromCrypto.Util.numberimport*# Use two strings that has md5 collisionsm1=bytes.fromhex('4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2')m2=bytes.fromhex('4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2')assertm1!=m2'''
After we properly padding the above string to follow the specification of MD5,
(64-bytes per block), both of the string will produce the same state.
So, if you append any same string, the produced hash will still be the same.
#
In this case, k = HASH(m11 || x) == HASH(m22 || x) will be the same.
But, HASH(r || m11) != HASH(r || m22), because the 64-bytes block are different
#
So, if we sign this two message, it is basically the same case as re-used nonce k,
which is vulnerable. Notice this.
s2-s1 = k2-k1 - x(e2-e1)
If k2 == k1, that means:
x = -1 * (s2 - s1) * (e2-e1)^-1
'''m11=m1+b"\x80"+b"\x00"*55+p64(0x200)m22=m2+b"\x80"+b"\x00"*55+p64(0x200)io=remote(b'142.93.35.133',int(31079))io.recvuntil(b': ')# Retrieve the public keyg=int(io.recvline())io.recvuntil(b': ')y=int(io.recvline())io.recvuntil(b': ')p=int(io.recvline())q=int((p-1)//2)# Sign the padded messagesio.sendlineafter(b'> ',b'S')io.sendlineafter(b'> ',m11.hex().encode())io.recvuntil(b': ')s1,e1=eval(io.recvline())io.sendlineafter(b'> ',b'S')io.sendlineafter(b'> ',m22.hex().encode())io.recvuntil(b': ')s2,e2=eval(io.recvline())# Recover xx=(((s2-s1)*inverse_mod(e2-e1,q))*-1)%qprint(f'recovered x = {x}')# Sign the required message and send it to the servermsg=b'I am the left hand'defH(msg):returnbytes_to_long(md5(msg).digest())%qk=H(msg+long_to_bytes(x))r=pow(int(g),int(k),int(p))%qe=H(long_to_bytes(r)+msg)s=(k-x*e)%qio.sendlineafter(b'> ',b'V')io.sendlineafter(b'> ',msg.hex().encode())io.sendlineafter(b'> ',str(s).encode())io.sendlineafter(b'> ',str(e).encode())io.interactive()
Flag: HTB{w3ll_y3s_bu7_4c7ual1y_n0…}
Biased Heritage
Description
You emerge from the labyrinth to find a massive door blocking your path to the relic. It has the same authentication mechanism as the entrance, but it appears to be more sophisticated and challenging to crack. Can you devise a plan to breach the door and gain access to the relic?
Initial Analysis
This is the upgraded challenge from the previous challenge (Colliding Heritage). Let’s try to see the given server.py
#!/usr/bin/env python3importsignalfromsecretsimportrandbelowfromhashlibimportsha256fromCrypto.Util.numberimportisPrime,getPrime,long_to_bytes,bytes_to_longFLAG="HTB{???????????????????????????????????????}"classSHA256chnorr:def__init__(self):# while True:# self.q = getPrime(512)# self.p = 2*self.q + 1# if isPrime(self.p):# breakself.p=0x184e26a581fca2893b2096528eb6103ac03f60b023e1284ebda3ab24ad9a9fe0e37b33eeecc4b3c3b9e50832fd856e9889f6c9a10cde54ee798a7c383d0d8d2c3self.q=(self.p-1)//2self.g=3self.x=randbelow(self.q)self.y=pow(self.g,self.x,self.p)defH(self,msg):returnbytes_to_long(2*sha256(msg).digest())%self.qdefsign(self,msg):k=self.H(msg+long_to_bytes(self.x))r=pow(self.g,k,self.p)%self.qe=self.H(long_to_bytes(r)+msg)s=(k-self.x*e)%self.qreturn(s,e)defverify(self,msg,sig):s,e=sigifnot(0<s<self.q):returnFalseifnot(0<e<self.q):returnFalserv=pow(self.g,s,self.p)*pow(self.y,e,self.p)%self.p%self.qev=self.H(long_to_bytes(rv)+msg)returnev==edefmenu():print('[S]ign a message')print('[V]erify a signature')returninput('> ').upper()[0]defmain():sha256chnorr=SHA256chnorr()print('g:',sha256chnorr.g)print('y:',sha256chnorr.y)print('p:',sha256chnorr.p)for_inrange(3):choice=menu()ifchoice=='S':msg=bytes.fromhex(input('Enter message> '))ifb'right hand'inmsg:print('No!')else:sig=sha256chnorr.sign(msg)print('Signature:',sig)elifchoice=='V':msg=bytes.fromhex(input('Enter message> '))s=int(input('Enter s> '))e=int(input('Enter e> '))ifsha256chnorr.verify(msg,(s,e)):ifmsg==b'right hand':print(FLAG)else:print('Valid signature!')else:print('Invalid signature!')else:print('Invalid choice...')if__name__=='__main__':signal.alarm(30)main()
As you can see, the generation of k is changed. Now, it uses sha256 instead of md5. Up until now, there isn’t any collision found for sha256, which mean we can’t use our previous approach to solve this challenge.
Solution
Reading through the Wikipedia again, it is mentioned that:
Warning
In fact, even slight biases in the value k or partial leakage of k can reveal the private key, after collecting sufficiently many signatures and solving the hidden number problem.
So, there is another method to recover the private key x which involves exploiting a weak bias in the generation of k. Let’s take another look at the new method used to generate k and see if it has any biases.
Notice that generation of k (nonce) is now 2 * sha256(msg || x). This is actually a weak generation. Even though the size of k is around 512 bits, the repeated sequence of bits in k reduces its entropy to only 256 bits. Therefore, k can be constructed as follows:
$$
k = 2^{256}b + b \\
k = b(2^{256} + 1) \\
$$
where $b$ is the 256 bits produced by the sha256 hashing algorithm, so there are indeed biases in the generated k, and we might be able to recover it.
This paper and writeup helped me a lot in understanding how to approach this problem. Basically, notice that the way of Schnorr signature mechanism works is actually similar to a hidden number problem. By incorporating the knowledge of how k is generated into the signature mechanism, we can obtain a new equation:
$$
\begin{align}
s = k - xe \mod q \\
s = b(2^{256}+1) - xe \mod q \\
s - b(2^{256}+1) + xe = 0 \mod q \\
\end{align}
$$
Notice that the $b$ value is actually smaller compared to the other value.
Usually, in this kind of setup, we can construct a lattice and use LLL to recover an unknown value that we have in the above equation. I recommend reading the write-up I mentioned above to understand the details of how lattices work, but basically, I came up with this lattice after reading through the previous paper and write-up.
where $B = 2^{256}$ ($B$ is bound of the b value that we’re trying to recover). It is the same like previous challenge, where we can only retrieve two signatures from the server, which is why the lattice only contains signature 1 and 2.
Using that lattice, we hope that that there exist a vector in the lattice that is small, which can be expressed as follows:
And because the bit lengths of $x$, $q$, $b_2$, $B$, and $b_1$ is pretty much the same or close, we hope that the above vector is small enough for the lattice. To find that target vector, we can assume that if we’re trying to look for a vector in the lattice that is close to the following vector,
we will find our target vector. To find the approximation of it, we can use the Babai CVP algorithm.
If we find the target vector, that means we have successfully recovered the private key x, and the rest of the steps are the same as the previous challenge.
Below is my full script (Sage script). Note that due to the lack of signatures that we can collect (only 2), the script’s success rate is not 100%, so you might need to re-run the script multiple times.
fromsecretsimportrandbelowfromhashlibimportsha256fromCrypto.Util.numberimportisPrime,getPrime,long_to_bytes,bytes_to_longfrompwnimport*importos'''
def H(self, msg):
return bytes_to_long(2 * sha256(msg).digest()) % self.q
Notice that the k generation is:
- k = self.H(msg + long_to_bytes(self.x))
The Hash message is weak, because that means:
k = b + 2^256*b = b(2^256+1)
where b is the 256 bits generated by the sha256, and it is small enough compared to q
This means, we can try to recover it by constructing a lattice that
can produced a vector containing the b value after being reduced
by LLL algorithm.
'''defBabai_closest_vector(B,target):# Babai's Nearest Plane algorithmM=B.LLL()G=M.gram_schmidt()[0]small=targetfor_inrange(1):foriinreversed(range(M.nrows())):c=((small*G[i])/(G[i]*G[i])).round()small-=M[i]*creturntarget-smallp=0x184e26a581fca2893b2096528eb6103ac03f60b023e1284ebda3ab24ad9a9fe0e37b33eeecc4b3c3b9e50832fd856e9889f6c9a10cde54ee798a7c383d0d8d2c3q=(p-1)//2g=3msg1=os.urandom(16)msg2=os.urandom(16)io=remote(b'206.189.112.129',int(30481))io.recvuntil(b': ')g=int(io.recvline())io.recvuntil(b': ')y=int(io.recvline())io.recvuntil(b': ')p=int(io.recvline())q=int((p-1)//2)io.sendlineafter(b'> ',b'S')io.sendlineafter(b'> ',msg1.hex().encode())io.recvuntil(b': ')s1,e1=eval(io.recvline())io.sendlineafter(b'> ',b'S')io.sendlineafter(b'> ',msg2.hex().encode())io.recvuntil(b': ')s2,e2=eval(io.recvline())B=2**256# b_i = (2^256 + 1)*b_i), and b_i bound is 2**256 because it is the result of sha256M=Matrix([[1,0,0,0,s2,s1],[0,2/q,0,0,e2,e1],[0,0,1/B,0,(B+1),0],[0,0,0,1/B,0,(B+1)],[0,0,0,0,q,0],[0,0,0,0,0,q],])# Try to find a vector resides in the lattice which is close to the# target vectorres=Babai_closest_vector(M,vector([1,1,-1,-1,0,0]))x=int(res[1]*q/2)-1# Based on observation, if we're lucky, our recovered x is differed by 1print(f'recovered x = {x}')# Sign the message with our recovered private keymsg=b'right hand'defH(msg):returnbytes_to_long(2*sha256(msg).digest())%qk=H(msg+long_to_bytes(x))r=pow(int(g),int(k),int(p))%qe=H(long_to_bytes(r)+msg)s=(k-x*e)%qio.sendlineafter(b'> ',b'V')io.sendlineafter(b'> ',msg.hex().encode())io.sendlineafter(b'> ',str(s).encode())io.sendlineafter(b'> ',str(e).encode())io.interactive()
As you hold the relic in your hands, it prompts you to input a coordinate. The ancient scriptures you uncovered near the pharaoh’s tomb reveal that the artifact is capable of transmitting the locations of vessels. The initial coordinate must be within proximity of the vessels, and an algorithm will then calculate their precise locations for transmission. However, you soon discover that the coordinates transmitted are not correct, and are encrypted using advanced alien techniques to prevent unauthorized access. It becomes clear that the true coordinates are hidden, serving only to authenticate those with knowledge of the artifact’s secrets. Can you decipher this alien encryption and uncover the genuine coordinates to locate the vessels and destroy them?
Initial Analysis
On this challenge, we were given a file called server.py. Below is the contents of the code:
fromsecretimportFLAG,p,a,bfromsage.all_cmdlineimport*classPRNG:def__init__(self,p,mul1,mul2):self.mod=p*6089788258325039501929073418355467714844813056959443481824909430411674443639248386564763122373451773381582660411059922334086996696436657009055324008041039self.exp=2self.mul1=mul1self.mul2=mul2self.inc=int.from_bytes(b'Coordinates lost in space','big')self.seed=randint(2,self.mod-1)defrotate(self):self.seed=(self.mul1*pow(self.seed,3)+self.mul2*self.seed+self.inc)%self.modreturnself.seed,pow(self.seed,self.exp,self.mod)classRelic:def__init__(self,p,a,b):self.E=EllipticCurve(GF(p),[a,b])self.P=Noneself.EP=Noneself.p=pself.prng=PRNG(p,a,b)defsetupPoints(self,x):ifx>=self.p:return'Coordinate greater than curve modulus'try:self.P=self.E.lift_x(Integer(x))self.EP=self.Pexcept:return'Point not on curve'return('Point confirmed on curve',self.P[0],self.P[1])defnextPoints(self):seed,enc_seed=self.prng.rotate()self.P*=seedself.EP*=enc_seedreturn('New Points',self.EP[0],self.EP[1],self.P[0],self.P[1])defmenu():print('Options:\n')print('1. Setup Point')print('2. Receive new point')print('3. Find true point')option=input('> ')returnoptiondefmain():artifact=Relic(p,a,b)setup=FalsewhileTrue:try:option=menu()ifoption=='1':print('Enter x coordinate')x=int(input('x: '))response=artifact.setupPoints(x)ifresponse[0]=='Point confirmed on curve':setup=Trueprint(response)elifoption=='2':ifsetup:response=artifact.nextPoints()print('Response')print((response[0],response[1],response[2]))else:print('Configure origin point first')elifoption=='3':ifsetup:print('Input x,y')Px=int(input('x: '))Py=int(input('y: '))response=artifact.nextPoints()ifresponse[3]==Pxandresponse[4]==Py:print('You have confirmed the location. It\'s dangerous however to go alone. Take this: ',FLAG)else:print('The vessels will never be found...')exit()else:print('Configure origin point first')else:print("Invalid option, sutting down")exit()exceptExceptionase:response=f'An error occured: {e}'print(response)exit()if__name__=='__main__':assertp.bit_length()==256main()
As we can see in the code, the server is basically a combination of Elliptic Curve and PRNG. Let’s check the PRNG code first.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classPRNG:def__init__(self,p,mul1,mul2):self.mod=p*6089788258325039501929073418355467714844813056959443481824909430411674443639248386564763122373451773381582660411059922334086996696436657009055324008041039self.exp=2self.mul1=mul1self.mul2=mul2self.inc=int.from_bytes(b'Coordinates lost in space','big')self.seed=randint(2,self.mod-1)defrotate(self):self.seed=(self.mul1*pow(self.seed,3)+self.mul2*self.seed+self.inc)%self.modreturnself.seed,pow(self.seed,self.exp,self.mod)
Well, this is just a usual PRNG, with an extra that it doesn’t only return the seed, but also the encrypted seed (encrypted with scheme similar to RSA rabin, which is $enc = \text{seed}^2 \mod (p*c)$, where $c$ is the constant hard-coded in the code).
classRelic:def__init__(self,p,a,b):self.E=EllipticCurve(GF(p),[a,b])self.P=Noneself.EP=Noneself.p=pself.prng=PRNG(p,a,b)defsetupPoints(self,x):ifx>=self.p:return'Coordinate greater than curve modulus'try:self.P=self.E.lift_x(Integer(x))self.EP=self.Pexcept:return'Point not on curve'return('Point confirmed on curve',self.P[0],self.P[1])defnextPoints(self):seed,enc_seed=self.prng.rotate()self.P*=seedself.EP*=enc_seedreturn('New Points',self.EP[0],self.EP[1],self.P[0],self.P[1])
Okay, so to summarize:
The Relic class uses the PRNG class as one of its attribute
It also has two variables to store points: P and EP
There are two main method:
setupPoints
This resets the Relic point to our chosen x, which is required to be a valid point.
It also resets both P and EP to store our chosen point.
nextPoints
This generates a new random number from the PRNG, and then multiplies:
P with seed
EP with enc_seed
There are three menus that we can interact with:
1
Reset the points that will be used by the Elliptic Curve.
If the given x is larger than the used p, it will return the message Coordinate greater than curve modulus.
Otherwise, it will try to generate a point (x, y) on the curve and return it to us if it is valid.
2:
Generate new points, which are:
P *= seed
EP *= enc_seed
where EP is basically the current point set in the Elliptic Curve multiplied with the encrypted seed.
It will then return only the EP to us.
3:
Print the flag, but we need to be able to predict the generated point by nextPoints method.
Based on this information, our goal is to recover the seed value and use it to predict the next generated point.
Solution
Firstly, we don’t know the parameters of the curve yet (p, a, b). So, we need to recover them first. Notice that in the first menu, we can perform a binary search to find the p value, because if we provide an x value greater than p, the program will indicate that the x value is greater than the p value.
Once we have recovered the p value, it is easy to obtain the a and b values. We just need to generate two points and then subtract them, just like what we did in the Elliptic Labyrinth Challenge. Below is the script that I used to recover the parameters (I used sagemath).
frompwnimport*r=remote('68.183.37.122',int(32073))# Binary Search the p. I've changed the high and low value in here to speed up the process as# I've already retrieved the value before making this writeup.high=91720173941422125335466921700213991383508377854521057423162397714341988797840low=91720173941422125335466921700213991383508377854521057423162397714341988797837whilehigh-low>=0:print(f'high, low = {high}, {low}')print(f'Curr diff: {high-low}')ifhigh-low==0:breakmid=(high+low)//2r.sendlineafter(b'> ',b'1')r.sendlineafter(b'x: ',str(mid).encode())out=r.recvline()ifb'greater'inout:# Too highhigh=midelse:low=mid+1p=highprint(f'recovered p = {p}')defsetup_point(x):r.sendlineafter(b'> ',b'1')r.sendlineafter(b'x: ',str(x).encode())_,x1,y1=eval(r.recvline().strip())returnx1,y1x1,y1=setup_point(4)x2,y2=setup_point(6)a=(((y1^2-y2^2)-(x1^3-x2^3))*inverse_mod(x1-x2,p))%pb=(y1^2-x1^3-a*x1)%pprint(f'recovered a = {a}')print(f'recovered b = {b}')E=EllipticCurve(GF(p),[a,b])
After we finally recovered the curve, the next step is to figure out how to recover the PRNG seed.
In ECC, discrete logarithm is hard. So, if we have equation like $A = kB$ where $A$ and $B$ are points, $k$ is the multiplier, and we only know $A$ and $B$, we won’t be able to recover the $k$ value easily. However, for this challenge, in order to recover the seed value, we need to retrieve the enc_seed first.
Even though we can setup the point (let’s call it A) via the first menu, and we can also get the EP value, which is EP = enc_seed*A, if the ECC is not weak, it won’t be possible for us to recover the enc_seed.
However, after playing around with the curve, I noticed that the curve order is actually the same with the p used in the curve.
1
2
3
4
sage: E.order()
91720173941422125335466921700213991383508377854521057423162397714341988797837
sage: E.order() == p
True
This is a weak curve that is vulnerable to Smart Attack. Below is the script that I used to perform the Smart Attack, taken from this github:
# Lifts a point to the p-adic numbers.def_lift(E,P,gf):x,y=map(ZZ,P.xy())forpoint_inE.lift_x(x,all=True):_,y_=map(gf,point_.xy())ify==y_:returnpoint_defattack(G,P):"""
Solves the discrete logarithm problem using Smart's attack.
More information: Smart N. P., "The discrete logarithm problem on elliptic curves of trace one"
:param G: the base point
:param P: the point multiplication result
:return: l such that l * G == P
"""E=G.curve()gf=E.base_ring()p=gf.order()assertE.trace_of_frobenius()==1,f"Curve should have trace of Frobenius = 1."E=EllipticCurve(Qp(p),[int(a)+p*ZZ.random_element(1,p)forainE.a_invariants()])G=p*_lift(E,G,gf)P=p*_lift(E,P,gf)Gx,Gy=G.xy()Px,Py=P.xy()returnint(gf((Px/Py)/(Gx/Gy)))gx,gy=setup_point(4)G=E(gx,gy)defnext_point():r.sendlineafter(b'> ',b'2')ifargs.LOCAL:print(r.recvline().strip())r.recvline().strip()_,x,y=eval(r.recvline().strip())returnx,ypx,py=next_point()P=E(px,py)enc_seed=attack(G,P)print(f'recovered enc_seed: {enc_seed}')# enc_seed = seed^2 mod p
By using the Smart attack, we will be able to recover the enc_seed, and now it’s time to move to the next part, which is recovering the seed from the known enc_seed.
To retrieve the seed, it is actually easy. SageMath has a built-in feature that can calculate the nth_root of an integer over a ring. So, we just need to use that, and there will be two roots that are recovered. One of the two roots is the seed. With 50:50 chance, I decided to always take the second root as the seed, and then use it to predict the next point in the server. After that, we will be able to get our flag.
Below is the full script that I used to solve the challenge (I use SageMath).
frompwnimport*r=remote('68.183.37.122',int(32073))p=NoneifpisNone:# Binary Search the p. I've changed the high and low value in here to speed up the process as# I've already retrieved the value before making this writeup.high=91720173941422125335466921700213991383508377854521057423162397714341988797840low=91720173941422125335466921700213991383508377854521057423162397714341988797837whilehigh-low>=0:print(f'high, low = {high}, {low}')print(f'Curr diff: {high-low}')ifhigh-low==0:breakmid=(high+low)//2r.sendlineafter(b'> ',b'1')r.sendlineafter(b'x: ',str(mid).encode())out=r.recvline()ifb'greater'inout:# Too highhigh=midelse:low=mid+1p=highprint(f'recovered p = {p}')a=Noneb=Nonedefsetup_point(x):r.sendlineafter(b'> ',b'1')r.sendlineafter(b'x: ',str(x).encode())_,x1,y1=eval(r.recvline().strip())returnx1,y1ifaisNoneorbisNone:x1,y1=setup_point(4)x2,y2=setup_point(6)a=(((y1^2-y2^2)-(x1^3-x2^3))*inverse_mod(x1-x2,p))%pb=(y1^2-x1^3-a*x1)%pprint(f'recovered a = {a}')print(f'recovered b = {b}')# Now that we have recovered the curves parameter build the curveE=EllipticCurve(GF(p),[a,b])print(f'Vulnerable to smart attack: {E.order()==p}')assertE.order()==p# Vulnerable to Smart Attack# Lifts a point to the p-adic numbers.def_lift(E,P,gf):x,y=map(ZZ,P.xy())forpoint_inE.lift_x(x,all=True):_,y_=map(gf,point_.xy())ify==y_:returnpoint_defattack(G,P):"""
Solves the discrete logarithm problem using Smart's attack.
More information: Smart N. P., "The discrete logarithm problem on elliptic curves of trace one"
:param G: the base point
:param P: the point multiplication result
:return: l such that l * G == P
"""E=G.curve()gf=E.base_ring()p=gf.order()assertE.trace_of_frobenius()==1,f"Curve should have trace of Frobenius = 1."E=EllipticCurve(Qp(p),[int(a)+p*ZZ.random_element(1,p)forainE.a_invariants()])G=p*_lift(E,G,gf)P=p*_lift(E,P,gf)Gx,Gy=G.xy()Px,Py=P.xy()returnint(gf((Px/Py)/(Gx/Gy)))gx,gy=setup_point(4)G=E(gx,gy)defnext_point():r.sendlineafter(b'> ',b'2')ifargs.LOCAL:print(r.recvline().strip())r.recvline().strip()_,x,y=eval(r.recvline().strip())returnx,ypx,py=next_point()P=E(px,py)enc_seed=attack(G,P)print(f'recovered enc_seed: {enc_seed}')# enc_seed = seed^2 mod pinc=int.from_bytes(b"Coordinates lost in space","big")Z=IntegerModRing(p)seeds_1=Z(enc_seed).nth_root(2,all=True)# There will be two rootsprint(f'recovered_seed: {seeds_1}')# Calculate next_seednext_seed=(a*pow(seeds_1[1],3)+b*seeds_1[1]+inc)%p# Take second entry (50:50)setup_point(4)# Reset point# Predictprediction_point=G*int(next_seed)print(f'prediction: {prediction_point}')r.sendlineafter(b'> ',b'3')r.sendlineafter(b'x: ',str(prediction_point[0]).encode())r.sendlineafter(b'y: ',str(prediction_point[1]).encode())r.interactive()