Score:1

Timing attacks: Symmetric vs Asymmetric Algorithms

us flag

There is a statement that I can't give a reference;

"Since the timing characteristics of symmetric algorithms are not as key dependent as asymmetric algorithms, they are more resistant against timing attacks."

Is it true?

kelalaka avatar
in flag
Secrecy in open channel, strange!
NB_1907 avatar
us flag
Not because secrecy, paper is not in English!
Score:5
ng flag

"Since the timing characteristics of symmetric algorithms are not as key dependent as asymmetric algorithms, they are more resistant against timing attacks."

This is largely but not absolutely true.

Data-dependent (including key-dependent) timing characteristics come essentially from

  1. Conditional execution, as occur in if this bit of the secret exponent/multiplier is set, then… common in RSA and ECC. There is rarely such thing in symmetric algorithms, and when there is the potential of having such conditional execution (e.g. in AES, XOR with a fixed polynomial when a bit shifted out is set), there are easy alternatives without.
  2. Multiplication, which on many CPUs takes time dependent on the argument. There is rarely such thing in symmetric algorithms (exception: IDEA), but that's central to RSA and ECC (except on binary curves).
  3. Division (seldom used in symmetric crypto, and at the instruction level in asymmetric crypto too, because it's slow, especially when there is no hardware support).
  4. Data-dependent rotation; that's rare (exception: RC5, RC6).
  5. Table lookups (e.g. substitution tables), due to cache effects. This is common in some symmetric algorithms including DES and AES, and the most important exception to the quote. However there is no table lookup in many other algorithms, including hashes (e.g. SHA-256) and the Chacha stream cipher. And cache-dependent timing dependencies are small and thus rather hard to exploit remotely (that's another matter when adversaries have a foot in the CPU: they can make timing measurements with better accuracy, and can flush the cache; they can also probe the cache, but then that's no longer a pure timing attack).

Note: the quote suggests that only key-dependent timing variations matter. This is not entirely true: any timing dependency on non-public data could in theory be a potential attack vector, in that it can leak information on the data.

b degnan avatar
ca flag
I think you really nailed it. Some trivia, that you likely know. Division is always multi-cycle as well unless you have special cases. When we do fixed-time division for Y/X, I have a hardware unit that does 1/X, which takes 4 cycles, and then the result of 1/X * Y that also takes 4 cycles. It's basically not worth doing as it so much silicon is used, unless you know you'll be doing this operation often. For this reason, I suspect that we'll never see a division in a cipher in practice.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.