[Cryptography] block size / block cipher versus stream cipher

[John Denker]

On 3/19/21 9:38 AM, Phillip Hallam-Baker wrote:

> I started to think that maybe we have got to the
> point where we should move past the 128 bit block size of AES.

> The obvious replacement choice is 256 bits.

===============

Some very smart people whom I respect have told me I'm wrong
about this, and may be I am ... but maybe not.

Here's how things look to me:

0) For today, let's talk about confidentiality only, not
 authenticated encryption.

1) A good cryptosystem should be able to encrypt anything.
1a) It should be able to encrypt known plaintext without harm.
1b) It should be able to encrypt chosen plaintext without harm.

2) Sometimes we are encrypting data at rest, but sometimes we
 are encrypting real-time interactive stuff, which means we
 care about latency. Sometimes care about good data compression.
 That means that sometimes we need to send a few bits or a single
 bit ... and do it /right now/. We cannot wait to fill a big block.

3) Block chaining modes are IMHO a fig leaf, used to cover up
 the ugliness of non-agile keying. It allows a key to be re-used
 from one block to another. In contrast, IMHO a proper cryptosystem
 simply uses a different key for each block. It does not require
 an expensive "key-scheduling" step, and it is not vulnerable to
 related-key attacks.

 Many well-known ciphers have expensive key-scheduling and/or
 related-key issues.

4) Key size is not the same as block size. PHB is AFAICT mostly
 arguing for a 256 bit key, which is fine with me. In contrast,
 I have yet to hear a persuasive argument for a 256-bit block,
 or any block at all.

5) AFAICT the whole point of having blocks is to perform a certain
 amount of autoencipherment; that is, using the plaintext to supply
 a some (?) amount of uncertainty. This strikes me as unsound
 engineering, because there is no provable lower bound to the
 entropy of the plaintext, as discussed in item (1) above. Also:

 Example #1: Consider a situation where the first many blocks
 consist of 256 zeroes. Every once in a while there is a block
 containing a one along with 255 zeros.

 Example #2: Similarly, consider a real-time interactive situation
 where once in a while I need to send a single bit /right now/.

 These fall into the category of almost-known plaintext.

 The point here is that using the entropy of the plaintext fails
 miserably in these examples. Crypto is supposed to be reliable.
 An approach that fails miserably in prosaic use-cases seems like
 a bad idea IMHO.

 Example #3: Block chaining modes are dead on arrival if we need
 to do random access.

6) I have heard a squillion argument against stream ciphers. The
 conversation generally goes like this:
 −− Stream ciphers are known to be bad.
 ++ What's the problem?
 −− Suppose the stream-generator fails in such-and-such way, then
  dot dot dot.....
 ++ So we should use a generator that doesn't fail.
 −− But you don't want to put all your eggs in one basket.
 ++ Birds have been thinking about this for tens of millions of
  years, and they have decided it's best to put all their eggs in
  one basket, and then scrupulously watch and defend that basket.
 −− There will be big trouble if somebody re-uses a key.
 ++ As Smith&Dale would say: So don't do that.
 −− Sometimes there *is* entropy in the plaintext. Why not use that?
 ++ You can't rely on that. A system that is good enough to encrypt
  low-entropy plaintext will also encrypt high-entropy plaintext
  just fine.
 −− Enigma had a small blocksize, and it got broken.
 ++ I can think of N different ways of making Enigma vastly stronger,
  N−1 of which don't require blocking.
 .. and so on, ad infinitum.

 Seriously: A large number of weak arguments are not a valid
 substitute for one strong argument. A thousand data points with
 one-sigma confidence to not outweigh a single data point with
 ten-sigma confidence.

7) Any block cipher can be turned into a stream cipher using CTR
 mode. Actually I would prefer to see KTR mode, i.e. Key-Counter
 Mode, where you increment the key (not just the plaintext) each
 time.

8) Existence argument: Ciphers in the Salsa/ChaCha family have
 agile keying and huge keyspaces. The last time I checked (2020),
 the best public cryptanalysis of these ciphers was not very scary.
 If you really don't like putting all your eggs in one basket, you
 can superencrypt the stream using AES or whatever else you like.

9) Bottom line: My rule of thumb is that any discussion of block
 sizes is misguided, and any discussion of chaining modes is
 misguided. A proper cryptosystem should be able to encrypt a
 single bit, right now, without any dependence on other plaintext
 bits.

So ... what am I missing?