12
$\begingroup$

In the the main post about MAC methods it mentions a few methods:

  • Authenticate And Encrypt: The sender computes a MAC of the plaintext, encrypts the plaintext, and then appends the MAC to the ciphertext.

  • Authenticate Then Encrypt: The sender computes a MAC of the plaintext, then encrypts both the plaintext and the MAC

  • Encrypt Then Authenticate: The sender encrypts the plaintext, then appends a MAC of the ciphertext.

I would like to know which of the last two methods (listed above) is better to provide integrity and authentication for a one-time pad message using HMAC. The method would need to be information-theoretically secure. I do not think it matters if the HMAC method wastes parts of the one-time pad to encrypt the MAC tag.

This paper which is linked in the post above Sadeq Dousti mentions:

On the positive side we show that the authenticate-then-encrypt method is secure if the encryption method in use is either CBC mode (with an underlying secure block cipher) or a stream cipher (that xor the data with a random or pseudorandom pad). Thus, while we show the generic security of SSL to be broken, the current practical implementations of the protocol that use the above modes of encryption are safe.

  1. If HMAC was applied to a one-time pad message using the Authenticate then Encrypt method, would this be more secure than using Encrypt then Authenticate method?

    My thoughts on this are that the Authenticate then Encrypt method is information-theoretically secure because the MAC tag is encrypted by the one-time pad as well. Are there any actual attacks against Authenticate then Encrypt when used with the one-time pad? The paper above claims it is still secure. Also when providing input into the HMAC function, the attacker is missing two key parts of the equation (the plaintext and the key) to be able to create a forgery. There could be any combination of message and any combination of key. It would be impossible for an attacker to determine the real message.

    The general consensus in the post earlier seems to be that Encrypt then Authenticate is more secure method when using standard encryption methods. However this would leave the MAC tag unencrypted so it is not information-theoretically secure. The attacker is already provided with the ciphertext, so perhaps a computationally unbounded adversary could brute force key combinations using HMAC to find the pad/key which matches the MAC tag and available ciphertext, therefore eventually they would find a matching key and be able to decrypt the message.

    Maybe one method to use the Encrypt then Authenticate method in an information-theoretically secure way would be to split the one-time pad into two parts. One part to encrypt the ciphertext message and the other to encrypt the MAC tag. First the message would be encrypted with the first part of the pad. Then the HMAC computed on the ciphertext using the full one-time pad as the key. Then the MAC tag would be encrypted with the second part of the pad and appended to/sent with the ciphertext. For verification it means you can verify the MAC faster by only decrypting the MAC tag first which is a simple xor operation. Maybe it provides just enough speed boost to fend off a Denial of Service attack?

    Which is the better option to use? What alternatives are better for an information-theoretically secure MAC to be used with a one-time pad?

  2. Is there any rule where the MAC tag output length should be related to the length of message or key which is input into the HMAC?

    For example, if the message was 64 bytes in length, should the HMAC tag length be 1/4 of it (16 bytes/128 bit), 1/2 of it (32 bytes/256 bit), same length (64 bytes/512 bit) or something else? Given that the MAC tag will probably be encrypted with one-time pad anyway, is it possible to get away with a shorter tag length and still be information-theoretically secure?

Improve this question
$\endgroup$
13
  • $\begingroup$ Related question: Is there anything wrong with doing $E_k(m)= K\oplus(m||h(m))$ for a secure hash function? $\endgroup$
    – Cryptographeur
    Commented Apr 4, 2014 at 14:11
  • 1
    $\begingroup$ Why do you insist on using HMAC as your authentication mechanism? And more importantly, do you really need to use a one-time pad? Anyway, if unconditional security is your goal for integrity, why not go with a one-time polynomial-based MAC? $\endgroup$
    – hakoja
    Commented Apr 4, 2014 at 16:20
  • $\begingroup$ @hakoja : $\:$ These approaches could make sense if lightspeeder wants $\hspace{1.98 in}$ Long-Term security with minimum key size. $\;\;\;\;$ $\endgroup$
    – user991
    Commented Apr 4, 2014 at 16:55
  • 1
    $\begingroup$ @lightspeeder Note that all the attacks mentioned in that paper are based on real-world schemes where the key is reused for many messages. I suggested a one-time polynomial MAC's for which none of these attacks apply. Since you have already insisted on using a one-time pad for encryption, why not for the MAC as well? $\endgroup$
    – hakoja
    Commented Apr 5, 2014 at 9:00
  • 1
    $\begingroup$ I'm sure a one-time polynomial-based MAC could be applied successfully within the context of UMAC spec, ie selecting a random one-time polynomial-based MAC, performing the MAC the ciphertext then encrypting the MAC tag. What this question is about is why you can't do the same, but use a one-time HMAC instead. I think this has better security e.g. 2^128, 2^256 or 2^512 depending on the hash used, and the tag itself is encrypted with OTP. $\endgroup$
    – lightspeeder
    Commented Apr 5, 2014 at 21:49

1 Answer 1

Reset to default
8
$\begingroup$

First of all there does exist information theoretically secure message authentication codes suitable for use with a one time pad. An HMAC is not one of those information theoretically secure.

As far as I recall the first article presenting such a construction is the 1981 article by Wegman and Carter: New hash functions and their use in authentication and set equality

The construction build upon a specific class of universal hash functions. The MAC is constructed by computing a hash tree over the message, and finally applying a one time pad to the MAC tag.

Since we are not talking about a specific hash function but rather a class of hash functions, you will need key material to chose a hash function for each level in the tree. The key material needed at each level will be the same size as the final tag, the number of levels will be logarithmic in the maximum message size.

The key material used to chose hash functions for each level in the tree is reusable. The one time pad applied to the tag is of course not reusable. Quite conveniently the part of the key material which can be used only once is the smaller part, and doesn't grow with the message size.

If you combine this authentication scheme with a one time pad, the number of key bits consumed by the one time pad will be much larger than the number of key bits consumed by the authentication.

But this kind of authentication scheme can also be used in scenarios where you just need the authentication and not the confidentiality. For example the classical channel used in quantum key exchange need authentication but not confidentiality. So the two can supplement each other well as this construction provides the authentication needed for the quantum key exchange, and the quantum key exchange produce a stream of bit suitable for a one time pad, which can then be utilized by the authentication.

I have seen newer constructions than the one from the Wegman Carter article. All of them have build on the idea from the Wegman Carter article. They use the same hash tree plus one time pad construction, but they use other classes of hash functions. If each message will be several MB in size, I believe bucket hashing from a 1997 article by Rogaway is the fastest algorithm.

The question about whether to authenticate or encrypt first is a moot point if you are combining this kind of authentication with a one time pad, because the authentication itself by definition applies a one time pad to the tag.

Whether you apply a single one time pad or two one time pads to the tag doesn't change the security one bit. However if you do end up applying two one time pads, you will use twice as many key bits to achieve the same level of security. This would however only matter for small messages, because for large messages the key bits used for authentication is negligible compared to those used for the one time pad on the message.

Improve this answer
$\endgroup$
10
  • $\begingroup$ What is it about the 'tree hashing' that makes the Wegman-Carter MAC scheme information-theoretically secure? I am theorising that it is actually the encryption of the tag itself with the one-time pad that actually makes it information-theoretically secure. If that is true then why do you need a complex tree-hashing scheme? Why not just do a HMAC-SHA-256, then encrypt the tag with part of the OTP reserved especially for encrypting the MAC tag? Or why not do a simple one pass MAC with Skein e.g. Hash(Key | encrypted message) then encrypt that MAC tag with OTP? $\endgroup$
    – lightspeeder
    Commented Dec 12, 2014 at 9:58
  • $\begingroup$ Perhaps tree hashing adds extra integrity of the message. But is perfect integrity really needed for information theoretic security? With a 128 bit tag (encrypted with OTP), an attacker has a 1 in 2^64 chance of creating a successful forgery (with birthday attack). The implementation would reject those invalid attempts. It would be impossible for an attacker to know or determine the real key which was used to create the message from the MAC tag information, as it's encrypted with OTP. $\endgroup$
    – lightspeeder
    Commented Dec 12, 2014 at 10:10
  • 2
    $\begingroup$ FYI, the one-time authenticator was first introduced to the literature nearly a decade before Carter and Wegman considered it, by Edgar N. Gilbert, F. Jessie MacWilliams, and Neal J.A. Sloane, ‘Codes which detect deception’, Bell System Technical Journal 53(3), March 1974, pp. 405–424 (with apologies for the paywall). What Carter and Wegman introduced was a particular way to reuse key material from one message to the next for one-time authenticators—subject to reforgery as in AES-GCM, which is why, e.g., NaCl avoids C-W authenticators. $\endgroup$
    – Squeamish Ossifrage
    Commented Aug 13, 2017 at 4:57
  • 1
    $\begingroup$ Here's a non-paywalled scan of the article: cr.yp.to/bib/1974/gilbert.html $\endgroup$
    – Squeamish Ossifrage
    Commented Aug 13, 2017 at 13:34
  • 1
    $\begingroup$ @kasperd You gave a very clear and detailed answer, but it would have been very nice to see an example. $\endgroup$
    – Patriot
    Commented Sep 28, 2019 at 9:00

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.