# Converting a stream cipher into a block cipher

The well-known Counter-Mode (CTR) mode of operation for a block cipher essentially converts any block cipher into a stream cipher. Is there a way to do the reverse? In other words, given a "good" stream cipher $G$, can we construct a block cipher that builds its strength based on $G$?

-

In an answer to another question, Zooko mentioned the BEAR and LION constructions, linking to this paper: Two Practical and Provable Secure Block Ciphers: BEAR and LION.

These build a block cipher (with large blocks) from a stream cipher and a hash function (a keyed one (i.e. a MAC) for BEAR, a unkeyed one for LION).

The authors basically build block ciphers (with variable block sizes $m$) from a keyed hash function (a function family $H_K : {0,1}^* \to {0,1}^k$) or a normal hash (a function $H' {0,1}^* \to {0,1}^k$) and a stream cipher (a function $S : \{0,1\}^k \to \{0,1\}^n$, for arbitrary $n$ from context; here $n = m-k$).

These work by fist splitting the input block of size $m$ in two parts, one (L) of size $k$ and one (R) of size $m-k$, doing the encryption/decryption, and putting the two parts again together. We also have two keys $K_1$ and $K_2$, each of length $k$.

For BEAR, the encryption is done by

$$L := L ⊕ H_{K_1}(R)$$ $$R := R ⊕ S(L)$$ $$L := L ⊕ H_{K_2}(R)$$

and decryption the other way around:

$$L := L ⊕ H_{K_2}(R)$$ $$R := R ⊕ S(L)$$ $$L := L ⊕ H_{K_1}(R)$$

For LION, we use a un-keyed hash function $H'$, and we have two calls of the stream cipher instead of the hash function instead of two keyed hash calls. Encryption:

$$R := R ⊕ S(L ⊕ K_1)$$ $$L := L ⊕ H'(R)$$ $$R := R ⊕ S(L ⊕ K_2)$$

Decryption:

$$R := R ⊕ S(L ⊕ K_2)$$ $$L := L ⊕ H'(R)$$ $$R := R ⊕ S(L ⊕ K_1)$$

E.g. decryption is in both cases just encryption with swapped key halves.

These are effectively Feistel networks with three asymmetric rounds.

The paper proves that these are secure (against certain attacks) as long as even one of the component functions is secure (e.g. breaking the composed primitive allows breaking both of the components).

There is a third construction mentioned in this paper, LIONESS, which uses four rounds (two keyed hashes, two stream cipher calls), which also provides resistance against an adaptive combined chosen plaintext and ciphertext attack.

-
This does not answer the originally posed question. It requires not just a stream cipher, but also a keyed hash function. There is no guarantee that the strength of the block cipher is based upon the strength of the stream cipher (i.e., the stream cipher might be secure, but the BEAR/LION construction that uses it might be an insecure block cipher). BEAR/LION also places unusual requirements on the stream cipher: it requires the stream cipher to be secure against related-key attacks. Many stream ciphers are not secure against related-key attack. –  D.W. Sep 22 '11 at 4:45

There is a theoretical construct described here (published in FSE 2007), assuming that the stream cipher is "seekable" (it suffices that the stream cipher can be initialized with a key and an IV, so that you can have many streams for a given key; the stream ciphers described in the eSTREAM Project accept an IV, but RC4 does not). The construction is "perfect" in the following sense: for any block size (actually, any finite space of block values), a permutation is selected among the $N!$ possible permutations (where $N$ is the number of possible block values, e.g. $N = 2^{128}$ if you want 128-bit blocks); the permutation selection is uniform is the stream cipher produces uniformly random bits). Any successful attack on the resulting block cipher becomes, mechanically, a distinguisher on the stream cipher output.

I have implemented it and it works but it very slow (I can encrypt, say, a dozen blocks per second on a PC) because the computation involves using floating point numbers with arbitrary precision.

-