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.

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.

share|improve this question

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
We do not care to construct a WIDE block cipher with an odd permutation; however this is sometime done in the context of Format Preserving Encryption with small block size. –  fgrieu Apr 15 at 15:59
    
Great answer. Thanks! +1 –  RomeoAndJuliet Apr 15 at 19:31
    
Generalizing your first example, if we start with any permutation, and extend the state space being permuted by at least one extra bit (which does not affect the permutation and is not affected by it), then the resulting extended permutation will be even. –  Ilmari Karonen Apr 15 at 22:04

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.