# Tag Info

## Hot answers tagged feistel-network

24

Well, AES is not a Feistel cipher because it's a substitution-permutation network instead. If I were taking a test that asked me why AES was not a Feistel cipher, this would be my argument: namely, that the structure of substitution-permutation networks is fundamentally different from that of Feistel networks. (Here one could elaborate on invertibility and ...

17

DES actually demonstrated that a Feistel structure was not a guarantee against attacks. In "academic" terms, DES is broken by both differential and linear cryptanalysis, because they require, respectively, $2^{47}$ chosen plaintexts and $2^{43}$ known plaintexts, whereas the DES key is (effectively) 56 bits. Of course, for practical attacks, we would brute ...

14

There are designs called generalised unbalanced feistel networks which do exactly this. See the paper by Schneier and Kelsey here. The CAST cipher, an AES competition entry was an early example. The article on cryptowiki gives a brief summary here Here is an example:

13

Iterated ciphers need variability between rounds to resist so callad Slide attacks. One common way to thwart this attack is with a key schedule generating different round keys for each round. Slide attacks exploit the repeating rounds of the cipher by finding a collision between one input plaintext and the intermediate value after one round of encryption of ...

12

By definition, a Feistel network uses a series of rounds that split the input block into two sides, uses one side to permute the other side, then swaps the sides. As always, Wikipedia has a nice diagram. AES doesn't do this. Performing a round necessarily permutes the entire state. Each round consists of the SubBytes, ShiftRows, MixColumns, and AddRoundKey ...

12

This is due to Luby and Rackoff's proof about Feistel networks. The proof assumes the PRFs are independent. See sections 4.5 and 5 of How to Construct Pseudorandom Permutations from Pseudorandom Functions (paywall). Simply using the same key for four rounds is not secure, but there are other ways to key with fewer than four round keys which are secure, see ...

11

The proof is loosely as below. Lets assume a one round Feistel network, where $2n$ bits are divided into $n$ bits each $L_0, R_0$ The encryption is defined as $L_{1} = R_{0}, \\ R_{1} = L_0 \oplus f(R_0)$ where f is any random function (PRF) and $\oplus$ is XOR operation Now the cipher text is $L_{2} = R_{1}, R_{2} = L_1$ Decryption is same as ...

11

The simple answer is that fewer than 3 rounds can be easily distinguished from a random permutation. The 2-round Luby-Rackoff cipher on $2n$ bits, using random functions $f_i$ mapping $n$ bits to $n$ bits, consists of $$F(L, R) = (A, B),$$ where $A = L \oplus f_1(R)$ and $B = R \oplus f_2(L \oplus f_1(R))$. Now consider an attacker that wants to ...

11

Let's look at a picture of a generic feistel cipher Notice that no keying material is used during or after that final swap. So, we can conclude that the final swap does not impact security at all. So, why include it? It is so that all rounds will be identical. This could help with some implementations. That is all.

9

If such a network had only a single round, then you might have a valid concern. This is why there needs to be least three rounds, so that every bit from L can potentially affect every other bit from L (via R from the second round). It isn't a structural flaw, because multiple rounds are assumed. Changing this round structure would mean that it was no longer ...

9

It's there to facilitate a simple implementation. As there is no key addition applied afterwards, the final swapping of the halves does not contribute towards security. The Feistel cipher entry on tutorialspoint explains: Decryption Process The process of decryption in Feistel cipher is almost similar. Instead of starting with a block of plaintext, the ...

9

The main issue is that this only holds if you start with a PRF. Constructing a secure PRF is just as hard as constructing a secure strong PRP, so haven't gained much. In practice we typically start with constructing a PRP and then turn it in into a PRF, not the other way round. Feistel based blockciphers use many rounds, because their round functions are ...

9

I answer in hopefully didactic order. What does the author mean by the intermediate texts exactly? The intermediate texts after $n$ rounds are the 64-bit quantities $L_n\mathbin\|R_n$, numbering these per the specification of DES. $L_n$ and $R_n$ are the halves. Why after the eighth round of encryption the two halves must be equal? I do not know if ...

8

DES with 2 rounds is broken. It is trivial to find a way to get the key with much less work than for the full DES (and even that is broken). DES is a Feistel cipher, so we have two halves, the left and the right half. For every round, we do something with the one half and a subkey, and then XOR it with the other half. After that we switch both halves, ...

8

No, this is not a structural weakness of Feistel networks. For instance, we know it can't hurt diffusion properties. Actually, we know that it's not a structural weakness. How do we know that? Because we have a proof of security for Feistel networks (under certain conditions and assumptions). Those proofs imply that there is not a structural weakness in ...

8

You run the algorithm with two different plaintexts (whose difference is usually small – just a few bits, everything else being equal). Wherever these plaintexts lead to different inputs to an S-box (in any layer/round of the algorithm), we call this S-Box “active” (since the other S-boxes produce the same result for both plaintexts, they are called “...

8

A Feistel network is a way of constructing an invertible permutation from a (possibly non-invertible) function. If the function used is pseudorandom and has a large domain, then 3-4 rounds yields a pseudorandom permutation (3 rounds suffice if the adversary can only ask "compute" queries, and 4 rounds are needed if the adversary can ask "invert" queries). ...

8

What exactly does the "round function F" do Pretty much anything it wants, with the proviso that it must be a deterministic function of the right hand data and the keying data; it cannot depend on the left hand data. With that constraint, you get an easily invertible cipher structure, with the inverse function being essentially the same (except that you ...

7

The simple answer is "Because its an SPN cipher". What is difference between Feistel and SPN? SPN operates on whole data in one round, where as Feistel divides data into N parts where N>=2 , then operate upon X parts where 0 Image Sources: FEISTEL, SPN In balanced, data is divided in Two parts i.e N = 2, and X=1 (example is camellia cipher) In Unbalanced,...

7

You should read David Wagner's original paper. You can see all of his work here. He authored the 'Slide Attack', 'Advanced Slide Attacks' and a few more related to the attack. Wikipedia has a good introduction here Feistel ciphers like Simon are very vulnerable to Slide Attacks and similar. Removing the round constants from the key schedule will likley ...

7

The Luby-Rackoff theorem says that a 3-4 round Feistel network is a pseudorandom permutation for some sufficiently large block size. As this paper by Patarin on Feistel networks with 5 or more rounds puts it: We will denote by $k$ the number of rounds and by $n$ the integer such that the Feistel cipher is a permutation of $2^n$ bits → $2^n$ bits. In [3] ...

7

I read that two-round Feistel network is not a secure PRP That's easily seen:                                     It holds $P_L\oplus C_L=F_0(P_R)$. That implies a distinguishable property: for any fixed $P_R$ and whatever the round function $F_0$, when we flip bit(s) in $P_L$, that flips the corresponding bit(s) in $C_L$ and leaves the other bit(s)...

6

The question has morphed over time. I am answering the following. So to be sure, with DES, only when you encrypt something twice with a weak key. You get the back the original plaintext? That is correct as that is the definition of a DES weak key, a key for which encryption and decryption have the same effect. So when using DES in OFB mode with a ...

6

In a Feistel networks (from the German IBM cryptographer Horst Feistel), the input is divided into two blocks ($L_0$ and $R_0$) which interact with each other. Main example is DES. basic construction: In a SPN (Substitution Permutation Network), the input is divided into multiple small blocks, applied to a S-box (substitution), then the bits positions are ...

6

According to Definition 7.81 given by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, A Feistel cipher is an iterated cipher mapping a $2t$-bit plaintext $(L_0,R_0)$, for $t$-bit blocks $L_0$ and $R_0$, to a ciphertext $(R_r,L_r)$, through an $r$-round process where $r\ge1$. For $1\le i\le r$, round $i$ ...

6

It does not make sense to say that any fixed function $F$ "is a good PRF". A distribution on functions can, however, be pseudorandom (indistinguishable from the uniform distribution over the set of all functions). Therefore, it makes sense to consider keyed functions to emulate a random oracle.

6

There's a simple way by which "each round of DES algorithm is its own inverse". Consider round $n$ of DES as involving (almost only) a function $g_n$ with $$g_n(L\mathbin\|R)=\bigl(L\oplus f(R,K_n)\bigr)\mathbin\|R$$ where $K_n$ is the 48-bit subkey for round $n$, function $f$ is the "cipher function" (given in the definition of DES), and $L$ and $R$ are 32-...

6

First thing to observe is that a DES-like confusion function can be a permutation, depending on the contents of the S-boxes. DES S-boxes are formally defined as $6\rightarrow 4$ functions, with the leftmost and rightmost bits selecting a row, which itself defines a $4\rightarrow 4$ function applied on the four central bits of the input. This last function is,...

5

As a page at ibm.com indicates, there could have been a bit of a "contra" attitude against Feistel ciphers thanks to DES having seen the first breaks in it's security etc. Down with the Feistel structure! In most ciphers, the round transformation has the well-known Feistel structure. In this structure typically part of the bits of the intermediate ...

5

It's required for diffusion and achieving the avalanche effect. The concept of diffusion and the avalanche effect basically means that each input bit should influence each output bit evenly. Changing one input bit should flip, on average, half the output bits. Due to the nature of the Feistel construction, how it is split up into halves, only one side ...

Only top voted, non community-wiki answers of a minimum length are eligible