14 votes
Accepted

Need for 3 rounds in Luby Rackoff theorem

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$ ...
Samuel Neves's user avatar
  • 12.4k
14 votes
Accepted

Can a Feistel network have more than two halves, widening the block width?

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 ...
kodlu's user avatar
  • 21.2k
13 votes
Accepted

Why do Feistel ciphers need round keys?

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 ...
user49042's user avatar
  • 146
12 votes

Why do Feistel ciphers need round keys?

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 ...
otus's user avatar
  • 32k
11 votes

Feistel-Network - why wire crossing?

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. ...
mikeazo's user avatar
  • 38.5k
9 votes

Feistel-Network - why wire crossing?

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 ...
Ella Rose's user avatar
  • 19.5k
9 votes
Accepted

Why 3 round Feistel cipher are not common

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 ...
CodesInChaos's user avatar
  • 24.8k
9 votes
Accepted

How to find fixed points for DES weak keys

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 ...
fgrieu's user avatar
  • 138k
8 votes

Why is AES not a Feistel cipher?

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 ...
crypt's user avatar
  • 2,397
8 votes

In a Feistel cipher structure, what exactly does the "round function $F$" do?

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 ...
poncho's user avatar
  • 145k
7 votes
Accepted

Slide attack: creating an actual attack on the Simon Cipher

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 ...
Matthew Fisher's user avatar
7 votes
Accepted

How random are permutations generated from Feistel networks with a small number of rounds?

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 ...
Luis Casillas's user avatar
7 votes
Accepted

Two Round Feistel network

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: ...
fgrieu's user avatar
  • 138k
6 votes
Accepted

What is the definition of Feistel Cipher?

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 ...
fgrieu's user avatar
  • 138k
6 votes
Accepted

What is the diffrence between Feistel networks and SPN?

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:...
Biv's user avatar
  • 9,969
6 votes

Need for 3 rounds in Luby Rackoff theorem

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 ...
Ella Rose's user avatar
  • 19.5k
6 votes

Why do Feistel ciphers need round keys?

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 ...
p-steuer's user avatar
  • 126
6 votes
Accepted

How can I prove that a Feistel round is its own inverse for DES?

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)\...
fgrieu's user avatar
  • 138k
6 votes
Accepted

DES f function injective for no fixed subkey?

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 ...
Thomas Pornin's user avatar
5 votes
Accepted

Does XOR have diffusion properties?

Let's take the definition from Wikipedia: Diffusion means that if we change a single bit of the plaintext, then (statistically) half of the bits in the ciphertext should change, and similarly, if ...
Maarten Bodewes's user avatar
  • 91.9k
5 votes
Accepted

Is 3 rounds of Feistel enough for making a PRP?

Wel'll consider a symmetric Feistel cipher with $n$-bit block using ideal independent random functions at each round. Making it computationally indistinguishable from a random permutation requires ...
5 votes
Accepted

Disadvantages of the Feistel network

Well, what are we comparing Feistel networks to? The other major design paradigm is SPN: https://en.wikipedia.org/wiki/Substitution-permutation_network. In comparison to SPN, the cons are: Not a ...
DepressedDaniel's user avatar
5 votes

What is the importance of $f_k$ in a feistel network being a permutation

I assume that you are referring to the round function. This is false. The whole advantage of a Feistel network is that $f_k$ does not need to be a permutation. Indeed in DES, it is not a permutation. ...
Yehuda Lindell's user avatar
5 votes
Accepted

PRP vs PRF for the F-function of a Feistel network

Does it impact Luby and Rackoff's observation regarding 3 and 4-round Feistel networks with ideal F-functions? No. What are the theoretical cryptographic implications of using a PRP instead of a ...
SEJPM's user avatar
  • 45.7k
4 votes
Accepted

Big block cipher as memory-hard function

I've been toying around with your function, and I've come to the conclusion it's not memory hard. The amount of required memory can be reduced to at maximum ...
Daan Bakker's user avatar
4 votes
Accepted

Can the round function $F$ in a Feistel Network be practically any non-invertible function?

Yes you could use a hash function as round function, but if you are using the "same key" over all rounds, you are vulnerable to slide attacks. Using a hash function is not a very good idea. Your ...
thepacker's user avatar
  • 188
4 votes
Accepted

How does Feistel cipher create diffusion between blocks?

If a message is longer than the block length, how would changing one part of the message affect the encryption of other parts of the message? That really doesn't depend on the block cipher in use,...
SEJPM's user avatar
  • 45.7k
4 votes
Accepted

Can you decrypt with 1 round key?

It depends on the block cipher in question - specifically its key schedule. Knowing any round key of AES-128 would let you calculate the key, because the schedule is reversible. OTOH, e.g. TEA would ...
otus's user avatar
  • 32k
4 votes
Accepted

Are non bijective sboxes weaker (on feistel networks)?

No. It is one of the main features of a Feistel network that both decryption and encryption just need to evaluate the S-box in the same direction. It could potentially be a weakness if you used ...
tylo's user avatar
  • 12.6k
4 votes
Accepted

Feistel cipher key generation and round function algorithms

In the best maths I can manage, Feistel ≠ DES but rather DES ∈ Feistel. This is important as that's what's confusing you. It's just that DES is extremely prominent in the literature so articles are ...
Paul Uszak's user avatar
  • 15.2k

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