Score:2

Why key reuse is not an issue in a Feistel cipher?

ec flag

I have a good understanding of stream ciphers and one time pad. I also know the dangers of using the same key in a PRG for a stream cipher.

However as far as I can tell, the Feistel block cipher uses the same key for every block of plain text (which is expanded into keys for each round). If this is true, why is this not a problem? Is it because the function F and specifically the S boxes used are non invertible (i.e. a single output has many possible inputs)?

et flag
A stream cipher functions like a one time pad - using the same key twice makes it a 2-time-pad which can be attacked - https://crypto.stackexchange.com/questions/59/taking-advantage-of-one-time-pad-key-reuse
et flag
Even in block cipher, you have to alter the key each time by changing the IV etc else information about the plaintext leaks which breaks security. Check modes of operation for block ciphers.
user2357 avatar
us flag
@user93353 I think the modern stream cipher problem of the harm of using the same key has been solved by using IV, am I right?
Score:2
in flag

The one-time pad reuse reveals the differences of plaintexts due to its linearity: $$c_1 = m_1 \oplus k,~~~~ c_2 = m_2 \oplus k,~~~~ c_1 \oplus c_2 = m_1 \oplus m_2.$$

Good block ciphers (based on Feistel Networks or SPN or anything else) on the other hand reduce the information directly leaked by the key reuse: if $c_1 = E_k(m_1), c_2 = E_k(m_2)$, then, given $c_1$ and $c_2$ we can only conclude whether $m_1$ and $m_2$ are equal or not (by checking whether $c_1$ and $c_2$ are equal or not).

First of all, this is not sufficient for modern encryption requirements: such an encryption is still considered insecure, because it still leaks information about the messages.

However, by using an appropriate block cipher mode (such as CBC, CTR), we can randomize the inputs to the block cipher, such that, even if the messages are the same, the inputs and outputs to the block cipher will be different (with very high probability). This way, an attacker won't be able to say if the messages were equal or not just given the ciphertexts.

UPD: to drive the point home, it's not about the non-invertability of the Feistel function $F$ itself: it can be invertible and the FN will still be secure (maybe with a few more rounds). In fact, you don't even need to invert $F$ to decrypt a block. The difficulty of breaking it is that an unknown secret key is used in a complex nonlinear way, making extracting any meaningfull relationship between plaintext/ciphertext blocks very hard (on the contrary to many-time pad, where the relationship is linear and simple).

Maarten Bodewes avatar
in flag
Some indication why it would not be possible to retrieve the key given both known plaintext and ciphertext blocks for a Feistel based cipher would be nice, given the question.
Abhisek Dash avatar
ec flag
@Fractalice Thank you for your response. I understand what you are implying. My question was aimed at finding the "governing dynamics" of block ciphers. All the complexity that goes into a block cipher like the F function that takes half of the input and the key in Feistel ciphers is doing something non invertible. So backtracking is not possible (or atleast very difficult). Is my reasoning correct?
Fractalice avatar
in flag
@RajavelPeriyarajan it's not about the non-invertability of the $F$ function itself. Invertible $F$ can be easily secure. In fact, you don't even need to invert $F$ to decrypt a block. The difficulty is that an unknown secret key is used (before, after, or inside $F$), and this makes decryption very difficult.
Abhisek Dash avatar
ec flag
@Fractalice Yes you are right. The key is what makes the cipher secure. But there is another issue namely key reuse. I think all the complexity inside the non-invertible F function in Feistel cipher facilitates key reuse for every block of plaintext. As you pointed out the cipher may be vulnerable to Chosen Plaintext Attack but at-least it is not as dangerous as two time pad. Without the F function the Feistel cipher would be vulnerable to two time pad. Am I correct in assuming this? Also, can you point me to some ciphers that use an invertible function?
Abhisek Dash avatar
ec flag
In other words, what does the F function accomplish? I guess this is all I wanted to ask.
Fractalice avatar
in flag
@RajavelPeriyarajan e.g. [LBlock](https://eprint.iacr.org/2011/345.pdf)
Fractalice avatar
in flag
@RajavelPeriyarajan It accomplishes something called "confusion": it makes the relation between plaintext/ciphertext/key very complex.
Abhisek Dash avatar
ec flag
@Fractalice Got it. The F function is a PRF (Pseudo Random Function which is non invertible) but the Feistel Cipher as a whole is a PRP (Pseudo Random Permutation which is invertible.) I have a clearer understanding now.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.