Re: Don't use S-boxes!

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 11/19/04 

Date: Fri, 19 Nov 2004 20:47:05 +0000 (UTC)

>David Wagner wrote:
>> >The specific values of cycles-per-byte for the encryption function
>with
>> >a pre-expanded key increased from 375 to 750 cycles per byte on my
>> >reference implementations.
>>
>> That counts as extremely slow -- so slow as to render this
>> implementation strategy pretty useless, most likely.
>
>They're slightly smaller if you time the function after it is loaded
>into the processor's cpu-cache: 226 and 628 cycles per byte.

Slightly slower than 'extremely slow' is still 'very slow', alas.

>I've tried four different Athlon platforms and two Pentium:
>AMD Athlon 800MHz, AMD Athlon ? MHz, AMD Athlon XP 2000, AMD Athlon
>1GHz, Pentium-S 100MHz, Pentium-M. I get nothing but random numbers
>for the S-Box table lookup version, with or without table lookups for
>the Xtime function calls.

Huh. Well, that renders my hypothesis pretty implausible.
I have no clue, then; sorry.

>There seems to be some difference of opinion as to the difficulty of
>obtaining a constant time AES implementation. You say it's trivial,
>while Professor Bernstein says it's nearly impossible.

It's trivial. See my earlier post; you turn it into a circuit, and
then you use XOR, AND, OR, and NOT instructions.

What seems to be very difficult (perhaps nearly impossible?) is to
achieve a portable constant-time AES implementation that is almost as
fast as the best non-constant-time AES implementation. At least, I don't
know how to do it.

>I would say
>that expecting a single implementation strategy to be sufficient for
>all platforms is idealism. The only real platform where timing attacks
>should be a problem is the stand-alone device, like the DES PC cards
>used for electronic banking, that have 8-bit processors without caches.
>Of course today, one would expect engineers to design using embedded
>processors with cache. On this platform, absolute constant time would
>be necessary, or randomized timing.

That makes sense to me.