[Cryptography] Gates are cheap. Should cipher design change?

[Ray Dillinger]

On 03/30/2016 02:30 AM, ianG wrote:

> But we could work with powers of 2.  There has been a recent shift
> towards hiding length, as that can be used to figure out what part
> of the protocol is being used.

How about "any multiple N of 64 bits, for N >= 7" ?

There's a "twist" construction Bill Cox invented in the context of doing
fast hashes on large documents without enabling block-based collision
attacks.

I've been intending to nail down an algorithm for generating the twist
sequences and verify that it can be applied to any multiple >7 of the
subblock size, because it's also applicable to round-based ciphers
including Feistel ciphers.

It is based on a fixed-blocksize hash function.  It slices the plaintext
into subblocks the size of the hash's primitive block, then does chained
partial hashes in a "twist" sequence on the blocks using a single
iteration of the hash's round function on each block. The total
iterations of the hash's primitive round function is min(2N, N+M) where
N is the length of the block measured in subblocks, and M is the number
of rounds in the underlying hash.

So far I've proven that it achieves complete diffusion across blocks
whose size is a multiple of a "primitive" block size, and shown that
particular constructions of it are *at least* as strong in terms of
confusion as a corresponding round-based hash that's applied to it. I
haven't yet shown that it can be applied to *every* multiple of the
subblock size, but it can be applied to the ones I've tried that are
seven or greater.

What I haven't done yet is fully formalize an algorithm for generating
"twist" sequences and prove that twist sequences can be generated for
any number of subblocks >7. I have an algorithm for generating twist
sequences which is easy to do by hand (build a graph with certain
properties and find an Eulerian path) but not immediately obvious how to
code. I also have an easy-to-code test/definition for whether something
is a correct twist sequence.

On 03/30/2016 02:30 AM, ianG wrote:
> On 29/03/2016 07:29 am, dj at deadhat.com wrote:

>> NIST/NSA public consumption ciphers seem to deliberately avoid
>> large block sizes. The absence of 256 bit block sizes from AES and
>> Simon/Speck is clearly deliberate. We want all the powers of 2
>> block sizes up to at least the size of the largest jumbo packets
>> and the largest unit of disk block storage.
> 
> From software complexity pov, I'd actually say we want arbitrary
> sized, not even "powers of 2".

I think the short block sizes are deliberate for two main reasons:

The first is purely technical; They want to build vector-processing
chips that do one block per clock cycle, and that means strict lower
limits on the pin count required per chip for I/O.  Bigger block sizes
require disproportionately larger chip dies in order to have the I/O
pins needed for vector processing, but still can't have more blocks "in
flight" through the processor at a time than the number of gates in the
maximum-length gate path required to do encryption/decryption.  The
number of nanoacres used goes up linearly with pin count, whereas the
number of nanoacres paid for goes up with the square of die size.  You
also wind up with less data throughput per board because you can only
fit sqrt-n times as many chips on the same size board, and get n-times
as much data throughput per chip.  So all told they'd  rather use
smaller, cheaper chips with a "more reasonable" ratio of size and gates
to I/O pins, for reasons of cost and bandwidth per board. And that means
smaller block sizes.

The second is security-related, and is the main reason why we want
bigger cipher blocks; There are a whole lot of attacks that allow
information to be extracted from ciphers, or ciphertext/plaintext to be
manipulated, based on knowing (or guessing) where the block boundaries
are. Smaller blocks give more opportunities to find such attacks.

			Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160330/ac927270/attachment.sig>