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

[dj at deadhat.com]

>>> What would a modern cipher designed for efficient hardware
>>> implementation look like? Is it just DES with more rounds and a bigger
>>> block size? How about mixing up different cipher principles in one
>>> cipher? So start with a Feistel, then an S-box, then...
>>
>> Look at Simon and Speck
>> 	https://eprint.iacr.org/2013/404.pdf
>> <https://eprint.iacr.org/2013/404.pdf>Simon and Speck specifically deal
>> with the question of *expensive* gates:  They are for low-end, cheap
>> devices.  Just the opposite of what the OP brought up.
>
> Suppose we ignore those.  The linked paper indicates that the smallest
> known AES implementations require about 2500 gates.  Suppose you had a
> budget of a million gates and wanted to design a cipher that made full use
> of them.  What would you do?
>
> One interesting issue this highlights is the difference between hardware
> and software implementation:  Given that many gates, you can build a very
> large S-box in hardware.  Software trying to implement such an algorithm
> would have significant problems avoiding various kinds of side-channel
> leaks via memory accesses.
>

The authors of Simon may have had small crypto implementations in mind,
but the underlaying property of these 'lightweight' algorithms (compared
to say AES) is that they are more efficient with their use of gates - they
get more done per gate. It's perfectly possible to throw lots of gates at
Simon and produce a high performance, high security strength cipher
implementation.

The smallest AES implementations are proportionately slower than larger
implementations. The work done per unit are doesn't change much compared
to a native 10 clock, 1 round per clock implementation.

S-boxes dominate the AES area. The optimum sbox implementation (table,
synthesized table, Boyar Peralta, Canwright etc.) varies depending on what
you are optimizing for (clock speed, power, area etc.)  Memory accesses in
an sbox implementation would be not a good idea. They can done in gates
with much better side-channel properties and we have the solutions
available in published papers. Those same algorithms can be implemented in
software with state small enough to remain in registers, particularly the
tower field stuff that have long skinny dependency graphs.

A while back I published my proposed parameters for Simon with a 256 bit
block size on this fine email list. Amongst the various things was a
number of rounds that had the most integer divisors (above the minimum
acceptable number of rounds), for optimum unrolling flexibility. These
things matter a lot when it comes to hardware implementations.

Maybe back to the original point, we want ciphers with huge, and
preferably arbitary size blocks. A guy from Cisco made essentially the
same point in his talk at the NIST lightweight crypto workshop so it's not
just me and the people I work with. 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.

Take a look at the lightweight ciphers which have various block sizes. You
can plot the number of rounds against block size and see that the rounds
per block-bit goes down as the block size increases. These algorithms get
more efficient as the block size increases. There's no good reason not
have larger block sizes.

I found Rogaway's Sometimes Recursive Shuffle, to be an interesting
direction in block size independent ciphers. I don't know where that's
going to go. I have good uses for it though.

Friends don't let friends do crypto in software.