12
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

12
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Apr 15, 2014 at 15:59
  • $\begingroup$ 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. $\endgroup$ Apr 15, 2014 at 22:04
  • $\begingroup$ Poncho, everything is explicitly written here, however, the deducing the remaining 2 after $2^n-2$ entries is not clear for me. There are still $2^n!/2 - 2^n$ even permutations. What is the method here? $\endgroup$
    – kelalaka
    Oct 9, 2020 at 18:35
  • 1
    $\begingroup$ @kelalaka: no, after $2^n-2$ entries are specified, there are only 2 possible permutations remaining - we have two inputs $I_0, I_1$ that weren't mentioned in a specified entry, and two outputs $O_0, O_1$ that weren't mentioned in a specified entry. Hence, we have a permutation that maps $I_0, I_1 \rightarrow O_0, O_1$ and we have a second permutation that maps $I_0, I_1 \rightarrow O_1, O_0$; those are the only two possibilities. And, the parity of those two permutations will be different (as you can convert one to the other with a single exchange); hence one will be even and the other odd $\endgroup$
    – poncho
    Oct 9, 2020 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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