4 ms·

Sorry that I confused the terms "round function" and "Fiestel function", I thought my intended meaning would still be clear. The Fiestel construction still take

by joppy 7y ago

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.

thaumasiotes 7y ago
I'll repeat my point: 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.

by joppy 7y ago

thaumasiotes 7y ago

I'll repeat my point: 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.