Republic of Pwning

[EN] [ES]

The last year, while we were performing an ethical hacking assessment, we found a curious vulnerability in a cryptosystem implementation based on RSA.

Our client centralized the authentication of their internal applications in a web login. This login, after verifying the username and password, redirects to the selected internal application and pass a misterious Base64 encoded parameter to such application. Obviously, we decoded it to reveal its content, but we got just a random binary stream. The content was encrypted.

So we unsuccessfully performed some crypto tests looking for vulnerabilities like Padding Oracle and with one of them we got a modulus error. And so we discovered that the encryption was RSA.

Understanding the test

RSA use the aritmethic operation modulo. This operation finds the remainder in a division. The divisor is known as the modulus and usually is represented as \(N\). The values that RSA can encrypt or decrypt must be theorically in the range \([0, N-1]\) but in practice this range is lower for security reasons. If we try to encrypt a message greater than \(N\), part of the message will be lost. For this reason many RSA implementations checks for the message value and throws an exception if it is greater than the modulus. Similarly for decryption operations.

In our test, we sent a too long input to the internal application. The application decoded it from Base64 and got a number greater than its RSA modulus. Then, when tries to decrypt it, throws an unhandled exception: modulus error.

http://internal-app/verify?secret=AAAAAAAAAAAA[...]AAAA

The cryptosystem

After the centralized login validates the user’s credential, it needs to send to the internal application a message with the user information. But this message contains sensitive information so it is necessary to protect it. To acomplish that the applications have a preconfigured RSA public/private keys pair. So the first application uses the public key to encrypt the message and sends it to the second one by a redirect through the browser. Then the internal application uses the private key to decrypt the message, recover the user information and starts his session.

The vulnerability

If we want to send a fake message to the internal application we need the ability to encrypt arbitrary messages. That is why we need the public key. But in this case the public key is not really public. I mean, it is stored in the server and we can’t access to it. However, we found a way to obtain it.

A RSA public key is composed by two numbers: the modulus \(N\) and the public exponent \(e\). The most common public exponent is \(65537\). This value is a convention to optimize the calculus. In other hand, the modulus is the result from multiplying two large prime numbers \(p\) and \(q\) that are generated randomly. If we discover the modulus we will obtain the public key.

Modulus Oracle

Do you remember the modulus error from the beginning? We can use this error as an oracle. When we send a encrypted message that results in a number greater than the RSA modulus, we get a modulus error and when is lower, we obtain another type of error. So we can use a binary search algorithm to recover the modulus value. Since the binary search get one bit of information with each request, we need as many requests as bits the modulus has. In example, for a RSA 1024 key we need arround 1024 requests.

Demo

We have coded a Flask application that simulates this vulnerability. For dramatic effects, in this case the message is a command line and if you get the public key you will achieve RCE. Also we have included the script modulus-oracle.py that implements the Modulus Oracle Attack. You can download this demo from our github repository.

And now, view it in action:

We are investigating another useful scenarios to apply this Modulus Oracle Attack but we will tell you more in the next post.

See you then!

Written by RoP Team