How to model this "un predicatability" problem?
tl;dr: This is not a great candidate for machine learning solutions.



It is not exactly true that "the strength of an encryption scheme is measured by the randomness (unpredictability, or entropy) of the output".  Instead, strength of an encryption scheme is how resistant it is to cryptanalysis. Yes, input $\rightarrow$ output maps that show patterns are relatively easy to break. But the input $\rightarrow$ output map might be very random (high entropy) from many perspectives but still might be defeated through feasible cryptanalysis.

You offer another definition: "informally, the strength of an encryption scheme is determined by the number of such input-output pairs needed beyond which it becomes predictable."  This is usefully different from your first definition because it focuses on the information that might be gleaned about the encryption scheme from a stream of input $\rightarrow$ output pairs.  This is different and easier than the usual cryptanalysis problem where all you have is a data set of (encrypted) outputs.

Framed this way, I think you are heading toward a model selection problem.  While this may be relatively straight forward with weak encryption schemes, it becomes very hard, very quickly with strong schemes.  In fact, I believe you walk right in to the No Free Lunch theorem:


  "In formal terms, there is no free lunch when the probability distribution on problem instances is such that all problem solvers have identically distributed results. In the case of search, a problem instance is an objective function, and a result is a sequence of values obtained in evaluation of candidate solutions in the domain of the function. For typical interpretations of results, search is an optimization process. There is no free lunch in search if and only if the distribution on objective functions is invariant under permutation of the space of candidate solutions."


Translated: if you find yourself needing to search over all possible cryptanalysis methods, there exist input $\rightarrow$ output streams where no method is probabilistically better than any other. This will defeat any model selection method based on optimization of some objective function.