# Parity attack on block cipher

My misunderstanding is all about the parity attack mentioned in "Cryptography Engineering by Ferguson, Schneier and Kohno".

Most modern block ciphers have a 128-bit block size, but they operate on 32-bit words. They build the encryption function from many 32-bit operations.This has proved to be a very successful method, but it has one side effect. It is rather hard to build an odd permutation from small operations; as a result,virtually all block ciphers only generate even permutations.

I still do not get in how far a parity attack will be helpful. Why only ideal ciphers have odd permutations? Can someone form an example why odd permutations need more operations and why it is hard to realize with the current hardware being able to do 32-bit operations only?

I did not get smart by another thread on this forum exactly on this question.

When dealing with a block cipher of large block size, the text appearing as a quote in the question

Most modern block ciphers have a 128-bit block size, but they operate on 32-bit words. They build the encryption function from many 32-bit operations.This has proved to be a very successful method, but it has one side effect. It is rather hard to build an odd permutation from small operations; as a result,virtually all block ciphers only generate even permutations.

is about a merely theoretical attack. The book's chapter 3 acknowledges it:

This attack has no practical significance whatsoever.

That's because knowing the parity of the permutation implemented by an otherwise ideal block cipher with a $$b$$-bit block and some fixed key only helps adversaries after they have obtained $$2^b-2$$ plaintext/ciphertext pairs: the last two plaintext/ciphertext pairs are revealed by that parity. Before that threshold, nothing actionable comes from that one bit of information.

For example, with $$b=3$$, after an adversary obtained plaintext/ciphertext pairs 0/1, 1/6, 2/5, 3/0, 4/2, 5/7, which we can picture as
0   1   2   3   4   5   6   7
1   6   5   0   2   7   ?   ?
and if the permutation is known to be even, then the adversary can determine¹ that the remaining pairs are 6/3, 7/4 (rather than 6/4, 7/3). But before the adversary obtained the pair 5/7, knowing that the permutation was even was of no help to predict if 5 maps to 3, 4, or 7.

Even if a 128-bit block cipher is known to implement an even permutation for any key, that's not an exploitable weakness. It does allow to build a theoretical distinguisher from an ideal cipher, but only after making so many queries ($$2^{128}-1$$) to the encryption or decryption oracle² that it does not count as attack against usual or reasonable security definitions.

The quoted text is somewhat exaggerating the difficulty of building an odd permutation from small operations; see these comments by poncho:

The standard trick for small block Feistel ciphers is to use modular addition, rather than xor, in each round; that way, the round, and hence the permutation, has a 0.5 probability of being odd. (…) If the two halves of the Feistel state are $$a, b$$, then the update $$a\gets a+F(k,b)$$ can be odd; in fact, it will be if an odd number of the $$F(k,b)$$ values are odd (fixed $$k$$, over all possible values of $$b$$).

¹ Proof: going from 01234567 to 16502734 can be done with an even number of permutations, e.g. 01234567102345671623450716534207165042371650243716502734.

² The challenger randomly choose an ideal random cipher or an even random cipher, the distinguisher tries to guess that choice. It needs $$2^{128}-1$$ queries to determine if the cipher is even or odd, if odd outputs 'ideal', otherwise outputs 'even'. It succeeds with probability $$3/4$$.

• Thanks to @kelalaka for pointing the book and the other part of it that I now quote. I did not find a legal and free online source, thus I quote minimally. – fgrieu Oct 8 '20 at 21:04
• Thanks for clarifying. I got it now. – killertoge Oct 10 '20 at 9:28
• 2^128 - 1 queries to know if it is even or odd at all (last plaintext maps to last ciphertext). And after knowing it we only would need 2^128 - 2 queries for other keys, by acknowledging if a certain mapping is possible with odd or even permutations. Regarding poncho's answer, I need my time to understand. I am not familiar with the formalities there. Thank you again! – killertoge Oct 10 '20 at 9:51