0
$\begingroup$

Imagine modeling the "input(plaintext) - output(ciphertext)" pairs of an encryption algorithm as a data science problem. Very informally, the strength of an encryption scheme is measured by the randomness (unpredictability, or entropy) of the output. This is counter-intuitive to classic regression problems, which are frequently used for prediction. Say, informally, the strength of an encryption scheme is determined by the number of such input-output pairs needed beyond which it becomes predictable.

How do we model this as data science problem? Given all pairs of two different encryption schemes, can we determine which is stronger just by using the input-output pairs of both the schemes? Is there any other way apart from regression to solve this problem?

$\endgroup$
  • $\begingroup$ Before anything, to model this as a "data science" problem, you need to define a metric to determine how "close" the encryption is to the original text. I am not sure this is feasible, since the computing time required to decrypt/encrypt isn't really a good metric for how good/bad an encryption algorithm is. $\endgroup$ – rocinante Dec 30 '14 at 14:14
  • $\begingroup$ You need a model for the encryption algorithm, then you set about estimating the model parameters. $\endgroup$ – Emre Dec 30 '14 at 19:10
  • $\begingroup$ Unless you are working with weak or broken encryption, then the amount of processing and data you would need to differentiate between two modern schemes is likely to be prohibitive. Most of the pad generating algorithms are statistically random, and very hard to differentiate from truly random sources without knowing the decryption key. $\endgroup$ – Neil Slater Dec 30 '14 at 21:25
2
$\begingroup$

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.

| improve this answer | |
$\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.