Hack.lu CTF 2021, Silver Water Industries Writeup

Analyzing the code

For this challenge we are provided with the server network address and the source code:

Let’s first look at the main function. It first generates some two values N and token. Then it prints us the N and each byte of the token encrypted by function encryptByte(b, N). After that the program waits for our input and if the value of input is equal to token we get the flag. So we need to decrypt the ciphertext we are given.

Now, let’s go deeper and see what functions getN() and encryptByte() do.

The genN() function generates two 64-bit prime numbers p, q and returns their multiplication.

But note that those prime numbers have specific properties:

Right now it is not clear why primes must have these properties, but obviously they are important for the cryptosystem.

Now let’s look at the encryptByte()

This function first creates new variable z = -1 and an array of integers of size 8.

Next, in the for loop it performs the following steps 8 times:

1. Take one bit of the provided byte
2. Generate value x with function genX(N).
3. Set x = x^2 mod N.
4. If bit is 1 set x = x * z mod N.
5. Put x into the array enc.

After the for loop the function returns enc, which is an array of 8 integers.

The function genX() just generates the random value x such that GCD(x, N) = 1.

Summarizing the cryptosystem

Now we can describe the cryptosystem we need to brake. First of all note that it encrypts each bit of the plain text individually. For every bit b in the plain text we have the number in the ciphertext c such that:

For some random value of x. So this is a basically the Goldwasser-Micali cryptosystem. This cryptosystem is based on the following problem.

Goldwasser-Micali cryptosystem problem

Suppose that we have c and N, where N is composite. There is no way to determine whether c is a quadratic residue modulo N, i.e., there is no way to determine whether there exists a such that

The thing is that c is a quadratic residue modulo a composite number if and only if it is a quadratic residue modulo every prime factor of N. If we knew prime factors of N we could calculate Legendre symbol for every prime p to determine if c is a quadratic residue modulo p

And if Legendre symbol equals to 1 for every prime factor of N than c is a quadratic residue modulo N. Even better, we could calculate Euler’s criterion for each prime, that says that

But we don’t know prime factors of N. (Actually, because primes are of size 64 bit we can easily factor N. That’s actually how I solved the challenge in the first place, but let’s move on to see the actual cryptosystem failure)

There is also a Jacobi symbol modulo N. If Jacobi symbol equals -1 then c is definitely not a quadratic residue modulo N. However, if it equals to 1, then we still can’t tell for sure if c is a quadratic residue modulo N.

Cryptosystem failure

Now let’s consider the encryption scheme again to see where the system fails

If the plaintext bit equals to 0 then we add quadratic residue modulo N to the ciphertext. Jacobi symbol for this value will return 1 and cryptanalyst will not have a way to tell if this value is a quadratic residue modulo N.

Now, what if the plaintext bit equals to 1 then we add quadratic residue modulo N multiplied with (-1) to the ciphertext. What will Jacobi symbol be equal to for this value? For original Goldwasser-Micali cryptosystem we should’ve picked multiplier a such that it is a quadratic nonresidue modulo p and q. This would yield Jacobi symbol to be equal to 1, because

But we have the problem with (-1). Remember that p and q have properties

This yields

but

Thus,

And this is a major failure, because we want it to be 1. Using this failure we can easily decrypt ciphertext. All we need to do is to compute Jacobi symbol for every ciphertext number modulo N. If it equals to 1 then we add 0 to decrypted text. If it equals to -1 then we add 1 to decrypted text.

The code for the exploit:

Also there is a solution I made in the first place using the factorization and Euler’s criterion: