Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Assume Alice and Bob are using RSA to create a common session key and Cindy is listening, attempting to obtain the session key.

Alice and Bob each have their public- and private-key pairs ($\left[pub_{A}, pri_{A}\right]$ for Alice and $\left[pub_{B}, pri_{B}\right]$ for Bob) and Alice, Bob, and Cindy all know everyone else's public key.

  1. Alice generates a random $n_{A}$ and sends out $En_{pub_{B}}\left(n_{A}\right)$ ($n_{A}$ encrypted with Bob's public key).

  2. Bob generates a random $n_{B}$ and sends out $En_{pub_{A}}\left(n_{B},n_{A}\right)$ and sets the session key to $n_{A}\oplus n_{B}$.

  3. Alice sends out $En_{pri_{A}}\left(n_{B}\right)$ and sets the session key to $n_{A}\oplus n_{B}$.

My thinking is, Cindy decrypts message 3 with Alice's public key to obtain $n_{B}$. Now Cindy has a plaintext, ciphertext pair and the key that decrypts the ciphertext.

My question is, is it possible with this information for Cindy to find $pri_{A}$ in order to decrypt message 2 and find $n_{A}$?

share|improve this question
1  
Is $En_{pri_A}(n_B)$ the signature of $n_B$ ? One never encrypts with a private key, see this. Also: before step 3., does Alice verify that the cryptogram she received (allegedly) from Bob at step 2. deciphers to a message ending in $n_A$? Also: Is Cindy a passive eavesdropper (often called Eve), or an active adversary (often called Mallory)? –  fgrieu Mar 7 '13 at 19:42
add comment

1 Answer

up vote 8 down vote accepted

No matter how bad a protocol built on top of RSA is, there is no known risk that a private key leaks from valid plaintext/ciphertext pairs, even if the adversary chooses plaintext or ciphertext; that's one of RSA's virtues. Thus to the question is it possible with this information for Cindy to find $pri_A$ we can answer: as far as we know, no; and more, Cindy can not find an equivalent to $pri_A$.

More precisely: even with access to an oracle accepting any $x$ and answering with $x^d\bmod N$, a computationally bound adversary can not (as far as we know):

  • factor $N$;
  • or otherwise compute any of the several equivalent private exponents $d$ or private keys;
  • or compute $x^d\bmod N$ for some random $x$ submitted to the adversary after access to the oracle has been denied.

That does not answer if Cindy can decrypt message 2 or otherwise find $n_A$ (which was not asked :-).


It is now asked if Cindy can find $n_A$. The answer is yes, at least in some setup matching the question. To justify that claim, I'll explain one such a setup, and how Cindy proceeds.

Assume that:

  • $En_{pub}$ and $En_{pri}$ are the public (encryption) and private (decryption) operations of textbook RSA;
  • the modulus in the public keys of Alice and Bob have the same bit size $m$;
  • the random $n_A$ and $n_B$ have (at most) fixed bit size $r$, with $2\cdot r<m$;
  • at step 2., $n_B,n_A$ designates the integer corresponding to the concatenation of the $r$-bit strings representing $n_B$ and $n_A$, using little-endian convention;
  • Bob verifies that applying $En_{priv_B}$ to the cryptogram he obtained at step 1. yields an alleged $n_A$ of at most $r$ bits, which he proceeds to use during step 2.;
  • Alice verifies that applying $En_{priv_A}$ to the cryptogram she obtained at step 2. yields an alleged $n_B,n_A$ of at most $2\cdot r$ bits, from which she extracts $n_B$ that she proceeds to use during step 3.;
  • Cindy can play the role of Bob with respect to Alice, and of Alice with respect to Bob, and further Cindy can persuade Bob to engage in a protocol where Bob acts just as Alice does (e.g. because Alice and Bob use the same program and parameters save for the value of their public key pairs, and Cindy persuades Bob to use his program to establish a session key with Alice in the manner Alice uses her program to establish a session key with Bob).

Cindy does the following:

  • Impersonating as Bob to Alice in a protocol initiated by Alice, Cindy gets the cryptogram $En_{pub_B}(n_A)$ generated by Alice at step 1;
  • Impersonating as Alice to Bob in another protocol this time initiated by Bob, she gets (and ignores) the cryptogram generated by Bob at step 1, then passes the aforementioned $En_{pub_B}(n_A)$ as the cryptogram allegedly generated by Alice for Bob at step 2. of that other protocol;
  • In preparation of step 3. of that other protocol, Bob applies $En_{priv_B}$ to that cryptogram, yielding $n_A$;
  • that $n_A$ is just the same as $n_A,0$ that Bob would legitimately receive at that step should he have chosen his random number as $0$ in the first step of that other protocol (which he likely did not);
  • as nothing in the protocol asks Bob to check that the random he has chosen appears in what he obtained, Bob dutifully compute $En_{priv_B}(n_A)$, and sends it to what he believes is Alice, and in reality is Cindy;
  • Cindy persuades Bob to start over, this time in a protocol where Bob acts as Alice expects Bob to act;
  • Cindy passes $En_{pub_B}(n_A)$ to Bob as the cryptogram of the first step of that new protocol, as if it was from Alice (which it was in the original protocol started by Alice, which meanwhile is still waiting for Bob);
  • from then on, Cindy let Bob and Alice communicate normally;
  • Cindy has $En_{priv_B}(n_A)$ (obtained from Bob at step 3 of the fake instance of the protocol), applies $En_{pub_B}$ to that, and now has $n_A$ in the protocol now being used by Alice and Bob;
  • Cindy has $En_{priv_A}(n_B)$ (obtained from Alice at step 3 of the real instance of the protocol), and as noted in the question applies $En_{pub_A}$ to that, obtaining $n_B$ in the protocol now being used by Alice and Bob;
  • Cindy can thus obtain the session key $n_A\oplus n_B$.

That attack can sometime be adapted to big-endian conventions (unless I err, at least when the public exponent $e$ is such that $3^e<2^r$; thus with $m=2048$, $r=512$, $e=257$ or less).

Towards turning that protocol into something safe, we are missing:

  • A check before step 3. by Alice (and every legitimate party performing her role), that the random $n_A$ she generated in step 1. is found by deciphering with her private key the cryptogram received in step 2., allegedly from Bob;
  • An additional step 4. where Bob (and every legitimate party performing his role) checks that the random $n_B$ he generated in step 2. is indeed found by verifying, with Alice's public key, the cryptogram received in step 3., allegedly from her;
  • Forward secrecy, that is insurance that past session keys do not leak should one of Alice's or Bob's private key leak at some point in time. One technique towards that goal, which more generally avoids that the authentication step 3. turns into a decryption oracle (that's how the above attack could be outlined), is to split $n_A$ and $n_B$ into two parts: one used only to build the session key, another used for authentication purposes.
  • A proper encryption at steps 1. and 2., rather than textbook RSA;
  • A proper signature (possibly with message recovery) at step 3, rather than textbook RSA.

It is left as an exercise to the reader to exhibit attacks working with the first two tweaks alone (that's trivial unless $r\cdot e\gg m$ holds, but I fear there could be other cases).

share|improve this answer
    
Can Cindy find $n_{A}$? –  geoff92 Mar 10 '13 at 3:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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