0
$\begingroup$

a quick example:

The encryption function: y = E(x) = (13x + 9)(mod 27), when the letters A–Z are taken to be the numbers 0–25 and the Space (punctuation) is the number 26.

The opponent has the ciphertext y = "NZC"

For each letter, he will cipher it again and again until he gets the starting value.

I'll show the letter 'N': 'N' = 13

E(13) = 16

E(16) = 1

E(1) = 22

E(22) = 25

E(25) = 10

E(10) = 4

E(4) = 7

E(7) = 19

E(19) = 13

So, the opponent knows that the letter 'T' = 19 was encrypted to get 'N'

Same goes to 'Z' = 25, the letter 'W' = 22 was encrypted to get 'Z'

and for 'C' = 2, the letter 'O' = 14 was encrypted to get 'C'

From that, the opponent reveals the the plaintext: "TWO"

What is the name of this attack?

Thanks.

$\endgroup$
  • $\begingroup$ "Chosen Plaintext Attack" $\endgroup$ – SEJPM Jul 5 '19 at 11:49
  • $\begingroup$ The definition from the book: Chosen plaintext attack - The opponent has obtained temporary access to the encryption machinery. Hence he can choose a plaintext string x and construct the corresponding ciphertext string y. But here, the opponent possesses a string of ciphertext y. $\endgroup$ – Asaf Jul 5 '19 at 11:56
  • $\begingroup$ So my understanding of this question is that an adversary is given access to the encryption machinery as well as to a specific ciphertext and "wins" if they can recover the randomly chosen plaintext. Is that correct? If so this is a chosen plaintext attack though an unnecessarily weak one that any standard CPA secure cipher will protect against. $\endgroup$ – SEJPM Jul 5 '19 at 12:06
1
$\begingroup$

Actually, this specific attack against RSA is known as a 'cycling attack'; it works because RSA defines a permutation, and so by doing repeated encryptions a sufficient number of times, you'll always get back to where to started with eventually.

However, people have analyzed this attack, and shown that (with extremely high probability) the amount of work required by this attack (for a randomly chosen RSA modulus) takes more work than the known factorization methods.

$\endgroup$
0
$\begingroup$

The question defines a notion "chosen plaintext attack" capability for an adversary. Whether it is "the" notion introduced in the reference text does not matter as that is what it actually is: an adversary has tries to induce information about an underlying message while having the ability to get encryptions. Below I'll explain how this relates to the more standard "find-then-guess" CPA security notion as can be found in e.g. this paper (PDF).


So the usual definition of "security against chosen plaintext attacks" goes as follows:

Suppose you have an adversary $\mathcal A$. You first pick a secret bit $b$ uniformly at random and run the key generating algorithm for the encryption scheme to receive a key $k$. You then run $\mathcal A$ and ask it to output two messages of the same length $m_0,m_1$ while it has access to the encryption machinery $\mathcal E_k(\cdot)$. You invoke the adversary again and provide it with $c=\mathcal E_k(m_b)$. It then outputs a bit $b'$ and "wins" if and only if $b'=b$. If the probability that the adversary wins is "negligible" for a given scheme and all adversaries then the scheme is called "CPA-secure".

Now the scheme proposed in the question is very similar to the above one, it just appears that the adversary does not get to choose nor see the pool of messages that make up the ciphertext.

So obviously an adversary that wins the CPA definition of the question also wins the standard one, but the converse likely does not hold.

$\endgroup$

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.