Use constant-time string comparison algorithm. #43
Conversation
This borrows the string comparison code from Devise to prevent timing attacks (http://codahale.com/a-lesson-in-timing-attacks/).
|
Is this actually necessary? Supposedly the generated values can't be predicted, so how could an attacker learn anything based on the time of this comparison? I'm not a security expert, so hopefully @emboss can comment here. :-D |
|
bcrypt's preimage resistance makes timing attacks a non-issue here. |
|
Good to know. Thanks. |
|
@tenderlove You're right. Actually, I discussed this very issue a couple of months ago. If the hash function were ideal, timing the comparison here would not reveal anything useful to the attacker. All timing could do here is finding out how many "correct bits" we have in arbitrarily chosen passwords. In theory, there's no efficient way that would get you efficiently from "password a with n correct bits" to "password b with n+1 correct bits" other than by brute force. On the other hand, it wouldn't hurt to be defensive here, either. Since we cannot prove the security of today's hashes with absolute certainty, it might be prudent to prevent leaking information of any kind, so we won't be susceptible to attacks that are not known at this time. But this is just paranoid me :) |
|
@emboss bcrypt being susceptible to easily computable first-preimage attacks would be astonishing. The current state of the art here is a 2012 attack on AES-256-based hashes on 7 of 14 rounds with a work order of ~2**125, and AES's key schedule has nothing in common with Blowfish. While we can't prove bcrypt's security with "absolute certainty" (leaving aside the lack of real-world impact of security proofs), we also can't do the same for the discrete logarithm problem being NP. |
|
@codahale I agree that the ability to get easily from n correct bits to n+1 bits would give an efficient algorithm for computing preimages, which would contradict preimage resistance. Still, near collisions showed to be a problem for SHA-0. I'm not aware of similar results for today's algorithms and I don't argue with the fact that it would be highly unlikely at this time. But then again, it is always conjectured that a certain characteristic cannot be exploited in a given context until finally somebody does so :) My point was just that the most defensive approach is to try not to leak any information at all if the cost for doing so is acceptable, even if it seems unnecessary at the moment. Please don't get this the wrong way, I myself was advertising that constant time comparison in this context is unnecessary. It's just that today I'm more on the side of "why risk it if I can easily avoid it" again. |
|
@emboss Sure, but it's like having your last line of defense be a litter of kittens: hopefully the army storming the castle will stop to pet them? An SQL injection attack, a lost or stolen backup tape — the type of offline attacks that bcrypt is specifically intended to mitigate — would be computationally trivial to exploit. If there is a first-preimage attack on bcrypt, the only responsible thing to do would be to immediately switch to a different hash function and jettison bcrypt-ruby entirely. In that incredibly unlikely event, timing attack resistance wouldn't mean anything. |
|
Assuming that this gem is being used in a web application, being able to perform an offline brute force is a substantial advantage over an online brute force. Here is a scenario:
If the attacker guesses an arbitrary password who'se hash is
8000
computed as A constant time comparison would defeat this attack. |
|
@eggie5 - try running this: |
|
@mastahyeti, you're missing the part where picking an input which hashes (with or without a known salt) to a chosen output is a hard problem. The hardness of this problem is such that cryptographic proof-of-work systems have been built with it as an assumption (c.f., Hashcash, Bitcoin). That's what I meant when I said that a constant-time comparison is not a reasonable response to a viable first-preimage attack on bcrypt. At that point you'd want to be running the fuck away from it. There is no evidence that |
|
I'm not suggesting that there is a feasible attack vector here, but rather that a non-constant-time comparison provides a slight advantage to the adversary. There is no downside to using constant time comparison except for a minuscule performance hit. |
|
@mastahyeti, the only advantage it provides to an attacker is the ability to perform efficient online timing attacks if and only if they have an efficient first-preimage attack on bcrypt. It's like saying holding an umbrella gives you a "slight advantage" over holding nothing over your head when a piano is dropped on you. |
|
To go back to your original point:
Given a cryptographic hash function So for bcrypt you'd be able to crack the first bit by timing about 2 candidate passwords. For the second bit, you'd need to find 4 candidates. For the third bit, 8; for the fourth, 16; etc. etc. etc. and for the 192nd bit you'd need to try around 2191 passwords before being able to unlock that last bit. |
|
@codahale sorry for the slow response. I've been travelling lately. I think that you're missing the point. The lack of a preimage vulnerability doesn't protect bcyrpt from a brute-force or dictionary attack. Fact that it is difficult to find a preimage matching For starters, your numbers, while not inaccurate, are misleading because ruby does byte-wise comparisons of strings instead of bit-wise. Also, you are assuming the worst case for every bit instead of the average case. The average case is that you could find the first byte after 128 online checks. To find byte two, you would need to find on average, 127 two byte prefix combinations matching the first byte (we are subtracting the one we already found). This means (256 ** 1) * 127 offline hash calculations and 127 online checks. After the first few bytes, you will be able to do huge numbers of offline checks for every necessary online check. This is where the advantage lies. Lets assume the password is 7 random characters, alphanumeirc. That gives us 78364164096 permutations, so it would require an average of 39182082048 checks to guess the password. Assuming bcrypt is poorly configured, with the minimum cost of 4, an EC2 micro instance can do ~440 checks/second. This means it would 24879 hours to guess the password offline. With micro currently surging to $0.007/hour, this would cost an adversary about $175 and could be accomplished in a much shorter amount of time by distributing the work across many spot instances. The benefit to the attacker is greatly increased when you start thinking about dictionary attacks instead of exhaustive brute force attacks. I think that this constitues a much greater advantage compared to a plain online brute force attack than your umbrella vs piano metaphor suggests. Also, it reduces the likelihood of the attack being noticed or accounts being locked out. When you consider that there is no downside to doing constant time comparison, I'm not sure why you wouldn't. |
|
I totally agree that timing attacks are valid; I've written about them fairly extensively as well as found vulnerabilities in Java, Rails, and Rack. I understand how those work. But the efficiency of a timing attack on bcrypt like you're describing depends entirely on the efficiency of a first-preimage attack on bcrypt. This is where you're going wrong, @mastahyeti:
I'll walk you through it. In order to find candidate passwords which hash to all possible first bytes, I'll need to try at least 256 candidate passwords. Let's say I do that, and I discover that the first byte of the hash is My next step is to find a set of 256 candidate passwords which hash to If you don't believe me, you can try it yourself: see how long it takes you to find a candidate password (from a dictionary or otherwise) which hashes to anything starting with Timing attacks only work when the software is doing a variable-time comparison between client-provided data 8000 and secret data. If your software accepted a bcrypt hash and compared it to a secret value, for example, you'd be at risk for a timing attack. But for bcrypt, you're comparing the result of a one-way hash of client-provided data to a secret value, and in the absence of an efficient preimage attack on bcrypt that doesn't give you a handhold. As it stands, performing a timing attack on a bcrypt hash would require work on the order of 2192. My umbrella-and-piano metaphor, then, radically understates the case: it's more like holding an umbrella while someone drops around 21 million Milky Way-sized galaxies on you (or just 31 Shapley superclusters). |
|
The goal of the attack I am describing is not to figure out the whole hash, but to reduce the set of possible hashes. If you figure out the first 3 bytes (127 * 3 online attempts, 2**24 offline attempts) and then stop the timing attack, you greatly reduce the number of possible valid hashes by knowing that the hash you are looking for starts with those three bytes. Now, as you are burning through your dictionary or brute forcing offline, if you find a hash matching those first three bytes, you can try that password online. While you still need to exhaust your brute-force attack or burn through your dictionary offline, you don't need to make all of the online requests. Your assessment of the problem is valid if you were trying to use the timing attack to learn the whole hash rather than to simplify the problem of guessing the preimage. |
|
You're conflating what the attacker would know in your online vs. offline cases. In the online attack, the attacker doesn't know the salt; they only know that, given whatever the salt is, the digest of the candidate password matches In order for that knowledge to be useful in an offline dictionary attack, the attacker must have the salt in order to know that the first three bytes of a candidate hash is the same as that on the server. But if they have the salt, it beggars the imagination to assume that the attacker does not then also have the digest itself, making the timing attack pointless. |
|
Scroll up. The attacker knowing the salt is definitely required for this to work. The problem is that people do stupid things like using the same salt every time and committing it publicly to version control or disclosing it some other way. Your API is designed to make this less likely, but I would argue that the cost of constant time comparison is worth protecting the one idiot who uses this library totally wrong. |
|
To summarize, a timing attack might reduce the security of the bcrypt hash by
I am totally OK with that. That idiot is going to get in trouble regardless of what this library does. |
|
It doesn't take any rewriting to call |
|
Ok, I guess I'll just be blunt: no. |
This borrows the string comparison code from Devise to prevent timing attacks (http://codahale.com/a-lesson-in-timing-attacks/).
See #42.