Re: Don't use S-boxes!

From: BRG (brg_at_nowhere.org)
Date: 11/13/04


Date: Sat, 13 Nov 2004 21:25:32 +0000

David Wagner wrote:
> BRG wrote:
>
>>But it can also be implemented with quite small
>>tables at about half normal speed and I have not seen any timing
>>anomalies in this implementation.
>
> By "quite small", do you mean an 8-bit to 8-bit table
> (e.g., for inversion in GF(2^8))? Or do you perhaps mean
> the trick by which inversion in GF(2^8) can be expressed as
> a few operations in GF(2^4), which I presume could be expressed
> with 4-bit tables?

I did think about these options but the one I was specifically thinking
of is different as all of these options are very slow in software.

The normal AES implementations use large tables of 4096 bytes each and
can have up to 4 such tables with a total table byte count of up to
16384 bytes (half this for encryption only). This puts a lot of
pressure on the cache in some machines and it is this that the timing
attack is able to exploit.

But AES can be implemented at about half maximum speed with two tables
each of 1024 bytes (or only 1024 bytes for encryption alone). While
this won't completely eliminate timing issues it is not pressing the
cache anywhere near as hard and will therefore be far less likely to be
easily exploitatble.

It was this option that I had in mind. I have run DJB's timing attack on
this code in a P3 - where the attack works for large tables - and was
unable to see any timing effects with his code.

    Brian Gladman