1
$\begingroup$

Another way to ask this question: when block ciphers were invented, why did they add the restriction that the block cipher would be restricted to blocks of a fixed size?

From my laymen's point of view, I don't see why rounds of S-box and P-box operations couldn't be performed with inputs of variable size.

$\endgroup$
5
  • $\begingroup$ What is an unfixed size for you? $\endgroup$
    – kelalaka
    Oct 27 '20 at 22:30
  • $\begingroup$ @kelalaka A variable size that's sufficient to fit any one message anyone could want to cipher. $\endgroup$ Oct 27 '20 at 22:32
  • 2
    $\begingroup$ So, you need to design and analyze lots of sizes. And the larger the block the harder to diffusion. It is easy to design one and use the mode of operations. What about the hardware implementation? $\endgroup$
    – kelalaka
    Oct 27 '20 at 22:41
  • $\begingroup$ @kelalaka that makes sense! Maybe that should be the annswer. I just found it's really strange that all ciphers that came before DES didn't have a plaintext size restriction. I wanted to know what was the rationale for adding this restriction to DES and all other block ciphers that came after. $\endgroup$ Oct 27 '20 at 23:42
  • $\begingroup$ Block ciphers have that restriction, by definition. Stream ciphers don't, though they do have a point after which keys/nonces must be changed to maintain security. Block ciphers before DES had a fixed block size, stream ciphers before DES didn't. DES (or any other block cipher) in a streaming mode of operation like CTR doesn't have a fixed plaintext size, though the internal block size doesn't change. $\endgroup$ Oct 28 '20 at 1:38
2
$\begingroup$

Let us begin with what is a block cipher;

A block cipher is a family of permutations $$F:\{0,1\}^\ell\times\{0,1\}^b \to\{0,1\}^b$$ where $\ell$ is the key lenght and $b$ is the block size ( DES has 64, AES has 128 bit block sizes). From the key space $\mathcal{K}$ with $2^\ell$-size, a block cipher with the given $k \in \mathcal{K}$ selects one permutation form all possible permutations from $\{0,1\}^b \to\{0,1\}^b$. That makes at most $2^b!$ permutations. With the Stirling Formula

$$2^{b}! \approx \sqrt{2\pi 2^{b}} \bigl(2^{b}/e\bigr)^{2^{b}}$$ if you plug some numbers like AES-256 you will see how small the keyspace is compared to number of possible permutations;

$$2^{256}! \approx \sqrt{2\pi 2^{126}} \bigl(2^{256}/e\bigr)^{2^{256}} \!= \sqrt{2\pi 2^{256}} e^{-2^{256}} \bigl(2^{256}\bigr)^{2^{256}} \gg 2^{256}$$

Still what we want from a block-cipher like AES that they are a Pseudo-Random Permutation (PRP), not distinguishable from a random permutation. No one is able to show a distinguisher for AES yet in more than 20 years and no-one is able to prove it. We strongly believe it is a PRP.

Why are iterated substitution-permutation product ciphers only used on fixed-size plaintext blocks?

The substitution (Sbox in AES) can be used to design a larger block size, however, when you changed the block size from 64 to 128 bits you need a new permutation. Besides, for a better design, you will need to change the substitution, too.

When block size increased more and more, the control of diffusion (MixColumns+ShiftRows in AES) will be harder, too.

The above are some theoretical aspects of such design. There are other problems with the software and hardware. You need to implement many different sizes for software and hardware. This will increase the cost and area. Besides, in the hardware, we want small designs to reduce the area size and reduce power consumption. Even using the CTR mode removes the decryption implementation of the block cipher.

Although one possibly easily implement these in software, the problems are multiplied. You need to provide countermeasures for each implementation against the side-channeled attacks. The same applies to the hardware, too. Yet we are not perfectly able to do one, we will face multiple problems. See AES side-channel attacks, including the cache-attacks on AES.

Instead, it is better to design one with a fixed block size so that we can analyze it with more concentration. There is a nice post about the block cipher analyzing methods;

We can use a block cipher with various modes of operation to achieve the goal of encryption of large messages up to a limit, of course. I'll not list all of them here, each has pros and cons. Some to be mentioned

Arbitrary block sizes are also problematic if the block size is less than 128. There is a nice page about this, see

Another solution for your case the stream ciphers, they are designed to fast and can encrypt for large block sizes. They doesn't need paddings and they are encryption bit-by-bit or more in some designs.

Another way to ask this question: when block ciphers were invented, why did they add the restriction that the block cipher would be restricted to blocks of a fixed size?

The above reasons, especially the design and implementation. This will be more clear if you consider that during that age, people hadn't advanced as today. And the time showed that some decisions were right.

From my laymen point of view, I don't see why rounds of S-box and P-box operations couldn't be performed with inputs of variable size.

Hold on! they are not magical tools that like in LEGO that you may replace a 2x8 block with 4 2x2 blocks. Even there in some places, the structure will fail!

Each variation in the design needs to be designed, analyzed, and needs good implementation.

$\endgroup$

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.