Strings that have more characters in common take longer to compare. This can result in a timing attack. However, in practice strings are often not compared one byte at a time, and time differences are very small. Therefore, timing attacks are not necessarily possible, even when using strcmp or == to compare strings.

Introduction

When an application compares two strings, this can take longer if the strings are more similar. The theory is that the strings are compared character by character. If the first character is different, the application can stop comparing immediately. If the first character is the same, subsequent characters are compared, and this takes longer. When comparing against a secret value, the time the comparison takes may give information on the content of the secret value.

However, this naively assumes that the comparison function compares one byte at a time, and bails out at the first difference. This is not always the case. Even if it is the case, it is not always detectable.

Glibc strcmp

The C implementation of strcmp in glibc first compares bytes until hitting a word boundary, and then compares words. On my system, words are 8 bytes. Comparing 8 bytes at a time is much faster than comparing one byte at a time. Furthermore, it is more secure. To mount a timing attack, the attacker now has to guess all 8 bytes correctly to get a difference in timing.

For modern CPUs, glibc has strcmp variations for AVX2 and EVEX instruction sets, that can compare 32 bytes at a time.

In the below graph, you can see the time it takes strncmp and memcmp to compare two strings. The compared strings are equal for the first x characters, varied over the x-axis. As you can see, strncmp does have variable timing which can be used in a timing attack. However:

  • The time varies in blocks of 8 bytes, so you would have to guess 8 bytes at a time.
  • The time varies by less that a nanosecond, so you would have to detect less of a nanosecond in difference to exploit this.

The graph below also shows memcmp. The difference is that strcmp searches for a null-byte that indicates the end of the string while comparing, while memcmp just compares a number of bytes. With memcmp, comparing more bytes does take more time, but as we see in the graph this is negligable for the 40 bytes I tested. If systems use memcmp instead of strcmp, e.g. because they store the length of the string instead of relying on a terminating null-byte, they are unlikely to be vulnerable to a timing attack.

C#

The string comparison in C# can be smarter than in C, because it can take the current culture into account when comparing Unicode. To do a proper Unicode comparison, it has to do UTF8 parsing and Unicode normalization, which is much more expensive than just comparing bytes.

The “smart” comparison can be disabled by specifying StringComparison.Ordinal as the comparison method. Then, the timing differences disappear.

So, a timing attack is possible, but:

  • Only when doing a culture-sensitive string comparison.
  • The time again varies by less than a nanosecond.

Python

I could show you the timing graph for Python, but it would look like a flat line. Strings that have a longer prefix in common do take longer to compare, but for the 40-byte string I used to test this with, that difference is too small to detect.

Conclusion

Timing attacks on string comparison are sometimes possible. However, it is not as straightforward that any use of strcmp or == is vulnerable. Some implementations compare multiple bytes at a time, making it impossible to guess one byte at a time. The time differences for individual characters are often below one nanosecond, making it virtually impossible to detect remotely.

Read more