for (int i=0;i<LEN; i++) {
for (char c=0; c<255;c++) {
if (tainted[i] == c) {
untainted[i] = c;
}
}
}
send(untainted);
If no - protection doesn't work obviously. If yes - almost all variables are tainted (you don't usually read stuff that doesn't influence codepaths or global state in your application).In the promiscuous world of imperative programming there's millions of ways to introduce dependency that can't be automaticaly checked.
For more complex - you can have workers/threads doing while() { sleep(), next_letter; } and other workers killing them after calculated time.
Or you can get different number of pseudorandom numbers from generator with known seed in one loop depending on tainted data, and after the loop untainted data is set depending on the current random number from the same generator. Calling rand() taints the generator.
I thought they would just mark the whole etension as tainted once it reads tainted data. And then any communication with other sites show the warning.
Yes, because the assignment happens inside a conditional that references a tainted variable.
In the promiscuous world of imperative programming there's millions of ways to introduce dependency that can't be automaticaly checked.
That is not true.
workers/threads doing while() { sleep(), next_letter; }
What is that supposed to achieve?
known seed in one loop depending on tainted data
Every variable assigned to within a "loop depending on tainted data" becomes tainted. Calling rand() doesn't taint the generator. Seeding it within a tainted scope does.
Edit: I was wrong (see below), of course rand() also taints the generator.
What if it was
if (!tainted[i]==c) {
continue;
}
untainted[i]=c;
?If your checker is smart enough to catch this - your whole program is tainted by your password once you check it in the login screen.
> What is that supposed to achieve?
Global state is incramented by another worker every second to the next value. My thread kills the other worker after N seconds. global state = N and I haven't touched it.
If you don't want to call kill from if depending on tainted data - sleep in that if, and call kill immediately after it.
> Calling rand() doesn't taint the generator. Seeding it within a tainted scope does.
It does:
set_seed(1337);
for(int i=0; i<tainted[0]; i++) {
rand();
}
int tmp = rand()); // now I know what tainted[i] was
// because I know how many times
// rand() was called, because I know
// the whole sequence because I know
// (untainted) seed.To clarify, tainting "scope" doesn't refer to variable scope but is commonly implemented as a (thread-local) global dict that tracks tainted access in execution order.
In your example the variable 'c' would be tainted from the moment the conditional evaluates until it is either re-assigned (from a non-tainted source) or until the program ends.
If your checker is smart enough to catch this - your whole program is tainted by your password once you check it in the login screen.
Not sure what you mean by "your password" in this context. Which password, from what source?
Calling rand() taints the generator
Pardon, you are of course right. Yes it does.
Timing attack against yourself.
Something along the lines of the following, for instance:
<thread 1>
for (int i = 0; i < LEN; i++) {
for (int j = 0; j < sizeof(char); j++) {
while (flagA) {}
if (tainted[i] && (1 << j) == 0)
sleep(1);
flagA = true;
}
}
<thread 2>
flagA = false;
for (int i = 0; i < LEN; i++) {
for (int j = 0; j < sizeof(char); j++) {
sleep(0.5);
if (flagA)
untainted[i] ||= (1 << j);
while (!flagA) {}
flagA = false;
}
}
(Note that it doesn't need to explicitly call sleep. It can do pretty much anything that takes an ~constant amount of time.)(Note that you can also leak LEN at the start, as to avoid tainting the loop.)
I think tainting can only be made reliable in a single-threaded environment.
Even without shared workers timing attack works - untainted worker can connect to attacker site every second and update value, and be killed by untainted code after the tainted worker finished.
EDIT: or you can do this with no multithreading at all, just getMiliseconds() before and after tainted code, and make the tainted part last secret_number miliseconds.
Or if you blacklist getMiliseconds as tainting - do this on server instead.
callAttackersServer();
{
var tainted_int = getFromOtherServer();
for (var i=0; i<tainted_int; i++) {
sleep(100 ms);
}
}
callAttackersServer();
and the difference in time between calls will be interpreted on the server as the secret number.Within the call-stack we should probably simply consider all I/O that happens after a tainted variable was accessed to be tainted as well.
That and banning trusted extensions from using concurrency mechanisms should sort those out. Correct me if I'm missing something, though!
Also: yes, you are missing something. Namely that you don't need concurrency for this sort of timing attack. Even something as simple as "X does work or doesn't" and "Y measures execution time" leaks timing info.
For another example: X either reflows the page, or doesn't. Y keeps track of the refresh rate of the page. Or does a timing attack to determine if the page was reflowed or not. Or injects JS into the page to ping website Z when a reflow happens. (Note that it can inject this JS before it grabs the sensitive data.)
For another example: Depending on sensitive data, I either allocate a large array or don't. And then detect how much is allocated before a GC happens.
Note that this can be part JS / part "trusted" extension. It can also even take advantage of parts of existing pages.
The more I consider this scheme, the more I think it's an elegant scheme against accidental leaks, but is fundamentally flawed against malicious leaks. Unfortunately, since the entire point of it is to protect against malicious leaks...
So if you read my cookies and then access the DOM (to trigger a reflow or inject JS), then all future accesses to the DOM will be considered tainted.
This doesn't taint "everything", but it should taint exactly what we want to be tainted (all possible paths to our sensitive data).
Yes, the challenge would be to find and treat all covert channels (time, GC, PRNG etc.), but that seems surmountable. The very exotic channels (like your GC example) are best handled by trimming down the general API for trusted extensions.
I.e. most extensions don't need any kind of GC access to begin with. If your extension does then all bets for fine grained taint-checks are off and it must be marked as "fully trusted" by the user before proceeding.
That's actually not the entire point. At least in this paper, we do not claim to address attacks that leverage covert channels. But the attacker model assumption is weaker (i.e., the attacker is assumed to be more powerful) than that originally assumed by the Chrome design (e.g., that only pages are malicious and will try to exploit extensions). And this is important. Particularly because the design that we end up with will be more secure than the current one. So, at worst, the new system addresses the limitations of the existing system under their attacker model. Then, depending on how far you are willing to hack up the browser, underlying OS, or hardware you can also try to address the covert channel leaks.
IFC/tainting mechanism:
The style of IFC we are proposing is not not the tainting style used by more typical language-level systems. In particular, we're proposing a mostly-coarse grained system:
- A single label is associated with a context. A context can be the main extension context or, more likely, a light-weight worker the main extension context created. This single label is conceptually the label on everything in scope. As such, when performing some I/O this label is used by the IFC mechanism to check if the code is allowed to perform the read/write. This coarse-grained approach alleviates the need to keep track of tricky leaks due to control flow: the branch condition has the label of the context so any control flow within the context is safe. If you want to perform a public computation after a secret computation, you need to structure your program into multiple contexts (e.g. create a new worker wherein you intend to perform the secret computation).
- Labels can also be associated with values. A new constructor Labeled is provided for this task. You can think of it as a boxing the value and, by default, only allowing you to inspect the label of the value. You can pass such labeled values around as you see fit (and this is pretty useful in real applications). Importantly, however, when you read the underlying (protected) value the IFC system taints your context---i.e., it raises the context label to let you read the value, but also restricts your code from writing to arbitrary end-points since doing so may leak something about the newly-read value.
An important requirement of this IFC approach is that there be no unlabeled (implicit) shared state between the different contexts. For example, rand() in context A and B must not share an underlying generator. This kind of isolation can be achieved in practice and is an important detail when considering covert channels.
Timing channels:
It turns out that if you do IFC in this coarse-grained fashion you can prevent leaks due to timing covert channels, if you are willing/able to schedule contexts using a "secure scheduler." In [1] we showed how to eliminate timing attacks of the style described in this thread (internal timing channels) that are inherent to the more typical IFC systems. In [2] we extended the system to deal with timing attacks due to the CPU cache by using an instruction-based scheduler (IBS). IBS and other techniques to deal with timing channels are nicely described in [3]. (I'd be happy to expand here, but this is already a long reply.)
[1] http://www.scs.stanford.edu/~deian/pubs/stefan:2012:addressi... [2] http://www.scs.stanford.edu/~deian/pubs/stefan:2013:eliminat... [3] https://ssrg.nicta.com.au/projects/TS/timingchannels.pml
I think you missed the point of the article, which proposes exactly that.
All I/O functions would tag all variables populated by them with the source of the data.
When a tagged ("tainted") variable is used in an I/O function again, we can compare origin/destination and apply firewall-style filtering or prompt the user.