Re: AES Timing Attack Implementation & Karl Malbrain code...

karl malbrain wrote:
BRG wrote:
karl malbrain wrote:
BRG wrote:
rohit wrote:
Dear All,

I was analysing Cache-timing attacks on AES by Daniel J. Bernstein, and
tried running the source posted by Karl Malbrain at following URL:

http://www.geocities.com/malbrain/aestable_c.html
This code implements AES without using large tables. It will be very
slow but will not (typically) be vulnerable to the DJB attack since this
depends on a lot of cache space being used for tables.
The encryption timing results are 130 cycles per byte for a large table
C version, and 229 cycles per byte for the immune small table C
version. I believe the current BRG assembly code runs about 30 cycles
per byte.
Are you including or excluding the cost of setting up the key schedule?
If you are including the key schedule cost, over how many encryption or
decryption blocks is this cost being spread?

The figure is an error I attempted to correct in a subsequent post.
When compiling for maximum optimization I get 40 cycles per byte w/o
key scheduling cost.

On the 32-bit Intel x86 architecture, without including the cost of key
scheduling, my encryption and decryption routines for 128-bit keys run
in 21 cycles per byte for C code and 18 cycles per byte for assembler.

It is also worth remembering that Daniel Bernstein found that modern
(post Pentium) x86 systems allow misaligned accesses to memory with no
appreciable penalty. This allows AES to be implemented using more
compact tables with a much reduced vulnerability to his attack without
any significant speed penalty. In fact it seems highly likely that such
implementations are faster in practice than large table versions because
of the reduced load on the cache.

This is an interesting idea. I'll have to try implementing it.
Thanks.
Have you tried doing anything with this observation yet?

Yes, I provide AES in x86 assembler code for using this technique. My
64-bit assembler code for AES also uses this approach.

I don't do this in my C code because a lot of systems will fail if a
misaligned memory access is attempted.

Brian Gladman
.

Relevant Pages

  • Re: AES Timing Attack Implementation & Karl Malbrain code...
    ... This code implements AES without using large tables. ... slow but will not be vulnerable to the DJB attack since this ... and 229 cycles per byte for the immune small table C ... Are you including or excluding the cost of setting up the key schedule? ...
    (sci.crypt)
  • Re: AES Timing Attack Implementation & Karl Malbrain code...
    ... This code implements AES without using large tables. ... and 229 cycles per byte for the immune small table C ... Are you including or excluding the cost of setting up the key schedule? ... I provide AES in x86 assembler code for using this technique. ...
    (sci.crypt)
  • Re: AES Timing Attack Implementation & Karl Malbrain code...
    ... This code implements AES without using large tables. ... slow but will not be vulnerable to the DJB attack since this ... and 229 cycles per byte for the immune small table C ... Are you including or excluding the cost of setting up the key schedule? ...
    (sci.crypt)
  • Re: Dont use S-boxes!
    ... >>timing attacks. ... resultant cycles per byte timings are not constant for some unknown ... I'm unable to duplicate the published attack, ... how the "simple cache-timing attack on AES" keeps the S-BOX values out ...
    (sci.crypt)
  • Re: Quadruple Algorithms
    ... occurring" (a fatal flaw being found in AES, ... the most likely attack on your entire system, ... Threat one: Your implementation of AES has an undiscovered ... with the output of one cipher feeding ...
    (sci.crypt)