4
$\begingroup$

There are a number of message authentication codes (MACs) used in practice. They are highly used in practice (f.ex. in TLS), but there's (at least) one application where they can't be used: Full Disk Encryption (FDE).

Now most FDE applications just don't bother with authentication. TrueCrypt for example has no authentication mechanism in place for authenticating the bulk data. However it uses CRC-32 (!) to ensure integrity of the data encryption keys in the header. The advantage this provides is that the ciphertext may be completely indistuingishable from random.

Now I want to create a data container format with the same property (complete file is random-looking) but want to perform strong authentication of the data encryption keys. This means I need to use authenticated encryption (AE).

Most of the AE schemes append a tag to the ciphertext and to ensure pseudorandomness of the whole file this tag also has to be random looking. The desired notion for this would be IND-CPA.

So my question:
Are the output tags of the common MACs / AE-modes indistinguishable from random data under chosen plaintext (or eavesdropper?) attacks?

What is considered common MACs / AE-modes:

  • GCM
  • EAX
  • CWC
  • HMAC
  • CMAC / CCM
Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I'm a little confused by your title. The security notion usually targeted by MACs is unforgeability against a chosen message attacks (UF-CMA), not IND-CPA. It is not clear to me what it should mean for a MAC to satisfy IND-CPA. When you say that you want the MAC tag to be "random looking" did you mean this in the sense of the MAC being a PRF? Still, note that a MAC does not necessarily have to be a PRF in order to be UF-CMA (a PRF is a secure MAC though). Moreover, it is not necessary for the tag to be "random looking", as you say, in order for an AE scheme to be IND-CPA/IND-CCA secure. $\endgroup$
    – hakoja
    Aug 7, 2015 at 12:31
  • $\begingroup$ @hakoja, that's kinda my question: Are the deployed MACs random looking? I already know that they're UF-CMA. As for what I understand under random-looking: Assume the standard IND-CPA experiment: The advesary output some message and gets two strings (=the tags) in response (generated accordingly to the mode). One of these strings is the valid MAC, the other one is just random. Now he has to decide which one of those is random and which one is the MAC-tag. Before and after seeing the tag he has full access to an oracle generating MACs (and probably ciphertexts). $\endgroup$
    – SEJPM
    Aug 7, 2015 at 12:36
  • $\begingroup$ Yeah, "indistinguishable from random" seems like you want to know which of them are PRF. @SEJPM, do you want them to be indistinguishable from a MAC of a random message or from random data? $\endgroup$
    – otus
    Aug 7, 2015 at 12:36
  • 1
    $\begingroup$ First, the IND-CPA game is meant for encryption schemes not MAC's. Secondly, in the IND-CPA game the adversary does not submit one message and gets back two ciphertexts. It's the other way around :-) I.e., he submits two messages and gets back the encryption of one of them. Thirdly, it seems to me now then, that the security notion you should be looking at regarding the MACs is PRF. $\endgroup$
    – hakoja
    Aug 7, 2015 at 12:45
  • $\begingroup$ And to partially answer your question: Yes, some deployed MACs are also PRFs. Like e.g. HMAC. $\endgroup$
    – hakoja
    Aug 7, 2015 at 12:47

1 Answer 1

Reset to default
4
$\begingroup$

The property you are probably looking for is whether the MACs are PRF.

With HMAC it depends on the pseudo-randomness of the hash function used. If the hash is a PRF then the HMAC is as well. However, that is not required for MAC security of HMAC, so it's not necessarily true even with a secure HMAC. See New Proofs for NMAC and HMAC: Security without Collision-Resistance.

In both of EAX and CMAC, the MAC is a particular (unique) output of the block cipher and is indistinguishable from random as long as the block cipher is a PRP and the outputs are not seen too many times to distinguish a PRP from a PRF.

Similarly, GCM outputs the XOR of a unique block cipher output with the GHASH and so is PRF as long as the block cipher is. (You also have to assume that the GHASH output is independent of the block cipher output.)

CWC has a Carter-Wegman MAC that is again indistinguishable as long the block cipher is, because it outputs a XOR of two independent block cipher outputs.

Improve this answer
$\endgroup$
1
  • $\begingroup$ For GCM, you can show independence of the GHASH output from the block cipher output (at least for 96 bit nonces), as the block cipher output is from a plaintext that is distinct from any out the block cipher outputs used to generate the GHASH; hence if the block cipher is a PRP, and we haven't seen enough outputs to distinguish the PRP from a PRF, we're golden. For non-96 bit nonces, it's a bit more subtle. $\endgroup$
    – poncho
    Aug 7, 2015 at 13:24

Your Answer

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

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