Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Can anyone explain the following text passage to me?
Most real-world block ciphers build even permutations, because it's hard to build odd ones using small operations (32 bit) on larger (128 bit) block size.
I don't understand the connection between parity of a permutation and small operations.
First of all, we need to review what they mean by "parity of a permutation"; they don't mean whether the input block had a even number of 1's.
Instead, they view the $n$ bit cipher (with a specific key) as a permutation on $2^n$ objects; that is, it can be review as a way of rearranging that set of $2^n$ objects onto itself.
Now, permutations on a finite set of objects has a "parity"; that is, any specific permutation can be generated by a series of exchanges between the objects; there are a large (actually, infinite) number of ways of expressing any specific permutation as a series of exchanges, however if an permutation can be expressed as an even number of exchanges, any other set of exchanges that express that same permutation will also be even; we then say that this is an "even" permutation. Similarly, if a permutation can be expressed with an odd number of exchanges, we say that this is an odd permutation.
Now, if we perform an even permutation on a set of objects, and then do a second even permutation, the resulting permutation will also be even. Because block ciphers are commonly expressed as concatenations of round functions (where you first do one round function, then the second, etc), that means that if each round function is even, then the overall block cipher will be even.
Now, what does this have to do with small operations? Well, most of the obvious ways to use a 32 bit operation within a 128 bit block cipher will result in an even permutation. For example:
If you use the 32 bit operation on 32 bits of the block in an invertible way, and don't touch the other 96 bits, this will always be even. AES can be modeled in this way.
If you take a function of some of the block cipher bits (and possibly key bits), and exclusive-or that into the other block cipher bits (Feistal network), this will always be even, as long as you're excluseive-or'ing into at least two bits. Hence, virtually most Feistal-based ciphers will be even.
Now, just because most operations will be even, it doesn't mean that all operations are. Here is one that can be odd: if we split the 128 bit block into 4 32-bit tracks $A$, $B$, $C$, $D$, then this operation can be an odd permutation:
A += F(B, C, D, Key)
(where the addition is performed modulo $2^{32}$). Obviously, that can be a part of an unbalanced Feistel design.
So, if it is possible that we can construct a block cipher with an odd permutation, why don't we? Well, as far as I can tell, because no one cares. If the attacker knows that a block cipher is an even permutation, all that means is that if he obtains $2^n-2$ entries in the code book, he can deduce the last two. Given that he can't really deduce anything more than that, people are content to leave that on the table.
