13
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Vast subject! Do you plan to answer your own question, or do you want others to dive in? $\endgroup$ – fgrieu Nov 7 '14 at 16:06
  • $\begingroup$ Not this time. It was more that I need a pointer for the answer on my self answered question here, and found nothing on this site. I guess that a list with pointers is enough, I don't expect every attack on RSA fully explained ;) $\endgroup$ – Maarten Bodewes Nov 7 '14 at 16:07
  • $\begingroup$ @fgrieu Maybe I should rephrase as "why should raw/textbook RSA be avoided? Then the full list may not be required. What do you think? Please dive in! $\endgroup$ – Maarten Bodewes Nov 7 '14 at 16:12
  • $\begingroup$ What research have you done? There's lots written on this. See, e.g., Dan Boneh's survey. Or, search on "textbook RSA" on this site (or elsewhere) and you'll find many references. $\endgroup$ – D.W. Nov 9 '14 at 7:37
  • $\begingroup$ @DW I (now) searched and found Dan's Survey. Padding is mentioned, but although it is claimed that he indicated that padding may thwart the attacks mentioned, he did not discuss it much. The main reason to ask is that I could not find too many specific (lists) of attacks that mentioned padding; I thought of creating a list myself, but as I'm not performing crypo analysis on a daily base myself, my list would certainly not be complete and possibly incorrect. There is much information about this but it is too much and too spread out. $\endgroup$ – Maarten Bodewes Nov 9 '14 at 10:16
16
$\begingroup$

This describes some attacks against textbook RSA (also known as raw RSA), where the public or private functions $x\to y=x^e\bmod N$ or $y\to x=y^d\bmod N$ are applied directly to the message.

Encryption / Decryption

  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

  1. 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}$).
  2. 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.
  3. 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).

$\endgroup$
7
$\begingroup$
  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*.
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.