Incorporate mathematical definition of an input-distinguishing attack?

[defuse]

I just wrote this to James:

I came up with an idea while reading your paper that would appeal to
USENIX. The idea is that the Flush+Reload side channel might be limited
enough that it's possible to explore the entire space of attacks.

Define a One-Shot Automated Input Distinguishing Attack as a tuple
(ProbeFind, Recover) where:

- ProbeFind is an algorithm which takes as input:
    - The target program (binary).
    - The target input (what would be the "true positive.")
    - A set of non-target inputs ("false positives").
  ProbeFind outputs the F+R wait time c in cycles, and a list of probes.

- Recover is an algorithm that gets the attack tool's output (with
ProbeFind's parameters) and outputs 0 to guess it saw a non-target input
and 1 to guess it saw the target input.

Define the "advantage" as how much more likely the attack is to be right
than if it just made a random guess. This would be really similar to
cryptography where attacks are polynomial-time adversaries which have
non-negligible advantage in some experiment.

With that definition we can talk about the space of all attacks, and
carve it up into subspaces. One is the subspace you explored in your
work, and another is the subspace I explored in my original paper.

Here's why I think this is valuable:

1. If our definition is good enough, it captures all possible attacks
that can be done with Flush+Reload (crypto key leaking attacks imply the
existence of One-Shot Automated Input Distinguishing Attacks).

2. It's a huge mathematical space, but it's not totally unmanageable. It
can be carved up into smaller pieces, which can be tackled one at a
time. If you hold the binary and inputs constant then it's nearly finite
and maybe even completely searchable on a supercomputer.

3. The parts of the space which haven't been explored yet are obvious
candidates for future work, that other researchers can pick up on.

4. To propose a defense, you'll have to say which part of the space it
defends against. You can either prove it's good for all possible
attacks, or you'll see some space which it doesn't defend against.

5. The more we know about the properties of the Flush+Reload
side-channel itself (e.g. restrictions on probe locations, maximum
number of probes, CPU prefetching weirdness) the smaller and more
manageable the mathematical space gets.

6. It sets a precedent of mathematically defining what an "attack" is.
The space of all RCE attacks is so huge that it never made sense to
define what one was, so we just kept our intuitive idea, which lead to
lots of broken defenses. Maybe in the far, far, future we can actually
understand the entire space.

[defuse]

To do this we'd only have to:

1. Rewrite section 3 to add the definitions.
2. Frame the discussion of the automation and training as an instantiation of an automated attack finder. The automated attack finder outputs the probe list and Recover algorithm (which includes the training set).
3. Frame the attacks as instances of specific attacks (as output by an automated attack finder).
4. In future work, talk about the whole space of attacks and how it can be carved up.
5. Rewrite the abstract to say we defined blah blah and then found instances blah blah.

[defuse]

The definition should be determining which of a set of N inputs was given, not "target input vs non-target input" because the latter definition is captured by the former with N=2 where the first is the target input and the second is the worst (most likely to false positive) of all other inputs.

(edit: And the success rate of the which-of-N attacks is more intuitively understandable.)

[defuse]

We also probably want to include the possibility of exercising the program during the attack (e.g. in one crypto attack they sent thousands of carefully-crafted ciphertexts to leak extra information about the key). In our instantiations for this paper, it would be a no-op since we don't do that, but it needs to be part of the definition to include those more-complicated attacks.

[defuse]

How will this take into account the setting of the attack, e.g. cross-VM vs. cross-user?

[defuse]

Instead of a complicated all-encompassing definition, restrict it as much as possible and add notes about what it doesn't capture.

[defuse]

Section 3 conflates what I'm calling a "mathematical definition" here with instantiation details. It both describes the general setting of an attack (probe selection, spying, recovery) and describes how we instantiated those parameters at the same time. It would be cleaner to split it into the definition of what an attack is first, and then say that we prove there exists a working instantiation of that definition.

[defuse]

This will make the results less ad-hoc. The definition is not ad-hoc, it's a general category of attacks. Our instantiation is ad-hoc, but that's fine, because we're claiming the existence of a working instantiation. Future work is to explore the space of possible instantiations.

[defuse]

The attack definition and instantiation details are actually conflated everywhere throughout the paper. One strategy to deal with this without rewriting the whole thing is to make the formal definitions up front and then the conflation comes off as re-explaining the definition inline which isn't so bad.

[defuse]

Defining the "success probability" would reduce the word count a lot. We could say "... In one experiment ... we observed a success probability of ..." Instead of repeating "... of the X the tool guessed Y right, a success rate of ..."

[defuse]

Class-distinguishing attacks can be verified experimentally by showing they work with samples chosen randomly from the entire class. (For TrueCrypt, we can argue that a new empty volume is computationally indistinguishable from a random sample of the input class, since otherwise you'd have found an attack on TrueCrypt).

[defuse]

The definition should be about distinguishing classes of input, since asking which class an input was in is equivalent to asking a question about the input (which has a finite number of possible answers, the set of possible answers known in advance).

[defuse]

This would probably be better to go into a second paper that includes things like #33.