How does one conduct a known-plaintext attack on an algorithm?

Question

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?

Answer 1

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.