String Comparison Timing Attacks | Hacker News Reader

String Comparison Timing Attacks

sjoerdlangkemper.nl

31 pointstodsacerdoti13 comments

The author of this seems to conclude that timing attacks are very difficult, because the effects seem very small. And they are pretty hard. But attackers are also very resourceful, and they have all sorts of tricks to extract signal out of noise. Even the coarsest of timers falls victim to statistics if you sample enough. And there are all sorts of tricks to increase the measured times, too: a clever attack would be to influence the heap so that the string straddles a cache line or page boundary, then force the remaining data out of the cache so you can notice a much larger bump if it gets read.

It was interesting how small the differences in these computations are. Can you do timing attacks like this in the web at all, or do they only work if you already have direct access to the machine without additional variance (like networking) to take into account?

You can, but maybe not in the "standard" way.

Standard way being trying to measure the precise differences between requests. The smaller the difference the more requests are needed to level things out and that just becomes pretty impractical quickly but still possible in some situations.

If you actually wanted to do a timing attack on the web you'd probably want to do something like a "Timeless Timing Attack" [0]. At a high-level the idea is to measure relative timing differences rather than the precise difference. Answering which request completes faster rather than how much faster.

The specific attack from the paper is taking advantage of HTTP/2 multiplexing to send two requests within a single packet, ensuring they arrive at the same time. Then uses the response order to determine which was processed faster/slower. It still requires making multiple requests to smooth out the data just not as much since you're only interested in the relative competition time.

Its not practical everywhere, but its more practical for the web than the traditional technique.

[1] https://www.usenix.org/conference/usenixsecurity20/presentat...

Given the Y scale in ns, no doubt it has to be local

That doesn't necessarily follow. Even if the network latency is 50ms, the variance in network latency can often be less than 1ms, and then even smaller timing differences can be measured through statistical sampling.

I am not sure that the general conclusion is warranted.

See for example the cryptopals exercise https://cryptopals.com/sets/4/challenges/31

Experience has shown that this is even detectable remotely.

When auditing any cryptographic library, this is one of the first things I look for.

There are a many ways how to recover a signal from the noise. This means that the sidechannel from the string comparison looks irrelevant, but given enough samples there is an information in that. And well, somehow getting rid of the noise is the idea behind essentially any side-channel attack.

For context: the GPS signal that your phone fixes to is something like -120dB under the noise floor, there is a way to recover that.

I remember a decade and a half ago, a network protocol which was flat , statistically, on internet traffic metrics (bandwidth expensive as even with 0 traffic encrypted blank noise was isochronously transfered).

It was at the time rumors spread about statistical attacks on tor with man-in-the-middle agents and corrupted nodes.

The rumors said the author of the published thesis was asked nicely by "authorities" to un-publish it...

The author's conclusion to question of "are timing attacks viable?" seems to be... it depends on the nature of the language or library. Are most devs going to understand these nuances though?

In the time it takes to research the timing behavior of your runtime, you could have reached for a constant-time comparison instead.

Similarly, in the time it takes you to reach the conclusion the comparison you're using isn't vulnerable, you could have reached for a secure compare instead.

I'm not convinced this post makes a compelling case against the best practice of always using a secure compare for secret strings.

In fact the bottom line is

> The time differences for individual characters are often below one nanosecond, making it virtually impossible to detect remotely.

What I'm taking away is: scrutinizing the algorithm used for string comparison should be low priority compared to other security-related concerns.

BREACH attack [1] is another interesting study.

I learned about it when someone suggested using compression to address scenarios where Tailwind CSS is duplicated in HTTP responses, and a BREACH attack was suggested as a potential downside to consider.

[1] https://en.m.wikipedia.org/wiki/BREACH

BREACH is, of course, a compression side channel, not a timing side channel.

Maybe this can save you by accident but it feels too fragile to rely on for security. For in-house code you might know every compiler and CPU you will run on now and in the future. For open source, are you comfortable releasing code with silent assumptions that turns into a security hole if someone runs it on an AVR.

Reply on news.ycombinator.com