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.

$\endgroup$
  • 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$ – Demi May 24 '16 at 3:33
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).
$\endgroup$
  • $\begingroup$ So tables are safe if they are in dedicated hardware/cache-less environments? I've always wondered about that. Thanks fgrieu! $\endgroup$ – Ella Rose May 24 '16 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$ – fgrieu May 24 '16 at 16:35

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.