Fixed-points in block ciphers; why don't they indicate a vulnerability?

Question

I've seen a few questions here on fixed-points in ciphers, most asking about the possibility and existence. Most of the answers however pointed out that fixed points are not exactly a security threat. Googling about it didn't fetch me much. All I found was this book, which stated it well but does not go on and explain it why!

---

My thoughts (from an attacker's perspective)

If I find out that the block that I captured is a fixed-point, I know the pText as well as eText for this key. So it'd certainly help me crack it faster (both chosen-plaintext-attack and chosen-ciphertext-attack). Additionally, I know that the number of keys that result in such a fixed-point are very few. So maybe there is a way for me to get the possible keys given the fixed-point.

My assumption was that it'd be easy for the attacker to find out that the captured block is a fixed-point because it retains all of the original message's pattern. Also I assumed that the relation from fixed-point to key is quite obvious.

---

So it seems this attack is not considered a threat because my assumptions are wrong (one or both). What am I missing?

Answer 1

Intuitively, the reason fixed points are not a problem is the same reason that zeros in a one time pad are not. Because the transform is supposed to be random, a ciphertext that looks like plaintext could be that plaintext... or it could be any other plaintext. With proper encryption they are all equally likely.

If I find out that the block that I captured is a fixed-point, I know the pText as well as eText for this key.

Yes, but how would you find out that it is a fixed point? By knowing that the plaintext and ciphertext blocks are equal. I.e. this is not additional information.

Additionally, I know that the number of keys that result in such a fixed-point are very few. So maybe there is a way for me to get the possible keys given the fixed-point.

The number of keys with that particular fixed point depends on the key and block sizes. E.g. with AES-256 you'd expect about $2^{128}$ keys with any fixed point you want. In the case of AES-128 it is true that a fixed point would likely be unique to one or two keys. However, there is no way to exploit that knowledge.

If you know $E_k(x)=x$, you can iterate all keys testing for that. But you can do the same if you know $E_k(x)=y$ for some other $y$. So the fact that it is a fixed point does not make key recovery any simpler, unless the internal structure of the cipher is somehow weak with regard to this fact.

So...

My assumption was that it'd be easy for the attacker to find out that the captured block is a fixed-point because it retains all of the original message's pattern.

That assumption is wrong, because there are supposed to be many other blocks that produce patterns that aren't in the original message. The probability that $D(x)=x$ should not be higher if $x$ has patterns.

Also I assumed that the relation from fixed-point to key is quite obvious.

It is not at all obvious. There could be a relation, but that should be considered a weakness in the cipher.