9
$\begingroup$

Consider the following protocol: Bob has a private RSA key $B_{priv}$, and Alice knows the public key $B_{pub}$. Alice wants to send confidential messages to Bob (no integrity intended). To send a message, Alice randomly generates a single-use symmetric key (say, an AES key) $K$, encrypts the message with this symmetric key, and sends this encrypted message alongside with $K$ encrypted with RSA with Bob's public key.

Suppose we use no padding for $\textrm{RSA}_{B_{pub}}(K)$ (in other words, to pad with zero bytes). The obvious (to me) problems with a lack of padding are that an attacker can guess the plaintext (not possible here, it's random) and that encrypting the same plaintext twice gives the same result (again, not happening here). What are the known weaknesses of this scheme (or is it safe)?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
14
$\begingroup$

If you pad a 128-bit value $K$ with zeroes to the left, and interpret the value numerically with big-endian convention (as happens in PKCS#1 in general), you end up with a value which is no greater than $2^{128}$. If the public exponent is $e = 3$, then the "encrypted value" is no greater than $2^{768}$, and no actual modular reduction takes place. Consequently, a simple cube root extraction on plain integers reveals $K$.

So, that can be quite unsafe.

What is safe is the following:

  • you generate a random integer $x$, between $0$ and $n-1$ ($n$ is the RSA modulus);
  • you encrypt $x$ by simply raising it to the power $e$ modulo $n$;
  • the encryption key you will use with AES is $h(x)$ for some hash function $h$.

It is still relatively limiting, in that this is safe as long as you do one encryption only of $x$. If you want to "send" your symmetric key $K$ to several recipients (a common model, e.g. for email encryption), then the scheme above does not work, and, more generally, you need some per-encryption randomness inserted (as PKCS#1 does for encryption).

Improve this answer
$\endgroup$
6
  • $\begingroup$ Ouch, defeated by simple math. Hmm, what if I encrypted $K + 2^{\mathop{lg}(n)-1}$? And incidentally, with multiple recipients, does the unpredictability of the padding matter, or is it enough never to apply RSA to the same plaintext with different keys? (Don't worry, I'm asking out of curiosity, I'm not planning to implement anything like this.) $\endgroup$
    – Gilles 'SO- stop being evil'
    Feb 2, 2012 at 0:02
  • 3
    $\begingroup$ @Gilles: if padding is deterministic, and you encrypt the same $K$ (padded to $\pi(K)$) for three different recipients, with $e = 3$, then you send the value $\pi(K)^3$ modulo $n_1$, $n_2$ and $n_3$. By the Chinese Remainder Theorem, this is sufficient to rebuild $\pi(K)$ modulo $n_1n_2n_3$, and since $\pi(K) \lt n_i$, the modulo disappears. This is the historical justification for using $e = 65537$ instead of $e = 3$, but the real issue is that a deterministic padding for RSA encryption is definitely unsafe. You MUST have a random padding. $\endgroup$
    – Thomas Pornin
    Feb 2, 2012 at 12:34
  • $\begingroup$ @ThomasPornin Your argument doesn't show that per-encryption randomness is required. For example you don't show why padding based on hash(m,e,n) is a problem. Such a scheme is still deterministic, and doesn't suffer from this specific problem. $\endgroup$
    – CodesInChaos
    Apr 18, 2012 at 13:27
  • $\begingroup$ @CodeInChaos: yes, my argument does not show why per-encryption randomness is required, which is why I wrote in my response "more generally". You need per-encryption randomness to avoid exhaustive search attacks on the encrypted text (which may or may not be applicable, depending on context -- it depends whether you are encrypting a meaningful message, or a random session key). $\endgroup$
    – Thomas Pornin
    Apr 22, 2012 at 22:56
  • $\begingroup$ Out of curiosity: Will this scheme also work without the final step $k = H(x)$, e.g. by simply taking the $n$ left- or rightmost bits of $x$? $\endgroup$
    – lxgr
    Jul 15, 2014 at 18:43
2
$\begingroup$

Thomas Pornin's answer is almost (but not quite) Victor Shoup's RSA-KEM-DEM construction and fails to recognise that authenticating a message is required for the security proofs that are necessary due to the lack of padding.

Pick an $r \in \{0, 1, 2, \dots, n-1\}$, compute and send $r^e \bmod n$, and derive the key $k = \text{kdf}(r \mathbin\| (r^e \bmod n))$.

Notice that $k$ is derived from both $r$ and $r^e \bmod n$ instead of just $r$; this eliminates the RSA-side of malleability attacks and significantly reduces the control an adverarial client has over the resulting $k$.

Recall that DEM only requires a single-message authenticated encryption. For multi-message authenticated encryption we need more proofs; however, this is conjectured to be safe when using an AE[AD] such as AES-CTR-PMAC (or better an MRAE such as AES-CTR-PMAC-SIV).

With the above tweak we've gone from the proven single-message RSA-KEM-DEM to the unproven (conjectured safe) multi-message RSA-KEM-AE.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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