Author(s): Bruce Schneier

ISBN: 0471128457

Publication Date: 01/01/96

Previous | Table of Contents | Next |

Rambutan is a British algorithm, designed by the Communications Electronics Security Group (one of the aliases used by GCHQ). It is only sold as a hardware module and is approved for the protection of classified material up to “Confidential.” The algorithm itself is secret, and the chip is not generally commercially available.

Rambutan has a 112-bit key (plus parity bits) and can operate in three modes: ECB, CBC, and 8-bit CFB. This strongly indicates that it is a block algorithm, but rumors point elsewhere. Supposedly, it is a LFSR stream cipher. It has five shift registers, each one of a different length around 80 bits. The feedback polynomials are fairly sparse, with only about 10 taps each. Each shift register provides four inputs to a very large and complex nonlinear function which eventually spits out a single bit.

Why call it Rambutan? Perhaps, like the fruit, it’s spiny and forbidding on the outside but soft and yielding inside. On the other hand, maybe that’s not the reason.

**Additive generators** (sometimes called lagged Fibonacci generators) are extremely efficient because they produce random words instead of random bits [863]. They are not secure on their own, but can be used as building blocks for secure generators.

The initial state of the generator is an array of *n-*bit words: 8-bit words, 16-bit words, 32-bit words, whatever: *X*_{1}, *X*_{2}, *X*_{3},..., *X*_{m}. This initial state is the key. The *i*th word of the generator is

*X*_{i}= (*X*_{i-a}+*X*_{i-b}+*X*_{i-c}+...+*X*_{i-m}) mod 2^{n}

If the coefficients *a, b, c,..., m* are chosen right, the period of this generator is at least 2^{n} - 1. One of the requirements on the coefficients is that the least significant bit forms a maximal-length LFSR.

For example, (55,24,0) is a primitive polynomial mod 2 from Table 16.2. This means that the following additive generator is maximal length.

*X*_{i}= (*X*_{i-55}+*X*_{i-24}) mod 2^{n}

This works because the primitive polynomial has three coefficients. If it has more than three, you need some additional requirements to make it maximal length. See [249] for details.

*Fish*

Fish is an additive generator based on techniques used in the shrinking generator [190]. It produces a stream of 32-bit words which can be XORed with a plaintext stream to produce ciphertext, or XORed with a ciphertext stream to produce plaintext. The algorithm is named as it is because it is a Fibonacci shrinking generator.

First, use these two additive generators. The key is the initial values of these generators.

*A*_{i}= (*A*_{i-55}+*A*_{i-24}) mod 2^{32}*B*_{i}= (*B*_{i-52}+*B*_{i-19}) mod 2^{32}

These sequences are shrunk, as a pair, depending on the least significant bit of *B*_{i}: if it is 1, use the pair; if it is 0, ignore the pair. *C*_{j} is the sequence of used words from *A*_{i,} and *D*_{j} is the sequence of used words from *B*_{i}. These words are used in pairs—*C*_{2j}, *C*_{2j+1}, *D*_{2j,} and *D*_{2j+1}—to generate two 32-bit output words: *K2j* and *K2j*+1.

*E*_{2j}=*C*_{2j}⊕ (*D*_{2j}^*D*_{2j+1})*F*_{2j}=*D*_{2j+1}^ (*E*_{2j}^*C*_{2j+1})*K*_{2j}=*E*_{2j}⊕*F*_{2j}*K*_{2i+1}=*C*_{2i+1}⊕*F*_{2j}

This algorithm is fast. On a 33 megahertz 486, a C implementation of Fish encrypts data at 15 megabits per second. Unfortunately, it is also insecure; an attack has a work factor of about 2^{40} [45].

*Pike*

Pike is a leaner, meaner version of Fish, brought to you by Ross Anderson, the man who broke Fish [45]. It uses three additive generators. For example:

*A*_{i}= (*A*_{i-55}+*A*_{i-24}) mod 2^{32}*B*_{i}= (*B*_{i-57}+*B*_{i-7}) mod 2^{32}*C*_{i}= (*C*_{i-58}+*C*_{i-19}) mod 2^{32}

To generate the keystream word, look at the addition carry bits. If all three agree (all are 0 or all are 1), then clock all three generators. If they do not, just clock the two generators that agree. Save the carry bits for next time. The final output is the XOR of the three generators.

Pike is faster than Fish, since on the average 2.75 steps will be required per output rather than 3. It is far too new to trust, but looks good so far.

*Mush*

Mush is a mutual shrinking generator. It’s easy to explain [1590]. Take two additive generators: *A* and *B*. If the carry bit of *A* is set, clock *B*. If the carry bit of *B* is set, clock *A*. Clock *A*, and set the carry bit if there is a carry. Clock *B*, and set the carry bit if there is a carry. The final output is the XOR of the output of *A* and *B*.

The easiest generators to use are the ones from Fish:

*A*_{i}= (*A*_{i-55}+*A*_{i-24}) mod 2^{32}*B*_{i}= (*B*_{i-52}+*B*_{i-19}) mod 2^{32}

On the average, three generator iterations are required to produce one output word. And if the coefficients of the additive generators are chosen correctly and are relatively prime, the output sequence will be maximal length. I know of no successful attacks, but remember that this algorithm is very new.

Previous | Table of Contents | Next |