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$?
3 Answers
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.
-
3$\begingroup$ 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. $\endgroup$– D.W.Sep 22, 2011 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.
-
$\begingroup$ +1 for the link to "Perfect Block Ciphers with Small Blocks", an algorithm I hadn't seen before. Both WEP and CipherSaber initialize RC4 with a key and an IV. So it seems incorrect to say "RC4 does not". $\endgroup$ May 19, 2016 at 14:16
No, there is not a good way to build a block cipher out of a stream cipher. There are constructions, but they are very slow and not very practical.
Why do you ask? It's not clear to me why you'd want to build a block cipher out of a stream cipher. Perhaps if you tell us what you are actually trying to accomplish, we can find a better way to achieve it.
-
1$\begingroup$ I'm asking out of general interest; to me it's interesting if one primitive can be efficiently converted to the other. $\endgroup$– FixeeSep 19, 2011 at 2:58
-
1$\begingroup$ Using Salsa20 and a three round feistel in BEAR/LION style constructs one can achieve a block cipher of small block size (say 128-bit) with around a 15x slowdown compared to the stream cipher. For Salsa20 or similar, this could be only a few times slower than AES in software. For larger block sizes, the slowdown is even less. I would consider them practical and not very slow if you actually have the need - but obviously a real block cipher is always faster. $\endgroup$ Sep 20, 2011 at 10:35
-
2$\begingroup$ @Nakedible, But BEAR/LION requires more than a secure stream cipher; it also requires a keyed hash function, and it requires a stream cipher that is secure against related-key attacks. The spirit of Fixee's question is to look for a way to build a block cipher out of just a stream cipher (any old stream cipher). $\endgroup$– D.W.Sep 22, 2011 at 4:43
-
1$\begingroup$ You are right, any old stream cipher won't do and it isn't trivial, so it is not a generic solution. $\endgroup$ Sep 22, 2011 at 9:52