Can I achieve data authentication with ChaCha20 without MAC?

Question

My case is rather special. I need to send data in small chunks, each under 32bytes. ChaCha20 state is 64 bytes.

Since I will be receiving data stream in chunks, id like to verify it on the fly (i.e. after I receive each chunk, make sure it was not tempered with).

Using MAC is a bad choice, as I'd have to compute MAC every time I send my 32byte chunk and append it to the message. And I don't think this is a standard approach as with Poly1305, where as I understand, you compute MAC only once when ALL the data is transferred, not sending intermediate MACs.

So I got this idea: instead of computing MAC (with Poly1305 or other), why not just use the 32byte data twice, make a 64byte chunk that can be XORed with one state of ChaCha20.

Upon deciphering, I verify that the first 32 bytes are equal to the latter 32 bytes. If yes, there was no modification. If no, there was some tampering / transmission errors.

So my questions are:

1. Does repeating ciphertext twice compromise security of the stream cipher? (Assume attacker knows this)

2. Is there some standard way how to provide message authentication with stream ciphers without this "hack"?

Thanks for answers and opinions!

Answer 1

For one block, the cleartext is 64 bytes, which are actually 32 bytes repeated. The repeat does not affect what happens next. The ChaCha keystream is random looking 64 bytes. You XOR the keystream with the cleartext, thus creating the ciphertext. You send the ciphertext over the wire. The attacker flips bits in the ciphertext. You produce the same keystream on the other side, XOR it with the tampered received ciphertext and you now have the cleartext with the bits flipped exactly where the attacker flipped them. If the attacker knows the structure of the cleartext, they can flip bits in such a way that the message still makes sense (deserialized, parsed, interpreted) but has different meaning.

This is not purely theoretical: Matthew Green famously attacked Apple iMessage which used deflate compression and managed to flip bits in huffman encoded compressed data that still decompressed fine. That attack was possible because the ciphertext was not authenticated.

It seems you do not understand how CTR or Chacha encryption works. It is not like CBC where the cleartext is fed into the random permutation and a bit flip will scramble the entire block (in CBC the bit flip scrambles one block but affects the next block precisely, so CBC is still very malleable and must not be used without authentication, but ChaCha and CTR are even more malleable).

Don't do what you described. Use a MAC. Not using a MAC invokes "The Cryptographic Doom Principle".

If you need a MAC optimized for sending short messages, maybe someone here can recommend something, though I think doing what ssh does with ChaCha20Poly1305 is the correct thing to do.

In general: Do you have an advanced degree in cryptography? No? Don't invent your own cryptographic primitives. Use good cryptographic primitives that were tested by the community. Don't combine good cryptographic primitives in novel ways. Use good tested combinations/protocols. Try to not implement good protocols yourself. Use good tested implementations.

Answer 2

You're in luck! According to your question, you have 64 bytes of bandwidth per 32-byte message available. The authenticated cipher crypto_secretbox_xsalsa20poly1305 has a ciphertext expansion of only 16 bytes—that is, the ciphertext is only 16 bytes longer than its plaintext, no matter how long the plaintext is, so in this case it will use only 48 bytes and leave you 16 bytes under budget!

Just use crypto_secretbox_xsalsa20poly1305 for each 32-byte message before you act on it—if you use NaCl/libsodium, you won't even be allowed to get at the decrypted plaintext if it's a forgery—and you'll be good to go.

If you already have a message sequence number, use that as the crypto_secretbox_xsalsa20poly1305 nonce; if not, you can use 8 of the remaining 16 bytes available to you for a message sequence number. If you ever repeat a nonce with the same key, the security vanishes.

No need to worry about stream ciphers (which can fail to protect confidentiality if you act on forged messages), MACs (which don't protect confidentiality at all), HMACs (which are a specific kind of MAC), etc. Focus on authenticated ciphers like crypto_secretbox_xsalsa20poly1305 or AES-GCM.

Answer 3

If you really want to use nothing but ChaCha20, you can use the ChaCha20 internal permutation with the Even-Mansour scheme.

Set k ← ChaCha20(K, nonce || pad). This assumes that ChaCha20 is a PRF.

With P representing the permutation and P' the reverse operation:

Your ciphertext is c ← k ⊕ P(k ⊕ (m || {0})).

To decrypt, compute P'(c ⊕ k) ⊕ k and verify that the lower half bits are {0}.

That scheme can be useful if you absolutely want the implementation to be as small as possible.

However, not only ChaCha20 was never designed to be used that way, but also, as pointed out by Squeamish Ossifrage, you can end up with a shorter ciphertext by using a standard AEAD construction.