Stream cipher malleability

Question

Considering a stream cipher that produces a ciphertext "c" from a message "m" and a key "k" is it possible to apply operations (multiplication and/or addition) directly to "c" without knowing the key ?

Example : m > encrypt > c > c+5 > decrypt > m+5

I can not manage to get a valid "m" at the end : I tried to work with hex values, binary data... no success so far

Could you please confirm if this kind of operation is possible on AES-ctr / Xsalsa20 (this one uses nonces) and how to properly do it ? Thanks !

Answer 1

AES in counter mode works by XORing the output of an encrypted counter against the plain-text. This easily allows you to flip bits in the ciphertext and have that bit flip in the plain-text.

The easiest way to get the kind of behaviour you're looking for is rather than XORing the encrypted counter against the plain-text, add it mod $2^{128}$. Decryption proceeds by subtracting the encrypted value mod $2^{128}$.

Then if you deduct $5\mod 2^{128}$ from the ciphertext, that deduction will also affect the plain-text.

This is because:

$c = m + AES(counter,k) \mod 2^{128}$

$m = c - AES(counter,k) \mod 2^{128}$

So:

$c+5 = (m + AES(counter,k))+5 \mod 2^{128}$

$c+5 = (m + AES(counter, k)+5) \mod 2^{128}$

$c+5 - AES(counter, k) = (M+ AES(counter, k) - AES(counter,k) + 5) \mod 2^{128}$

$c+5 - AES(counter, k) = m+5 \mod 2^{128}$

$(c - AES(counter, k)) + 5 = m+5 \mod 2^{128}$

We can then clearly see that the left hand side is the decryption equation + 5 and this five is carried through in to the plain-text.