Dramatic Speedup in AES Timing Attacks

Thomas Ptacek | June 27th, 2006 | Filed Under: New Findings

Via sci.crypt, a new paper from Joseph Bonneau at Stanford and Ilya Mironov at Microsoft , which times AES keys with thousands, not hundreds of millions, of samples, by conducting a white-box attack (informed by the structure of the AES implementation) on the last round of AES encryption.

Two interesting vectors for the attack, from the paper:

  • In multiprocessor environments, an unprivileged process on one processor can “snoop” keys from privileged processes on the other processor using timing.

  • Attackers can trigger and time encryption of disk blocks in network storage environments.

From Bernstein’s post:

The bottom line is that S-boxes (arrays with input-dependent indices) create absurdly complex, fragile, vulnerability-prone cryptographic systems. The obvious way out of this mess is to stop using S-boxes.

3 Comments so far

  • Halvar

    June 30th, 2006 6:32 am

    … so let’s stop using S-Boxes and switch to more ADD/XOR/ROL madness for which we have no clear understanding :)

  • Thomas Ptacek

    June 30th, 2006 10:14 am

    You know a lot more about cryptography than I do, but my intuitive sense of it is that side channel attacks are more significant than practically any other cryptanalytic attack, with the possible exception of parallel computation.

    I understand the gist of your point (that the simple structure of DJB’s proposed alternatives bothers you) but I with you’d write more about it so I could learn.

    Meanwhile, I think I have a pretty good handle on the implications of cache timing; and, because caching, and therefore data-dependent timing, is hard to avoid with S-box schemes (which are just lookup tables), I see the argument that DJB is making pretty clearly.

  • Halvar

    July 3rd, 2006 5:20 pm

    I happen to not know enough about crypto myself, but:

    - Cache timing should be avoidable if you have a dummy memory reference to the beginning of the table prior to accessing it
    - Throwing overboard a paradigm that we happen to understand pretty well (S-Boxes, their linear and differential characteristics and how to construct them in order to make modelling them as polynomials annoying) because of an implementation issue that we could fix is “emptying the bath with the child”
    - MD4, MD5 and SHA-1 are glorified variants of an ADD/XOR/ROL scheme, and they have not fared all that well. Modelling addition as operation on GF2-Polys (representing each output bit) gives very nice and clean recursive formulas, and I am unsure wether this could not be exploited. The tests I have done myself end up generating polynomials that in my naive way of storing them end up being equivalent to bruting the relevant bits, but perhabs someone finds a clever way to compactly represent the resulting polynomials. Yes, this is all operating on a hunch, but we really do not understand the algebra generated by add/boolean funcs/rol all that well, and certainly not well enough to put all our eggs in that basket.

    Beers and discussion about this in Vegas ?

    • Leave a reply