4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The probability of there being a fixed point is very low, for most keys there will not be one. If a cipher had a fixed point for EVERY key, then that would be bad, but most likely only a single fixed point per key exists, and only for a handful of keys $\endgroup$ – Richie Frame Sep 6 '15 at 6:44
  • $\begingroup$ For a random permutation, the probability of picking a key with a fixed-point is 63%. Inferred from the link. Also can we say anything about the number of fixed points? I guess we can't because that's going to random... $\endgroup$ – Harsh Sep 8 '15 at 5:59
  • $\begingroup$ I should have been more clear, I was not talking in a statistical sense, but rather in a "for the bulk of inputs, which is a fraction of the cipher's possible inputs, the chance of one of them having a fixed point is small" sense $\endgroup$ – Richie Frame Sep 9 '15 at 11:09
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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