Can string lookups be vulnerable to timing attacks like array lookups are?

Per “Can non-assembly crypto libraries truly be secure against timing attacks?”, array lookups are vulnerable to timing attacks. Like, if you do cresult[map[i]] and map is an array and cresult, is a string then map is vulnerable to timing attacks because it's an array but is cresult?

• How would you expect strings to be stored in memory? – yyyyyyy Aug 2 '15 at 23:37
• Since this can strongly depend on the chosen programming language, may I ask if you are simple asking “in general” or if you are refering to some specific programming language? – e-sushi Aug 3 '15 at 3:11
• @yyyyyyy - I'm not sure but maybe contiguously? Although I gues string concatenation could make that not so easy.. – Julie Applegate Aug 3 '15 at 3:50
• If you consider C, then strings actually are arrays, so anything there can just be applied to both. But in general: It depends on the context and the actual usage in the algorithm. As a rule of thumb: If you have a algorithm where no one took explicitly care of sidechannels, it is very likely that there is one. This is especially true for any deterministic part. – tylo Aug 3 '15 at 9:36
• A timing attack and a cache attack are different things. A cache attack is not a concern if you don't have arbitrary processes executing on the same processor. An array reference is typically time invariant. – Steve Peltz Aug 4 '15 at 17:24

1 Answer

Yes, string algorithms can be vulnerable to timing attacks.

A very common example is string comparison. The best performing way to implement it in general is to compare two strings one character (or memory word) at a time and return inequality as soon as they don't match. However, this kind of a routine is vulnerable to timing attacks that can find the (approximate) length of the common prefix. Using such a string comparison routine to compare passwords or hashes has lead to attacks (an early 1970s example, a random 2009 example).

Similarly, when you are using a multibyte encoding, simply looking up a character in a string can allow timing to reveal details about the string before then.