Will a 128 bit block have some security implication in post-quantum cryptography?

  • $\begingroup$ @otus I'm pretty sure that the blocksize won't have any implications with regards to QC, but that's the part I would not be able to argue successfully. I'm pretty sure with regards to Grover's attack because of the nature of it. But that would come down to an educated guess. $\endgroup$
    – Maarten Bodewes
    May 5 '19 at 20:21
  • $\begingroup$ I'm not sure that this is a duplicate, since OP is specifically asking about security against quantum computers, and the linked duplicate answer does not explain that. $\endgroup$
    – forest
    May 7 '19 at 0:30

Does the block size of a symmetric cipher impact the security of the cipher itself?

Yes, absolutely. A small block size limits the amount of data that can be encrypted with a given key, and some block modes are more badly affected by this than others. Additionally, some cryptographic attacks against weak ciphers can be made more practical against a block cipher with a small block size, such as the slide attack, which becomes very difficult to implement when the block sizes are large.

The classical issues with small block sizes are well documented, and other questions on this site on that topic have been answered. Generally, a small block size opens up a can of cryptographic worms regardless of whether or not your adversary is quantum-capable. A 32-bit block size is silly. A 64-bit block size is worrying and can be insecure in certain situations. A 128-bit block size is okay. A 256-bit block size is better. A 512-bit block size is generally excessive. This holds true, quantum or not.

Will a 128 bit block have some security implication in post-quantum cryptography?

No, a small block size will not generally be affected by quantum computers. The quantum algorithm that would be responsible is Grover's algorithm, which is a search algorithm. All the attacks against block ciphers that rely on a small block size are limited by the amount of ciphertext the attacker has, not by the number of operations an attacker is able to perform. Sweet32, slide attacks, etc. depend on nothing more than being able to collect a lot of ciphertext that has been encrypted under a single key. Once sufficient data has been collected, the number of computations required to break the guarantees of the cipher are not great enough to benefit substantially from Grover's algorithm.

It's important to note, however, that a block cipher used for authentication, e.g. with CBC-MAC, is more vulnerable against a cryptanalytic quantum computer. The reason for this is that a small block size results in a small authentication tag size, and Grover's algorithm can be used to brute force the small tag with more ease. The same is true if the block cipher is used as the core of a hash function, which would result in smaller digests that are easier for a quantum computer to attack.

  • 1
    $\begingroup$ The CBC-MAC security theorem, which is affected by the block size, is independent of the adversary's computational limits. When instantiated, only the AES security conjecture depends on the adversary's computational limits, and then it is essentially just the key size that affects the cost, not the block size. (The situation is exactly the same for the one-time pad security theorem and its instantiation with AES-CTR; this is why the conceptual structure is worth highlighting rather than obscuring by dogmatically imposing a barrier to connecting the terminology!) $\endgroup$ May 7 '19 at 4:25
  • $\begingroup$ @SqueamishOssifrage The security theorem remains fine, but the small tag size is bad. $\endgroup$
    – forest
    May 7 '19 at 4:27
  • $\begingroup$ The security theorem—that the advantage distinguishing $\operatorname{CBC}_\pi\colon \{0,1\}^{mb} \to \{0,1\}^b$ for uniform random $\pi$, from uniform random $f\colon \{0,1\}^{mb} \to \{0,1\}^b$, is bounded by $\binom{mq}{2} 2^{-b}$—is the main half of what justifies using $\operatorname{CBC}_\pi$ as a MAC; the other half is the obvious fact that a uniform random function is (strongly) unforgeable. Neither of these is affected by Grover, because the adversary can't tell offline whether a candidate authentication tag is correct or not. $\endgroup$ May 7 '19 at 4:32
  • $\begingroup$ Why do you say the small tag size is bad? $\endgroup$ May 7 '19 at 4:32
  • $\begingroup$ @SqueamishOssifrage Ah I see what you mean. Should I remove my mention of CBC-MAC? $\endgroup$
    – forest
    May 7 '19 at 4:33

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