How secure RSA is in practice?

Brute force attacks

Even though it is possible to try every possible value for d (Decryption key) till we find the correct value, for larger keys it is highly inefficient process for any practical usage.

Another way to break RSA is to factor n. The security of RSA depends on the problem of factoring large numbers. Attacker having the public key e and modulus n has to factor n to find d. Even though brute force attack can be successfully deploy against RSA encrypted message if the key lengths are not long enough using the modern day factorising algorithms and faster machines it is still harder and impractical to break RSA using brute force attacks on larger (E.g. 1024 or more bit key sizes) keys.

On the other hand keys once considered impractical to break have become vulnerable in recent years.

For example even though Rivest predicted that it will take about 40-quadrillion years to factorize 129 bit long key , in reality it took only about 8 months to determine it with the help of an world wide distributed system. [Riele H, 1995, Factoring Large Numbers]

This suggests us that even larger key sizes are not 100% secure in the long run.

Implementation flows, constraints and bugs

Hybrid architecture

Encrypting bulk messages using asymmetric ciphers such as RSA is extremely slow and processor intensive process compared to the other encryption methods using symmetric ciphers such as AES. This makes it using pure asymmetric ciphers to encrypt messages impractical in everyday applications. In software implementations, encryption/decryption using asymmetric ciphers such as RSA is 100 times slower than using symmetric ciphers such as AES to do encryption/decryption operations.

To circumference this limitation in practice, applications use symmetric ciphers to encrypt the bulk messages and then encrypt the session key using the asymmetric ciphers for secure exchange between communicating parties. These are called hybrid cipher systems. The issue with this method is that the system is strong as its weakest link. If the application make use of vulnerable symmetric ciphers or use less than adequate key lengths for the session key , attack can be deploy against the message directly with out being bothered to decrypt the session key encrypted using the asymmetric cipher.

This vulnerability can be addressed by choosing keys with satisfactory length to encrypt messages when using symmetric ciphers.

Not so random number generators

Sometimes even if long enough RSA keys are used, a known flows in the random number generator or not having enough entropy while calculating p and q may make the system vulnerable to attacks. This will give an opportunity to the attacker to simulate/guess and check p and q with out going through a full brute force method to factor n to find p and q.

Attacks against choosing common e

In practical algorithms, to make modular exponentiation operation faster for RSA , encryption exponent e is chosen to be same for all users and one of 3, 17 or 65537 values. This is to simplify the calculation of c = M^e mod n.

When e is chosen as 3 then cube root attack is possible.

When e is chosen as 3 and message (M) is less than n ^1/3

Then modular operation becomes effect less and thus c = M³

In this situation attacker can easily determine message M from the cipher text (c) alone by simply calculating cube root of c.

This security issue can be easily avoided by padding short messages with random bits so that message M is larger than n ^1/3

Key management

Poor key management and signing techniques used by careless users can jeopardise the ability to communicate securely and will weaken the web of trust. It is absolutely essential to verify (Key fingerprint can be used) the identity of the key owner before signing any key. Secondly all public key signatures should be verified before using it to ensure secure communication.

Threats posed by network/password sniffing applications are virtually eliminated by using RSA based asymmetric cryptographic systems. Shared secrets do not need to be exchanged insecurely or in a cumbersome way to initiate a secure communication. Using RSA public/private key pares, this exchange of shared secret can be automated and secured.

Social engineering attack

Vulnerability exists where intercepting party can recover an encrypted message using carefully altered cipertext message and some social engineering techniques. For example Alice send encrypted message to John which get intercepted by Malory. Malory alters the cipher text and sends the message to John as it is coming from him. When John tries to decrypt the altered message it returns garbage. When John notify this to Malory , Malory can request that decrypted garbage to be sent back to him. If John is careless enough to do that, Malory can easily determine/recover the session key by analysing the decrypted data injected by him in to the cipher text. Then this session key can be used to decrypt the original message sent by Alice.

This vulnerability can be easily avoided by practising some common sense and not returning any data from a failed decryption attempt to any one who asks for it.