0
$\begingroup$

If the construction of stream ciphers is already secure why does the construction of block cipher involve pseudo permutations and complex operations that makes block ciphers less faster? Is a construction of a block cipher defined as just Xor-ing a block of bytes with a block of key bytes (removing all permutations and other operations) not secure?

$\endgroup$
  • $\begingroup$ The general term ‘block cipher’ and the technical cryptology term ‘pseudorandom permutation’ are almost synonymous. (The difference is that some cryptology literature assumes a somewhat stronger technical condition, ‘ideal block cipher’, like ‘random oracle’ for a hash function.) You might find better enlightenment by asking: What is a block cipher? What is a stream cipher? The answers to these may make the answer to your question obvious in retrospect. $\endgroup$ – Squeamish Ossifrage Mar 16 '18 at 19:35
2
$\begingroup$

An XOR cipher is insecure if the same key is used more than once (or, more generally, if any bit of the key is used to encrypt more than one bit of data).

For stream ciphers, this is fine, since the keystream can be made arbitrarily long. (Of course, the keystream generator itself must involve something more than just XOR.) But in a block cipher, we want to be able to encrypt many blocks with the same (relatively short) key. If the encryption process consisted of just XORing the key with the block, this would become insecure as soon as we tried to encrypt more than one block with the same key.

Of course, we could consider having some kind of a key expansion process that generated an endless stream of "block keys" from a single master key, and then just XORing each block of data with a different block key. But this would really just be a stream cipher operating on blocks of data, not a block cipher.

$\endgroup$
  • $\begingroup$ But even for a block cipher many-time key encryption is not possible unless there is a mode of operation that involves block chaining with nonce or random IV, and I assume such modes won't work if the block cipher is just a simple XOR, is that correct? $\endgroup$ – M.Mounir Mar 16 '18 at 23:03
5
$\begingroup$

If the construction of stream ciphers is already secure why does the construction of block cipher involve pseudo permutations and complex operations that makes block ciphers less faster?

A stream cipher consists of more than just a single XOR operation. They first have to spend time generating the key stream from the key and nonce/seed. They actually use many of the same operations and take about the same amount of time as a block cipher does to do so.

For example, Salsa20 is a stream cipher that uses addition, rotation, and XOR to generate the key stream.

salsa20 round function

After the key stream is generated, it is combined with the message via XOR.

The stream cipher is only secure if the key stream is unpredictable. The complexity and time goes into making the output unpredictable.

Is a construction of a block cipher defined as just Xor-ing a block of bytes with a block of key bytes (removing all permutations and other operations) not secure?

Yes, such a construction is insecure. Suppose that the adversary knows a single plaintext message. They can simply subtract out the known message to retrieve the key, which allows them to subtract out the key from any other ciphertext to recover the plaintext message.

$c \leftarrow m \oplus key\\ key \leftarrow c \oplus m$

Unless your messages are the output of a random number generator and have 8-bits per byte of entropy, then they are susceptible to a known plaintext attack. Any meaningful message will not have 8-bits/byte of entropy, and so you have to assume that the adversary already knows the plaintext messages when designing a cipher.

Additionally, assume that you have two messages $m_1$ and $m_2$ that differ by only a single bit. When you XOR the key into them, the only difference in the resultant ciphertexts is at the place where the messages differed by one bit. A block cipher should produce a random permutation of message blocks, and this is clearly non-random behavior. A block cipher needs to spend time creating diffusion, where flipping a single input bit flips approximately half of the output bits.

$\endgroup$
5
$\begingroup$

If the construction of stream ciphers is already secure why does the construction of block cipher involve pseudo permutations and complex operations that makes block ciphers less faster?

Because stream and block ciphers are not in fact comparable types of object. They're practical approximations to two different types of ideal object:

  • A stream cipher is designed to behave like a randomly-chosen one-time pad.
  • A block cipher is designed to behave like a randomly chosen permutation of the set of all bit strings of a fixed length.

Note also that:

  • For a message of length $n$, there are $2^n$ distinct pads that could be used to encrypt it.
  • For a block size of $n$ there are $2^n$ distinct values, and therefore $2^n!$ (the factorial of $2^n$) distinct permutations of blocks of that size.

$2^n!$ is a vastly larger number than $2^n$. It follows that the probability that a randomly selected $n$-bit permutation will have the same effect on its inputs as the application of any of the $2^n$ one-time pads of length $n$ is therefore very unlikely. And this means you can't build a reasonable block cipher by using the OTP strategy of XORing to the input; XORing with an OTP only allows you to permute inputs in $2^n$ different ways.


One piece of practical advice: in spite of many introductory cryptography materials' description of block ciphers as "encrypting messages one block at a time," try not to think of block ciphers as message encryption algorithms at all. Think of them more as a basic building block that tries to behave in a very specific, well-defined manner, which cryptographers then reuse to build practical encryption algorithms out of.

$\endgroup$
  • 1
    $\begingroup$ Can't emphasize enough how harmful it has been for textbook authors to promulgate the deceptive simplicity of the concept of a block cipher encrypting a message a block at a time. Always calling it a pseudorandom permutation family might help to dissuade unwary laymen from handling such sharp-edged tools… $\endgroup$ – Squeamish Ossifrage Mar 16 '18 at 20:42
  • $\begingroup$ But isn't a block cipher with a fixed key is also a 2^n permutation? In this case what makes us use PRPs with fixed key in cryptographic constructions instead of simple XOR? $\endgroup$ – M.Mounir Mar 16 '18 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.