2
$\begingroup$

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)?

$\endgroup$
3
  • $\begingroup$ A stream cipher functions like a one time pad - using the same key twice makes it a 2-time-pad which can be attacked - crypto.stackexchange.com/questions/59/… $\endgroup$
    – user93353
    Sep 28, 2021 at 12:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – user93353
    Sep 28, 2021 at 12:12
  • $\begingroup$ @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? $\endgroup$
    – user2357
    Sep 30, 2021 at 17:02

1 Answer 1

2
$\begingroup$

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).

$\endgroup$
8
  • 2
    $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Sep 28, 2021 at 13:50
  • $\begingroup$ @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? $\endgroup$ Oct 4, 2021 at 15:09
  • 1
    $\begingroup$ @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. $\endgroup$
    – Fractalice
    Oct 4, 2021 at 15:59
  • $\begingroup$ @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? $\endgroup$ Oct 4, 2021 at 16:56
  • $\begingroup$ In other words, what does the F function accomplish? I guess this is all I wanted to ask. $\endgroup$ Oct 4, 2021 at 17:16

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.