Re: Don't use S-boxes!

From: BRG (
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

Relevant Pages

  • Re: Cross-Site History Manipulation (XSHM)
    ... vulnerability" and "compromise web applications" caught my eye. ... timing, cache timing, CSS:visited, probing frames.length and other ... The problem of unconstrained Internet -> ... whether a security attack such as XSS or XSRF succeeded. ...
  • Re: Steps back to trust in hardware?
    ... side-channel (including timing) attacks were ... However power analysis via his ground loop attack is feasible. ... Yes - there's control path leakage but there's also data path leakage. ...
  • Re: Steps back to trust in hardware?
    ... an 'internal' agent - with timing subtleties down in the nS level, ... extracts the temperature of servers over the internet using their clock ... timing attack that was internet-exploited. ...
  • Re: AES Timing Attack Implementation & Karl Malbrain code...
    ... |> Does this imply that an algorithm using large tables is susceptible to ... | This type of attack needs to be considered in any situation in which ... most all contemporary machines have extensive caching with AES. ... if an attacker has been able to put a timing ...