[Cryptography] Recommended Process for a new cipher mode submission

Phillip Hallam-Baker phill at hallambaker.com
Sat Jul 17 23:43:22 EDT 2021


On Sat, Jul 17, 2021 at 7:11 PM Jon Callas <jon at callas.org> wrote:

>
>
> > 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.
>

OCB starts down the tweakable route...



> 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.)
>

Agree.


> 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.
>

Very much agree. If we were ever going to do another block cipher
competition it will be because we want longer block sizes. I have in the
past considered using the Rijndael modes that didn't become AES...



> 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.
>

QUIC has taken the same route and I have followed with RUD, IP Packets come
in chunks of 1400 bytes which mean payloads of ~1280 bytes. Turns out that
you might as well always pad to the max packet size because the routers are
limited more by the number of packets than the number of bits.



> 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.)
>

Also agree. Though I would like to repeat my plea for shorter block sizes.

One of the conceits of RUD is that every single bit of the IP payload is to
be encrypted once a connection is established. And RUD connections can
persist for decades.

So the question arises of how to tell the recipient which connection a
packet is bound to so it can work out which primary key to use to derive
the session key. And so we end up with some sort of 'one time identifier'
that is a kerberized ticket. And, well 128 bits is a lot to spend on that.
I would rather spend less, much less.

\

> > 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.
>

Actually it was two separate patent holders, not just the one. Had it been
just one, it could probably have been sorted. But there was a second patent
claim
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20210717/0104b977/attachment.htm>


More information about the cryptography mailing list