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?

PhilipRoman
  • 133
  • 3
  • 1
    Is the attacker **exclusively** using collected timing data? – belkarx Apr 08 '22 at 21:27
  • I'd say yes, not sure what other information you had in mind – PhilipRoman Apr 08 '22 at 21:31
  • Other side channel attacks perhaps. But that doesn't fit with the scope of the question – belkarx Apr 08 '22 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 08 '22 at 22:25

1 Answers1

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.

forest
  • 64,616
  • 20
  • 206
  • 257
  • 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. – PhilipRoman Apr 08 '22 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 08 '22 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 – PhilipRoman Apr 08 '22 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 08 '22 at 22:52
  • Yeah it seems that any type of timing vulnerability that allows putting unused/unaccessed bits into clientInput (which is almost the definition of a timing vulnerability) can eventually be exploited since the unused bits will generate distinct hashes that can be averaged out. – PhilipRoman Apr 08 '22 at 23:00
  • @forest: To your answer: I agree with your statement that *secretSalt* cannot be revealed because of crypto hash. But *serverSecret* **can** be attacked. – mentallurg Apr 08 '22 at 23:55
  • 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 08 '22 at 23:55