In the cryptography lecture at my university, we had the theorem that (randomized) OFB mode is IND-CPA secure if the used pseudorandom function (PRF) is IND-PRF secure.

Afterwards, we investigated the security of rOFB if a pseudorandom permutation (PRP) is used instead of an PRF. As we can only distinguish a PRP from a PRF if the PRF produces a collision, we can use them interchangeably as long as the block length is large enough. This is the case as for large block lengths the probability of a collision is negligible.

From this result we deduced that we can also use PRPs in rOFB mode which results in a IND-CPA secure encryption scheme.

I totally understand that we can distinguish a PRP from a random function oracle (RFO) if the RFO produces a collision. Therefore, the PRP 'does not look random' if we can query many outputs. However, the security of rOFB mode requires that we do not have a collision in the ciphertexts. Therefore, I do not understand why the security of rOFB mode is lower when we use a PRP instead of a PRF (negligibly lower, but lower) as a PRP does rule out exactly this attack on OFB.

It is clear for me that the PRP-OFB mode does not look like an OTP for many queries, but I cannot imagine why the attack surface should be negligibly higher if there is NO collision possible.


1 Answer 1


I think the final negligible term depends on the way you prove the rOFB security. If you construct OTP in the ideal word based on random functions, then use PRF; if based on random permutations, then use PRP. Note that in the latter case, replacing block ciphers with random permutations cannot guarantee that no collisions happen among the block cipher outputs. In other words, such collisions are not the same as those considered in PRF/PRP.

The attack surface for PRP is not negligibly higher. It seems higher just because you first prove the security with PRF and wants an easy reduction based on the advantage difference between PRP and PRF. Btw, any negligible difference should not matter in the security proofs.

  • $\begingroup$ Based on your answer, I think that I got our slides the wrong way. I think that they wanted to point out that we have to be aware about such changes and that we have to consider collisions if we want to use a PRP as a PRF replacement. But this does not imply that the ES is less secure. Thanks for the clarification! I know that a negligible difference does not matter in practice, but I wanted to mention that we get some difference in theory which I could not understand. $\endgroup$
    – PraMiD
    Feb 17, 2018 at 8:08
  • $\begingroup$ @PraMiD Sure! I am happy to help on this. $\endgroup$
    – Shan Chen
    Feb 17, 2018 at 21:23

Your Answer

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

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