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$ ...
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 ...
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 ...
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 ...
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.
...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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:...
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 ...
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 ...
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)\...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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,...
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 ...
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 ...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
feistel-network × 132block-cipher × 34
des × 30
encryption × 24
algorithm-design × 16
pseudo-random-permutation × 12
s-boxes × 9
aes × 8
format-preserving × 8
cryptanalysis × 7
pseudo-random-function × 7
keys × 6
provable-security × 6
known-plaintext-attack × 6
spn × 6
luby-rackoff × 6
permutation × 5
symmetric × 3
chosen-plaintext-attack × 3
substitution-cipher × 3
blowfish × 3
hash × 2
attack × 2
xor × 2
complexity × 2