1
$\begingroup$

I know that implemntations with T-tables such as Golang's are prone to side-channel attacks, but is AES's S-Box wihtout any additional table also insecure ?

$\endgroup$
  • $\begingroup$ Must read: Daniel J. Bernstein's Cache-timing attacks on AES. $\endgroup$ – fgrieu Jun 25 at 9:50
  • 1
    $\begingroup$ @fgrieu: I always thought that paper was a bit of a cheat; it exploited timing attack on AES "over the network", but by having a local agent on the attacked device do the timing measurements and then send the timing data to the remote. When I think "timing attack over the network", I expect the timing to be based on packet timing... $\endgroup$ – poncho Jun 25 at 12:19
  • $\begingroup$ @poncho a software which is not resistant to this is still weak. $\endgroup$ – moutonlapin28 Jun 25 at 12:29
  • 1
    $\begingroup$ @kelalaka: AES-NI is not available everywhere... $\endgroup$ – poncho Jun 25 at 13:19
  • 1
    $\begingroup$ a few times that I've been in this pit: crypto.stackexchange.com/questions/53528/… crypto.stackexchange.com/questions/67091/… $\endgroup$ – b degnan Jun 25 at 16:55
2
$\begingroup$

I assume the question is 'suppose you had an AES implementation that uses a precomputed SBOX table (and no other tables); can we do a key recovery attack using a timing or cache side channel?'

The answer to that question is "yes (at least potentially; we have to make some assumptions on the CPU hardware; at the very least, if it actually does have a cache)"

Here is a simple (and plausible) scenario where it is easy to recover some of the key bits (actually, we can recover them all, however that'd require more explanation)

Assume that we are on a CPU with 16-byte cache lines (that is, the cache stores things in 16 byte chunks; if the CPU reads in a location, the memory controller reads in all 16 bytes of that chunk). We also assume that the sbox happens to be aligned at a 16-byte boundary (and so it occupies 16 cache lines) - actually, it'd be easier to exploit if it were misaligned; however for now, we'll assume aligned.

And, for our cached-based side channel, we can flush the cache, present a plaintext block, ask AES to encrypt it, and then check the cache to see which cache lines of the sbox were read in. I'll cover the timing-based version of the attack below.

Here is how the attack would work: we flush the cache, and present a random plaintext, run it, and see which cache lines the sbox occupied. The AES processing performs 160 sbox references (assuming AES-128); if we model each reference as random, then we have about a 1 in 2000 chance that there is some sbox cache line that is not referenced by any of the 160 reads. Now, if (say) the cache line that corresponded to the 5X entries (that is, the sbox indicies with a high nybble of 5), then we can deduce that it was never refenced in the initial round; that is, for each byte $B_i$ of the plaintext and each key byte $K_i$, we have $B_i \oplus K_i \ne 5X$; that is, we can deduce what the high nibble of each key byte is not.

We can repeat this process until we've eliminated all possibilities for the high nybble of each key byte except for the correct one - this gives us half the key. And, this would take maybe 30,000 or 50,000 probes (depending somewhat on whether we get to pick the plaintexts or have someone else generate random ones). And, it's easy enough to recover the lower nybble as well (say, by relying on the second round sbox references); that would take more explanation.

As for how you would convert this into a timing attack (using the same base assumptions, except that the attacker cannot determine which cache lines are in the cache after the AES operation, but can measure the time), we can perform the same base attack, however before the AES operation, we set the cache so that 15 cache lines within the sbox are in the cache and 1 line is not, and then perform the AES operation. If the 1 line is referenced, the CPU will read that line into the cache (which is an expensive operation; there's a reason CPU manufactures include a cache), and that would measurably increase the time. By measuring the time, we can deduce whether that cache line was referenced, and hence we can proceed with the same attack (albeit with rather more probes required; we're getting data on whether a specific cache line was read, not data on all 16).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Is there a reference to the non-aligned easiness? $\endgroup$ – kelalaka Jun 25 at 15:51
  • 1
    $\begingroup$ @kelalaka: well, if the sbox was misaligned by 8 (and so the entries 0-7 are in there own cache line, as well as entries 248-255), then these two short lines will be not referenced with probability 1/80 (1/160 for each); that means that significantly fewer probes will be needed before one of these short lines will be not referenced (and hence our attack is significantly faster) $\endgroup$ – poncho Jun 25 at 16:00
  • 1
    $\begingroup$ @kelalaka crypto.stackexchange.com/questions/53528/… You'll see double fetches if you are on boundaries in the image there. $\endgroup$ – b degnan Jun 25 at 16:53
  • $\begingroup$ Thank you for the answer, but is an implementation of AES that doesn't uses a precomputed table secure ? I mean by calculating SBox[x] when and each time it is needed. $\endgroup$ – moutonlapin28 Jun 26 at 1:23
  • $\begingroup$ If you compute the sbox each time, then it depends on how you compute it. You can compute it in constant time, however it isn't especially cheap... $\endgroup$ – poncho Jun 26 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.