For a one-time pad, which MAC method is information-theoretically secure? 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.



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?
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?
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.