Timing attacks and usernames (2012)(brendanlong.com)
brendanlong.com
Timing attacks and usernames (2012)
https://www.brendanlong.com/timing-attacks-and-usernames.html
15 コメント
I never understood how these side-channel attacks can possibly succeed. So many other factors can dominate checking a single character in RAM. Seriously? How would that even work!
by performing the same operation repeatedly and taking the average measurement, you can separate the effect on latency caused by the password length vs. all the other things going on with the system.
Why not actually try it? Write a timing attack.
I've done it before, against a server that deliberately had a vulnerability left on it.
A super-naive approach with no statistical rigor managed to produce usable results at a slow-but-practical rate. Improved technique would have made it faster and less noisy.
The big realization you quickly make is that partial accuracy is good enough to in a vast majority of cases. Sure, 100% accuracy is hard. But 50% accuracy is both surprisingly easy and surprisingly powerful.
I've done it before, against a server that deliberately had a vulnerability left on it.
A super-naive approach with no statistical rigor managed to produce usable results at a slow-but-practical rate. Improved technique would have made it faster and less noisy.
The big realization you quickly make is that partial accuracy is good enough to in a vast majority of cases. Sure, 100% accuracy is hard. But 50% accuracy is both surprisingly easy and surprisingly powerful.
How were you able to make the timing attack work? Each letter takes like a nanosecond to test! And the rest of the time is dominated by random noise.
While not exactly the same thing, this Browser based timing [1] attack is a pretty good demonstration.
[1] https://labs.tom.vg/browser-based-timing-attacks/
[1] https://labs.tom.vg/browser-based-timing-attacks/
Not an expert, but from what I understand, many of these attacks rely on being able to make LOTS of attempts (on order of thousands/millions). Any factor which doesn't correlate directly to the username & password inputs should approach a constant as the sample size grows, since it's timing distribution (by definition) isn't affected by changes in the user/password inputs. This is especially true of things like adding a random amount of delay.
That said, I'm curious as to how well that plays out in the real world, particularly over a noisy connection.
---
But if it is feasible, the best method to defeat it is probably rate-limiting. That then gets tricky. You can rate limit on username alone, IP address alone, or a complex derivative of them (e.g. to detect botnets). But all those approaches introduce their own DDOS and scalability issues.
That said, I'm curious as to how well that plays out in the real world, particularly over a noisy connection.
---
But if it is feasible, the best method to defeat it is probably rate-limiting. That then gets tricky. You can rate limit on username alone, IP address alone, or a complex derivative of them (e.g. to detect botnets). But all those approaches introduce their own DDOS and scalability issues.
Remember that many services are running in a cloud computing environment. Attackers can spin up machines right next to those that they are attacking and bypass much of the network related variables.
Timing attacks aren't as simple as often presented. Writers often give a set time for checking each character and ignore all other operations in order to make the issue easy to understand, but most people use this to write off the attack altogether. Surely it can't be that simple.
It isn't trivial to take advantage of timing attacks remotely, but researchers have shown that they are definitely exploitable. [1][2]
[1] https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf [2] https://www.blackhat.com/docs/us-15/materials/us-15-Morgan-W...
Timing attacks aren't as simple as often presented. Writers often give a set time for checking each character and ignore all other operations in order to make the issue easy to understand, but most people use this to write off the attack altogether. Surely it can't be that simple.
It isn't trivial to take advantage of timing attacks remotely, but researchers have shown that they are definitely exploitable. [1][2]
[1] https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf [2] https://www.blackhat.com/docs/us-15/materials/us-15-Morgan-W...
> Attackers can spin up machines right next to those that they are attacking and bypass much of the network related variables.
Can they? Do cloud providers typically short circuit routes within their public address space? At least in AWS, this is not the case unless e.g. vpc peering is used.
On second thought, even if the attacker egresses via their internet gateway, the next hop will be pretty close to their victim.
Can they? Do cloud providers typically short circuit routes within their public address space? At least in AWS, this is not the case unless e.g. vpc peering is used.
On second thought, even if the attacker egresses via their internet gateway, the next hop will be pretty close to their victim.
For passwords, I get it. But seriously, to see if an email or username exists, just try and sign up with it...
"This email address is already in use."
"This email address is already in use."
Typical network jitter is in the range of +/- 10ms over the Internet, optimistically. So the hash computation needs to be well over 10ms to be noticeable, or you need so many observations on each username that something emerges statistically.
Both seem unlikely. Am I missing something?
Both seem unlikely. Am I missing something?
What matters is how the jitter is distributed. If it resolves to a small number of cases (spikes in the p.d.f.), then that means trouble. Also, attackers may work from the same datacenter, meaning that the jitter could be much smaller.
By repeating the query lots of times you can eliminate both the jitter and the sleep.
This was my thought as well, and what I was referring to re: "so many observations on each username" in the parent.
The reason this seems unlikely to me is mainly rate limits and password lockouts. Plus you're adding a multiple on # of requests for each username you want to try. Say your dictionary has 10,000 usernames (very small IMO). That turns into 10,000,000 requests if you need 1,000 observations on each to control for jitter.
Not impossible to find this in the wild, I suppose, but pretty trivial to prevent at any layer.
The reason this seems unlikely to me is mainly rate limits and password lockouts. Plus you're adding a multiple on # of requests for each username you want to try. Say your dictionary has 10,000 usernames (very small IMO). That turns into 10,000,000 requests if you need 1,000 observations on each to control for jitter.
Not impossible to find this in the wild, I suppose, but pretty trivial to prevent at any layer.
perhaps bcrypt with sufficient rounds to deter bruteforcing stolen hashes would take >10ms to compute?
One other concern is that a db hit and miss could take very different amount of times (e.g., L1 hit vs miss that travels to disk).
* Don't waste server time hashing a password if you already know the user doesn't exist.
doesn't seem like too big of a concern, since you're spending the time anyway, it's just increasing server load marginally.
To solve the first problem, how about running two queries in parallel against the db, one for a fixed username and one for the given username? However, depending on the database, now you may run into caching issues with the fixed username, speeding up that query. Querying for a random username at the beginning might also push that row into the cache.
Maybe keep a large, randomized linkedlist of usernames on-disk (initialized on server startup), read out the next link, and use that as parallel username?
For these ideas I believe you would need to enforce a max-password-length and take up that many steps to check equality for all passwords.