# Stream cipher malleability

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 !

-
You can only apply xor directly to c causing the same xor to m. –  CodesInChaos Jul 31 '12 at 19:43

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.

-
@fgrieu - if you read the second paragraph, I think it's clear that I do not say that AES-CTR is addition mod $2^{128}$. What I suggest is a modification to traditional CTR mode in order to get the behaviour the person was after. –  Simon Johnson Oct 5 '13 at 20:22
You are right, I did not read your text thoroughly enough, and wrongly assumed the equations where supposed to answer the question as stated. The other (minor) notation problem remains: the answer uses $a=b \mod n$ where it should use $a\equiv b\pmod n$, writen $a\equiv b\pmod n$. The former, by definition, implies $0≤a<n$, and, formally, that makes the equation $(c - AES(counter, k)) + 5 = m+5 \mod 2^{128}$ wrong with odds about $1/2$. –  fgrieu Oct 6 '13 at 9:22

With the usual definition of AES-CTR or Xsalsa20, no, it is not possible to reliably perform some arithmetic operation $\odot$ (such as addition or multiplication) with a known constant $a$ on ciphertext, without some additional knowledge or restriction. In these stream ciphers, the ciphertext is the exclusive-OR of plaintext with some unknown keystream $K$, that is $C=P\oplus K$, and in general there is no way to reliably deduce the desired $C'=(P\odot a)\oplus K$ from $C$ and $a$ only.

Still, there are a number of cases where we can reliably compute $C'=(P\odot a)\oplus K$ from the ciphertext $C$ and $a$ (In the following I assume binary representation of numbers):

• When $a$ is the neutral element of the operation $\odot$, e.g. $a=0$ when $\odot$ is $+$, $a=1$ when $\odot$ is $\cdot$; in theses cases $C'=C$.
• When the operation $\odot$ we want to perform is $\oplus$; in that case, we can use commutativity and associativity of $\oplus$: $C'=(P\oplus a)\oplus K=(a\oplus P)\oplus K=a\oplus(P\oplus K)=a\oplus C$; hence $C'=C\oplus a$.
• When we know $P$, and $P\odot a$ has the same bit size as $P$; in that case we have $C'=(P\odot a)\oplus K$ and $K=P\oplus C$, hence $C'=(P\odot a)\oplus P\oplus C$;
Note: if $P\odot a$ has a lower bit size than $P$ that also works: with little-endian convention we just truncate $C'$ accordingly; with big-endian $C'=(P\odot a)\oplus((P\oplus C)\rangle\!\rangle n)$ where $\rangle\!\rangle$ is right-shift and $n$ the number of bits to remove.
• When the operation $\odot$ is $+$ or $-$, and we know partial information about $P$. For example if we know that $P$ is a multiple of $2^{\lceil\log_2a\rceil}$, then $P+a=P\oplus a$, hence $C'=C\oplus a$.

Restricting to operation $\odot$ being $+$ or $-$, and using that these operations are close cousins of $\odot$, we can make guesses of $C'=(P\odot a)\oplus K$ with fair probability to be correct, especially when $a$ can be written as the sum of few powers of 2. In particular:

• When $a=2^n$, $P+a=P\oplus a$ when $\lfloor P/a\rfloor$ is even; and when not, $P+a=P\oplus(3\cdot a)$ when $\lfloor P/(2\cdot a)\rfloor$ is even; and when not, $P+a=P\oplus(7\cdot a)$ when $\lfloor P/(4\cdot a)\rfloor$ is even. Thus for $a=2^n$ and huge random $P$, we know that $C'=(P\odot a)\oplus K$ is one of $C\oplus a$, $C\oplus(3\cdot a)$, $C\oplus(7\cdot a)$ with odds $7/8$.
• For any $a\ne 0$, and huge random $P$, a guess that $C'=(P\odot a)\oplus K$ is $C\oplus a$ has odds $2^{-b}$ to be correct, where $b$ is the number of bits set in $a$.
-