KISS: A bit too simple

KISS (‘Keep it Simple Stupid’) is an efficient pseudo-random number generator specified by G. Marsaglia and A. Zaman in 1993 [1]. G. Marsaglia in 1998 posted a C version to various USENET newsgroups, including sci.crypt, culminating in a final version [3]. While Marsaglia himself has never claimed cryptographic security for the KISS generator, he does hint about it, and others have made the intellectual leap and claimed that it is of cryptographic quality. In this paper we show a number of reasons why the generator does not meet some of the KISS authors’ claims, why it is not suitable for use as a stream cipher, and that it is not cryptographically secure as a pseudo-random number generator. Indeed, this paper is written as a cautionary tale; stream ciphers and cryptographically secure random number generators are hard to get right, even for some of the world’s preeminent experts on the subject of randomness. We present a number of standard attacks that damage KISS to some extent, and our best attack requires only 70 words of generated output and on average 2^29.1 operations of a simple algorithm to recover the initial state. We attempt to present the reasoning that leads to the attacks.

Since 1998 Marsaglia has posted a number of variants of KISS (without version numbers), including [4] in January 2011. In the sequel, we refer to this as KISS11 for disambiguation. These variants have similar design elements but ever increasing state sizes, making them impractical for most cryptographic uses anyway. We present a straightforward divide-and-conquer attack on this (currently) latest version of KISS, requiring 2⁴¹ operations equivalent to key initializations.

Marsaglia’s generators are primarily intended for scientific applications such as Monte Carlo simulations. There are many other generators in use, often with (ridiculously) long periods, for example the Mersenne Twister [6], and later versions of KISS. We choose to examine the 1999 version of KISS rather than some of these later proposals, because:

Other proposals often involve large state variables, often calling on simpler RNGs to initialize these large states. For cryptographic purposes, the lack of a well-specified initialization or keying phase, the large state, and the time required for initialization are all undesirable. It is our opinion that most of these other proposals are also cryptographically weak, but that doesn’t matter because they are also impractical in the context of a stream cipher. In any case, one recent proposal is examined below.

In Section 2 we describe KISS and the components that make it up. Section 4 discusses some simple structural attacks. Mathematical properties of the components are described in Section 3, and in Section 5 these properties are combined to form a cryptanalytic key recovery attack in the known-keystream model. A variation of the attack would even apply to unknown plaintext, if the input language is sufficiently biased and with a significant slowdown. Finally Section 6 examines the 2011 version of KISS (KISS11) and presents a simple attack.

Quotations in this document are from Marsaglia’s USENET posting [3] unless mentioned otherwise.

KISS consists of a combination of four sub-generators each with 32 bits of state, of three kinds: The four generators are updated independently, and their states are combined to form a stream of 32-bit output words. The four state variables are treated as unsigned 32-bit words. Figure 1 shows C code from [3], while Fig. 2 shows the structure pictorially. We refer to the state registers using the names of the C macros.

The four registers, of three kinds, that make up KISS are independently updated, then combined using shifts, adds, and one XOR operation. As is often the case, the registers that use arithmetic operations are combined with XOR, while the results that are produced bitwise are combined with addition modulo 2³².

Marsaglia, in a different article [2], writes:

It is a common theme in both amateur and professional cryptography to start with a design, and as defects are discovered, to try to cover them with another feature or another generator. In the case of KISS, this design is apparent with the use of simple generators with known flaws to cover each others’ deficiencies. The job of the cryptanalyst, conversely, is to find ways to expose the flaws and defeat them in detail. In this section we not only show a key recovery attack against KISS, but we attempt to reveal the thought process, and experiments conducted, to arrive at this attack. This paper hopes to teach a little bit of cryptanalysis technique.

Our goal is to take some amount of known keystream (a standard assumption for cryptanalysis of stream ciphers) and recover the initial state of the four registers.

We first began by analyzing the components, to better understand them, as Marsaglia’s USENET posting was short on details. We did not try to obtain the original technical report [1], which probably contains more analysis, in favor of developing our own understanding. CONG was already well understood. The Multiply With Carry generators wnew and znew were new to us, so we wrote code to enumerate the cycle structure, and looked at how easy it was to run the generators backwards.

When it came time to analyze the SHR3 generator, at first we accepted the implication that it had the maximum possible period of 2³² − 1, and wanted to find the equivalent LFSR, as we were more familiar with cryptanalyzing such structures. Using the default initial value from the KISS paper, we generated 128 output words, and selected the least significant bits for input to the Berlekamp-Massey algorithm. As expected, a degree-32 polynomial was the output, which did not contradict our belief that it might have a maximum length cycle. We continued on that assumption.

Sorting out the combination of four generators seems already to be difficult, but one of the generators, znew, only contributes to the upper half of the output words. Concentrating on the lower half reduces the number of generators to three. This is already an application of the Divide and Conquer strategy. The generators are combined with both integer addition and XOR. Either the carries from the addition must be accomodated, or we could focus on the least significant bit, in which addition and XOR are equivalent since there is no carry in. This approach looked promising, as the behaviour of the least significant bits of two of the generators were easily analyzed.

The least significant bit of wnew did not exhibit any linearity or other non-random properties we could detect, as was to be expected from Marsaglia’s description. Further, it depended on the entire 32-bit state of the register. But only the very first output depended on the full state; the second and all subsequent outputs were in one of the known cycles. By skipping the first output word, at least for now, only 1,179,648,000 values (about 2^30.1) for the state needed to be considered.

This suggests the first part of the attack. Assume that the cryptanalyst knows some amount of output keystream words Z _i ,0 ≤ i ≤ N for some as yet undetermined number N. We want to apply some sort of Guess and Determine attack. In such an attack, we guess a value for some unknown quantity, determine from the known and guessed values some other values, and then attempt to verify whether or not the guess was correct, that is, consistent with known values or properties. If the verification fails, we try another guess, thus eventually enumerating some subset of the unknown state.

Step 1. Ignore Z ₀ . Ignore all but the least significant bits of Z _i . We will worry about the actual initial state later; for now we try to recover the state after the first output word. We now have a sequence of N bits of known keystream.

Step 2. Guess w n e w ₁ (that is, the state of the register wnew immediately after the first output). We only have to enumerate the values in cycles. From this guess, generate the stream of least significant bits w _i = w n e w _i &1,1 ≤ i ≤ N.

Step 3. Guess the LSB of C O N G ₁ . As discussed above, the stream of LSBs is alternating zeros and ones, but we don’t know which it starts with. We need to test both. Let c _i = 010101010…. If this guess doesn’t work out, invert it; in fact, we can just invert the entire sequence used in steps 4 and 5.

Step 4. Determine the possible LSBs of the SHR3 output. Set s _i = Z _i ⊕ w _i ⊕ c _i ,1 ≤ i ≤ N.

Step 5. Verify that s _i is the output of an LFSR. When we first implemented this step, we used the discovered polynomial 1 + x ³ + x ⁵ + x ⁸ + x ¹⁸ + x ²² + x ³⁰ + x ³² to check the parity of the corresponding output bits, with N = 100. If our guesses for the wnew and CONG registers were correct, the sums of the bits should all be zero, otherwise with overwhelming probability (1 − 2⁻⁶⁷) at least one of the parity equations would be one. This worked fine for the set of initial values used by default in KISS, but our second trial did not find a solution! After a bit of thought, the only reason we could think of was that there was not a single LFSR that described the system. We already had a very simple program to enumerate cycles in a 32-bit function, so with one minute of editing and three minutes of computation on an Apple laptop, we were able to find the details in Appendix A. We could have proceeded with the verification by checking all 16 of the distinct sets of LFSR taps, but instead chose the simpler approach of just using the Berlekamp-Massey algorithm again. 64 bits of input are necessary to discover the longest LFSR, and only surprisingly few more bits are needed to detect if the bit stream is not linear. With high probability, an extra 5 bits will show that. It is faster to let a small number of false positive results through this stage and eliminate them later than to run extra bits through the Berlekamp-Massey algorithm, which has O(n ²) behaviour in the number of bits. This turns out to be the limiting step in the attack, and could perhaps be optimized further.

Step 6. Recover S H R 3 ₁ . A simple matrix multiplication turns the bits s _i ,1 ≤ i ≤ 32 into the initial state S H R3₁. At this point, with high probability, we know all 32 bits of SHR3.

Step 7. Recover the least 16 bits of C O N G ₁ . Given the known output, and full (assumed correct for now) values for SHR3 and wnew, the least significant 16 bits of CONG are recovered. At first we assumed that the well known result [7] would reveal the full initial state, but we had misremembered the result. At this point we know the full state of two of the registers, half the state of CONG, and nothing about znew.

Step 8. Guess the high 16 bits of C O N G ₁ . We have to apply the Guess and Determine attack again, guessing one of the registers and determining the other. It is obviously most efficient to guess the remaining contents of the register that is partially known, rather than the whole 32 bits of the other unknown register. We then generate 3 output words from the three known or guessed registers.

Step 9. Determine the least 16 bits of znew. From the known keystream and the other registers, we recover the low 16 bits of z n e w _i ,1 ≤ i ≤ 3.

Step 10. Verify consistency of the guess of C O N G ₁ . From the low 16 bits of the first two values of znew, we derive the full state of z n e w ₁. From this we generate z n e w ₃ and verify that the least 16 bits agree with those generated in Step 9. If not, we continue enumerating the high order bits of CONG.

Step 11. Verify the entire state. We now have a candidate for the state of all four registers after the first output. We generate 8 words of output from KISS with that state, and check that they agree with Z _i ,1 ≤ i ≤ 8. Checking 8 values is almost certainly more than necessary.

Step 12. Recover the true initial state. Remember that we skipped the first output Z ₀, because the multiply-with-carry registers might not have started with values in their corresponding cycles. For each of the registers there are two (or for wnew sometimes three) possible initial states. We simply need to check which of the (up to 6) possibilities are consistent with the known output Z ₀.

The algorithm above is completely dominated by the time taken in Step 5; at most a handful of candidates get through to steps 7-12. This step runs the Berlekamp-Massey algorithm on 69 bits; in the worst possible case it will be run on about 2^31.1 inputs (the possible cycles of the wnew register, times two for the LSB of the CONG register). It takes on average about 2 hours on a single CPU of an Apple Macbook Pro (2.66 GHz Intel Core i7), with negligible memory usage. We did not bother optimizing or parallelizing the code. By the nature of the Guess and Determine steps, there are no obstacles to parallelization. Possible optimizations of this step include performing the parity checks instead; we think this would result in a significant speed increase but we didn’t actually try it.

We note in passing that Step 5 could be done by applying a Fast Correlation Attack to unknown plaintext, if the least significant bits of the plaintext language are sufficiently biased and enough output is available. Of course this would take significantly longer to run the attack.

KISS11 (shown in Fig. 3, with one declaration moved for readability) has three components. The congruential generator and the 3-shift generator (CNG and XS respectively) have new names but are otherwise the same as described above (with XS corrected). The real change is that the two small Multiply With Carry generators have been replaced with a single, huge Complementary Multiply With Carry generator, implemented by the function b32MWC. This generator has 2²² + 1 words of state (the array Q and integer carry above). We don’t try to explain how it works; for that see [4]. Marsaglia does mention its cryptographic weakness, and attempting to hide it:Really, the only cryptographic strength of this subgenerator is its huge (just over 2²⁷ bits) state. For the first 16 megabytes of output, it is behaving like a Vernam cipher. For simplicity in the discussion below, we refer to R = 2²² as the number of outputs in a “round”, that is, a full pass through the array Q.

We assume that the contents of Q, cng and xs are initialized completely randomly and independently of each other. Note that the initial value of carry is explicitly set to zero. We assume that the output stream from KISS is known to the attacker (a standard cryptographic assumption); call this output stream Z _i ,i = 1...

Some observations:

1) at every stage, carry will usually be only 28 bits in length. The exception is when the high order 28 bits of the input Q value are all zero, carry will (almost never, but depending on the input carry value) become 0xFFFFFFFF. This is rare enough not to worry about in the attack below.

1a) if you know the input value Q[t], the output carry value is almost entirely defined by the most significant 28 bits. 15/16ths of the time, whether the optional subtraction of 1 happens is determined by comparing the least significant and most significant 4 bits of the input Q[t], independent of the input carry.

2) at every stage t, the output of b32MWC will be the input value of Q[t mod R] to the calculation of b32MWC R steps later.

3) CNG and XS are easily invertible (see above).

4) b32MWC is also invertible; if you know both the input Q[j] and the output Q[j] not only can you derive the output carry, you can also derive the input carry.

5) given (3) and (4), you can run the generator backwards if you need to.

The simple attack we present is a trivial application of the divide-and-conquer method, splitting the generator into two parts.

1. Start by guessing (enumerating) the 2⁶⁴ possible pairs (x s ₀ and c n g ₀).

2. Run the subgenerators CNG and XS forward R+3 rounds, and calculate M _i−1 = Z _i − c n g _i − x s _i ,(1 <= i <= R + 3). These are possible candidate values for the Q[i − 1 mod R] values.

3. If we guessed the initial values correctly in the first step, then M ₀ should be the output Q[0] (hence also the input to the calculation of Q[R]), and M _R should be the output Q[0] after R steps. From these, we can calculate c a r r y _R , and from c a r r y _R and M _R+1 (which we hope equals output Q[1]) we can check whether, in fact, the computation given input and output Q[1], and what we just calculated, agree with each other. If they don’t, go back to step 1. If they do (which might happen randomly), do the same for R + 2, and R + 3. At this point, if all checks worked, with high probability we must have guessed CNG and XS correctly.

4. Run b32MWC backwards to recover the initial settings of Q[i].

The expected work to do this is about 2⁸⁵ times the work to generate output words, which is a pretty normal measure. That is 2⁶⁴/2 (since you expect to search half the values) times about 2²² words generated (because of the huge state space). The attack requires a little more than 2²² words of known keystream, again because of the size of the state. Another way to look at this is that it’s about 2⁶³ times the cost of doing a key setup (independent of how you actually set up that huge key!).

However this attack can be significantly optimized. First we note that most of the generated values of from CNG and XS are not used in the important validation step; of the R + 3 pairs of values generated, only the first three and last three are used. Secondly, we note that both generators can be jumped forward a known amount (in our case R steps) with very much less complexity than simply evaluating the functions R times. In the case of XS, we can precompute the update matrix, and compute x s _R by multiplying x s ₀ by it. Similarly, CNG can be jumped forward using a modular “square and multiply” exponentiation calculation.

When enumerating the possible initial values of XS and CNG, there is no reason to enumerate them as counters. Since the values all fall on cycles (a single cycle in both cases, given the corrected values in XS) the values can be enumerated in the sequence produced by the cycle. For example, we start with c n g ₀ = 0, and quickly calculate c n g _R from that. By iterating CNG we easily calculate c n g ₁..c n g ₃ and c n g _R+1..c n g _R+3 as required above. After testing this value (and presumably failing), we can test the next value by discarding c n g ₀, using the old c n g ₁ as the new c n g ₀, similarly rolling over c n g _R and so on. The cycle of XS can be handled in the same way. Only once the correct values for c n g ₀ and x s ₀ have been identified is it necessary to run the generators R steps to recover the initial values of the Q array. Parallelization of this attack is a bit more tricky, but still easy. With this optimization, about 2⁶³ operations on average can be expected to recover the key. Since the Q array is so large, this corresponds to about 2⁴¹ key setup operations.

We conclude that the KISS generator, unsurprisingly, should not be used in any context where cryptographic security is important. Its period is more than sufficient for tasks like simulations, so long as it is correctly initialized, but care should be taken with this initialization step. Its period (maximum, expected, and minimum) is not as long as its authors claim.

As a design rule, updating the component generators independently leads to easy analysis, which is both a good and a bad thing. Exchanging values between the various state registers might defeat the kind of attack we have applied, but it would also make any kind of rigorous analysis impossible, and might make the generator weaker in ways that are difficult to deduce but damaging in practice.

We would like to thank our colleague David Jacobson for help with the linear algebra, and the anonymous reviewers who provided suggestions for improvement.