I have been casually participating in the Cyber Apocalypse CTF 2024. During this time, I managed to solve all the challenges in the pwn, crypto, blockchain, and hardware categories. In this write-up, I will share my solutions for all the challenges in the crypto category that I solved. If you are interested in reading the write-up for all the blockchain & hardware challenges, check out this post. If you are interested in reading the write-up for all the pwn challenges, check out this post.
Crypto
ROT128 [insane]
Description
In the eerie stillness of the Bitting village, a dilapidated laboratory lies forgotten and forsaken, its ancient walls whispering secrets of unspeakable horrors. As you awaken within its confines, a shiver runs down your spine, the air thick with the weight of untold darkness. With no recollection of how you came to be here, you begin to explore the place. The dim glow of flickering lights casts long shadows across the worn floors, revealing rusted equipment and decaying machinery. The air is heavy with the scent of decay and abandonment, a tangible reminder of the atrocities that once transpired within these walls. Soon, you uncover the sinister truth lurking within the laboratory’s forgotten depths. This place was a chamber of horrors, a breeding ground for abominable experiments in human cloning. The realization sends chills coursing through your veins, your mind reeling at the thought of the atrocities committed in the name of science. But there is no time to dwell on the horrors of the past, because a sinister countdown echoes through the laboratory, its ominous tones a harbinger of impending doom. Racing against the ticking clock, you discover the source of the impending catastrophe—a chemical reactor primed to unleash devastation upon the village. With the weight of the world upon your shoulders, you realize that you alone possess the knowledge to defuse the deadly device. As a chemist, you understand the delicate balance of chemical reactions, and you know that triggering a specific collision multiple times is the key to averting disaster. With steady hands and a racing heart, you get to work. As the seconds tick away, you feel the weight of the world bearing down upon you, but you refuse to falter.
Initial Analysis
In this challenge, we were given a source code named server.py.
importrandom,os,signalfromCrypto.Util.numberimportlong_to_bytesasl2b,bytes_to_longasb2lfromsecretimportFLAGROUNDS=3USED_STATES=[]_ROL_=lambdax,i:((x<<i)|(x>>(N-i)))&(2**N-1)N=128defhandler(signum,frame):print("\n\nToo slow, don't try to do sneaky things.")exit()defvalidate_state(state):ifnotall(0<s<2**N-1forsinuser_state[-2:])ornotall(0<=s<Nforsinuser_state[:4]):print('Please, make sure your input satisfies the upper and lower bounds.')returnFalseifsorted(state[:4])inUSED_STATES:print('You cannot reuse the same state')returnFalseifsum(user_state[:4])<2:print('We have to deal with some edge cases...')returnFalsereturnTrueclassHashRoll:def__init__(self):self.reset_state()defhash_step(self,i):r1,r2=self.state[2*i],self.state[2*i+1]return_ROL_(self.state[-2],r1)^_ROL_(self.state[-1],r2)defupdate_state(self,state=None):ifnotstate:self.state=[0]*6self.state[:4]=[random.randint(0,N)for_inrange(4)]self.state[-2:]=[random.randint(0,2**N)for_inrange(2)]else:self.state=statedefreset_state(self):self.update_state()defdigest(self,buffer):buffer=int.from_bytes(buffer,byteorder='big')m1=buffer>>Nm2=buffer&(2**N-1)self.h=b''foriinrange(2):self.h+=int.to_bytes(self.hash_step(i)^(m1ifnotielsem2),length=N//8,byteorder='big')returnself.hprint('Can you test my hash function for second preimage resistance? You get to select the state and I get to choose the message ... Good luck!')hashfunc=HashRoll()for_inrange(ROUNDS):print(f'ROUND {_+1}/{ROUNDS}!')server_msg=os.urandom(32)hashfunc.reset_state()server_hash=hashfunc.digest(server_msg)print(f'You know H({server_msg.hex()}) = {server_hash.hex()}')signal.signal(signal.SIGALRM,handler)signal.alarm(2)user_state=input('Send your hash function state (format: a,b,c,d,e,f) :: ').split(',')try:user_state=list(map(int,user_state))ifnotvalidate_state(user_state):print("The state is not valid! Try again.")exit()hashfunc.update_state(user_state)ifhashfunc.digest(server_msg)==server_hash:print(f'Moving on to the next round!')USED_STATES.append(sorted(user_state[:4]))else:print('Not today.')exit()except:print("The hash function's state must be all integers.")exit()finally:signal.alarm(0)print(f'Uhm... how did you do that? I thought I had cryptanalyzed it enough ... {FLAG}')
The code is extensive, but essentially, the task is to create a unique hashing algorithm referred to as HashRoll. Upon checking through the HashRoll’s design, we can see that it operates with six internal states.
These states are manipulated through the update_state function. The hashing process involves the digest function, which computes the hash for the given message. To illustrate, if we consider a 32-byte message in the buffer, the digest function begins by dividing this message into two 16-byte segments, denoted as $m_{0}$ and $m_{1}$. The computation of the hash result follows this segmentation.
Next, let’s find out the goal of this challenge. Looking at the for loop, the main task is to come up with new, unique states. With the same $\text{m}$ and $\text{digest}$, our input states should give us back the same $\text{digest}$.
Knowing what we need to do, let’s start thinking about how to tackle this challenge.
Solution
First, I tackled this challenge by trying to express its logic through mathematical equations. The task is to find different states that would lead to the same hash_step result for both $h_{0}$ and $h_{1}$.
To figure out the values of $h_{0}$ and $h_{1}$ our states input needs to generate, observe that given $m$ and its hash $\text{digest}(m)$ (let’s call $\text{digest}(m)$ as $d$), we can easily find the $h$ values. By dividing both $m$ (into $m_0$ and $m_1$) and $d$ (into $d_0$ and $d_1$), we notice:
Next, while attempting to mathematically represent the hash_step operation, I noticed that the xor operation can be represented as addition in $GF(2)$, and the ROL operation can be represented as multiplication by a special matrix in $GF(2)$ that can rotate a vector or another matrix.
For instance, if we want to calculate _ROL_(2, 2) in an 8-bit space, it is equivalent to the following equation:
So, by analyzing how the hash_step is generated, we can deduce it is equivalent to an equation involving $\text{ROL}_{i}$, the matrix I described earlier.
With these equations in hand, we find ourselves with only $h_0$ and $h_1$ known, leaving us with two equations and six unknowns.
To tackle this, I decided to define four of the unknowns myself: $r_0$, $r_1$, $r_2$, and $r_3$. I set the value of $r_0$ equal to $r_2$ to help eliminate variables in our equations. Assuming we set:
Both $r_0$ and $r_2$ to $\text{ROL}_a = r_a$
$r_1$ to $\text{ROL}_b = r_b$
$r_3$ to $\text{ROL}_d = r_d$
This leads us to the following equation:
$$
\begin{align}
h_0 = r_as_4 + r_bs_5 \\
h_1 = r_as_4 + r_ds_5 \\
\end{align}
$$
If we subtract the equations we have, we will arrive at a new equation as follows:
$$
\begin{align}
(h_0 - h_1) = (r_b-r_d)s_5 \\
\end{align}
$$
Knowing $h_0$ and $h_1$, and having defined $r_b$ and $r_d$ ourselves, we can easily solve this equation to find $s_5$ with the help of SageMath’s solve_right() function.
After determining $s_5$, and since we’ve also chosen $r_a$ ourselves, figuring out $s_4$ becomes straightforward.
$$
\begin{align}
h_0 = r_as_4 + r_bs_5 \\
h_0 - r_bs_5 = r_as_4 \\
\end{align}
$$
To solve this equation, we can use SageMath’s solve_right() again. Now, we just need to implement this. We have three rounds, and I’ve predefined the values as follows:
You find yourself in the middle of a deadly ancient maze. The maze sprawls before you, its secrets veiled in shadows, its gates locked tight against intruders. With thousands of keys shimmering under the harsh light, you steel yourself for the daunting challenge ahead. Each chamber of the maze presents a new puzzle to unravel, each gate a barrier to overcome. Armed with determination and resolve, you set forth into the labyrinth’s depths, knowing that your survival hinges on unlocking the path forward by finding the proper key. With each new chamber you enter, you are greeted with a cup of tea—a brief respite from the perilous journey that lies ahead. But the tea is not the only gift bestowed upon you in these chambers. With each cup, you receive a hint that will guide you on how to move on.
NOTE: ’tea.py’ can be found in the challenge ‘Iced Tea’
Initial Analysis
In this challenge, we were provided with a file named server.py.
fromteaimportCipherasTEAfromsecretimportIV,FLAGimportosROUNDS=10defshow_menu():print("""
============================================================================================
|| I made this decryption oracle in which I let users choose their own decryption keys. ||
|| I think that it's secure as the tea cipher doesn't produce collisions (?) ... Right? ||
|| If you manage to prove me wrong 10 times, you get a special gift. ||
============================================================================================
""")defrun():show_menu()server_message=os.urandom(20)print(f'Here is my special message: {server_message.hex()}')used_keys=[]ciphertexts=[]foriinrange(ROUNDS):print(f'Round {i+1}/10')try:ct=bytes.fromhex(input('Enter your target ciphertext (in hex) : '))assertctnotinciphertextsforjinrange(4):key=bytes.fromhex(input(f'[{i+1}/{j+1}] Enter your encryption key (in hex) : '))assertlen(key)==16andkeynotinused_keysused_keys.append(key)cipher=TEA(key,IV)enc=cipher.encrypt(server_message)ifenc!=ct:print(f'Hmm ... close enough, but {enc.hex()} does not look like {ct.hex()} at all! Bye...')exit()except:print('Nope.')exit()ciphertexts.append(ct)print(f'Wait, really? {FLAG}')if__name__=='__main__':run()
Looking at this challenge, the summary is that, given 10 ROUNDS, in each round, we need to provide 4 different keys. These keys, when used as the key for the Tiny Encryption Algorithm (TEA) with the same input, should generate the same encryption result. Below is the implementation of the TEA (sourced from another challenge named Iced TEA). I’ve added the decrypt_block method to the code below.
importosfromCrypto.Util.PaddingimportpadfromCrypto.Util.numberimportbytes_to_longasb2l,long_to_bytesasl2bfromenumimportEnumclassMode(Enum):ECB=0x01CBC=0x02classCipher:def__init__(self,key,iv=None):self.BLOCK_SIZE=64self.KEY=[b2l(key[i:i+self.BLOCK_SIZE//16])foriinrange(0,len(key),self.BLOCK_SIZE//16)]self.DELTA=0x9e3779b9self.IV=ivifself.IV:self.mode=Mode.CBCelse:self.mode=Mode.ECBdef_xor(self,a,b):returnb''.join(bytes([_a^_b])for_a,_binzip(a,b))defencrypt(self,msg):msg=pad(msg,self.BLOCK_SIZE//8)blocks=[msg[i:i+self.BLOCK_SIZE//8]foriinrange(0,len(msg),self.BLOCK_SIZE//8)]ct=b''ifself.mode==Mode.ECB:forptinblocks:ct+=self.encrypt_block(pt)elifself.mode==Mode.CBC:X=self.IVforptinblocks:enc_block=self.encrypt_block(self._xor(X,pt))ct+=enc_blockX=enc_blockreturnctdefencrypt_block(self,msg):m0=b2l(msg[:4])m1=b2l(msg[4:])K=self.KEYmsk=(1<<(self.BLOCK_SIZE//2))-1s=0foriinrange(32):s+=self.DELTAm0+=((m1<<4)+K[0])^(m1+s)^((m1>>5)+K[1])m0&=mskm1+=((m0<<4)+K[2])^(m0+s)^((m0>>5)+K[3])m1&=mskm=((m0<<(self.BLOCK_SIZE//2))+m1)&((1<<self.BLOCK_SIZE)-1)# m = m0 || m1returnl2b(m)defdecrypt_block(self,msg):m=b2l(msg)m1=m&((1<<(self.BLOCK_SIZE//2))-1)m0=m>>(self.BLOCK_SIZE//2)K=self.KEYmsk=(1<<(self.BLOCK_SIZE//2))-1s=self.DELTA*32foriinrange(32):m1-=((m0<<4)+K[2])^(m0+s)^((m0>>5)+K[3])m1&=mskm0-=((m1<<4)+K[0])^(m1+s)^((m1>>5)+K[1])m0&=msks-=self.DELTAdecrypted_block=l2b(m0)+l2b(m1)returndecrypted_block
Now that we understand the main goal of the challenge, let’s consider how to approach it.
Solution
First, note that in server.py, a static IV is used. Recovering the IV is straightforward, because when the server provides the message and the encryption result, we also know the key since it’s provided by us. To recover the IV, we can simply connect to the server, then decrypt the given encryption result with our input key, and finally xor it with the message.
After recovering the IV, the next step is to figure out how we can find 4 different keys that produce the same encryption result for the same input. Upon searching about the TEA cipher on Google, we found a paper which explains that the key of the TEA cipher can be defined as:
$$
K = K_0 || K_1 || K_2 || K_3
$$
If we flip the most significant bits (MSBs) of both $K_0$ and $K_1$, or both $K_2$ and $K_3$, we end up with a different key that produces the same encryption result. This indicates that we can start by generating a random key and then create 4 pairs of keys as follows:
The original key.
A key with the MSBs of both $K_0$ and $K_1$ flipped.
A key with the MSBs of both $K_2$ and $K_3$ flipped.
A key where the MSBs of all $K_i$ are flipped.
Below is the full script used to implement the above strategy:
You drop to the ground as a voltaic mist of energy surrounds you; within it are the Aranaya, reflections of your emotions that break into the physical world from the spiritual realm. Love, hate, pain and more writhe and dance before your eyes in an endless storm. As one tears into your soul, a lightning bolt strikes your inner being and the emotion remoulds into another. Startled and wide-eyed, you recognise an undeniable truth: they are all reflections of one another, an ecosystem of your being that you could lose forever. Consciousness leaves you as the psychedelic show whirls on. To retain your self, you must brave the storm: a cyclone of patterns, an infinitude of permutations.
Initial Analysis
In this challenge, we were given two files named source.py and output.txt.
fromCrypto.CipherimportAESfromCrypto.Util.PaddingimportpadfromCrypto.Util.numberimportlong_to_bytesfromhashlibimportsha256fromrandomimportshufflefromsecretimporta,b,FLAGclassPermutation:def__init__(self,mapping):self.length=len(mapping)assertset(mapping)==set(range(self.length))# ensure it contains all numbers from 0 to length-1, with no repetitionsself.mapping=list(mapping)def__call__(self,*args,**kwargs):idx,*_=argsassertidxinrange(self.length)returnself.mapping[idx]def__mul__(self,other):ans=[]foriinrange(self.length):ans.append(self(other(i)))returnPermutation(ans)def__pow__(self,power,modulo=None):ans=Permutation.identity(self.length)ctr=selfwhilepower>0:ifpower%2==1:ans*=ctrctr*=ctrpower//=2returnansdef__str__(self):returnstr(self.mapping)defidentity(length):returnPermutation(range(length))x=list(range(50_000))shuffle(x)g=Permutation(x)print('g =',g)A=g**aprint('A =',A)B=g**bprint('B =',B)C=A**bassertC.mapping==(B**a).mappingsec=tuple(C.mapping)sec=hash(sec)sec=long_to_bytes(sec)hash=sha256()hash.update(sec)key=hash.digest()[16:32]iv=b"mg'g\xce\x08\xdbYN2\x89\xad\xedlY\xb9"cipher=AES.new(key,AES.MODE_CBC,iv)encrypted=cipher.encrypt(pad(FLAG,16))print('c =',encrypted)
The challenge is akin to the Diffie-Hellman key exchange but operates within a Permutation Group instead. The output.txt file provides us with g, A, B, and c.
The task is to discover the private key, either a or b, enabling us to generate C and use it to decrypt the encrypted flag.
Solution
First, we should load the given g, A, and B, and experiment with them. I prefer using Sage for debugging in such challenges because of its convenience. Let’s start by converting the list to Permutations and PermutationGroup in Sage.
fromCrypto.CipherimportAESfromCrypto.Util.PaddingimportpadfromCrypto.Util.numberimportlong_to_bytesfromhashlibimportsha256out=open('output.txt').read()exec(out)print(len(g))print(len(A))print(len(B))a=Ab=B# sage permutations doesn't allow 0, so we can simply increase all of it :Dforiinrange(50_000):g[i]+=1a[i]+=1b[i]+=1V=Permutations(50_000)G=V(g)A=V(a)B=V(b)PG=PermutationGroup([G])
Now, this is a discrete log problem, where given g and A, we need to find a so that g**a = A. Let’s check the group order first.
1
2
order=PG.order()print(f'{order= }')
As you can see, the order is 3311019189498977856900. Let’s check whether this can be factorize or not.
Notably, the order of the group is quite smooth, allowing the potential application of the Pohlig-Hellman algorithm to deduce the private key a. For a detailed explanation, refer to this resource. In summary, this strategy involves simplifying the discrete logarithm problem to a smaller subgroup, where finding the discrete log is feasible. Subsequently, the findings from these smaller subgroups can assist in reconstructing the accurate private key using the Chinese Remainder Theorem.
Below is the script I used to solve this challenge:
fromCrypto.CipherimportAESfromCrypto.Util.PaddingimportpadfromCrypto.Util.numberimportlong_to_bytesfromhashlibimportsha256out=open('output.txt').read()exec(out)print(len(g))print(len(A))print(len(B))a=Ab=B# sage permutations doesn't allow 0, so we can simply increase all of it :Dforiinrange(50_000):g[i]+=1a[i]+=1b[i]+=1V=Permutations(50_000)G=V(g)A=V(a)B=V(b)PG=PermutationGroup([G])order=PG.order()print(f'{order= }')# Order is smooth, so we can do Pohlig-Hellman :)primes=[2^2,3^3,5^2,7,11,13,23^2,47,53,101,149,163,379]dlogs=[]forfacinprimes:print(f'===')print(f'{fac= }')t=int(order)//int(fac)GG=G**tAA=A**t# Subgroup is smaller, so we can easily bruteforce it (and do CRT later)print(f'Start bf...')fordloginrange(fac):print(f'Try {dlog}...')test=GG**dlogiftest==AA:# found!print(f'Found!!!')dlogs+=[dlog]breakprint("factor: "+str(fac)+", Discrete Log: "+str(dlog))#calculates discrete logarithm for each prime orderprint(f'===')print(f'{dlogs= }')priv_a=crt(dlogs,primes)assertA==G**priv_aC=B**priv_a# Restore back to permutations starting from 0list_c=[x-1forxinlist(C)]sec=tuple(list_c)sec=hash(sec)sec=long_to_bytes(sec)hash=sha256()hash.update(sec)key=hash.digest()[16:32]iv=b"mg'g\xce\x08\xdbYN2\x89\xad\xedlY\xb9"cipher=AES.new(key,AES.MODE_CBC,iv)msg=cipher.decrypt(c)print(msg)
Flag: HTB{w3lL_n0T_aLl_gRoUpS_aRe_eQUaL_!!}
Partial Tenacity [medium]
Description
You find yourself in a labyrinthine expanse where movement is restricted to forward paths only. Each step presents both opportunity and uncertainty, as the correct route remains shrouded in mystery. Your mission is clear: navigate the labyrinth and reach the elusive endpoint. However, there’s a twist—you have just one chance to discern the correct path. Should you falter and choose incorrectly, you’re cast back to the beginning, forced to restart your journey anew. As you embark on this daunting quest, the labyrinth unfolds before you, its twisting passages and concealed pathways presenting a formidable challenge. With each stride, you must weigh your options carefully, considering every angle and possibility. Yet, despite the daunting odds, there’s a glimmer of hope amidst the uncertainty. Hidden throughout the labyrinth are cryptic clues and hints, waiting to be uncovered by the keen-eyed. These hints offer glimpses of the correct path, providing invaluable guidance to those who dare to seek them out. But beware, for time is of the essence, and every moment spent deliberating brings you closer to the brink of failure. With determination and wit as your allies, you must press onward, braving the twists and turns of the labyrinth, in pursuit of victory and escape from the labyrinth’s confounding embrace. Are you tenacious enough for that?
Initial Analysis
In this challenge, we were given a quite simple source code.
To summarize, we were provided with only the odd digits of p and the even digits of q. With this information, we need to find a way to recover p and q.
Solution
The approach I chose involves a sort of brute-force method combined with backtracking. To illustrate, consider the following scenario.
1
2
3
4
5
last_digit only
3_4_1 <- p
_9_5_ <- q
---------- x
2117357569 <- n
Upon careful observation, we can identify a relationship that can be derived. Below is the illustration if we were to perform the multiplication manually.
With this equation in mind, we can code our Depth-First Search (DFS) strategy as follows:
At the current digit, generate all possible combinations of the missing digits.
Then, for each of these possible combinations,
Insert it into the equation derived above and check:
If the result modulo 10 matches the known $n_i$ digit, this indicates a possible combination, so store it.
If the result modulo 10 does not match the known $n_i$ digit, skip it.
If the list of possible combinations has more than 0 items, we can proceed to the next digit.
If there are no possible combinations, something was wrong with our choice of digits. We need to backtrack to the previous digit and try a different combination.
Below is the implementation of the strategy described above (with detailed comments). After recovering p and q, decrypting the flag becomes straightforward.
fromCrypto.PublicKeyimportRSAfromCrypto.CipherimportPKCS1_OAEPfromCrypto.Util.numberimport*# -1 == unknown digitori_p_digits=[1,-1,5,-1,1,-1,4,-1,4,-1,1,-1,4,-1,7,-1,3,-1,3,-1,5,-1,7,-1,1,-1,3,-1,6,-1,1,-1,5,-1,2,-1,9,-1,8,-1,5,-1,2,-1,1,-1,6,-1,9,-1,8,-1,0,-1,3,-1,9,-1,7,-1,5,-1,2,-1,5,-1,5,-1,9,-1,1,-1,3,-1,0,-1,5,-1,8,-1,7,-1,5,-1,0,-1,9,-1,4,-1,2,-1,8,-1,8,-1,7,-1,3,-1,8,-1,8,-1,2,-1,0,-1,6,-1,9,-1,9,-1,0,-1,6,-1,9,-1,2,-1,7,-1,1,-1,6,-1,7,-1,4,-1,0,-1,2,-1,2,-1,1,-1,6,-1,7,-1,9,-1,0,-1,2,-1,6,-1,4,-1,3]ori_q_digits=[-1,1,-1,5,-1,6,-1,2,-1,4,-1,3,-1,4,-1,2,-1,0,-1,0,-1,5,-1,7,-1,7,-1,4,-1,1,-1,6,-1,6,-1,5,-1,2,-1,5,-1,0,-1,2,-1,4,-1,6,-1,0,-1,8,-1,0,-1,6,-1,7,-1,4,-1,2,-1,6,-1,5,-1,5,-1,7,-1,0,-1,9,-1,3,-1,5,-1,6,-1,7,-1,3,-1,9,-1,2,-1,6,-1,5,-1,2,-1,7,-1,2,-1,3,-1,1,-1,7,-1,5,-1,3,-1,0,-1,1,-1,6,-1,1,-1,5,-1,4,-1,2,-1,2,-1,3,-1,8,-1,4,-1,5,-1,0,-1,8,-1,2,-1,7,-1,4,-1,2,-1,6,-1,9,-1,3,-1,0,-1,5,-1]assertlen(ori_p_digits)==len(ori_q_digits)# Reverse the list, so the first least significant digit will be in the start of the arrayori_p_digits=ori_p_digits[::-1]ori_q_digits=ori_q_digits[::-1]# This will be used to store the temporary digits that we found during doing DFS.# There might be modification during backtracking.p_digits=ori_p_digitsq_digits=ori_q_digitsn=118641897764566817417551054135914458085151243893181692085585606712347004549784923154978949512746946759125187896834583143236980760760749398862405478042140850200893707709475167551056980474794729592748211827841494511437980466936302569013868048998752111754493558258605042130232239629213049847684412075111663446003defdfs(curr_i,carry):# Get n_itarget=int(str(n)[::-1][curr_i])# We already find all the digitsifcurr_i==len(str(n)):returnTrue# If the curr_i is beyond the length of the p_digits and q_digits,# it is guaranteed that the validitiy of our digits only based on the previous carryifcurr_i==len(p_digits)andcurr_i==len(q_digits):returncarry==target# Get the current digitpossible_combi=[]# (p, q, carry)p_digit=p_digits[curr_i]q_digit=q_digits[curr_i]iter_p=[p_digit]iter_q=[q_digit]# If in the curr_i p digit is unknown, put all the possible digits (0..9)ifiter_p[0]==-1:iter_p=[num_pfornum_pinrange(10)]# If in the curr_i p digit is unknown, put all the possible digits (0..9)ifiter_q[0]==-1:iter_q=[num_qfornum_qinrange(10)]# Execute the equation of calculating n_i digit that we derive before.fornum_piniter_p:fornum_qiniter_q:res=carryforiterationinrange(curr_i+1):i=curr_i-iterationj=iterationcurr_p=p_digits[i]ifi==curr_i:curr_p=num_pcurr_q=q_digits[j]ifj==curr_i:curr_q=num_qres+=curr_p*curr_q# If the last digit is same as n_i digit, that means this is a possible combinationifres%10==target:possible_combi.append((num_p,num_q,res//10))# This means we failed to found at least one possible combinationiflen(possible_combi)==0:returnFalse# Now, for each combination that we found, employ DFS, where we will# use the found digit as the temporary digit, then move to the next digit# dfs function will backtrack if in the future it failed to find any possible combinationforcombiinpossible_combi:p_digits[curr_i]=combi[0]q_digits[curr_i]=combi[1]is_valid=dfs(curr_i+1,combi[2])ifnotis_valid:p_digits[curr_i]=ori_p_digits[curr_i]q_digits[curr_i]=ori_q_digits[curr_i]# Start the DFS :)dfs(0,0)# DFS is finished, means that we already recover all the missing digitsp=int(''.join([str(x)forxinp_digits[::-1]]))q=int(''.join([str(x)forxinq_digits[::-1]]))assertp*q==nct=bytes.fromhex('7f33a035c6390508cee1d0277f4712bf01a01a46677233f16387fae072d07bdee4f535b0bd66efa4f2475dc8515696cbc4bc2280c20c93726212695d770b0a8295e2bacbd6b59487b329cc36a5516567b948fed368bf02c50a39e6549312dc6badfef84d4e30494e9ef0a47bd97305639c875b16306fcd91146d3d126c1ea476')e=65537phi=(p-1)*(q-1)d=inverse(e,phi)key=RSA.construct((n,e,d))cipher=PKCS1_OAEP.new(key)flag=cipher.decrypt(ct)print(f'{flag= }')
Flag: HTB{v3r1fy1ng_pr1m3s_m0dul0_p0w3rs_0f_10!}
Arranged [medium]
Description
Noiselessly turning the corner, you see before you two men. In a former life, the two were best friends; pressure and pain has reduced them to mere animals, single-minded automatons devoid of emotion or feeling. The sickening, grim reality of the competition is that it is what it is designed to do, and none escape the inevitable doom. You raise your bow and bury two arrows into their chests; given their past, it was the least you could do. Death would be kinder to them than life.
Initial Analysis
In this challenge, we were given a file named sage.py and output.txt.
fromCrypto.CipherimportAESfromCrypto.Util.PaddingimportpadfromCrypto.Util.numberimportlong_to_bytesfromhashlibimportsha256fromsecretimportFLAG,p,b,priv_a,priv_bF=GF(p)E=EllipticCurve(F,[726,b])G=E(926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367,4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253)A=G*priv_aB=G*priv_bprint(A)print(B)C=priv_a*BassertC==priv_b*A# now use it as shared secretsecret=C[0]hash=sha256()hash.update(long_to_bytes(secret))key=hash.digest()[16:32]iv=b'u\x8fo\x9aK\xc5\x17\xa7>[\x18\xa3\xc5\x11\x9en'cipher=AES.new(key,AES.MODE_CBC,iv)encrypted=cipher.encrypt(pad(FLAG,16))print(encrypted)
Looking at the challenge, our objective is to somehow recover priv_a, allowing us to compute C and use it as the AES key. This simulates the implementation of the Diffie-Hellman Key Exchange.
Understanding the task at hand, let’s think how to craft the solution.
Solution
First, note that we don’t know the values of $b$ and $p$ yet, so our initial task is to ascertain these values. We have two pairs of points, A and B.
We’ll begin by attempting to recover the $p$ value. An elliptic curve is typically represented as $y^2 = x^3 + ax + b \mod p$. Given two points, we have the following 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}
$$
Knowing $a$, $y$, and $x$, subtracting one equation from the other eliminates $b$:
Now, we know that $(y_1^2 - y_2^2) - ((x_1^3 - x_2^3) + a \cdot (x_1-x_2))$ is a multiple of $p$. Our next step is to factor this expression and check for any prime numbers, as $p$ is prime. Below is the initial script I used to first recover that value.
The result of the $kp$ that I found is 159876543767731641091481517970757427845475606054901986278343644849685033675014920747838399719911540214497783751629486726130353637225421487102773147275840819453085461179225204956109588744706616404640700114680030501842814692877925213179751117553624678716957461607736397000873235881970428009381374977362878056793806499363109868757164944583438598058337581715444472442097008263247672258671662471244150568581060911658678179702219608062901555447642033897327594285850816
If we input this number into factordb, we can see that one of its factors is a good candidate for $p$, which is 811640204116707417092117962115673978365477767365408659433165386030330695774965849821512765233994033921595018695941912899856987893397852151975650548637533
Now that we have recovered $p$, we can easily find the $b$ value:
$$
b = y_1^2 - (x_1^3 + ax_1) \mod p
$$
With the curve parameters fully recovered, let’s explore further. This is a discrete logarithm problem, so we start by checking its order.
We find that the order is 6811640204116707417092117962115673978365477767365408659433165386030330695774842975950864518820891774127689003723319868798748651155450639754051764297493817
Next, we check if this order can be factorized (with the help of factordb again).
Indeed, the order can be factorized, and it has 4 small prime factors: $3$, $11$, $11083$, and $158891976157$. We can attempt the Pohlig-Hellman algorithm. For a detailed explanation, refer to this resource. In summary, this strategy involves reducing the discrete logarithm problem to smaller subgroups, where finding the discrete log is manageable. Then, the findings from these smaller subgroups can be combined to reconstruct the accurate private key using the Chinese Remainder Theorem.
Let’s proceed with that approach and check if we can successfully find the correct priv_a.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
G=E(926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367,4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253)A=E(x1,y1)B=E(x2,y2)primes=[3,11,11083,158891976157]dlogs=[]order=6811640204116707417092117962115673978365477767365408659433165386030330695774842975950864518820891774127689003723319868798748651155450639754051764297493817forfacinprimes:t=int(order)//int(fac)dlog=discrete_log(t*A,t*G,operation="+")dlogs+=[dlog]print("factor: "+str(fac)+", Discrete Log: "+str(dlog))#calculates discrete logarithm for each prime orderpriv_a=crt(dlogs,primes)assertA==G*priv_a
Executing the above code confirms that the assertion is True, meaning we have successfully recovered priv_a.
After obtaining priv_a, we can calculate C and use it as the AES key to decrypt the flag. Below is the full script to solve this challenge (with the assistance of SageMath):
x1=6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599399265706997y1=2456156841357590320251214761807569562271603953403894230401577941817844043774935363309919542532110972731996540328492565967313383895865130190496346350907696x2=4226762176873291628054959228555764767094892520498623417484902164747532571129516149589498324130156426781285021938363575037142149243496535991590582169062734y2=425803237362195796450773819823046131597391930883675502922975433050925120921590881749610863732987162129269250945941632435026800264517318677407220354869865a=726kp=((x1^3-x2^3)+a*(x1-x2))-(y1^2-y2^2)p=6811640204116707417092117962115673978365477767365408659433165386030330695774965849821512765233994033921595018695941912899856987893397852151975650548637533b=(y1^2-x1^3-a*x1)%pF=GF(p)E=EllipticCurve(F,[726,b])order=E.order()print(order)G=E(926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367,4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253)A=E(x1,y1)B=E(x2,y2)primes=[3,11,11083,158891976157]dlogs=[]forfacinprimes:t=int(order)//int(fac)dlog=discrete_log(t*A,t*G,operation="+")dlogs+=[dlog]print("factor: "+str(fac)+", Discrete Log: "+str(dlog))#calculates discrete logarithm for each prime orderpriv_a=crt(dlogs,primes)assertA==G*priv_aC=priv_a*Bsecret=C[0]fromCrypto.CipherimportAESfromCrypto.Util.PaddingimportpadfromCrypto.Util.numberimportlong_to_bytesfromhashlibimportsha256hash=sha256()hash.update(long_to_bytes(int(secret)))key=hash.digest()[16:32]iv=b'u\x8fo\x9aK\xc5\x17\xa7>[\x18\xa3\xc5\x11\x9en'cipher=AES.new(key,AES.MODE_CBC,iv)ct=b'V\x1b\xc6&\x04Z\xb0c\xec\x1a\tn\xd9\xa6(\xc1\xe1\xc5I\xf5\x1c\xd3\xa7\xdd\xa0\x84j\x9bob\x9d"\xd8\xf7\x98?^\x9dA{\xde\x08\x8f\x84i\xbf\x1f\xab'flag=cipher.decrypt(ct)print(f'{flag= }')
Flag: HTB{0rD3r_mUsT_b3_prEs3RveD_!!@!}
Blunt [easy]
Description
Valuing your life, you evade the other parties as much as you can, forsaking the piles of weaponry and the vantage points in favour of the depths of the jungle. As you jump through the trees and evade the traps lining the forest floor, a glint of metal catches your eye. Cautious, you creep around, careful not to trigger any sensors. Lying there is a knife - damaged and blunt, but a knife nonetheless. You’re not helpless any more.
Initial Analysis
In this challenge, we were given a source code named source.py and output.txt.
fromCrypto.CipherimportAESfromCrypto.Util.PaddingimportpadfromCrypto.Util.numberimportgetPrime,long_to_bytesfromhashlibimportsha256fromsecretimportFLAGimportrandomp=getPrime(32)print(f'p = 0x{p:x}')g=random.randint(1,p-1)print(f'g = 0x{g:x}')a=random.randint(1,p-1)b=random.randint(1,p-1)A,B=pow(g,a,p),pow(g,b,p)print(f'A = 0x{A:x}')print(f'B = 0x{B:x}')C=pow(A,b,p)assertC==pow(B,a,p)# now use it as shared secrethash=sha256()hash.update(long_to_bytes(C))key=hash.digest()[:16]iv=b'\xc1V2\xe7\xed\xc7@8\xf9\\\xef\x80\xd7\x80L*'cipher=AES.new(key,AES.MODE_CBC,iv)encrypted=cipher.encrypt(pad(FLAG,16))print(f'ciphertext = {encrypted}')
Based on the above source code, seems like it try to implement Diffie-Hellman key exchange. The goal here is we need to recover the private key a, so that we can calculate C.
Solution
Observed that discrete log is hard, but the value that is used here is too small. We can easily find the discrete log with the help of sagemath, so that we can recover C (which is used as the AES key), and we can decrypt the flag. Below is the script that I use to decrypt it.
Locked within a cabin crafted entirely from ice, you’re enveloped in a chilling silence. Your eyes land upon an old notebook, its pages adorned with thousands of cryptic mathematical symbols. Tasked with deciphering these enigmatic glyphs to secure your escape, you set to work, your fingers tracing each intricate curve and line with determination. As you delve deeper into the mysterious symbols, you notice that patterns appear in several pages and a glimmer of hope begins to emerge. Time is flying and the temperature is dropping, will you make it before you become one with the cabin?
Initial Analysis
In this chalenge we were given a source code named source.py and output.txt.
importosfromsecretimportFLAGfromCrypto.Util.PaddingimportpadfromCrypto.Util.numberimportbytes_to_longasb2l,long_to_bytesasl2bfromenumimportEnumclassMode(Enum):ECB=0x01CBC=0x02classCipher:def__init__(self,key,iv=None):self.BLOCK_SIZE=64self.KEY=[b2l(key[i:i+self.BLOCK_SIZE//16])foriinrange(0,len(key),self.BLOCK_SIZE//16)]self.DELTA=0x9e3779b9self.IV=ivifself.IV:self.mode=Mode.CBCelse:self.mode=Mode.ECBdef_xor(self,a,b):returnb''.join(bytes([_a^_b])for_a,_binzip(a,b))defencrypt(self,msg):msg=pad(msg,self.BLOCK_SIZE//8)blocks=[msg[i:i+self.BLOCK_SIZE//8]foriinrange(0,len(msg),self.BLOCK_SIZE//8)]ct=b''ifself.mode==Mode.ECB:forptinblocks:ct+=self.encrypt_block(pt)elifself.mode==Mode.CBC:X=self.IVforptinblocks:enc_block=self.encrypt_block(self._xor(X,pt))ct+=enc_blockX=enc_blockreturnctdefencrypt_block(self,msg):m0=b2l(msg[:4])m1=b2l(msg[4:])K=self.KEYmsk=(1<<(self.BLOCK_SIZE//2))-1s=0foriinrange(32):s+=self.DELTAm0+=((m1<<4)+K[0])^(m1+s)^((m1>>5)+K[1])m0&=mskm1+=((m0<<4)+K[2])^(m0+s)^((m0>>5)+K[3])m1&=mskm=((m0<<(self.BLOCK_SIZE//2))+m1)&((1<<self.BLOCK_SIZE)-1)# m = m0 || m1returnl2b(m)if__name__=='__main__':KEY=os.urandom(16)cipher=Cipher(KEY)ct=cipher.encrypt(FLAG)withopen('output.txt','w')asf:f.write(f'Key : {KEY.hex()}\nCiphertext : {ct.hex()}')
Taking a look at the challenge, we were given the KEY and the ciphertext. That means the challenge here is we only need to create a decrypt function, because they gave us the KEY.
Solution
The above source code is trying to implement TEA. We can simply follow the wikipedia example (or just ask ChatGPT to made it for us :D). Below is the function that we can use to decrypt it.
Surrounded by an untamed forest and the serene waters of the Primus river, your sole objective is surviving for 24 hours. Yet, survival is far from guaranteed as the area is full of Rattlesnakes, Spiders and Alligators and the weather fluctuates unpredictably, shifting from scorching heat to torrential downpours with each passing hour. Threat is compounded by the existence of a virtual circle which shrinks every minute that passes. Anything caught beyond its bounds, is consumed by flames, leaving only ashes in its wake. As the time sleeps away, you need to prioritise your actions secure your surviving tools. Every decision becomes a matter of life and death. Will you focus on securing a shelter to sleep, protect yourself against the dangers of the wilderness, or seek out means of navigating the Primus’ waters?
Initial Analysis
In this challenge, we were given a file named source.py and output.txt.
The problem with the above encryption is that the n is actually a prime number, not the result of multiplication two prime numbers. Due to this, the private key d recovery is quite straightforward.
Solution
To calculate the private key d, we can simply calculate it by doing inverse_mod(e, n-1). After recovering d, we can simply decrypt the c by doing pow(c,d,n).
Weak and starved, you struggle to plod on. Food is a commodity at this stage, but you can’t lose your alertness - to do so would spell death. You realise that to survive you will need a weapon, both to kill and to hunt, but the field is bare of stones. As you drop your body to the floor, something sharp sticks out of the undergrowth and into your thigh. As you grab a hold and pull it out, you realise it’s a long stick; not the finest of weapons, but once sharpened could be the difference between dying of hunger and dying with honour in combat.
Initial Analysis
In this challenge, we were given a file named source.py and output.txt
You find yourself trapped inside a sealed gas chamber, and suddenly, the air is pierced by the sound of a distorted voice played through a pre-recorded tape. Through this eerie transmission, you discover that within the next 15 minutes, this very chamber will be inundated with lethal hydrogen cyanide. As the tape’s message concludes, a sudden mechanical whirring fills the chamber, followed by the ominous ticking of a clock. You realise that each beat is one step closer to death. Darkness envelops you, your right hand restrained by handcuffs, and the exit door is locked. Your situation deteriorates as you realise that both the door and the handcuffs demand the same passcode to unlock. Panic is a luxury you cannot afford; swift action is imperative. As you explore your surroundings, your trembling fingers encounter a torch. Instantly, upon flipping the switch, the chamber is bathed in a dim glow, unveiling cryptic letters etched into the walls and a disturbing image of a Roman emperor drawn in blood. Decrypting the letters will provide you the key required to unlock the locks. Use the torch wisely as its battery is almost drained out!
Initial Analysis
In this challenge, we were given a file named source.py and output.txt
fromsecretimportFLAGfromrandomimportrandintdefto_identity_map(a):returnord(a)-0x41deffrom_identity_map(a):returnchr(a%26+0x41)defencrypt(m):c=''foriinrange(len(m)):ch=m[i]ifnotch.isalpha():ech=chelse:chi=to_identity_map(ch)ech=from_identity_map(chi+i)c+=echreturncwithopen('output.txt','w')asf:f.write('Make sure you wrap the decrypted text with the HTB flag format :-]\n')f.write(encrypt(FLAG))
The encryption here is quite straightforward, where it encrypt the text by shifting it based on the current character index.
Solution
We can easily make the decrypt method which try to shift back the encrypted character by its position. Below is the script that I used to solve this challenge: