is accessing elements of an array in secret order vulnerable to timing attack?

Question

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.

Answer 1

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).

Answer 2

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.