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

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. ...
    (Bugtraq)
  • 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 ...
    (sci.crypt)
  • Re: How serious is AES timing flaw?
    ... Can one do it from software running on the same LAN? ... further away more timing uncertainties get added to the timing data that ... precision timing data without a lot of effort if the OS has not been ... certainly have a lot more to worry about than this timing attack. ...
    (sci.crypt)
  • Re: Cheaters
    ... Some groups of posts that should show up as a single thread ... would think the attack had gone unchallenged. ... The timing tells us that. ... And only one other participant remains at this point. ...
    (comp.lang.java.programmer)
  • Re: Molotov cocktail thrown at Chicago North Side temple
    ... of the "No war for Israel" movement within the anti-war movement. ... Some people are questioning the timing of the ... attack given the recent spiraling violence between Israel and Hamas. ...
    (soc.culture.jewish.moderated)