Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

So according to Wikipedia unbalanced feistel ciphers provide greater provable security. Specifically, they state:

The Thorp shuffle is an extreme case of an unbalanced Feistel cipher in which one side is a single bit. This has better provable security than a balanced Feistel cipher but requires more rounds.

Which is a summary of the paper "How to Encipher Messages on a Small Domain — Deterministic Encryption and the Thorp Shuffle".

Forgive the simplicity of the question I'm about to ask, but as an amateur, to me this seems counter intuitive. If for each plaintext block we have:

$$L_{i+1} = R_i $$

and

$$R_{i+1} = L_i \oplus F(R_i, K_i)$$

Where F is the round function, then doesn't constraining either $L_i$ or $R_i$ to a single, or fewer bits (given whichever side is smaller, they will swap in the next round) mean that each xor is easier to reverse since only single bits are being altered at a time (and we know this reliably since algorithms aren't secret...)? Does that not make the cipher more susceptible to side channel attacks, essentially becoming more of a stream-like operation?

So, is this actually the case and if so why? Is there any particular implementation of an unbalanced feistel cipher one should avoid - for example, are there optimum sizes for the data size bigger than a single bit?

share|improve this question

1 Answer 1

up vote 16 down vote accepted

Actually the article you link to does not says that a balanced Feistel cipher is less secure than an unbalanced one; it says that the security of an unbalanced Feistel cipher is more easily proven, given enough rounds.

Luby and Rackoff have shown in 1988 that a balanced Feistel scheme with only 4 rounds is "perfectly" secure as long as the round functions are "random enough". This deserves clarification: Luby and Rackoff use n-bit blocks, and their results holds up to, at least, 2n/4 queries (the attacker is allowed to submit up to that number of blocks to encrypt or decrypt to a black box which knows the key, and yet he still cannot predict the encryption or decryption of another value with non-negligible probability). Maurer and Pietrzak, and then Patarin, later showed that with more rounds, one can get as close as wanted to the 2n/2 limit (6 rounds suffice, as Patarin demonstrated). (Of course, "random enough" round functions are ideal objects whose existence is not clear; existing Feistel-based ciphers use faster functions which are certainly not "random enough", and compensate by adding more rounds.)

By making n big enough, 2n/2 is large enough to achieve sufficient security (e.g. use n = 256).

Morris, Rogaway and Stegers study the problem of encrypting very small blocks; thus, they cannot make n "large enough". They must cope with a small n. The maximum theoretical security of a Feistel scheme (balanced or not) is 2n-3 queries (there are 2n possible block values; if the attacker knows the encryption of all save two, then he can guess the remaining two with 100% accuracy, because Feistel schemes are always even permutations; this is the only known structural weakness of Feistel ciphers). The authors say quite clearly (end of page 4) that there is no known practical attack on a Feistel cipher with enough rounds, even with small blocks, so the 2n-3 security limit is in practice achieved. But they want more than practical security, they want proven security. A security proof works by assuming that the round functions are information-theoretically secure, and sees how the whole cipher stands up under that assumption. The trouble with a balanced Feistel cipher is that such proofs cannot go beyond 2n/2.

On the other hand, with an unbalanced cipher and many rounds (much more than 6; figures in the article go to about 64 rounds), it is possible to get a security proof close to 2n. This does not mean that unbalanced Feistel ciphers are "more secure", only that information-theoretic tools are more easily applied for proving security of an unbalanced Feistel cipher. And a single unbalanced round is certainly not more secure than a single balanced round; quite the opposite: security-wise, a single unbalanced round sucks. But if you accumulate enough such rounds, then you can boost the security proof to higher levels.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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