4 ms·

Why does having a way to measure computation time at the server open up a whole range of attacks? I’m ignorant on the topic.

jacksnipe 6y ago
https://en.m.wikipedia.org/wiki/Timing_attack https://en.m.wikipedia.org/wiki/Timing_attack
CapriciousCptl 6y ago
If the webapp compares hmac digests, for instance, with something like (a == b), the comparison is short-circuited the sooner it hits an unmatched byte (the more left-ward). So, an attacker can go byte by byte left to right. There's a lot of noise over HTTP/1.1, but these attacks are at least theoretically possible over the wire. If you can do it without noise and with 10s of microseconds of resolution, your attack just got much more efficient. And it probably opens the door to timing things more crazy then simple equality.
- eis 6y ago
  If your crypto code doesn't use constant time functions for timing attack sensitive stuff (like digest comparisons) then you have more serious problems already. Relying on HTTP or other noise is not a good idea.
  - bawolff 6y ago
    Well, lots of web apps don't use constant time comparisons when checking $password == $actualPassword. Whether there exists enough timing difference to do something with that is very unclear even in ideal conditions
    - ReactiveJelly 6y ago
      If they're hashing the password, then the actual password should be already hashed in the DB, and even if the hash comparison is not constant-time, the avalanche effect should make it difficult to "safe-crack" the password one character at a time, because each change in the password will change half the hashed bits.
      - ArchOversight 6y ago
        Passwords are a bad example, but think of a simple signed cookie for example. It's signed with a key that is only known to the server, and the cookie is sent as signature + content. The server has to hash the content using the key, and then validate the signature matches the signature the server just created. If you don't use constant time comparison for this you leak information about the valid signature.
  - CapriciousCptl 6y ago
    Right, the question being answered above was "what is a timing attack."
  - zaroth 6y ago
    Generally true, but digest comparisons are a bad example. If you are hashing inputs on the server side, you can not determine a suitable pre-image through a timing attack without cracking the hash function. Timing attacks are a problem when the server is checking a value the attacker can control bit-by-bit. Hashed values do not meet this requirement.
    - Franciscouzo 6y ago
      It still helps though, let's assume they're using MD5 without salt, if the attacker has a rainbow table, this leads to a speed up, since the attacker only has guess bit-by-bit instead of trying every possibility.
      - tialaramex 6y ago
        Right, what you've got is an oracle that will tell you how many prefix bits of MD5(password) were correct. I suspect bytes is more realistic than bits but the same principle. Rainbow tables don't seem like a very applicable technology for this. I think you'd want to pre-process a dictionary of passwords you want to be able to guess (either from known passwords or just obeying some rule) so that you can group and order them by MD5 prefix. Using the oracle lets you narrow down 50% at a time, so if you've got a dictionary of 1 billion passwords, after 30 iterations you've either rejected all the possibilities or found a correct password. NB This makes no difference against a strong random password, since a hypothetical dictionary of such passwords is far too large, it only impacts ordinary human passwords that you could brute force if you had the hash.
      - zaroth 6y ago
        What you’re talking about is more like a hash table not a rainbow table. If you’re looking for a pre-image for the first 8 bytes of MD5 that would be a table with 2^64 rows * at least 8 bytes or at least 144 exabytes of data. Using such a table would allow you to select guesses that matched the first n bits of the stored hash and then use timing to try to guess the right choice for the n+1’th bit... up to the first 64 bits. You would then have limited the number of guesses down to just another 2^64 possibilities. So that’s not really a valid approach. A different approach would be to try to figure out the first ~32 bits of the hash using a much smaller (34GB) table and use that knowledge to screen potential candidate passwords offline. Again, all this works only as long as there isn’t a salt, and the value you are trying to discover is a guessable password and not a randomly generated key.

jacksnipe 6y ago

https://en.m.wikipedia.org/wiki/Timing_attack https://en.m.wikipedia.org/wiki/Timing_attack

CapriciousCptl 6y ago

If the webapp compares hmac digests, for instance, with something like (a == b), the comparison is short-circuited the sooner it hits an unmatched byte (the more left-ward). So, an attacker can go byte by byte left to right. There's a lot of noise over HTTP/1.1, but these attacks are at least theoretically possible over the wire. If you can do it without noise and with 10s of microseconds of resolution, your attack just got much more efficient. And it probably opens the door to timing things more crazy then simple equality.

eis 6y ago
If your crypto code doesn't use constant time functions for timing attack sensitive stuff (like digest comparisons) then you have more serious problems already. Relying on HTTP or other noise is not a good idea.
- bawolff 6y ago
  Well, lots of web apps don't use constant time comparisons when checking $password == $actualPassword. Whether there exists enough timing difference to do something with that is very unclear even in ideal conditions
  - ReactiveJelly 6y ago
    If they're hashing the password, then the actual password should be already hashed in the DB, and even if the hash comparison is not constant-time, the avalanche effect should make it difficult to "safe-crack" the password one character at a time, because each change in the password will change half the hashed bits.
    - ArchOversight 6y ago
      Passwords are a bad example, but think of a simple signed cookie for example. It's signed with a key that is only known to the server, and the cookie is sent as signature + content. The server has to hash the content using the key, and then validate the signature matches the signature the server just created. If you don't use constant time comparison for this you leak information about the valid signature.
- CapriciousCptl 6y ago
  Right, the question being answered above was "what is a timing attack."
- zaroth 6y ago
  Generally true, but digest comparisons are a bad example. If you are hashing inputs on the server side, you can not determine a suitable pre-image through a timing attack without cracking the hash function. Timing attacks are a problem when the server is checking a value the attacker can control bit-by-bit. Hashed values do not meet this requirement.
  - Franciscouzo 6y ago
    It still helps though, let's assume they're using MD5 without salt, if the attacker has a rainbow table, this leads to a speed up, since the attacker only has guess bit-by-bit instead of trying every possibility.
    - tialaramex 6y ago
      Right, what you've got is an oracle that will tell you how many prefix bits of MD5(password) were correct. I suspect bytes is more realistic than bits but the same principle. Rainbow tables don't seem like a very applicable technology for this. I think you'd want to pre-process a dictionary of passwords you want to be able to guess (either from known passwords or just obeying some rule) so that you can group and order them by MD5 prefix. Using the oracle lets you narrow down 50% at a time, so if you've got a dictionary of 1 billion passwords, after 30 iterations you've either rejected all the possibilities or found a correct password. NB This makes no difference against a strong random password, since a hypothetical dictionary of such passwords is far too large, it only impacts ordinary human passwords that you could brute force if you had the hash.
    - zaroth 6y ago
      What you’re talking about is more like a hash table not a rainbow table. If you’re looking for a pre-image for the first 8 bytes of MD5 that would be a table with 2^64 rows * at least 8 bytes or at least 144 exabytes of data. Using such a table would allow you to select guesses that matched the first n bits of the stored hash and then use timing to try to guess the right choice for the n+1’th bit... up to the first 64 bits. You would then have limited the number of guesses down to just another 2^64 possibilities. So that’s not really a valid approach. A different approach would be to try to figure out the first ~32 bits of the hash using a much smaller (34GB) table and use that knowledge to screen potential candidate passwords offline. Again, all this works only as long as there isn’t a salt, and the value you are trying to discover is a guessable password and not a randomly generated key.