8
$\begingroup$

Could somebody explain what is the difference between "word-based" stream ciphers and the regular ones? Those last ones use pseudo-random sequences XOR'd bit by bit with the message, as far as I know. How does that change when it comes to "word-based" ciphers?

Examples of word based keystream ciphers include SNOW, PANAMA, SOBER, ORYX. I also read that word based keystream ciphers "allow greater efficiency in software than most bit based stream-ciphers".

$\endgroup$
3
  • 2
    $\begingroup$ Would you care to provide a citation for your quotes? I don't think it is accurate to say that "less is known about the security of word-based stream ciphers than bit-based stream ciphers". $\endgroup$
    – D.W.
    Nov 15, 2012 at 2:35
  • 1
    $\begingroup$ Yes, they are from Analysis and Design Issues for Synchronous Stream Ciphers by Dawson and Simpson in Lecture Notes Series, Insititute for Mathematical Sciences, National University of Singapore written in 2002. $\endgroup$
    – geo909
    Nov 15, 2012 at 15:15
  • 2
    $\begingroup$ @D.W. You are right! I just realized I misread! There was a small part saying that "ORYX was found to be a seriously flawed design" but much less is known about the security of the rest of the above mentioned word based stream ciphers (i.e. SNOW,PANAMA,SOBER,ORYX), not all stream ciphers in general. Thanks for pointing that out! I removed that part of the question. $\endgroup$
    – geo909
    Nov 15, 2012 at 15:18

3 Answers 3

5
$\begingroup$

A word-based stream-cipher produces the pseudo-random sequence one word (of several bits) at a time. For example RC4 is a word-based stream cipher, with the word size a byte. By contrast, a typical bit-based stream cipher such as one using the ASG produces the pseudo-random sequence one bit at a time.

Word-based stream ciphers may be better suited to fast software implementations than are bit-based stream ciphers, since CPUs typically process one word no slower than one bit.

$\endgroup$
4
  • 2
    $\begingroup$ I don't have enough reputation to vote this up, but it answers my question, many thanks.. I was also wondering how one could compare word-based stream ciphers and block ciphers. I do not know much about block ciphers so there may be a very basic and fundamental difference that I do not see, however I can tell that they process blocks of bits at a time, so it seems that they are similar to woed-based stream ciphers in that sense? What is the difference? $\endgroup$
    – geo909
    Nov 14, 2012 at 20:11
  • 1
    $\begingroup$ @geo909: A stream cipher XOR the plaintext and keystream, and thus has the property $\mathtt{Enc}(P')=\mathtt{Enc}(P)\oplus P'\oplus P$. A block cipher does an arbitrary-looking permutation of plaintext block to ciphertext block, not bound by this property. That makes block ciphers versatile building blocks for all kinds of constructs: stream ciphers (using the CTR or OFB mode), MAC, hashes. Ah, also: even without reputation, you should still be able to accept an answer. $\endgroup$
    – fgrieu
    Nov 15, 2012 at 6:52
  • $\begingroup$ I'm not sure what $P'$ is but I do understand the difference now, thanks. I guess regular stream ciphers are more efficient in hardware implementation that block ciphers in CTR or OFB mode, right? $\endgroup$
    – geo909
    Nov 15, 2012 at 15:41
  • $\begingroup$ @geo909: $P'$ would be an alternate plaintext. The stated property allows computing the ciphertext for $P'$ from $P$, $P'$, and the ciphertext for $P$. This is a case of malleability. Efficiency of implementation depends on many factors, e.g. resistance to side-channel attacks, thus comparisons are hard; but at least one argument of the proponents of bit-based stream ciphers is that they are more efficient in hardware than block ciphers in CTR or OFB mode. $\endgroup$
    – fgrieu
    Nov 15, 2012 at 16:23
5
$\begingroup$

As D.W. notes, the distinction made between "bit-based" and "word-based" stream ciphers in the source you cite is irrelevant to the end-user. For both kinds of stream ciphers (as well as for block ciphers in streaming modes like CTR or OFB), the manner in which the keystream is combined with the plaintext is always the same: bitwise XOR, which operates at the bit level but is easily parallelized both in hardware and in software.

In any case, the actual distinction they seem to be making is between LFSR-based stream ciphers, which sequentially output one bit per iteration, and ciphers such as RC4 (and, presumably, block ciphers in streaming modes) which generate their output bitstream in larger chunks.

LFSR-based stream ciphers have generally been designed for direct hardware implementation, where they have the advantage of simplicity, but they've traditionally suffered from poor performance in software; whereas in hardware it's easy to shuffle single bits around and combine them using simple logic gates, typical CPUs are designed for carrying out higher-level operations on chunks of 8, 16, 32, 64 or 128 bits in parallel. Running a cipher that operates on single bits in software thus wastes most of the CPU's power, unless the algorithm can be reformulated to operate on many bits in parallel, something that many older LFSR-based cipher designs haven't been very well suited for.

On the other hand, ciphers like RC4 were designed for software implementation from the beginning, and do very well there. (Although RC4 itself operates on 8-bit bytes, which is arguably suboptimal for modern high-end CPUs, its simplicity still keeps is competitive there. Besides, there are still plenty of 8-bit processors around in embedded devices and such.) However, they often make use of features that are difficult and costly to implement in hardware, such as access to relatively large amounts of RAM (e.g. 258 bytes for RC4, accessed in an essentially random order).

In recent years, though, the trend in stream cipher design has been towards ciphers that blur these lines, being efficient to implement in both hardware and software. Good examples can be found e.g. in the eSTREAM portfolio: the Trivium cipher, for example, is fundamentally a "bit-based" shift register design, and can indeed be implemented as such if desired; however, it is designed such that up to 64 bits of the output can be computed in parallel, which allows very efficient software implementations using any word length of up to 64 bits. (Conveniently, the same parallelizability also allows Trivium to be made very fast in hardware, by essentially duplicating the circuitry up to 64 times, as long as available space permits this.)

$\endgroup$
2
$\begingroup$

From your perspective as a user of stream ciphers, the distinction is irrelevant.

As a driver of a car, you don't need to care the details of how the car's engine was built. What you care about is whether the car gets you there safely and rapidly.

Similarly, from your perspective as a user of a stream cipher, what you care about is whether the stream cipher is secure and how fast it is. If you measure those two things, you don't need to care about which type the stream cipher is.

Generally speaking, word-based stream ciphers are often built that way because operating on a word at a time can potentially be faster in software (on the other hand, bit-based stream ciphers can potentially be better in hardware, e.g., use less power and less silicon). However, rather than worry about this detail, you should just measure how fast the stream cipher actually is, and make your decision based upon that -- as well as whether the stream cipher offers sufficient security.

$\endgroup$
1
  • $\begingroup$ You are right about the car user analogy but my perspective is not exactly the driver's. I'm studying finite fields focusing on the non-applied side, however I wanted to have a small look on the applications and see how exactly finite fields are used and why we prefer this or that in cryptography. That is, I am mostly interested to have a sneak peak on the engine rather than going for a ride :) $\endgroup$
    – geo909
    Nov 15, 2012 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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