Introduction

LEVIATHAN [5] is a stream cipher proposed by David McGrew and Scott Fluhrer for the NESSIE project [6]. Like most stream ciphers, it maps a key onto a pseudorandom keystream that can be XORed with the plaintext to generate the ciphertext. But it is unusual in that the keystream need not be generated in strict order from byte 0 onwards; arbitrary ranges of the keystream may be generated efficiently without the cost of generating and discarding all prior values. In other words, the keystream is ``seekable''. This property allows data from any part of a large encrypted file to be retrieved efficiently, without decrypting the whole file prior to the desired point; it is also useful for applications such as IPsec [2]. Other stream ciphers with this property include block ciphers in CTR mode [3]. LEVIATHAN draws ideas from the stream ciphers WAKE [9] and SEAL [7], and the GGM pseudo-random function (PRF) construction [1].

The keystream is bounded at bytes. Though the security goals are stated in terms of key recovery, it is desirable that distinguishing this keystream from a random binary string should be as computationally expensive as an exhaustive search of the 128 or 256-bit keyspace. Keystream generation is best modelled as a key-dependent function , mapping a location in the stream to a 32-bit output word; catenating consecutive values of this function from 0 gives the entire keystream:

$$\textrm{Lev}(0)\vert\textrm{Lev}(1)\vert\textrm{Lev}(2)\vert\ldots \vert\textrm{Lev}(2^{48}-1)$$

Finding for arbitrary is not especially fast. However, once this is done, intermediate values can usually be reused to find much more efficiently. This is because the internal structure of the cipher is based on a forest of binary trees, each of which generates words of output, as shown in Figure 1.

Figure 1: Computation of an entire output tree of 8 words with . In the full cipher, and the complete output is built from such trees.

The notation we use to specify this function precisely is somewhat different from that given in [5], but is convenient for our purposes; we treat as a parameter, rather than as a word of state. The cipher is parameterised on and , where is divisible by 4 and ; LEVIATHAN sets and . denotes catenation of bit strings, bitwise complementation of , the XOR operation (addition in or as appropriate), and addition in the group , treating the first bit of the bitstring as the most significant and padding bitstrings shorter than bits with zeroes on the left. We specify the forest structure illustrated in Figure 1 recursively:

$$\begin{eqnarray*} \textrm{Lev}:\{0,1\}^{n+h} & \mapsto & \{0,1\}^{n}\\ \textrm{... ...z\vert) & = & A_{z}(V(t,z))\\ V(t,z\vert 1) & = & B_{z}(V(t,z)) \end{eqnarray*}$$

The internal state that functions , , and operate on (and the functions , , used to define them) is a 2-tuple of bitstrings ; we treat this as distinct from the catenated bitstring . The functions , , and operate on bytes within a word: and are rotates, while provides nonlinearity with the key-dependent permutations which map onto itself. These permutations are generated by the key schedule, which we omit. Note that and operate on each word of the tuple independently; mixing is provided by .

$$\begin{eqnarray*} C(x,y) & = & x\oplus y\\ A_{z} & = & F\circ D_{z}\\ B_{z} & ... ...lus S_{2}(x_{0})\vert x_{1}\oplus S_{1}(x_{0})\vert S_{0}(x_{0}) \end{eqnarray*}$$

[5] gives a functionally different definition of ( ); the one given here is that intended by the authors [4] and used to generate the test vectors, though the difference is not relevant for our analysis.

We present two biases in the LEVIATHAN keystream that distinguish it from a random bit string. We know of no other attacks against LEVIATHAN more efficient than brute force.