Another example is RealNVP, which has the same structure to enable inversion (partition, process half, then use the result to mutate the other half in an invertible way).
Sadly, I gather the computational performance Is pretty bad ..
This is a weird headline. It amounts to the claim that f(x) = x + 3 is made from non-invertible parts because its "subcomponent" g(x) = 3 is non-invertible.
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.
I think this is pretty dismissive of what the author is trying to explain: the round functions for ciphers are non-invertible, and there is a construction which strings them together such that the whole thing is invertible. That’s pretty interesting!
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”.
> what the author is trying to explain: the round functions for ciphers are non-invertible, and there is a construction which strings them together such that the whole thing is invertible. That’s pretty interesting!
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.
Sorry that I confused the terms "round function" and "Fiestel function", I thought my intended meaning would still be clear. The Fiestel construction still takes a non-invertible function and produces an invertible function, in a way that use useful cryptographically. Would you prefer that the article title was "making a useful invertible function out of non-invertible functions"? The Fiestel 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.
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.
I think the parent's point is that it's not `f(x) = x + g(x)`, but `f(x) = x + g(c)` for some c. Addition is invertible if one side is constant, no matter how that constant is determined: g can be bijective or constant, it doesn't matter for the invertibility of the addition.
Yes, the inclusion of the Feistel function makes the raw xor (a substitution cipher) into a Vigenère cipher instead, where the encryption key differs between locations in the text instead of being constant throughout.
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.
g(x) = 3, alone, is not. I give you 3, and there's no possible way you're telling me what the original x value was. f(x) = x ⋄ g(x) is (for ⋄ in {+, ×}), but that's a different matter entirely.
The article talks about Feistel networks and the most famous Feistel cipher, DES. I wrote a spreadsheet where you can examine every bit of the computation of DES encryption: https://www.nayuki.io/page/des-cipher-internals-in-excel
15 comments
[ 3.3 ms ] story [ 40.0 ms ] threadhttps://arxiv.org/abs/1802.07088
Sadly, I gather the computational performance Is pretty bad ..
https://arxiv.org/abs/1605.08803
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 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.
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.