Which attacks are possible against raw/textbook RSA?

Question

The PKCS#1 standard defines multiple padding schemes for signature generation/verification (EMSA-PSS and EMSA-PKCS1-v1_5), and encryption/decryption (EME-OAEP and the less safe EME-PKCS1-v1_5).

Which attacks are possible on signature generation/verification and encryption/decryption if no padding mechanisms are applied, i.e. if raw RSA is used over the plaintext or hash?

Answer 1

This describes some attacks against textbook RSA (also known as raw RSA), where the public function $x\mapsto y=x^e\bmod N$ or private function $y\mapsto x=y^d\bmod N$ are applied directly to the integer $m$ representing the message. Per standard assumption, the public key $(N,e)$ is known.

Encryption / Decryption

Per standard assumption, ciphertext $c\gets m^e\bmod N$ is known.

1. Determinism in textbook RSA allows an attacker - given a ciphertext - to search for the corresponding plaintext.
2. Determinism also leads to traffic analysis. It is possible to distinguish if the same encrypted message is sent, and when the message changes. This could reveal information. For example, if an attacker sees $E(\text{stay put})$, $E(\text{stay put})$, $E(\text{stay put})$, $E(\text{stay put})$, and finally $E(\text{attack})$, an attacker will know something has changed.
3. $e$^th root attack: For short messages $m$ and low $e$ (e.g. $e=3$), it may happen that $m^e<n$ so that the ciphertext $c=m^e$, and then it is possible to implement the decryption function as $e$-th root extraction. This attack has extensions to $\log_2(m)$ somewhat above $\log_2(n)/e$.
4. Broadcast Attack: When the same message is sent encrypted to at least $e$ different correspondents, it can (with high likelihood) be recovered without knowing any private key.
5. Meet in the middle attack; this is an improvement of 1 above that allows searching plaintext faster than brute force; if the message is assumed to be writable as $m=a\cdot b$ with $\max(a,b)\le u$ and $\min(a,b)\le v$, the effort is $\mathcal O(u)$ with memory $\mathcal O(v)$ for constant $N$.
6. Leak of Jacobi: if $c=m^e\bmod N$, then $\big({c\over N}\big)=\big({m\over N}\big)$. In other words, the Jacobi symbol of plaintext $m$ relatively to $N$ leaks from the ciphertext $c$. This can be a problem in some (rather hairy) protocols built on top of RSA, or/and for some constructions of message $m$; for example $m=4r^2+b$ with $r$ a 500-bit random secret, $b$ a single-bit secret, and 1024-bit $N$: when it is observed that $\big({c\over N}\big)=-1$, it is known with certainty that $b=1$.

Signature Generation / Verification

Per standard assumption, verification of signature $s$ computes $s^e\bmod N$ and either checks that against $m$, or checks that's a sensible $m$.

1. Eve can pick a random $s$, compute $m=s^e\bmod N$, and pretend $s$ is the signature for $m$. With a little trial an error, she can choose some of $m$, e.g. make it print as OK if it's displayed as a C string, with an expected $2^{24}$ attempts.
2. An attacker can combine signatures to create a new signature. For example - given a signature of $2$ (i.e., $2^d\bmod{N}$) - it is possible to create a signature for $4$ ($2^d\cdot 2^d\equiv 4^d\bmod{N}$).
3. Say Alice implements a signing service using her RSA private key. In particular, anyone can send Alice a message, she checks the message contents to make sure there isn't anything too bad in it. If the message isn't bad, she signs it. Let $m_b$ be a bad message. Eve can send $km_b$ for some constant $k$ to Alice. Since $km_b$ isn't bad, Alice will sign it. Giving Eve $(km_b)^d\bmod{N}$. Eve can also get a valid signature for $k$ from Alice since it isn't bad $k^d\bmod{N}$. Using those two, Eve can now get a valid signature for $m_b$, something that Alice would have never signed before, by multiplying the inverse of the second signature.
4. Eve knows the signature of some messages; e.g. the signature of $0$ is $0$, the signature of $1$ is $1$, the signature of $n-1$ is $n-1$, the signature of $k^e\bmod N$ is $k$ for $0\le k<N$. This could be a nuisance by itself, or could help attacks 1 and 2.

---

More attacks are described in Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem (in Notices of the AMS, 1999; or this other version with a few more references).

Answer 2

1. Textbook RSA encryption scheme is not IND-CPA secure as it is a deterministic scheme.
2. Textbook RSA signature scheme is not secure considering Existential Unforgability under Chosen Message Attack. e.g. if attacker $\mathcal{A}$ chooses random x $\in$ {1,2,...,n-1} and computes y = x$^{e}$ mod n, then sets m = y, $\sigma_{m}$ = x then $\sigma_{m}$ is a valid signature on m under the public key (e,n). The forgery is on a random message.
3. Consider the case where $\mathcal{A}$ wants to forge some signature on a target message m* of her choice. Given (e,n) $\mathcal{A}$ asks for signature on some message m$_{1}$ $\in$ {1,2,...,n-1} and another message m$_{2}$ = (m*/m$_{1}$) mod n. Sender gives back $\sigma_{m_{1}}$ = m$_{1}^{d}$ mod n and $\sigma_{m_{2}}$ = m$_{2}^{d}$ mod n. $\mathcal{A}$ sets $\sigma^{*}$ = $\sigma_{m_{1}}$.$\sigma_{m_{2}}$ mod n which is a valid signature on m*.