Re: Optimized S-Boxes in Software

• From: Tom St Denis <tom@xxxxxxx>
• Date: Wed, 29 Jul 2009 04:16:00 -0700 (PDT)

On Jul 28, 9:28 pm, MTGAP <mtga...@xxxxxxxxx> wrote:
Common s-box sizes are 4 bits and 8 bits. These sizes are easy to
produce. However, how do they work on today's 32-bit or 64-bit
processors? It seems that utilizing these s-boxes would be highly
inefficient. For example, if the block size is 128 bits, it has to be
broken up into 16 different chunks to be put through an 8-bit s-box.
Is there any efficient way to do this? This is the best way I can
think of, and it's rather inefficient: (C pseudo-code)

uint128_t block = (some number);
uint8_t smallerParts[16];
uint8_t sbox[256];
// initialize s-box

int i;
for (i = 0; i < 16; i++) {
smallerParts[i] = (block >> i*8) & 255; // &255 is a more
efficient way to do mod 256
smallerParts[i] = sbox[smallerParts[i]];

}

And then it has to be changed back into a 128-bit block, resulting in
more inefficiency. Is there any way to get around this? If not, why do
some modern algorithms (AES, Serpent) use s-boxes instead of some
other sort of nonlinear function?

I'd recommend you see how things like AES are actually implemented.
It's not like optimized reference code is impossible to come by.

The short answer is: You don't convert it to/fro during the ciphering
only at the edges.

Tom
.

Relevant Pages

• Re: Optimized S-Boxes in Software
... It seems that utilizing these s-boxes would be highly ... and it's rather inefficient: ... For this reason, there're many designs avoiding sboxes alltogether, ... just computes it's non-linear functions on the fly. ...
(sci.crypt)
• Re: Optimized S-Boxes in Software
... It seems that utilizing these s-boxes would be highly ... and it's rather inefficient: ... sliced implementations of AES avoiding it at some cost (just ... For this reason, there're many designs avoiding sboxes alltogether, ...
(sci.crypt)