4
$\begingroup$

Cryptographic libraries mostly use pre-computed lookup tables to implement block ciphers. These lookup tables require large amout of memory and a series of cache miss/hit makes them vulnerable to cache timing attacks. Are there any other disadvantages of lookup table based implementations?

$\endgroup$
  • 4
    $\begingroup$ Why do we need more disadvantages than that? If the table lookups are still used, shouldn't you be looking for advantages instead? Are large memory requirements really such a big deal for a software implementation? It needs to be a rather large table before it doesn't fit in my 1st level cache anymore to start with. I see a lot of presumptions here, and a rather strange introduction for the question itself. $\endgroup$ – Maarten Bodewes Jul 17 '19 at 13:10
  • 1
    $\begingroup$ You can countermeasure the cache attack very easily. Just access all the keys regardless of usage. $\endgroup$ – kelalaka Jul 17 '19 at 20:42
  • $\begingroup$ @kelalaka, any rough estimate about the overhead of the suggested method? $\endgroup$ – abraza Jul 18 '19 at 13:08
  • 1
    $\begingroup$ AFAIK, OpenSLL uses this method. Maybe you can find some numbers over there. $\endgroup$ – kelalaka Jul 18 '19 at 13:38
  • 1
    $\begingroup$ @khan you could do a bit-sliced implementation, but what a pain. Alternatively, if you are superuser, you could either lock the cache or disable it for an address range in the MMU. moserware.com/2008/09/how-do-locks-lock.html $\endgroup$ – b degnan Jul 18 '19 at 16:27
3
$\begingroup$

The disadvantages are simply the side-channel attacks that you mention. I can think of no other disadvantages from either a cryptographic or hardware angle. I have a description of cache and attacks from a hardware perspective.

The advantages are pretty clear:

  1. simplicity in implementation so that the mathematics is correct;
  2. it's faster than a bit-slice implementation, and
  3. it's smaller than doing the inverse mathematics for the irreducible polynomial.

Also, in non-x86 environments, these attacks are be mitigated through a cache lock where you do not flush the cache so you cannot miss.

|improve this answer|||||
$\endgroup$
  • 2
    $\begingroup$ One possible disadvantage is a higher cache pressure for large lookup tables. $\endgroup$ – forest Jul 18 '19 at 0:58
  • $\begingroup$ @forest good point. I'm not sure the largest lookup table used in a cryptographic algorithm. $\endgroup$ – b degnan Jul 18 '19 at 16:25
  • 1
    $\begingroup$ Many optimized implementations use a lot of lookup tables. AES has quite a few (far more than just a single 8-bit S-box). It can certainly put pressure on the L1d cache. $\endgroup$ – forest Jul 20 '19 at 6:23
0
$\begingroup$

I can think of two disadvntages

|improve this answer|||||
$\endgroup$

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.