Robust authentication and integrity for short OTP message

Question

Using any of the wonders of modern cryptographic technology, how is it possible to package a tweet-sized plaintext, which is to be encrypted with a proper one-time pad, to ensure its integrity and give it authentication? For these last two services we aim for at least a 128-bit level of assurance. We also want to indicate message order, with a tag, at the same level of protection.

Here are some ways to do it:

1.) One method would be to use a Carter-Wegman MAC.

2.) Another would be to use NaCl / Libsodium with the ChaCha20 stream cipher and the Poly1305 authenticator.

3.) Use an HMAC such as HMAC-SHA-256.

Is there another way that is reliable?

Thank you very much.

Answer 1

If you want to be consistent with OTP usage, then you should use a One Time MAC. Currently it seems the easiest path for that is to simply use Poly1305, but remember that you must never reuse keys for Poly1305, just like you can't reuse keys in OTP. (In particular, don't use the key generation routine used by ChaCha20-Poly1305 to derive the Poly1305 key from a nonce/key pair).

Using HMAC doesn't make much sense: if you're using OTP, that's probably because you don't trust any particular block cipher, so you shouldn't trust any particular hash or MAC algorithm.

Answer 2

Another way is to go weird, and do

$$nonce||\operatorname{AES-ECB_k}(m)||H \big(\operatorname{AES-ECB_k}(m)\big)$$

where $m$ is the message that is pre-encrypted with a OTP. This is a good example of code book mode working properly, due to the OPT. No cuddly polar creatures appear, and it follows the recommended encrypt then MAC doctrine.

$nonce$ is my message order(and pad ID for decryption), but it's not sequential. It's difficult in practice to maintain a correct (non repeating) sequence. It would be truly random, drawing upon the OTP key material. If you have the resources to make Kolmogorov random key material, then use it. Don't forget that if you also need a temporal component for the order, you can just introduce a timestamp into the message plain text.

I like this approach as it's simple to understand and implement. Java would only use existing internal functions as AES and SHA* are inbuilt. You just choose the bit length of the key, hash type and nonce. So you could have 256 bits throughout for symmetry. I think that I'd make the message length an exact multiple of 128 bits, for no particular scientific reason other than feng shui.

---

Using a separate key for encryption of the OTP key material has another advantage. It creates an ersatz two factor encryption system. Even if the OPT falls into enemy hands (say by just seizing the PC), past messages cannot be read.

It's worth pointing out that this is an atypical use case, and so I can't find loads of authenticated OTP research material. This leaves unanswered the question of whether you should include the OTP ID ( my $nonce$) within the MAC. You could I guess in minimising lookups for corresponding pads.