Before starting, let me introduce two terms used in the title:
- Textbook RSA – most basic implementation of RSA, used for educational purposes. It is easy to understand, but highly insecure. One of the vulnerabilities of textbook RSA lies in its deterministic nature. It means that encrypting the same message with public key, always gives the same output. This characteristic can be exploited.
- Padding – Crucial security measure, that makes textbook RSA much more resilient. Involves adding random data to a message before encryption. It removes deterministic nature from textbook RSA, making it significantly more secure.
There are multiple of attacks, that exploits lack of padding in textbook RSA:
- LOW EXPONENT ATTACK
To make it work, the attack needs 2 things:
– small e
– short message
The formula for maximum message length to make the attack work is `m < n^(1/e)`, where n is key length, and e=exponent. i.e. 512 bit key, and tiny e=3, maximum message is 21 ASCII characters. There are two countermeasures: using reasonably high exponent, and minimum message length. Arbitral padding will prevent too short messages - SHORT MESSAGE ATTACK
Requirements for successful attack:
– short message
– no padding
Idea behind this attack is simple. Knowing that encrypted message is short, we are encrypting every combination – brute force – and then compare encrypted messages. If we have some assumptions about the message, it is possible to create a dictionary, and test most probable options first. Simple padding (like PKCS 1.5) adds random bits at the beginning of the message. It makes the output nondeterministic, and resilient to brute force attack. - HOMOMORPHIC ATTACK. It requires 2 encrypted unpadded messages. This attack is interesting, because it does not reveal the message, but lets attacker manipulate data. Knowing encrypted(300) and encrypted(500), an attacker can construct (encrypted 300*500) by calculating encrypted(300) * encrypted(500). By adding padding, we are removing this property.
Here you can find script exploiting no padding vulnerability: https://github.com/o-lenczyk/rsa/blob/master/no_padding_attacks.py
sample output:
======================================================================
SUMMARY TABLE: RSA Textbook Vulnerabilities Across Key Sizes
======================================================================
Key Size RSA Bits Encrypt Low Exp Homom Brute
(primes) (modulus) Time Attack Attack Attack
----------------------------------------------------------------------
512 1024 0.000002 0.000045 0.000087 0.000107
1024 2048 0.000003 0.000030 0.000066 0.000093
2048 4096 0.000002 0.000036 0.000018 0.000078
----------------------------------------------------------------------
TOTALS 0.000007 0.000111 0.000171 0.000278
======================================================================Regardless of the key size, lack of padding is critical textbook vulnerability. In all test cases, breaking the encryption was literally instant.