Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 !

share|improve this question
1  
You can only apply xor directly to c causing the same xor to m. –  CodesInChaos Jul 31 '12 at 19:43
add comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
@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
add comment

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$.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.