Append data to authenticated ciphertext encrypted using a stream cipher

Question

Say we have xSalsa20 authenticated using Poly1305. If $ X $ is the ciphertext, $N$ is the nonce value, and $H$ is the authentication tag such that the final ciphertext is $ N || X || H $, then given the key $K$, is it possible to extend $ X $ with more data, without decrypting it, updating $N$ and $Y$ as needed? (I'm not sure if $N$ would need to be changed.)

To be clearer, say $ X_m $ is the original authenticated ciphertext. I want to append plaintext data $ A $ to it. I'm looking for a scheme to implement $ X_n = Append(X_m, A, K) $ such that $ Decrypt(X_n, K) = Decrypt(X_m, K) \| A $.

Salsa20 is a stream cipher so it produces a CSPR key-stream, $ S $, and then then ciphertext becomes $ X = S \oplus P $, where $P$ is the plaintext. So I intuitively feel as though this should be a lot easier to do than with a block cipher. Perhaps by generating the same key-stream up until the size of the ciphertext and encrypting the new data with the part of the key-stream past that point. If the authentication tag is generated from the ciphertext then decryption wouldn't be necessary for that either. Also the nonce would not really be reused in a scheme like this as far as I can see.

How well would this translate to other stream ciphers like XChaCha20-Poly1305?

Answer 1

If $ X $ is the ciphertext, $N$ is the nonce value, and $H$ is the authentication tag such that the final ciphertext is $ N \| X \| H $, then given the key $K$, is it possible to extend $ X $ with more data, without decrypting it, updating $N$ and $H$ as needed?

For most schemes, this is very much possible, yes.

There are two parts to this: The CPA-secure encryption function used and the message authentication code.

First for the encryption function:

• If it is CTR-based this is no problem as one simply skips the counter ahead to the index of the last block to get the neccessary keystream. AES-CTR gets covered by this, but also (X)ChaCha and (X)Salsa which both are PRFs in CTR mode.
• For CBC, Aleksander already has the answer: You decrypt the last block, continue filling it where padding was used and used the second-to-last block as IV.
• For CFB the story should be roughly the same as for CBC, but as it is much more rarely used I didn't look into the details.
• For OFB, as it essentially computes $S_i=E_k(S_{i-1})$ and uses the $S_i$ as the keystream you can recover the state from the last fully-used block as well if you know the corresponding plaintext and if you don't you got unlucky and have to start at the beginning with the nonce.

As for security considerations with these: At least for the streaming modes you never re-use the keystream so the secrecy of the message is preserved, but of course an adversary can tell that the message was extended.

As for the authentication code, here is where things get really messy:

• For HMAC this indeed seems impossible short of recomputing the full MAC even when knowing the key as the last step of HMAC is to run the key and and a reduction result of the entire message through a non-invertible PRF which doesn't allow to recover the internal state from the output.
• For CCM's CBC-MAC the picture is similarly grim, as it includes the precise message length at the beginning and every internal state following that depends on this value.
• For CBC-MAC using a non-invertible PRF (so not a block cipher) the picture is similar to HMAC, one cannot recover the state from the output.

This however leaves us with two widely used classes of MACs: block cipher CBC-MAC based MACs and Carter-Wegmann MACs like Poly1305 and GHASH.

• For CBC-MAC based schemes that use block ciphers and don't prepend the message, they usually have a special treatment for the final block, be it XORing a special value into the last message block or encrypting the ciphertext again with a different key. However these transforms are all invertible if you know the key. So you can efficiently recover the internal state before the last block and re-compute the MAC for the last block and your updates.
• For Carter-Wegman MACs, as poncho explained it's a bit more complicated and might work with special non-dangerous implementation treatment, but in princple it's possible (in particular with GHASH as used by GCM) though of course highly dangerous if the adversary gets to see both ciphertexts.

Note that it is safe to do this extension when using CBC-MAC based schemes (like EAX) as the variants used there are proper PRFs and so outputs for the correlated inputs have no observable relation to the key-less adversary.

Answer 2

Well, no you can't (without rescanning the entire ciphertext), and you probably shouldn't anyways.

The xSalsa20 is the easy half - it is effectively in counter mode, and so it'd be easy to generate a few more bits out of the xSalsa20 to use to encrypt the additional data you're appending (and those additional bits wouldn't change to previous ciphertext bits).

The problem is with the Poly1305 half; it treats the ciphertext as polynomial coefficients (over $GF(2^{130}-5)$) and then evaluates that polynomial for a secret value of $x$ (and then adds a secret nonce-dependent factor) - if that's all it did, then it would be fairly easy to adjust the polynomial result to account for the additional bits (by subtracting out the secret constant term, multiplying by a power of $x$ if necessary, and then adding in the new bits and adding back the secret constant term). However, it does one further step; it takes the output of the polynomial (which is a value between $0$ and $2^{130}-6$), and takes it mod $2^{128}$. That means that, for (almost) any tag value, there are 4 possible values that the polynomial would evaluate to, which implies 4 possible tags that the extended polynomial would need to be (because those two higher bits modify the lower bits once we multiply it by $x$), and you have no idea which one it might be (without recomputing the polynomial from scratch.

Now, one could modify the initial Poly1305 implementation to save those two upper bits that the $\bmod 2^{128}$ operation scraps away (and leaking those would not give any advantage to an attacker); this would allow an efficient incremental update. On the other hand, doing so might not be a great idea - if an adversary sees both ciphertexts (that is, the original and the extended version, both of which uses the same nonce), he can compute an explicit polynomial which has the secret value $x$ as a root - this allows him to recover a good guess of the value of $x$, and that would allow him to modify ciphertexts at will without being detected.

Because of this threat, I believe you really do want to change the nonce whenever you modify the ciphertext; that involves a full decryption and reencryption.