[Cryptography] block size / block cipher versus stream cipher

[John Denker]

On 3/22/21 10:48 AM, Phillip Hallam-Baker wrote:

> What I am looking at is ways to tune a cipher so that I can use
> frequent rekeying of the symmetric key to avoid the need to go
> through an expensive public key agreement.

So we agree. That's what I was suggesting. Nobody is suggesting
redoing the public-key stuff for every block.

> Rekeying on every block is a bad idea. Rekeying the symmetric cipher 
> between each frame of video is a very different proposition because I
> can do that in parallel and it costs me nothing.

Rekeying on every block versus rekeying on every frame ... are
those the same thing? If not, why is the difference significant?

Again I emphasize that I am talking about rekeying the cipher that
gets applied to the data (not the public key agreement stuff).

If rekeying on every block is a bad idea, please explain why. In
particular, if the frame-cost is zero, why is the block-cost nonzero?
Please avoid appeal to authority; that is, explain it like you are
talking to somebody who has made a career of doing stuff that the
textbooks say can't be done.

> The objective here is to limit lag to no more than two or three
> frames and try to make it one frame or less.

Three frames of lag at 30 fps is unacceptable for most real-time
interactive applications. When the guy at the other end is slow
to answer simple questions, it makes him seem stupid or dishonest.
There is a vast literature on the human factors involved.

> OCB can be configured so it can be used in the same manner as ECB
> (i.e. random lookup) but with a performance penalty for each 'seek'
> operation. And you can't do authentication of course.

What's the point of OCB if we aren't doing authentication? Why
should we accept any penalty at all?

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

Rogoway claims a ciphertext length of
	m + a + 1.016

I reckon that assumes the blocksize is huge compared to the size of
the nonce; otherwise things get a lot uglier. AFAICT authenticating
a very short message is always going to be hard.