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.

In a stream cipher, the bytes of the plaintext are usually XORed with the keystream to produce the ciphertext. Would there be anything wrong with adding the bytes instead (with overflow), if adding happened to be faster than XORing on a particular system?

share|improve this question

3 Answers 3

up vote 12 down vote accepted

On software platforms, bytewise adding will not be faster than bitwise XORing. It may be a bit slower, though, also this will be negligible with regards to the process which generated the stream (and, for that matter, will probably also be negligible with regards to the memory bandwidth).

On hardware platforms (FPGA, dedicated ASIC), addition is slower than XOR because of the need to propagate carries. A XOR is a simple layer of XOR gates, so it has minimal depth and minimal area; an addition requires more gates (so more area) and carry propagation over $n$-bit words requires a circuit of depth at least $\log n$, so the addition will induce more latency as well. The overhead will be probably limited for mere bytes, but it will never be as efficient as a XOR.

The only kind of architecture where adding would be somewhat faster than XORing would be an architecture which offers addition/subtraction primitives, but not XOR, or not as efficiently. This may be the case for some DSP, or possibly for some Javascript interpreters (in Javascript, numbers are thinly-disguised IEEE 754 floating-point values, and bitwise operations entail conversions to and from integer types). I still think that for most platforms (including recent JIT-able Javascript interpreters), the XOR will not be slower than bytewise addition.

As for security, bytewise addition is as good as XOR. Indeed, XOR is bitwise addition (XOR is the addition in $\mathbb{Z}_2$).

share|improve this answer
    
In fact, on the security side the bytewise addition is superior to the XOR operation. Simply put, with addition modulus 2^n each bit of the key and/or the plaintext has the chance to influence up to n bits of ciper text, which causes better diffusion of input data and complicates attacks on the cipher's output. –  Hanno Binder Sep 21 '13 at 22:02
3  
@HannoBinder If your stream cipher is so broken that this makes a difference, run. –  CodesInChaos Oct 23 '13 at 8:57
    
Whether your stream cipher is broken or not, ADD does make a difference compared to XOR. This is not about obscuring flaws in the cipher, but about using its output more effectively. –  Hanno Binder Oct 25 '13 at 14:41
    
I just checked the assembly code generated by MS Visual Studio and two +/- operations are translated into LEA instruction which someone even consideres as 'zero cost' :-) While one ^ remains one XOR. –  user11391 Jan 12 at 19:39
    
So the only objective for the choice of the bitwise operation in a stream cipher is efficieny?Could we use birwise AND/OR as well? –  curious Feb 22 at 0:37

You can use any invertible operation to apply the key stream to the plaintext for encryption (and use the inverse to apply the key stream to the ciphertext for decryption).

Addition/subtraction are such a pair, but you have to take care for the carry - either use it $\bmod 256$ (i.e. byte-wise), or use it $\bmod 2^n$ with $n$ some block size in bits. Make sure you use the same block size for encryption and decryption. (Use the block size that is native for your platform for optimal performance.)

It does not change anything about security, just the interoperability is more complicated (for XOR it does not matter how many bits you XOR at once, since there is no carry), and performance might differ.

Addition/subtraction might be preferable when your "blocks" are not multiples of whole bits (i.e. where you couldn't do XOR at all), but representable as numbers modulo some value. E.g. in many classical ciphers, which work on a small alphabet, we would have addition modulo 26.

share|improve this answer

consider you have a key $K$ and plaintext $P$.

then,

$P \oplus K = C$ (cipertext)

$C \oplus K = P$ (plaintext)

Here, algorithms for encryption and decryption are same (thats not true for addition). Also, $\oplus$ (X-OR) is faster than addition on most of the platforms. Additions generates carry forwards, X-OR operation does not.

share|improve this answer

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.