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

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?

-
Related question: Is there anything wrong with doing $E_k(m)= K\oplus(m||h(m))$ for a secure hash function? –  figlesquidge Apr 4 at 14:11
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? –  hakoja Apr 4 at 16:20
@hakoja : $\:$ These approaches could make sense if lightspeeder wants $\hspace{1.98 in}$ Long-Term security with minimum key size. $\;\;\;\;$ –  Ricky Demer Apr 4 at 16:55
@hakoja, I am asking from a theoretical point of view - why using HMAC and encrypting the MAC tag with OTP is not a possibility? Using HMAC seems to be the simpler solution and polynomial based MACs have several attacks. E(m) = K ⊕ (m || H(m)) seems to be the natural method and the paper linked in my post makes the assertion that this method is secure for a OTP or stream cipher. I am asking about this construction specifically and what tag length should be required... –  lightspeeder Apr 4 at 20:49
@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? –  hakoja Apr 5 at 9:00