Making an invertible function out of non-invertible parts
johndcook.com
johndcook.com
Sadly, I gather the computational performance Is pretty bad ..
But who cares? Our f(x) is as conceptually simple as an invertible function can be. If we're going to consider it to have been assembled from non-invertible parts, then what's interesting about the fact that an invertible function can be assembled from non-invertible parts? It's impossible to define any function, invertible or not, without using non-invertible parts -- by this definition.
Your example is also poorly chosen. f(x) = x + 3 is invertible because it is the composition of two invertible functions, the identity (x => x) and the add-three function (x => x + 3). If we took your f(x) = x + g(x) example, it would be non-invertible for many g, for example when g(x) = -x. So I think there really is something to be said for “assembling an invertible function out of non-invertible parts”.
But Vigenère ciphers aren't really an improvement on substitution ciphers. (And they're not more non-invertible than simple substitution ciphers.) Most of the work is being done by the transformation that swaps two halves of the text between rounds.
But this is just incorrect as a description of the article. The round functions for ciphers are not non-invertible. They're invertible individually, and that's why the overall cipher, which consists of chaining them together, is also invertible.
In order to invert a single round cipher, you need to know f(R_{n-1}, K_n). R_{n-1} is given, and by hypothesis you possess the key K_n, so you do know this value.
f(R_{n-1}, K_n) is the function identified as non-invertible, not the round cipher. It doesn't matter at all whether it's non-invertible, because you don't run it backward. You run it forward.
In your example, if we have f(x) = x + g(x), and we analogously have knowledge of the input to g, it still doesn't matter whether, in the absence of that knowledge, f(x) is invertible or not. Since we know the value of g(x), we can invert f(x), because f(x) is a single application of a trivially invertible function. (f(x) = x + g(x), where g(x) is constant.) Using your example, when f(x) = x + g(x), g(x) = -x, and I know that f(x) = 0 and g(x) is 5, I can easily invert f(x): x is -5.
My example was specifically suggested by the article:
> Here ⊕ is bitwise XOR (exclusive or) and f(R_{n-1}, K_n) is any function of the previous right sub-block and the key for the nth round. The function f need not be invertible. It could be a hash function. It could even be a constant, crushing all input down to a single value. It is one of the non-invertible parts that the system is made of.
(My emphasis.)
In fact, it is the only non-invertible part in the system as described.
If we keep the example of f(x) = x + 3, what you're saying above is that this function cannot be inverted by someone who knows that f(x) takes the form f(x) = x + g(x), but doesn't know that g(x) = 3. That's true, but -- once again -- I don't see how it means that f(x) is "made from non-invertible parts" in any way that every other function doesn't also satisfy.
> f(x) = x + 3 is invertible because it is the composition of two invertible functions, the identity (x => x) and the add-three function (x => x + 3)
This is begging the question. You just said that f is invertible because (1) it is the composition of f with the identity function [true - that is the definition of the identity function]; (2) the identity function is invertible [true again!]; (3) f is invertible [oops]. We can boil that down to "f is invertible because it is". In fact, f is invertible because it is one-to-one -- f(a) = f(b) if and only if a = b.
You even have a paragraph explaining what the author of the article is explaining, which is how to use a non-invertible function g(x) in an invertible way. So it still seems to me that "But who cares?" is pretty dismissive of the article.
By this article's definition of "made with non-invertible parts", _all_ functions are "made with non-invertible parts". As such, the description is fully meaningless.
Hence my reaction of "who cares?". In order for the idea "this function is made with non-invertible parts" to be interesting, it has to distinguish that function from some other function. Any other function.
> The Feistel construction also reduces making a cipher down to (more or less, putting aside key scheduling and number of rounds etc) to producing one extremely good non-invertible function.
This doesn't seem right either. Suppose we use the ultimate non-invertible function: f(a,b) = 0, an algebraic kernel. In that case, the cipher we get will be awful -- for one thing, using an even number of rounds will make the ciphertext equal to the plaintext. In order for the cipher to work well, the output of the Feistel function must be cryptographically unpredictable. It doesn't need to be non-invertible at all -- if we use, say, SHA-512 as the Feistel function, it is invertible in the same sense in which f(x) = 0 is non-invertible: each input maps to a unique output. (Likely; not absolutely guaranteed.) It is non-invertible in a more colloquial sense: given f(R,K), we don't know how to produce R and K, even though the solution is probably unique.[1] Saying we want the Feistel function to be non-invertible is confusing two different ideas of non-invertibility. (Also, since the goal in decrypting is just to produce f(R,K), the colloquial non-invertibility of SHA-512 looks like something of a red herring: what really counts is that, given f and R, we don't know how to produce f(R,K). This is why f(R,K) = 0 fails so badly.)
[1] The solution is probably unique because this is a block cipher operating on small bit vectors.