HackZone IX CTF: Likkrid’s Crypto writeups

Hello again, here we are at another edition of HackZone HZIX. Today, I am happy to share with you 2 writeups for Cryptography challenges that I prepared for the CTF. This is Likkrid, and this will be the author’s writeup, Let’s go ..

BabeRSA [10 Solves-449 Points]

This challenge is intended to be the typical easy “BabyRSA” challenge. Python source code is provided and it seems quite over-complicating a straightforward logic (or maybe it’s hiding a deadly mistake too 😈). Let’s break it down.

“keys” function:

This functions creates keys as follows:

• Generates 2 1024-bits prime numbers p, q and calculates modulus = p * q
• Generates 3 random numbers (b, rand1, rand2) and calculates:

figure 1.1

• Based on Fermat’s little theorem we have:

figure 1.2

• Generates another 2 random numbers, modulo the “modulus”, rand_b1 and rand_b2 and return private and public keys.

“encrypt” function:

• This function simply returns two parts of the ciphertext:

figure 1.3

“decrypt” function:

This part was omitted from the source code because:

• You can solve this problem with a one liner due to parameters “over-sharing” in the public key (sharing is caring 👀😝)
• Based on figure 1.3, it is quite obvious that solving the system of 2 linear congruences will provide the plaintext:

figure 1.4: Solving for x retrieves the flag

Solutions:

The “Cheesy” solution..

• Based on figure 1.3 we have:

figure 1.5

The modular inverse exists since, “by design”:

GCD(X, modulus) = GCD(Y, modulus) = 1

The “Smart” solution:

• Based on figure 1.2 we have:

figure 1.6

The first relation is based on Fermat’s little theorem, the second one “most likely (∗)” stands true (else we are facing a corner case where both partial ciphers are congruent to the modulus and can be read without factoring the modulus). We recover p with the GCD, then we use the Chinese remainder theorem to solve the system in figure 1.4.

That was mainly it for the first challenge, fairly easy but still a highly valuable one. Kudos to those who smashed this challenge with the cheesy solution 🧀

My ECC For Dummies [3 Solves-498 Points]

This Challenge provides us with a source code of a cryptosystem and a link to a paper. After reading this paper and, keeping in mind that the cryptosystem used is a variant of ElGamal ECC , we conclude that we are dealing with MV-ElGamal.

After some Google-Fu and source code exploration, We can summarize the key generation, encryption and decryption steps as follows:

figure 2.1: MV-ElGamal

The implementation seems legit and sticks to the description so let’s dive deeper and specific aspects of the source code.

The Flag <Plain_message> is divided in two parts and converted to integers and both are smaller than <p> so we have no data loss in the encryption process. But what is this ID variable 🧐 Seems sus..

It seems like a unique identifier for the encryption but it is tightly related to the second part of the flag (the bitwise shift operation is equivalent to powers of 2) so we have:

figure 2.2

This is a very bad choice for the function, because it introduces a simple modular e’th root problem. We can calculate successive square roots modulo the prime <p> for all possible powers of 2 and we should recover the m2 value.

Okay why does the author take us in this direction and how can we efficiently use the m2 value to recover the whole flag?

Let’s get back to the figure 1.2 and focus on the S point’s coordinates used to craft the ciphertext components, we have the following:

figure 2.3

We know that the point S satisfies the curve equations, so we can inject the S coordinates in the equation:

figure 2.4

We end up with a polynomial in m1 and m2 so if we know one of them we can recover the second part:

• In our case, we have the m2 so we can to solve the cubic root modulo <p> and we should recover the first part of the flag associated with one of the roots.
• I decided to use sage for this specific use-case because it felt easier to me!! We ended up solving modular square root for pow(2,20)

figure 2.5

• Hopefully this was of any help for you if you had fun participating in HackZone IX, struggled to solve one of this crypto challenges or just seeking a hint to dive deeper into the details. You can find challenges source code and solvers here.

If you made it this far, thank you for your interest in this humble Crypto writeup. Looking forward to hearing from you about topics/ideas/feedback regarding this post. Feel free to reach out if you found any other/unintended solutions and as usual stay safe and hack carefully 🧡🧡

Used embed.fun to embed all the beautiful formulas in this writeup !!