[Cryptography] Time to move to 256bit blocks?

[Jon Callas]

> On Mar 19, 2021, at 09:38, Phillip Hallam-Baker <phill at hallambaker.com> wrote:
> 
> I am almost done implementing OCB mode in C#. I have the encryption test vectors working for full blocks. All I need to do now is decrypt (which people might want to do).
> 
> While working on this, I started to think that maybe we have got to the point where we should move past the 128 bit block size of AES. This was a fine choice when it was made and arguably a decent choice today for hardware encryption. But it still represents a compromise that I would rather eliminate rather than work around.
> 
> The obvious replacement choice is 256 bits. While Rijndael offers 192 bits, that is a poor match to modern computer architecture where data moves in 2^n bit increments.
> 
> So the next question would be which 256 bit block cipher to use.  Rijndael? Something else? If Rijndael, how many rounds for a 256 bit key?
> 
> While I get that  Rijndael is a flexible cipher, I don't agree with all the choices on offer. I have never seen the point of 192 bit keys, I don't use them, I don't support them in the Mesh. Anyone using a 256 bit block size is going to go for a 256 bit key. I can't see a justification for keys larger than 256 bits but I can see a case for using more than 14 rounds.

[I forgot to hit return on this last weekend. Apologies for being late to the party.]

Forgive me, but it sounds like you're conflating block size and key size, so if I'm just confused, let me know.

The major advantage of AES is that it's in the CPU, at speeds that make it faster than a naive memory copy, and this means that using it as a primitive gets you speed enough that no one really worries about the speed any more. So the first thing to consider is using AES within some other mode to get you a bigger block size.

There are a number of fast, tweakable modes. A "tweak" is the generalization of an IV/nonce. A tweakable construction is fully secure, even if the tweak is under control of the attacker. XEX/XTS has a lot of nice properties, but you don't get it truly acting like a large block. EME or CMC are good options. They're two-pass on the encryption, each and the M stands for Mix. CMC uses CBC as its primitive, EME uses bare AES (a.k.a. ECB) and so is parallelizable better. EME was patented but the patent was abandoned. If you need the large-block-ness more than speed, then EME is a good choice. Despite being two-pass, you can do the encryption in parallel, and that gets an appreciative speedup on Intel hardware. I don't know if the ARM equivalent of AES-NI gets a similar boost for running in parallel.

If you don't want to do anything that builds on AES as a primitive, then it's into a different game. Non-AES Rijndael can do a block size in any multiple of 32 bits up to 256 bits, but why?

I agree with you that the 192-bit key stuff in AES is neither fish nor fowl. It has all the disadvantages of 256 bits (like needing more rounds), and isn't 256 bits. If you're concerned about quantum computers, for example, a 192-bit key gets you 96 bits of post-quantum strength, and why not go to 256? It really doesn't make a lot of sense.

Rijndael can do 160, 192, or 224 bits in block size as well as key. But why? You're going to have sit down and come up with all the right parameters and answer questions like why you didn't use EME if you're that concerned about block size.

I would suggest that if you really, really don't want anything based on AES, go to Threefish. In the full-disclosure part, I'm one of it's co-authors. It's a wide-block, tweakable cipher with a 128-bit tweak. There are variants that have block and key at 256, 512, and 1024 bits. In software, it's over twice as fast as AES/Rijndael. 

The advantage of a real tweakable cipher is that you can really toss chaining modes away. You can also do them, so if this bothers you in the least, you could both chain and tweak. (Might as well, as there's no reason not to use the tweak, because of the properties of a tweak -- you can hand the tweak over to the adversary and lose no security.)

I recommend Threefish-512, myself as the best-rounded of them, and after that Threefish-1024. The 256-bit one is not as fast and has a narrower block and thus kinda falls into that neither fish nor fowl zone. You're likely to need a bit of hacking the keys. They all want key size equal to block size. Any decent KDF/Keywrap function will do that, like even just a 512-bit hash function.

	Jon