[cryptography] State of the art in block ciphers?

Jon Callas jon at callas.org
Sat Dec 7 03:20:01 EST 2013


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Dec 5, 2013, at 12:13 AM, Matthew Orgass <darkstar at city-net.com> wrote:

> 
>  I recently looked into this and Threefish seems to be the only block cipher I could find that provides major advantages over AES.  The large block sizes and tweak parameter make it a good fit for disk encryption. I don't know how the performace compares to hardware AES.  I haven't so far come across any good reason to start using any block cipher other than AES or Threefish (unless special circumstances are involved).

Thanks. Full disclosure, I'm a Threefish/Skein coauthor.

Performance-wise, software anything is not going to compare against hardware anything-else. If you are so desperate for performance that you consider it more important than security, then there are lots of good answers for you. XOR, for example, is about as fast as you can get, and all you need is a good key generation algorithm. AES in hardware (like AES-NI) runs faster than one clock per byte if everything's set up correctly. If things aren't set up correctly, it runs at about twice software speed. 

In software, Threefish runs at about twice AES speed. There are many, many handwaves in my previous statement. Threefish was designed for a 64-bit, superscalar architecture with a good handful of registers. At the time, the exemplar of such an architecture was an Intel Core 2 CPU. It succeeds at using the whole of the CPU so well that Intel uses it internally as a literal burn-in test of a CPU. If you have a CPU with heat flow issues, running Threefish on it will find them. Often destructively. Notably, it's intentionally an ARX construction that uses register flow as a cheap way to get inter-round permutations. 

The wide-block is a huge advantage. You've noted its use in disk encryption, but it's also a great use just about anywhere else. Block ciphers in general have the advantage that they, um, well, encrypt in blocks. They didn't exist at all until relatively recently. (If you squint at it the right way, you can consider ADFGX to be an early block cipher, if not the earliest, but no doubt we can debate it). It's relatively easy to turn a block cipher into a stream cipher (counter mode), but relatively hard to turn a stream cipher into a block cipher. The wider the block is, the more mixing you get. A one-bit change in a block cipher affects the whole block, and as the block's width gets larger, the more it approaches All-Or-Nothing Cryptography.

Tweakable ciphers in general also have huge advantages. You can think of a tweak as the generalization of an IV or counter. This is why a tweakable cipher is good for disk encryption -- because the LBN of a disk block is definitionally not a secret parameter. But once you have a tweakable cipher, there are ways that you can re-think chaining modes.

For example, you can re-think counter mode trivially by moving your counter to the tweak and now you don't have to worry so much about counter re-use. Yay! You can even throw away nonces, at the cost of having to deal with short trailing blocks. That's often inconvenient so you can even do something like take some static initial data (I am trying not to call it an IV), and encrypt that iteratively with an incrementing tweak, XORING the result onto your plaintext. Now you have all the convenience of counter mode, and can be pretty careless in picking your nonce and counter.

It's also pretty easy to extend this basic ida (a tweak is a generalized IV/nonce) and re-think any mode you care to in the tweakable world.

Now, an obvious (to me) disadvantage of Threefish per se is that it not only has a wide block, but a wide key. Some people might consider this an advantage, and really, I'm happy to lose this argument. It's my cipher, after all. But from an engineering standpoint, it can be inconvenient to have to transport a wide key around. The wider your block is, the more inconvenient that will be. On the other hand, there's an easy solution to this inconvenience -- a KDF. Heck, run your short key through Skein, and then feed that to your Threefish operation and poof, Alice is your auntie.

The other obvious disadvantage (to me) of Threefish is that the tweak is only 128 bits wide. If the tweak were full-width, then it would be trivial to do what I handwaved above -- produce obvious tweak-based chaining modes that were trivially as secure as the underlying tweakable cipher. You could always hold your nose and just truncate to 128 bits and show 128-ish bits of security, but that's really unappealing at the least.

However, we could also just re-think chaining modes, as well. I am at present very fond of McOE mode, which is an authenticated mode. It was developed by a team at University of Weimar that includes my Skein/Threefish co-author, Stefan Lucks. The obvious search should find their paper. They designed it to work either with an AES-like cipher or a Threefish-like cipher, and has as a feature that it is itself misuse-resistant, providing security levels even in the event of nonce re-use etc.

I have some sample code that isn't optimized, and on my laptop (an i7 Haswell), here are some performance numbers in clocks per byte:

Bytes (    64):    15.58    15.91  //: 64-bit, GCC_v4.21
Bytes (   128):     8.22    10.64  //: 64-bit, GCC_v4.21
Bytes (   256):     7.06     9.66  //: 64-bit, GCC_v4.21
Bytes (   512):     4.94     5.09  //: 64-bit, GCC_v4.21
Bytes (  1024):     4.50     4.55  //: 64-bit, GCC_v4.21
Bytes (  2048):     4.27     4.96  //: 64-bit, GCC_v4.21
Bytes (  4096):     4.15     4.94  //: 64-bit, GCC_v4.21
Bytes (  8192):     4.10     4.74  //: 64-bit, GCC_v4.21
Bytes ( 16384):     4.07     4.85  //: 64-bit, GCC_v4.21
Bytes ( 32768):     4.06     4.81  //: 64-bit, GCC_v4.21

I had to give a low whistle, myself. That's pretty nice, and almost makes me rethink crypto hardware.

	Jon


-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 3.2.0 (Build 1672)
Charset: us-ascii

wj8DBQFSoto0sTedWZOD3gYRAl2aAJ9a+iYjYZbQq5bdF5ZrHqBhW0yHPwCg5HIK
ioqxTCKN3gJ9q6Zaduvv+7U=
=i/tc
-----END PGP SIGNATURE-----


More information about the cryptography mailing list