How many required known plaintexts for an attack are considered insecure? I stumbled over this problem when looking at symmetrical block ciphers with a relatively small block size like 32 bit.

When I was looking at more common block ciphers with a 64 bit, I learned that they can be considered secure when the number of plaintexts required for a known/chosen-plaintext attack is relatively high ($~2^{40}$ - $2^{64}$).

I have two questions. 


Firstly, is this a correct threshold for considering a cipher secure?
And secondly, does this mean that all 32-bit block ciphers are inherently insecure?




Another question that I asked after discussing my original post: Speaking in general terms, assuming that you have found an optimal attack for a block cipher that requires x known plaintexts or y chosen plaintexts. How large would x/y have to be so that the cipher could be considered secure?
Firstly, is this a correct threshold for considering a cipher secure?


Not exactly. Security is a spectrum, so what is secure for some applications may not be secure for others. Is a $2^{-64}$ probability of attack success too much? For some it is far too high. For others, even $2^{-32}$ is fine. In the case of known plaintext attacks, an attacker is usually assumed to have as much known plaintext as they want. In such cases, the bounds are placed on the amount of plaintexts that can be reasonably stored and processed. That is, a petabyte of known plaintext may be assumed (high-speed hardware that behaves as an encryption oracle may allow this), but $10^{90}$ exabytes? Usually not.

As stated, your question doesn't have an objective answer. You would need to append "when performing a specific number of encryptions" to get a real answer, in which case you consult the effects of block size on certain modes of operation. For example, Blowfish is a 64-bit block cipher and is considered secure when encrypting, say, one gigabyte of data under a given key. You can calculate the precise requirements for an attack under those conditions and show that the attack is not practical. If, on the other hand, you encrypt a hundred gigabytes, things will get nasty when using that block size.

A known plaintext attack for a given cipher is usually considered not to be a problem if either:


The specifications make it such that it is impossible to obtain enough known plaintext, or
The amount of known plaintext required would be so vast that no one could encrypt that much.


An example of the first reason for not worrying about known plaintext attacks is in two-level E0, as used in some older versions of Bluetooth. The E0 stream cipher is extremely vulnerable to known plaintext attacks. Rather than vastly modifying the Bluetooth specifications, an easier mitigation was to require rekeying before enough data is transmitted to provide enough known plaintexts to perform an attack.

It turns out that the best attack against E0 requires a bit of known plaintext from only $2^{23.8}$ frames, but the Blutooth protocol allows up to $2^{26}$ frames to be encrypted under a single key, rendering E0 more insecure than implied above.

An example of the second reason would be a 128-bit block cipher in CTR mode. The amount of data required to perform an attack on it is staggeringly huge. An online cost of $2^{64}$ is really quite massive.


  And secondly, does this mean that all 32-bit block ciphers are inherently insecure?


For the vast majority of uses, yes. For those asking if a 32-bit block size is too small, also yes. However there are a few edge cases when that block size is acceptable. This is only the case if truly minuscule amounts of data are being encrypted under a single key. Encrypting small session tags is one example.

The cipher Speck32/64, for example, is considered to be secure despite having a 32-bit block size and a 64-bit key size. It provides 64 bits of security under the constraints that only a trivial amount of data can be encrypted with it. But that doesn't mean you should be encrypting your hard drive with Speck32/64. That is because those parameters make it vulnerable to generic attacks under realistic conditions.

A generic attack is one that applies even to an ideal, perfect block cipher and is utterly independent of its internal workings. Brute force of the key and issues caused by the birthday bound when used with certain block modes are both kinds of generic attacks. A block cipher is not considered inherently insecure in the cryptographic sense just because a generic attack may apply to it, but it may be considered insecure by practitioners. After all, an attacker doesn't care that they broke something with a generic attack because you used a small key or a small block size instead of using some fancy and complex cryptanalysis.

Generally, you should assume the following statements about block sizes to be true:


256 bits is always safe from the limitations imposed by the birthday bound.
128 bits is safe for the vast majority of use cases with realistic amounts of data.
64 bits is worryingly small, but is acceptable if used carefully and not for a lot of data.
32 bits is only safe in extremely rare circumstances. For others, it is horribly insecure.