This is my writeup and walkthrough for all the crypto challenges from the final competition
After we have been qualified at the online filtration phase. We attended Arab Security Wargames on-site on 12th of Sep and my team Revers3c got the 1st place (The Titan). Actually, the challenges were so awesome and we had a lot of fun with them. As in my little knowledge in Cryptography and loving the math behind it, there was 6 cool crypto challenges among all 5 categories, and I’ll go through explaining each one of them.
This was the first and also simple challenge, we were given an encryption script encrypt.py and cipher.txt that contains the base64 of the data. So let’s look at the script to see what it does.
The script reads the flag, iterates over it charachter by charachter, then performs sha512(md5(sha512(char))) on each one, and finally encodes the result with base64 after reversing it.
Solution
Hopefully, this is a well-known attack called message signing, so we can encrypt a specific value and check if it is equal to the encrypted one. If so then this value is what we want otherwise, try another one. We can see the length of each character hashing is 128, so I wrote a script to try every possible character and print the flag.
The flag: ACSWG{Brute_F@RCE_1S_G00D_1337_7331_3317_3137_}
2. Retrive (300 points)
Alice intercepted a part of a plaintext but a there’s a small part he could not intercept . can u help alice ?
Intercepted part : ASCWG{y0u_N33d_t0Brut3_F0rce_th3
This one is a pretty straightforward, given retrive.py and c.txt that contains n, e, c. And the script wants us to brute force the last few bytes of the flag.
Solution
Also, this is the same attack as the above but with a bigger value. At first, I thought if the last bytes more than 6 characters then the search space is not feasible since we’ll try all the possible values of the last part. So later on, I realized that it’s an easy one so let’s start with 3 bytes and the last one is known.
And it prints the flag: ASCWG{y0u_N33d_t0_Brut3_F0rce_th3_k3y}
3. Hybrid (600 points)
This challenge is a bit tricky, also with 2 files encrypt.py contains the encryption code and data.txt with n, e, c. So let’s look at the script.
Analyzing the Script
The script reads the flag and the Euler Totient from the files, then it computes the private keyd and converts the value into a string format. After that, it performs bitwise xor for every character of the flag with the current digit value of private key. And if the length of the flag exceeds the length of the d, it starts from the beginning.
So, our goal here is to find the phi the Euler Totient, so first I always check if the modulus is weak so we can factor it and get the totient. Let’s start with Sage to see if it’s able to find it.
And after a second, I got the Totient. Now, let’s calculate our private key d and perform the same process of the encryption since it was an xor.
And here’s the flag: ASCWG{RSA_W1TH_X0R_M@Y_B3_S3CURE_?_!_!}
4. Robin Hood (600 points)
This one is harder than the above, this time we were given 3 files Robin.py the encryption script, public.txt contains the public modulus and flag.enc that contains the encrypted flag. Let’s look at the script to see this time what is it.
Analyzing Generate_Key
The script contains Generate_Key function that takes one argument, and calculates some p, q the primes for our modulus. And performs the same operation as the previous challenge, but this time with the first computed prime p. So, let’s look at the function and see how it computes the primes.
It takes one parameter k (the number of bits), and generate an odd random number of bit length k, then it computes p and q with some equations and predefined constants vp, vq, c. Honestly, I was stuck a bit at this one and confused about what I should do next. So, after a while, I grabbed my pen and paper, then start writing down the equations.
Note: Usually, in any competitions, you have to start using a pen and a paper to figure out how things work and see the whole picture of the problem since our brain is always stuck when things get more complicated especially with math.
Solution
Thereafter, I start realizing there was a quadratic equation of the second degree for each of p and q with 3 unknown variables. And I figure it out, if we multiply both equations, we should get another equation of the fourth degree with one unknown variable. So, I opened Sage and put the equations down to start solving them.
The last equation has only 4 real roots and one of them is the actual r, the random number that had produced the primes. Now, let’s calculate the desired p value and do the same process as before.
An it prints out the flag: ASCWG{R@bin_Crypt@_system_1s_N@T_S3cure_Y@u_C@n_S0lve_1t_By_sympy_Thanks_M@th_:)!!}
Note: There’s an alternative solution by using sympy library in python to do the same calculation, but I prefer using Sage, since it has a lot of mathematical features.
5. Simple RSA (900 points)
The challenge was a brain teaser in the beginning, given one file rsa.py contains both the encryption technique and the output. Let’s look and see what is hidden in that file.
Analyzing The Functions
There are 2 functions adlit and genadlit, and the script generates the actual prime p totally random and q based on the first function and the other prime. After playing arround with the adlit function, the term (2 ** l - 1) is called Mersenne Numbers and also a way to produce a number with all its bits are 1.
So, the adlit function just flips all the bits of x, and this means x + adlit(x) is a constant depending on the bit length of x. Let’s assume len(x) = 10, then x + adlit(x) = 2**10 - 1.
Solution
And from genadlit we know that q = adlit(p) + 31337. Let’s add these two function together p + q = 2**1024 + 31336, then multiply it with p and that produces an equation p*p - (2**1024 + 31336)*p + n = 0 of one unkown variable p.
Surprisingly, the two roots is the actual values of both p and q, thus we can calculate the private key and solve the challenge.
And here’s the flag: ASCWg{1t_1s_Equ_0f_2nd_dgree_n0t_rsa}
6. RSA in Hill (900 points)
This was the last crypto challenge in the compitetion and from its name looks the most hardest one. We were given a file challenge.txt contains n, e, c and a link to website that looks like.
So, The server can decrypt any cipher data except the original one c and prints out This Encrypted Data is BlackListed. After a lot of time thinking about it, I recognized this is chosen ciphertext attack.
Fake Flag
We know from the associative property of the RSA . If we choose an X ** e and multiply with the cipher c like image below, we can submit the value to the server, and the result would be MX where M is the flag.
\[x^e C = x^e M^e = (xM)^e \pmod n \\
xM = (xM)^{ed \pmod \phi} \pmod n\]
Let’s apply that in the decryption process of RSA and replacing the cipher with the modified one. By that, we tricked the server and it won’t able to recognize the ciphertext, but the result is a known to us.
After submitting the value to the server, the result was 768719114996765410378373905275198789078705807516, but this is not the actual flag we should divide that by our number, I chose 2 in my case.
Analyzing Hill Cipher
Now, I convert the value to bytes and I got CSGUOLGIOMXBSFIHODPN and it was all non-sense words. But from the name of the challenge RSA in Hill, maybe it has something with Hill Cipher, I realized that the output has a length of 20 all uppercase. So the key must be of length 4, since 2x2 key matrix, and it is feasible to brute-force the key values with 26**4 = 456976 possible keys.
Note: The following part I used my little experience with numpy library in python in order to perform the matrix operations easily. You can do your own work after analyzing the cipher.
Getting the Keys
We can perform known plaintext attack on the first 4 bytes of the flag ASCW to get all the possible keys. After converting those bytes into 2x2 integer matrix, then apply matrix multiplication with a key. if it is equal to the first 4 bytes of the fake flag CSGU, append the key matrix with modular inverse of 26 to our possible keys.
Getting the Flag
Eventually, we got all the possible keys, let’s try them and search for the known part ASCWG in all the possible decrypted flags.
The flag: ASCWG{RSAWITHKPAHILLL}
Conclusion
In the end, all the challenges were RSA with different attacks and techniques chosen ciphertext, known plaintext, and message signing attacks. During the 8 hours competition, the coolest thing was playing around with some math and equations trying to solve them and getting the flags. I’d like to send my regards to all of my teammates for helping me out and to the organizers for nudging us during the competition. If you need any help understanding any of the explanations above DM me.