5
$\begingroup$

It seems to me that algorithms like Blowfish and Twofish with key-dependent S-boxes are almost impossible to implement without table lookups, and thus are almost impossible to implement in software without being vulnerable to timing attacks (other than by linear search through a large array, which is much, much slower). Since these algorithms are also ill-suited to hardware implementation (since the S-box must be stored in RAM), this seems to make the algorithms suboptimal for all purposes.

Is this assessment correct? It seems strange to me that I can come to such a strong conclusion. Yet I cannot think of any way to (reasonably) implement key-dependent S-boxes in constant time, so my point seems to still stand.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ @TimMcLean I don't think so. That question asked about AES using only the operations on standard C, although better, non-portable implementations are known, such as bitslicing. This question asks if any techniques -- portable or otherwise -- are known in the case where the S-boxes are key-dependent. $\endgroup$ Commented May 24, 2016 at 3:33

1 Answer 1

Reset to default
7
$\begingroup$

The point in the question makes senses, especially if one restricts to portable software implementations. But:

  1. Small or moderately large constant-time RAM tables are reasonable, efficient, and (thus) common hardware building blocks. They are often used in DPA-protected DES and AES hardware coprocessors. Thus we can't dismiss key-dependent S-tables in hardware.
  2. When knowing and controlling one's CPU well enough, constant-time table lookups are often possible (e.g. if there is no cache for data RAM, as is the case on many embedded CPUs).
  3. There are other conceivable methods to guard against purely timing attacks, including releasing results with a fixed delay counted from start of computation, e.g. with the help of a hardware timer (however there often are other side-channels than pure timing, and that complicates things, a lot).
Improve this answer
$\endgroup$
2
  • $\begingroup$ So tables are safe if they are in dedicated hardware/cache-less environments? I've always wondered about that. Thanks fgrieu! $\endgroup$ Commented May 24, 2016 at 15:27
  • 1
    $\begingroup$ @Ella Rose: tables are safe from pure timing attacks if they are in dedicated hardware/cache-less environments. There might be other side-channel leakage (e.g. Differential Power Analysis). $\endgroup$ Commented May 24, 2016 at 16:35

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.