3
$\begingroup$

Consider a single round of a cryptographic permutation, what is so special about it that lacking some bits of information that either get mixed into it as a subkey or omitted at the end (sponge construction) makes you unable to revert it efficiently once it gets looped in sufficient number?

The best analogy I could come up with is a chaotic dynamical system, where any tiny change eventually gets amplified out of control (where the evolution of the two systems - changed and unchanged - no longer encodes any information about the change). And even though it is in a continuous domain where gradients can be analytically computed, after a certain point they either explode to infinity or vanish to 0.

There, there is the jargon of stretching and folding - the fractal dimension, how points get stretched out into the fractal dimension and then get folded back (this achieves a mixing of sort and eventually any two points no matter how close get further and further apart until eventually they completely dissociate as they each get sent into different parts of the attractor).

This seems similar to confusion and diffusion.

Is what's being done in cryptographic permutations the same phenomenon but in a discrete domain?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ The most simple (but not perfectly correct) analogy is addition. If I give you the number "427601", you have no idea what two integers I added to get it, despite addition being a trivial, public operation. $\endgroup$ – forest Aug 30 '19 at 6:26
  • $\begingroup$ @forest But this analogy seems bad. A permutation is a one-to-one mapping, it perfectly preserves information. Addition does not. $\endgroup$ – user71538 Aug 30 '19 at 6:29
  • $\begingroup$ Correct. It is a very simple analogy. I'm currently looking for a much better explanation, which I think I found on some site describing differential cryptanalysis. $\endgroup$ – forest Aug 30 '19 at 6:31
  • 1
    $\begingroup$ I would say what makes crypto permutations 'special' is that in most cases they are designed to be pseudo random permutations for the point of view of someone who doesn't have the key that selects the permutation. In other words, if we haven't observed anything then for an output y, all input $x$ have the same probability of being the input that gives this output.(The probabilities change after we observe a tuple $(x', y')$). So reversing is difficult unless you have alot of observations. Furthermore the permutaions have very large input and output spaces. $\endgroup$ – Marc Ilunga Aug 30 '19 at 11:29
  • 2
    $\begingroup$ So an adversary will need an exponential number of observation before the posterior probabilities allow for brute force or something like that. This is what the CBC-MAC for example uses, a chaining of permutations seeded by a random IV. And we can show that CBC MAC is secure up to $q$ queries where $q$ is essentially exponential. A bit of an unorganized answer(in the comments). I can write it better later. ;) $\endgroup$ – Marc Ilunga Aug 30 '19 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy