3
$\begingroup$

I am wondering: If we take this scheme/procedure and each of it seems very secure (to me at least), is it truly secure or is there a vulnerability hidden in the process?

This is the scheme:

Bob has an RSA key with modulo $N$ with a size that is considered safe, 2048 and a public power of $e=3$ (should assure efficient encryption).

Alice wants to send Bob a big file, and chooses symmetric encryption: She uses a random $k$ for AES and sends it encrypted using RSA using $C=k^e \bmod N$, and then sends the file encrypted by AES using key $k$.

To decrypt the file, Bob recovers $k$ using $k=C^d \bmod N$ and then decrypts the encrypted file using AES with $k$ is the key.

Is this procedure really secure?

On the paper, it uses secure parameters and seems secure, but I am not sure because $k$ is used too much here. Is there some hidden vulnerability I am missing here?

EDIT: what i am asking is in regards to attacking it, so could you please put an emphasize on attacking it rather than suggesting an alternative? i don't fully understand it, i understand that because of AES, $k^3$ cannot be more than 768 bits, so it does not pass the modulo (that is 2048). but i don't understand the technical details very well and would appreciate if you could elaborate on it instead of on possible mitigations.

thank you very much

$\endgroup$
  • 7
    $\begingroup$ This is trivially insecure because $k^3$ is at most 768 bit long whereas $N$ is 2048, so no reduction takes place and a simple cube root over the reals will yield $k$. $\endgroup$ – SEJPM Jan 6 at 10:07
  • $\begingroup$ @SEJPM - could you please elaborate regarding the insecurity, the reduction that does not takes place and how to mathematically attack it to gain k? if possible not generally, so i can understand and better comprehend it $\endgroup$ – alberto123 Jan 6 at 19:04
5
$\begingroup$

This scheme suffers from a classic problem of textbook RSA which is mitigated e.g. by RSA-KEM (as outlined by kelalaka) or RSA-OAEP.

When you compute $k^3\bmod N$, you'll experience that $$c=k^3\stackrel{k< 2^{256}}{\leq}\left(2^{256}\right)^3=2^{768}\ll 2^{2000}<N$$

Now remember how $x\bmod N$ works: If $x\geq N$, then you recursively compute and return $(x-N)\bmod N$ and else you return $x$.

Given that $c\bmod N$ fits the "else" case, $c$ is simply returned. Now an adversary can just compute $\sqrt[3]c$ as your calculator does for real numbers (with a bit more precision), you get $k$ back.

Note that the above weakness doesn't violate the RSA assumption because the assumption explicitly states that $x$ is uniformly randomly sampled from $\mathbb Z^*_N$ 1 in $c=x^e\bmod N$.

1: $\mathbb Z^*_N$ is the set $\{1,\ldots, N-1\}$ without any $x$ such that $\gcd$$(x,N)>1$

$\endgroup$
  • $\begingroup$ your answer really helped me a lot in understanding why it is not secure. you've given me important fundamentals on understanding this weakness. thank you again for elaborating so much $\endgroup$ – alberto123 Jan 7 at 11:45
4
$\begingroup$

What you describe is a little away from the RSA-KEM (KEM : Key Encapsulation Mechanism). As pointed out by SEjPM, in the comments, an AES-128 key when encrypted with the public modulus has almost 768 bits and this can be recovered by the cube-root attack. Here is the RSA-KEM;

RSA-KEM mitigates the attack that you have. RSA-KEM for a single recipient with AES-GCM simply as follows;

  • The Sender;

    1. First generate a $x \in [2\ldots n-1]$ uniformly randomly, $n$ is the RSA modulus.
    2. Use a Key Derivation Function (KDF) on $x$, $$key= \operatorname{KDF}(x)$$ for AES 128,192,or 256-bit depending your need.
    3. Encrypt the $x$, $$c \equiv x^c \bmod n$$
    4. Encrypt the message with AES-GCM genenerate an $IV$ and $$(IV,ciphertext,tag) = \operatorname{AES-GCM-Enc}(IV,message, key)$$
    5. Send $(c,(IV,ciphertext,tag))$
  • The receiver;

    1. To get $x$, They are using their private key $d$,$$x = c^d \bmod n$$
    2. Uses the same (KDF) on $x$ to derive same AES key, $$key= \operatorname{KDF}(x)$$
    3. Decrypts the message with AES-GCM $$message = \operatorname{AES-GCM-Dec}(IV,ciphertext,tag, key)$$

Note 1: If you want to send the key itself as you described, to prevent the attacks on textbook RSA, you will need a padding scheme like OAEP or PKCS#v1.5. RSA-KEM eliminates this by using the full modulus as a message.

Note 2: The above described RSA-KEM work for a single-user case. As noted by Fgriei on comments RSA-KEM for multiple user will fall into Håstad's broadcast attack. Instead using RSAES-OAEP makes it safe for multiple recipients with the same $x$ encrypted for different recipients. This will make it very useful to send the message multiple recipients instead of creating a new $x$ for every recipient and encrypting the message for each derived key (as PGP/GPG does).

$\endgroup$
  • 3
    $\begingroup$ Note: using RSAES-OAEP makes it safe to send the same $k$ encrypted to multiple recipients, which in turn is handy to have the bulk of the ciphertext common to all recipients (as PGP/GPG does). RSA-KEM does not, for it would fall to Håstad's broadcast attack. $\endgroup$ – fgrieu Jan 6 at 12:44
  • 1
    $\begingroup$ @alberto123 Since the exponentiation with 3 did not pass the modulus, there is no modulus operation and the value of the ciphertext can be found by cube-root algorithms. Cube calculation is easy (cube-root attack). To mitigate this a good padding scheme is necessary. $\endgroup$ – kelalaka Jan 6 at 12:53
  • $\begingroup$ @fgrieu thanks. Added as 2. note with some clarification. $\endgroup$ – kelalaka Jan 6 at 13:46
  • $\begingroup$ thank you very much for answering me @kelalaka. you've both complimented each other and i learnt a lot from both answers. i feel that the answer who gave me the most tools to understand the matter was SEJPM's one, so i marked him. however, i learnt a lot from your answer to apply the correct measures and how to fix the problem. thank you very much $\endgroup$ – alberto123 Jan 7 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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