[Cryptography] Recommended Process for a new cipher mode submission

[Jon Callas]

> On Jul 15, 2021, at 09:41, Phillip Hallam-Baker <phill at hallambaker.com> wrote:
> 
> There are several questions that need to be answered when considering any new cipher or operation mode.
> 
> 1) What is the rationale for introducing it?
> 
> At this point performance is not going to be sufficient to motivate a new tool unless the advantage is overwhelming. I can do AES CBC faster than I can write to disk or the network on most devices because of hardware support and most of those will do GCM or OCB just as fast.
> 
> The only good rationales for introducing new tools at this point are to provide additional functionality or to take advantage of a new design approach providing a stronger proof of security. GCM and OCB provided both, authenticated encryption was a new type of mode and the design of both was making use of 20+ years of developments in cryptographic proof since CBC was developed.

Absolutely agree on this.

Having said that, however, there is at least one thing that would be really good to have: tweakable ciphers. A tweak is the generalization of an IV/counter/nonce, and there are a lot of mode issues that go away if you have tweaks in the cipher. A tweakable cipher is secure even when the tweak is under attacker control. It collapses a lot of discussion about modes. 

You really only need a generalized counter, which is perhaps a glib thing to say. Nonetheless, if you generalize a counter to include increment by any given constant, or something extended like the cipher text of block $i$ becomes the tweak of block $i+1$ (which is the tweak-analogue of CBC), you don't need anything else. (And moreover, in the tweakable system, tweak-CBC is no more cipher-secure than a simple counter; it is, however, not parallizeable, which is either a flaw or a feature depending on what problem you want to solve.) (Additional note, tweak-counter is not the same thing as CTR mode. CTR mode is a stream cipher and suffers from all the stream cipher problems of key reuse letting you learn the underlying keystream, etc.; tweak-counter is chaining.)

The other major thing worth having is a wide-block block cipher. 1024bits (128 bytes) is good enough, I'd really like to have 4Kbits (512 bytes). Variable block size would even be cooler, as would a pony. The reason for the wide block is that it better approximates an idealized all-or-nothing transform. The wider a block is, the less some weaknesses matter. For example, with present 128-bit block ciphers, ECB mode easily leaks minor things. It isn't unreasonable, for example, for a data structure to have 16 bytes of zeroes. There are also lots of places where there are related issues -- many, many XML files start with "<?xml version="1.0" encoding="utf-8"?>" which is 38 bytes long. This is far less if a problem the wider the block is. The real solution is to use tweak-counter on your wide block. 

For those who are going to stress over sizes and padding, there are two viable answers. The best in my opinion is to let an upper layer worry about exact length. This really does work: every disk file system for as long as there have been disks has had to deal with this -- and they were dealing with blocks of 512 bytes! For those still stressing, it's easy to take your final block and make a tweak-cipertext-stealing analogue. This is really only taking a convenient ciphertext and XORing it onto that last block. You can fill out the specifics as well as I can. I also leave the tweak-analogue of CMAC/OMAC as an exercise for the reader. My final comment is that the astute reader will note that I've just been saying, "go ahead, roll your own crypto! Knock yourself out!" That's how good tweakable ciphers are to have.

For further reading on why this is what we really need, the paper, "Robust Authenticated Encryption" by Hoang, Krovetz, and Rogaway is absolutely the bomb. It's the theory paper for the "AEZ" construction that takes AES round-function primitives to make a variable width, large-block, tweakable cipher. <https://www.cs.ucdavis.edu/~rogaway/aez/rae.pdf> (AEZ itself  is a completely different discussion, and beyond the scope of the already-too-much I've said.)

> I really can't imagine us doing another curve selection contest unless people decided we really really need >448 bit curves after all. And that is a pretty short discussion because it's 512 bits or 521 which 521 wins and once you choose 521, you run the rigid parameter generator and we are done.

Also agree, with only the comment that it's possible to have nothing up one's sleeve and still do slight of hand.

> 
> Developing a new cryptographic elections scheme (and a proof) might get you tenure but it almost certainly won't get used. I am one of the very few people trying to get people interested in using threshold schemes and it is an uphill struggle which I would not be able to do in either academia or in any but the very largest industrial research labs. 

This!

These days, all a patent on cryptographic primitives is going to do is to delay its use by 20 years. By then, it may be too late. If OCB had not been patented, we wouldn't have the collection of AEAD modes including CCM (specifically created to be unencumbered), GCM (created because CCM was slow), EAX (created by OCB's creator as an alternative to CCM), and more. All of that morass because of an unfortunate patent.

	Jon