3

This question is purely theoretical, I have no intention of ever implementing this scheme in practice. I'm familiar with the shortcomings of sleeping as means of mitigating timing attacks. I'm more interested in this from the attacker's perspective.

Consider the following pseudocode running on the server side:

procedure X:
    clientInput = ReceiveUntrustedInput()
    TimingVulnerableOperation(clientInput, serverSecret)
    Sleep(Hash(clientInput + secretSalt))

Here, the execution time of TimingVulnerableOperation leaks information about the similarity of its inputs (a naive, early terminating password comparison, for example).

Assume Sleep is at least as granular as the operation itself (a busy cpu loop from 1 to N, for example) and the sleep time is within reasonable bounds.

The attacker can call the procedure with arbitrary inputs any number of times, and measure the execution time with perfect granularity. Can the attacker obtain any knowledge about serverSecret or secretSalt?

4
  • 1
    Is the attacker exclusively using collected timing data?
    – belkarx
    Apr 8, 2022 at 21:27
  • I'd say yes, not sure what other information you had in mind Apr 8, 2022 at 21:31
  • Other side channel attacks perhaps. But that doesn't fit with the scope of the question
    – belkarx
    Apr 8, 2022 at 21:47
  • Is clientInput of a fixed or at least bounded size? Does TimingVulnerableOperation() reveal any information about serverSecret based on the contents or properties of clientInput? It also largely depends on exactly how TimingVulnerableOperation() is vulnerable. Can it be made to be a no-op based on clientInput? Can it be made to take the same amount of time regardless of serverSecret depending on the value of clientInput? Etc.
    – forest
    Apr 8, 2022 at 22:25

1 Answer 1

5

Assumptions

  • Knowing how long TimingVulnerableOperation(clientInput, ...) takes is sufficient to reveal everything about the internal state of the function, including the value of serverSecret.

  • A clientInput value can be permuted without changing the time taken by the vulnerable function, or changed in a predictable way that does not rely on knowing serverSecret.

  • The length of clientInput is fixed but has a large number of possible values.

  • Hash() is an ideal random function and thus is not vulnerable to any cryptographic attacks.

  • The values of serverSecret and secretSalt are static, chosen at uniform random, and are sufficiently large that they cannot be brute-forced.

Attacking the server secret

By sending random input, the attacker will cause the sleep function to take a random amount of time. This would allow him to obtain information about the average time taken by the vulnerable function. As the attacker performs more queries, the certainty of the average delay of the sleep goes up, and with it, certainty of the average delay of the vulnerable function (by subtracting the averages).

Note that this is all largely theoretical. In the real world, the number of bits of min-entropy leaked by the vulnerable function would be far lower than that of the server secret, so practical attacks would need to be able to vary the time taken by the function via clientInput to leak additional bits. This would require the attacker be able to construct multiple values that differ but have the same exact effect on TimingVulnerableOperation(). Doing this multiple times with multiple "colliding" inputs would allow the attacker to determine how long the vulnerable operation takes for each input.

Attacking the secret salt

The attacker will not be able to learn anything about secretSalt, despite knowing the value made by Hash(clientInput + secretSalt). A cryptographic hash is secure against a preimage attack.

7
  • Interesting. For example, let's say I (attacker) measure the average sleep duration to be 1 second. If I then make some number of targeted guesses to find the secret, how would I decide which guesses are the closest? Surely I cannot just subtract 1 second from each result. Apr 8, 2022 at 22:51
  • 1
    @PhilipRoman If you subtract one second from each result, you get the average delay taken by your vulnerable function. More queries means a higher accuracy.
    – forest
    Apr 8, 2022 at 22:51
  • On second thought, attacker can send strings, for example like abc123, abc234, abc345, abc456, ... and the average duration would indicate how close "abc" is to being a prefix of the secret. The scheme is thus vulnerable Apr 8, 2022 at 22:52
  • @PhilipRoman I'm making the assumption that knowledge of the time it takes the vulnerable function to complete is, on its own, sufficient to obtain the server secret, since you haven't specified a specific type of timing vulnerability.
    – forest
    Apr 8, 2022 at 22:52
  • 1
    @mentallurg Correct. The previous revision of my answer assumes no ability to impact the vulnerable function (just check how long it takes), but I edited it to explain how it could be done with a more traditional timing attack by adding the assumption that there exist "collisions" in the vulnerable function. Thanks for pointing out the incompatibility with my assumptions and the ones OP posited.
    – forest
    Apr 8, 2022 at 23:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .