4 ms·

If you are going to go through all the effort to do it properly, you might as well use a proper comparison function. If nothing else, it reinforces the knowledg

If you are going to go through all the effort to do it properly, you might as well use a proper comparison function. If nothing else, it reinforces the knowledge that string comparisons can be part of security (which goes overlooked by many).

tptacek 14y ago
The == operator is a proper string comparison function in this setting.
- indygreg2 14y ago
  Assuming all the steps in the article are followed, yes, you are correct. I still think any article talking about verifying credentials is obligated to mention that string comparison could be an attack vector. Like I said, it plants a seed. And, I've seen way too many naive implementations where it is needed (like simple token-based auth systems) to know that this seed needs to be spread a lot more.
  - tptacek 14y ago
    No, not assuming that. It has nothing to do with the specific steps. To see why, try to imagine a scenario where there could be an operator== timing attack on a password hash. It feels sometimes like people hear about the idea of timing attacks and then want to see them everywhere.
    - tveita 14y ago
      > try to imagine a scenario where there could be an operator== timing attack on a password hash Sure, that's simple. You're leaking information about the password hash to the attacker, which they can use to speed up an attack where they have large offline resources but are limited in their online guessing capacity. Let's e.g. assume we have an unsalted hash, but the system limits us to one guess per second. The password is hashed, then compared with ==, taking some variable time we'll assume can be measured. We use an iterated timing attack to discover a prefix of the password hash, then run an offline dictionary or brute force attack using that prefix. Passwords that match the known part of the hash are tried online, potentially revealing more of the hash as we go. > It feels sometimes like people hear about the idea of timing attacks and then want to see them everywhere. When it comes to side channel attacks, "vulnerable" is the default state.
      - pmylund 14y ago
        How does this matter given a proper avalanche effect?
        pmylund 14y ago
        Nm. Got it.
      - tptacek 14y ago
        Does this sound remotely plausible to you? In all of /usr/share/dict/words, there are four (4) 4-byte prefix collisions of SHA1 hashes - 0.0016% of all the entries. That 4-byte prefix is just 1/5th of the total size of the SHA1 hash.
        tveita 14y ago
        Why, yes, it's eminently doable. Even a single byte will let you discard 255 out of 256 attempts, and as you kindly point out, 4 bytes would be enough to uniquely identify almost any word in the standard dictionary. Feel free to peruse some SHA-256 hashes with slightly above six bytes of fixed prefix - several orders of magnitude more difficult to find than a mere 32 bits partial collision: http://blockexplorer.com/ http://blockexplorer.com/ Now you can argue about how likely it is for an attacker to actually bother to find and exploit such a weakness, and how a salt would mitigate the severity and so forth, but the takeaway here is that this attack can be trivially and permanently defeated by using a timing independent comparison function.
        tptacek 14y ago
        The "timing leak" here does not uniquely identify any word in the dictionary; the attacker is on the opposite side of the problem. This attack is implausible.
        tveita 14y ago
        I'll make one more attempt. I don't think I can explain it any clearer than this: http://pastebin.com/MYT9kpgZ http://pastebin.com/MYT9kpgZ Here I model the server as a simple function that takes a password, hashes it, and compares it to a known digest with an '==' substitute. The function returns true or false, but also leaks information about how long the match was, through a simulated timing leak. This lets me identify the dictionary word that was used as a password using just 23 login attempts, instead of the expected 19300 from a brute force attack. In effect, you're giving the attacker the ability to perform an almost offline attack, as if they possessed the password hash, by supplying however much of the hash they need. I don't see how this would not be a security problem, if you acknowledge that testing a HMAC with == is. Again, this is trivially preventable by using a timing independent comparison.
  - dekz 14y ago
    I believe what tptacek is trying to say that an attack on the == operator is not a timing attack but a brute force attack. Sure the function may return quicker but it doesn't reveal any more information and will be a brute force attack of data returned from a hash function. For other readers, the == operator is comparing a password hash, as opposed to a password itself. One of the properties of a secure hash function is that, changes to the input drastically changes the output. Thus this attack is one of brute force and not a timing attack on the == operator.
    - tptacek 14y ago
      Changing operator== to secure_compare or some analog doesn't change this construction's resilience against attacks. This is very much unlike the situation with, for example, an HMAC verification.
pmylund 14y ago
I'm not sure I agree that it would matter, but, either way, using a constant-time equality function might have given readers the impression that my code was safe to use. It isn't. That was never the intention. One of my main points was that it's extremely hard to do properly. My (pseudo-code) examples were intended to explain the concepts of salting and stretching. Perhaps it's unfortunate that they're actually valid Python. People should use proven KDFs for password authentication, not implement their own (including using my SHA-salting/iteration examples.) Edit: removed "in web apps"
- tptacek 14y ago
  Many timing attacks are viable in web applications. But there aren't timing attacks against password hash comparisons, for obvious reasons.
  - pmylund 14y ago
    You're right. That was an unfortunate choice of words.

tptacek 14y ago

The == operator is a proper string comparison function in this setting.

indygreg2 14y ago
Assuming all the steps in the article are followed, yes, you are correct. I still think any article talking about verifying credentials is obligated to mention that string comparison could be an attack vector. Like I said, it plants a seed. And, I've seen way too many naive implementations where it is needed (like simple token-based auth systems) to know that this seed needs to be spread a lot more.
- tptacek 14y ago
  No, not assuming that. It has nothing to do with the specific steps. To see why, try to imagine a scenario where there could be an operator== timing attack on a password hash. It feels sometimes like people hear about the idea of timing attacks and then want to see them everywhere.
  - tveita 14y ago
    > try to imagine a scenario where there could be an operator== timing attack on a password hash Sure, that's simple. You're leaking information about the password hash to the attacker, which they can use to speed up an attack where they have large offline resources but are limited in their online guessing capacity. Let's e.g. assume we have an unsalted hash, but the system limits us to one guess per second. The password is hashed, then compared with ==, taking some variable time we'll assume can be measured. We use an iterated timing attack to discover a prefix of the password hash, then run an offline dictionary or brute force attack using that prefix. Passwords that match the known part of the hash are tried online, potentially revealing more of the hash as we go. > It feels sometimes like people hear about the idea of timing attacks and then want to see them everywhere. When it comes to side channel attacks, "vulnerable" is the default state.
    - pmylund 14y ago
      How does this matter given a proper avalanche effect?
      - pmylund 14y ago
        Nm. Got it.
    - tptacek 14y ago
      Does this sound remotely plausible to you? In all of /usr/share/dict/words, there are four (4) 4-byte prefix collisions of SHA1 hashes - 0.0016% of all the entries. That 4-byte prefix is just 1/5th of the total size of the SHA1 hash.
      - tveita 14y ago
        Why, yes, it's eminently doable. Even a single byte will let you discard 255 out of 256 attempts, and as you kindly point out, 4 bytes would be enough to uniquely identify almost any word in the standard dictionary. Feel free to peruse some SHA-256 hashes with slightly above six bytes of fixed prefix - several orders of magnitude more difficult to find than a mere 32 bits partial collision: http://blockexplorer.com/ http://blockexplorer.com/ Now you can argue about how likely it is for an attacker to actually bother to find and exploit such a weakness, and how a salt would mitigate the severity and so forth, but the takeaway here is that this attack can be trivially and permanently defeated by using a timing independent comparison function.
        tptacek 14y ago
        The "timing leak" here does not uniquely identify any word in the dictionary; the attacker is on the opposite side of the problem. This attack is implausible.
        tveita 14y ago
        I'll make one more attempt. I don't think I can explain it any clearer than this: http://pastebin.com/MYT9kpgZ http://pastebin.com/MYT9kpgZ Here I model the server as a simple function that takes a password, hashes it, and compares it to a known digest with an '==' substitute. The function returns true or false, but also leaks information about how long the match was, through a simulated timing leak. This lets me identify the dictionary word that was used as a password using just 23 login attempts, instead of the expected 19300 from a brute force attack. In effect, you're giving the attacker the ability to perform an almost offline attack, as if they possessed the password hash, by supplying however much of the hash they need. I don't see how this would not be a security problem, if you acknowledge that testing a HMAC with == is. Again, this is trivially preventable by using a timing independent comparison.
- dekz 14y ago
  I believe what tptacek is trying to say that an attack on the == operator is not a timing attack but a brute force attack. Sure the function may return quicker but it doesn't reveal any more information and will be a brute force attack of data returned from a hash function. For other readers, the == operator is comparing a password hash, as opposed to a password itself. One of the properties of a secure hash function is that, changes to the input drastically changes the output. Thus this attack is one of brute force and not a timing attack on the == operator.
  - tptacek 14y ago
    Changing operator== to secure_compare or some analog doesn't change this construction's resilience against attacks. This is very much unlike the situation with, for example, an HMAC verification.

pmylund 14y ago

I'm not sure I agree that it would matter, but, either way, using a constant-time equality function might have given readers the impression that my code was safe to use. It isn't. That was never the intention. One of my main points was that it's extremely hard to do properly. My (pseudo-code) examples were intended to explain the concepts of salting and stretching. Perhaps it's unfortunate that they're actually valid Python. People should use proven KDFs for password authentication, not implement their own (including using my SHA-salting/iteration examples.) Edit: removed "in web apps"

tptacek 14y ago
Many timing attacks are viable in web applications. But there aren't timing attacks against password hash comparisons, for obvious reasons.
- pmylund 14y ago
  You're right. That was an unfortunate choice of words.