1
$\begingroup$

I am quite new to the RSA and I have a couple of questions that confuse me.

Q1: A Timing attack on RSA can be prevented _____________________________

A. By performing the “square and multiply” modular exponentiation algorithm using keys with equal number of 1’s and 0’s in binary form

B. By randomizing the ciphertext or the exponent

C. By using the Montgomery modular Exponentiation algorithm

D. By performing an additional constant time computation after the concluding the modular exponentiation

I am confused among 4 options:

Option A: from what was told in the lecture, "square and multiply" is a naive algorithm which means it is not effective.

Option B: I do not see how that can prevent the timing attack, does't seem relevant?

Option C: From my understanding, it is an algorithm for a quicker calculation of modular arithmetic. It speeds up the decryption process.

Option D: By performing an additional constant time, the pattern can still be observed and the attacker can subtract the additional constant time and perform timing attack again.

My understandings may be wrong, and I am out of ideas :(

Q2: For the textbook RSA encryption scheme,

$ c = m ^ e \bmod n $

is used for encryption where $m$ is the message to be encrypted, $(e,n)$ is the public key and $c$ is the ciphertext;

the decryption will be

$ m = c ^ d \bmod n $

where $d$ is the private key.

Assume that Alice sends to Bob a message $m$ that is encrypted as $c$ and that Carol wants to retrieve the message $m$. Carol can use the Chosen Ciphertext attack for RSA. Describe how such an attack will be used in order to retrieve $m$.

For this question, I guess it is asking me to describe a timing attack?

Thanks in advance!

Update:

Many thanks to Squeamish Ossifrage for your clarification and fgrieu for your hints

I kind of getting the answer of Q2, but I am not too sure. Correct me if I am wrong.

  1. Suppose the original cipher $c_1 = m^e \bmod n $

  2. Carol creates a second cipher by multiply $c_1$ with a random number $r$. So Carol has $c_2 = c_1 * (r ^ e \bmod n )$

  3. Expand $c_2 = (m^e \bmod n) * (r ^ e \bmod n ) = (m^e * r^e) \bmod n$

  4. The corresponding plaintext of $c_2$, $m_2$, can be written as $m_2 = c_2^d \bmod n$

  5. Expand $m_2=c_2^d \bmod n = ((m^e*r^e) \bmod n)^d \bmod n = (m^{ed} \bmod n) * (r^{ed} \bmod n) = m * r $

  6. Therefore, original message $m$ can be calculated as $m = m_2/r$

$\endgroup$
  • 1
    $\begingroup$ For part (1): Have you reviewed Kocher's seminal paper on timing attacks? $\endgroup$ – Squeamish Ossifrage Nov 11 '19 at 19:59
  • 2
    $\begingroup$ Two unrelated questions in one post is not a good post! $\endgroup$ – kelalaka Nov 11 '19 at 20:00
  • $\begingroup$ For part (2): This is not about a timing attack. This is about a chosen-ciphertext attack. Another way to phrase it is: Given $(n,e)$ and a function $\mathcal O\colon c \mapsto c^d \bmod n$, how can you use $\mathcal O$ to find $t^d \bmod n$ for some target ciphertext $t$, without actually calling $\mathcal O(t)$? (You are allowed to pass anything else except $t$ to $\mathcal O$.) $\endgroup$ – Squeamish Ossifrage Nov 11 '19 at 20:00
  • $\begingroup$ (I don't think (1) is a good question, and it's not your fault. ‘Prevent’ is a bit of a strong word, and designing a logic circuit that runs in constant time for all inputs is not presented as an option! But one of the options does serve to mitigate timing attacks and is widely used in practice and is recommended by Kocher.) $\endgroup$ – Squeamish Ossifrage Nov 11 '19 at 20:04
  • $\begingroup$ Hint for 1: what timing dependency does the archetipal RSA timing attack exploit? Hint for 2: why would it be a timing attack ? In a chosen ciphertext attack, an attacker can choose a ciphertext (other than the one to be deciphered) and obtain the corresponding plaintext. $\endgroup$ – fgrieu Nov 11 '19 at 20:06

Your Answer

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

Browse other questions tagged or ask your own question.