2
$\begingroup$

My question is two-fold:

  1. Say I am given a total black box and I have n number of plaintexts as inputs that map directly to $n$-number of ciphertexts as outputs. This is all I know, and I do not have access to the algorithm. Is it possible to conduct a known-plaintext attack?

  2. In the event that I do have access to the algorithm's internals, how would one go about attempting a known-plaintext attack on a cryptosystem? What specific weaknesses or traits in the algorithm would one generally be looking for? Is it algorithm-specific or is there a generic process?

$\endgroup$
3
  • $\begingroup$ Yes, known-plaintext attacks require knowledge of the algorithm involved. $\endgroup$
    – SEJPM
    Feb 15, 2020 at 12:22
  • $\begingroup$ Well the first step in a cryptanalysis is to find out which encryption algorithm is being used. One way to do this would be, assuming the plain-texts are chosen randomly, is to see the statistics of the characters of the cipher-texts. Of course this attack will not work on the modern standard encryption algorithms. But with the older ones, like RC4, you can actually do statistical analysis to guess the algorithm being used. Note that if the black box encryption is not a standard one, then it will probably show some patterns -- ( security by obscurity is no more true these days.) $\endgroup$
    – Aven Desta
    Feb 15, 2020 at 16:25
  • $\begingroup$ 2. What specific weaknesses or traits in the algorithm would one generally be looking for? Is it algorithm-specific or is there a generic process? . Lets assume we have a large sample of plain-text, cipher-text pairs. Then there are generic attacks you can do such as statistical analysis, differential analysis (for block ciphers) etc... . There are also algorithm specific attacks, checking wikipedia for each cipher algorithm will be good for that. $\endgroup$
    – Aven Desta
    Feb 15, 2020 at 16:32

1 Answer 1

1
$\begingroup$

If your black-box access entails being able to query the cipher with keys and plaintext of your choice, then it is straightforward to mount a brute-force search for the key if given some plaintext-ciphertext pairs. This will in expectation, however, need about as many queries to the black box as the key space is large.

For strong modern ciphers, this brute force attack is meant to be the best attack already. For a cipher not known to be cryptanalytically broken, knowledge of the internals of the cipher will "only" help you to parallelize the attack and maybe do some inner-loop optimizations.

If "black-box access" means only having some pairs of ciphertext and plaintext but no access to the algorithm or an implementation of it, efficiently implementable algorithms can still be broken in theory given enough data. Briefly, given an algorithm A and some plaintexts P as well as ciphertexts C, checking whether A transforms P to C is doable basically in the time needed to run A on P. Hence, an adversary can for instance enumerate all instruction sequences in a language of their choosing in ascending length and stop when they find a match.

Note that while this is clearly even more impractical than the standard brute force attack on ciphers with a reasonable key size is, checking a solution is a polynomial-time problem in the length of P and A, under reasonable assumptions on A. There is no known proof that problems that are polynomial-time checkable cannot be solved in polynomial time (this is the P versus NP problem), so there is no proof that known plaintext attacks on unknown efficiently implementable ciphers cannot be executed efficiently (although there may be polynomial-time separation results that show that the defender can always get an advantage over the adversary).

However, everyone very strongly conjectures that secure ciphers exist. If that is the case, then of course breaking a strong cipher with only some examples of plaintext-ciphertext pairs will be utterly hopeless.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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