Save the world!
How to solve Save the World from We Chall!
Kevin Amado

Comment 
attacks 
20181121 
First of all let’s review the problem statement at
It is year 2018, the world war III is upcoming between USA and China. You are a secret agent working for the USA. The USA Information Gathering Agency gathered three RSA enciphered messages. All messages were originated from the same "clear text message", which is a symmetric key m. With this symmetric key there is a document encrypted. This document contains all the secret information about the newest hightech weapons made in China. This document was symmetrically encrypted with the CSEA (Chinese Super Encryption Algorythm). This algorythm is almost unbreakable.
You know, that the chinese government used RSA to encrypt the symmetric key. Your boss, general Eromzig bought a new supercomputer to factorize the RSA public keys. Scientists say they need 2 weeks to factorize one of the public keys. That’s why he hired you, because he thinks you can break the RSA algorithm in 1 hour. Your mission is to get the symmetric key in decimal format.
The solution is the last 20 digits of the symmetric key m
— WeChall
The RSA encryption equation for a single message is:
C_{i} = pow(m, e_{i}) (mod n_{i}) 
Please note that pow(m, e) denotes exponentiation of m to the power of e, and mod denotes the euclidian division remainder
The parameters that were used to encrypt the message are 300 digits long so they are shown here as n_{i} and c_{i} for simplicity:
first part of public key 
n_{1} 
second part of public key 
e_{1} = 3 
encrypted message sent to him 
c_{1} 
first part of public key 
n_{2} 
second part of public key 
e_{2} = 3 
encrypted message sent to him 
c_{2} 
first part of public key 
n_{3} 
second part of public key 
e_{3} = 3 
encrypted message sent to him 
c_{3} 
Understanding the problem
Since all messages were generated from the same clear text message. Then the main objective is to find a message m that once encrypted yields the message sent to each one of the receivers.
In mathematical language, the problem is to find m that simultaneously solves the equations:
C_{1} = pow(m, 3) (mod n_{1}) 
C_{2} = pow(m, 3) (mod n_{2}) 
C_{3} = pow(m, 3) (mod n_{3}) 
One of the main characteristics of RSA, is that it’s a very strong algorithm, but there are a lot of things one must be aware before implementing an RSA based crypto system. There is no secure RSA in three steps, and we’ll be exploiting the most known vulnerabilities in order to see which one let us solve the challenge.
Low encryption exponent Attack
If we look again at the asymmetric RSA encryption equation, we see that it is being normalized with respect to n_{i}:
C_{i} = pow(m, 3) (mod n_{i}) 
If for some reason someone uses a low exponent (in this case 3), the encryption process may exhibit the following behavior:
pow(m, 3) < n_{i} 
If this is the case, then the asymmetric encryption equation is reduced to:
C_{i} = pow(m, 3) 
And one can easily compute the message as:
m = cubic_root(C_{i}) 
We can adapt this method to our problem
first compute: m_{1} = cubic_root(C_{1}) m_{2} = cubic_root(C_{2}) m_{3} = cubic_root(C_{3}) 
And if we get that the messages are the same for the three receivers:
m_{1} == m_{2} == m_{3} 
Then we’ve solved the problem.
Let’s write this in Python:
1 2 3 4 5 6 7 8 9 10 11 12 13 14  # define constants from problem statement here
# define a function to get the cubic root of a big number here
def test_lee_attack():
print "test: assume pow(m, e) < n"
m_1 = find_cube_root(C_1)
m_2 = find_cube_root(C_2)
m_3 = find_cube_root(C_3)
if m_1 == m_2 == m_3:
print " it worked"
else:
print " it didn't worked"
test_lee_attack()

But once we run it, we get:
1 2 3  $ python test_lee_attack.py
test: assume pow(m, e) < n
it didn't worked

Coppersmith’s Attack

Suppose the receivers share the same first part of the exponent e.
Generals Sun Tzu, Qin Jiushao, and Ymenetn Gnauq share the same first part of the exponent (e = 3).

And suppose one sender sends the same message in encrypted form to e number of people:
We have e = 3, and we have three encrypted messages received by the three generals.
Then we can perform this kind of attack.
The process is the following:
Compute a constant C that simultaneously satisfies:
C = C_{1} (mod N_{1}) C = C_{2} (mod N_{2}) C = C_{3} (mod N_{3}) 
Any method is valid, but using the Chinese Remainder Theorem is particularly fast and handy, because it’s been already implemented in Python.
Once we have computed C, then we can get the message by taking the e_{th} root of C. In this case, the cubic root.
Since the answer to the problem is the last 20 digits of m then we can take the remainder by 1e20 as our solution:
1 2 3 4 5 6 7 8 9 10 11 12  # define constants from problem statement here
# define a function to get the cubic root of a big number here
def test_copper_attack():
vector_n = [N_1, N_2, N_3]
vector_c = [C_1, C_2, C_3]
value_C = chinese_remainder(vector_n, vector_c)
value_M = find_cube_root(value_C)
solution = value_M % 100000000000000000000
print 'enter this on wechall: ' + str(solution)
test_copper_attack()

Once we run it we get:
1 2  $ python test_copper_attack.py
enter this on wechall: 21987654321987654321

Brute Force Attack
At this point we know the message in base ten:
9876543219876543219876543219876543219876543219876543219876543219876543219876543 2198765432198765432198765432198765432198765432198765432198765432198765432198765 4321987654321987654321987654321987654321987654321987654321987654321987654321 
Did you noticed that the message is "987654321" repeated 26 times? Maybe we could have exploited this, however, who did know it?
This message have around 777 bits of length, and proves that a blind brute force approach would have take, as the statement says, weeks.
In fact, the strength of asymmetric RSA is that nowadays you can’t solve relatively fast (in polynomial time ) two mathematical problems:

The Integer Factorization Problem, and

The RSA Problem.
Despite the mathematical background on RSA is pretty solid, you should pay attention to the mathematical conditions that make the algorithm solid, otherwise you are risking what you encrypted.
As a conclusion to the attacks explained on this article, don’t send a message to people that share the same first part of the exponent, nor use low values for them. If you are to implement an RSA cryptosystem, tie yourself from the beginning to a cryptography standard like PKCS v2.0 or superior. It introduces some random salt in the clear text so messages are not equal for different receivers.
Finally
Thanks for reading, see you in another post!
References

WeChall. Save the World challenge. Web.
Civil Engineer 
"An algorithm must be seen to be believed" Donald Knuth 