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?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ How would you expect strings to be stored in memory? $\endgroup$– yyyyyyyCommented Aug 2, 2015 at 23:37
-
$\begingroup$ 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? $\endgroup$– e-sushiCommented Aug 3, 2015 at 3:11
-
$\begingroup$ @yyyyyyy - I'm not sure but maybe contiguously? Although I gues string concatenation could make that not so easy.. $\endgroup$– Julie ApplegateCommented Aug 3, 2015 at 3:50
-
$\begingroup$ 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. $\endgroup$– tyloCommented Aug 3, 2015 at 9:36
-
1$\begingroup$ 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. $\endgroup$– Steve PeltzCommented Aug 4, 2015 at 17:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
