In Alice/Bob/Cindy terms (EDIT: and with a little more detail):

Alice and Bob have each securely obtained one key of an RSA keypair from a trusted third party. Alice has one key ($e$ and $n$), Bob has the other ($d$ and $n$, where $d\equiv e^{-1} (mod\ \phi(n))$).

The RSA algorithm technically does not care which of the two keys is used to encrypt and which to decrypt; if $c_1 \equiv m^e (mod\ n)$ and $m \equiv c_1^d (mod\ n)$, then $c_2 \equiv m^e (mod\ n)$ and $m \equiv c_2^d (mod\ n)$. ($c_1 \neq c_2$)

Therefore, Alice uses $e$ and $n$ to encrypt a message $m_a$ into ciphertext $c_a$ and sends it to Bob, who decrypts it with $d$ and $n$, then encrypts his response $m_b$ with the same $d$ and $n$, and sends the ciphertext $c_b$ to Alice who can decrypt it with $e$ and $n$. Thus, one pair of asymmetric keys is being used to form a two-way communication channel, instead of the normal one-way usage.

Now, Cindy does not know $e$, $d$, or $n$, or any artifact used to produce them, such as $p$ and $q$. she can only see $c_a$ and $c_b$ as they are passed between Alice and Bob. Given that all other security concerns with RSA are properly handled, such as $\geq$2048-bit keys and OEAP padding scheme, is there an "efficient" way (an attack) by which Cindy can obtain $m_a$ and/or $m_b$?

  • $\begingroup$ Would any padding be used? $\:$ $\endgroup$ – user991 Dec 1 '12 at 1:42
  • $\begingroup$ How would that make a difference? $\endgroup$ – KeithS Dec 1 '12 at 1:56
  • 1
    $\begingroup$ @KeithS: $\:$ It would affect whether or not the scheme is trivially insecure. $\;\;$ $\endgroup$ – user991 Dec 1 '12 at 4:51
  • 1
    $\begingroup$ Your scheme is essentially symmetrical, so why would you use RSA over AES? $\endgroup$ – CodesInChaos Dec 1 '12 at 9:24
  • 1
    $\begingroup$ @fgrieu - Cindy does not know any part of the keyset including the shared modulo. She does not know any plaintexts involved. All she can see are the ciphertexts passed back and forth. $\endgroup$ – KeithS Dec 3 '12 at 19:14

The question and comments seem to be asking the following: If an implementation of RSA is used in the following way, is it still secure? An RSA modulus $N = pq$ and exponent $e$ are generated, and (N,e) is given to Party $A$ and $(p,q,e)$ is given to Party $B$. Then, the parties encrypt their communication where Party $A$ encrypts using the modulus and exponent, while party $B$ encrypts using the private primes and the exponent.

To really answer the question, we'd have to define what encryption padding method is being used (OAEP, PKCSv1.5, etc) and what notion of "secure" we want. We'd also have to define what it means to encrypt with the secret key instead of the public key. But as long as the encryption methods with either key are generating the same ciphertext (more precisely, the same distribution over ciphertexts), then whatever reasonable security notion we want will be achieved in this setting under the same hardness assumptions. This is because the adversary is seeing ciphertexts that are all indistinguishable for ciphertexts generated in the usual way, so the basic security achieved will transfer over easily in provable way.

  • $\begingroup$ By "encrypting with the secret key", I mean that by Wikipedia, a decryption exponent d can be derived from e and n, and given that, the decryption formula is nearly identical to the encryption formula. Alice's key is (e,n) and Bob's is (d,n). Since the two modulo operations are shown to be inverses, the only question in my mind is whether Cindy could derive d and e by seeing messages encrypted with both exponents (but not their plaintexts). $\endgroup$ – KeithS Dec 3 '12 at 17:10
  • $\begingroup$ As far as padding, see my edited question; let's assume OEAP padding. "Secure" is defined as Cindy not being able to discover the plaintexts of either message given only the ciphertexts; we can assume that Cindy has no access to Alice or Bob's plaintext messages on either end (before encryption or after decryption), or their keys. $\endgroup$ – KeithS Dec 3 '12 at 19:39

Basically, you are interested in a variation of RSA where both $e$ and $d$ are private.
In traditional RSA, a well known number is traditionally used for $e$, mostly $65537$ nowadays. More details can be found in this question. The answer there claims that using a non-standard exponents is not a weaknes by itself. But if you indend to keep the "public" exponent private, you'd probably have to use a non-standard key generator.

Keeping the modulus $n$ private will be difficult, but not necessary for keeping the scheme secure.
All encrypted messages will integers uniformly distributed over interval $(1, n)$ and if Cindy observes enough messages, she will be able to guess the value with a reasonable certainty.

Anyhow, the proposed scheme definitely falls under "key reuse", because

  • Message travelling from $A$ to $B$ is $m_a = \text{RSADecrypt(RSAEncrypt(}m_a))$
  • Message travelling from $B$ to $A$ is $m_b = \text{RSAEncrypt(RSADecrypt(}m_b))$
  • The latter is more traditionally written as $m_b = \text{RSAVerify(RSASign(}m_b))$

and if there is no padding trickery, any generic key reuse attack should apply. See this other question.

Furthermore, a cryptographic channel constructed like this has no integrity protection and is therefore vulnerable to attacks based on RSA malleability.


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.