2
$\begingroup$

Suppose there is an array containing bytes 0...255. Suppose this array is shuffled using a key for random data.

Since this is indexing the elements of a table using secret data, is it vulnerable to timing attack?

If so, Suppose the array is shuffled again. Since the state at the beginning of the second shuffle is a secret, random permutation of bytes 0...255, is this second shuffle vulnerable to timing attack as well?

Basically, is the core of the problem accessing an index of an array based on secret data? Is knowing the contents of the array/table in question a prerequisite for this type of attack? Or is there something else to this altogether?

Background

More specifically, I am curious about the vulnerability of following construction to timing attack:

shuffle(Z256, key) # this randomizes key too output = Z256[Z256[index]] for index 0...255 repeat

The problems that I see are the indexing based on secret data, both during the shuffle and output stage. However, since the set is shuffled every time, the key randomized, and the set iterated through completely, I think it should be resistant? My reasoning is that since the set is iterated through completely, the sum of the time spent accessing it should be more or less the same regardless of the order the accesses happen in. But I'm not sure exactly what causes the vulnerability to begin with.

$\endgroup$
  • 1
    $\begingroup$ Any secret data dependent table lookup has a very good chance to end in (at least) a cache timing side channel attack. But I'm not experienced in this particluar area, so I won't write a full answer. $\endgroup$ – SEJPM Apr 22 '16 at 15:01
  • 2
    $\begingroup$ One possible concern (which doesn't have anything to do with your question) is that a random permutation iterated twice is not a random permutation; for one, any point has double the expected probability of being a fixed point. It's easiest to see when considering the cycle structure; any odd-length cycle remains an odd-length cycle; any even-length cycle divides into 2 (so a length-8 cycle in the original becomes 2 length-4 cycles). Whether this is a concern depends on what you're using the permutation for... $\endgroup$ – poncho Apr 23 '16 at 19:23
  • $\begingroup$ @poncho Thank you for your insight. I always appreciate it! So far the only thing this is "used for" (in a research sense only, I promise) is a prng. The details can be found here. If I leave a message in the side channel, would you have time to explain? I'd like to ask more but I'm not supposed too here. $\endgroup$ – Ella Rose Apr 23 '16 at 23:38
  • 1
    $\begingroup$ I think the answer depends a lot on how you do your shuffling. However, the RC4 algorithm — which shuffles an array of 256 bytes based on a secret key — has been shown to be vulnerable to timing attacks: (di.ens.fr/~fouque/pub/acns11.pdf). $\endgroup$ – squeamish ossifrage Nov 24 '16 at 10:35
2
$\begingroup$

Being vulnerable to specific timing attack isn't property of construction, but of it's implementation. It isn't hard to imagine a microprocesor that always takes X time to access a byte of memory. Such implementation likely won't be vulnerable to timing attack (but probably will to variety of other, like power analysis). But also some high-level languages can reorganize your data in way which will make analysis far easier, even when you shuffle.

So from now on let's assume modern PC class CPU and a compiler that compiles to native code (assembly). In such case, compilers will very likely make data appear in memory how we see it in table (for optimization purposes).

Modern CPUs cache access to ram on more than one level. Usually cache line has 64bytes. Since all of your data likely won't fit into single cache line, it will likely take different amount of time to access depending where that data is. So it will leak some data about index. It doesn't change anything if you do a double-dereference - it will still leak information about index.

But it doesn't automatically mean that it has to be vulnerable. Some RSA libraries (like OpenSSL) won't have this trouble, because they interleave their data, so that each piece of secret lies on next cache line. This way CPU will always access same cache lines, without timing dependency on index. This of course will also result in performance decrease and isn't likely to be done by compiler.

So having that out of the way, assuming normal memory organization (for speed, not for resistance), your scheme probably is still vulnerable, but shuffling will likely prevent most attacks. Your key will leak because of shuffling, and with enough patience it will be possible to retrieve key and then learn index. Such attack is unlikely to happen, but the cost of shuffling data is very big. So best idea is to follow established protocol for such problems (RSA is well known for having this problem so I suggest looking in that direction).

$\endgroup$
0
$\begingroup$

If you're worried about the key being revealed, you could use a hash of the key to initialise the random number generator. Then even if there is a timing attack, you only reveal the hash.

$\endgroup$
  • 1
    $\begingroup$ The only problem with this idea is that hash becomes the effective key - an adversary then only needs to recover the hash to encrypt/decrypt messages. So while you are correct that it would protect the literal string of bits that is the unhashed key from becoming known by the adversary via timing attack, it does not actually solve the problem of maintaining confidentiality against unauthorized entities who can perform timing attacks. $\endgroup$ – Ella Rose Nov 24 '16 at 17:18

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.