16.8 Rambutan

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.

16.9 Additive Generators

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₁, X₂, X₃,..., X_m. This initial state is the key. The ith word of the generator is

X_i = (X_i-a + X_i-b + X_i-c +...+ X_i-m) mod 2ⁿ

If the coefficients a, b, c,..., m are chosen right, the period of this generator is at least 2ⁿ - 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ⁿ

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³²

B_i = (B_i-52 + B_i-19) mod 2³²

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⁴⁰ [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³²

B_i = (B_i-57 + B_i-7) mod 2³²

C_i = (C_i-58 + C_i-19) mod 2³²

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³²

B_i = (B_i-52 + B_i-19) mod 2³²

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.