Why is the block cipher in the CBC-MAC taken to be a pseudo random permutation (PRP) and not a pseudo random function (PRF)? We don't need the bijective property of the PRP. So why go with it?

  • $\begingroup$ Why not? Most of the time a PRP is faster, and it is nice if you can use the same primitive for both confidentiality and integrity/authenticity (e.g. CCM & EAX mode of encryption). $\endgroup$
    – Maarten Bodewes
    Commented Sep 1, 2014 at 17:37
  • $\begingroup$ Did a bit of research, but this algorithm goes back to FIPS 113 (1985), and that "standard" does not do too much reasoning. OMAC and CMAC papers don't list the reason either. So the best answer may be that it uses a PRP because if it was a PRF, it would be a HMAC :P $\endgroup$
    – Maarten Bodewes
    Commented Sep 1, 2014 at 18:07
  • $\begingroup$ @owlstead, i don't agree that a secure PRP is always faster than a secure PRF. We can make PRFs out of PRGs such as SALSA20 which is fast. Check out cryptopp.com/benchmarks.html $\endgroup$
    – BlaX
    Commented Sep 1, 2014 at 22:09
  • $\begingroup$ OK, maybe "most of the time" is taking it a bit far. The fact that you can use the same primitive as for confidentiality certainly is a feature though. Note that you could of course also use a stream cipher and a derived HMAC for confidentiality. See for instance the Spritz paper. $\endgroup$
    – Maarten Bodewes
    Commented Sep 2, 2014 at 11:18

1 Answer 1


The CBC-MAC construction indeed can use a PRF instead of PRP. It is now based on PRP due to historical reasons: the blockciphers used for CBC-MAC were based on permutations.

From the security point of view there will be no difference: the security proof for the CBC-MAC first converts PRP to PRF (which is indistinguishable up to $2^{n/2}$ queries) and then derives an actual upper bound on the adversary's advantage.

  • $\begingroup$ So this means I can based my CBC-MAC using SALSA20 where the message can be the seed? $\endgroup$
    – BlaX
    Commented Sep 3, 2014 at 14:27
  • $\begingroup$ You can put Salsa20 into the CBC-MAC, but you have to be care with making a PRF out of it. $\endgroup$ Commented Sep 3, 2014 at 14:39

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.