4 ms·

Understanding Have I Been Pwned's Use of SHA-1 and K-Anonymity

39 points by jacooper 4y ago

Genbox 4y ago
I find these issues all too common among programmers. Especially with regards to MD5 and SHA1. They see a headline saying "SHA1 is now fully broken!", but in reality it is a fluff-piece on either Shattered (Google) or Sha-mbles (Leurent, Peyrin), and broken is used for effect more than anything else. While it is quite impressive when someone manages to reduce the attack complexity, by let's say, reducing the cost of a chosen-prefix collision from billions of GPU hours to millions, it does not make the algorithm completely useless from one day to the next. It has to be taken into context.
rougka 4y ago
I don’t think there’s an infinite number of email addresses. The ‘username’ part is limited to 64 chars, while it almost never exceeds 20 (or even less). The number of domains is also a fixed number at any given time, while I suspect that 10 domains contain over 80% of e-mail addresses I didn’t see the email API and it is not obvious to me if this breaks any privacy protection (or what is the threat), but generating a lot of SHA-1 hashes for popular gmail addresses is probably very possible
vlovich123 4y ago
> [sha256 is] also a slower hashing algorithm Unfortunately, in an otherwise good post, the author is likely just repeating a myth. Due to HW acceleration, sha512 is the fastest and both sha256 and sha512 are faster than sha1. Go ahead. Compare sha1sum, sha256sum and sha512sum on a large file. If you don’t have HW acceleration for some reason Blake3 is the fastest and as secure as sha3 (since sha1 doesn’t benefit from HW acceleration, Blake3 would be a better hashing algorithm from this perspective). That being said, it might be true that sha1 is faster on lots of small inputs as most benchmarks focus on the aggregate speed of large files. Still, my prior would be that sha1 would still lose out unless I specifically benchmarked that use case and found it performed differently. This doesn’t take away from the author’s main point that sha1 is still fine and there’s probably a certain amount of inertia with HIBP that makes changing the hash more difficult operationally/not worth it.
- Vecr 4y ago
  You can truncate blake3 down to 128 bits output without massive problems to create a perfect drop-in for sha1, and it's still way, way faster.
  - vlovich123 4y ago
    The problems would likely not be around the hash length but that the hashes need to be recomputed for a very large amount of data AND that they change from what they were previously (ie clients would have to know to look for a different hash)
jimmywetnips 4y ago
For anyone else going wtf are they on about, read this cloudflare post. https://blog.cloudflare.com/validating-leaked-passwords-with-k-anonymity/ https://blog.cloudflare.com/validating-leaked-passwords-with...

39 points by jacooper 4y ago

I find these issues all too common among programmers. Especially with regards to MD5 and SHA1. They see a headline saying "SHA1 is now fully broken!", but in reality it is a fluff-piece on either Shattered (Google) or Sha-mbles (Leurent, Peyrin), and broken is used for effect more than anything else. While it is quite impressive when someone manages to reduce the attack complexity, by let's say, reducing the cost of a chosen-prefix collision from billions of GPU hours to millions, it does not make the algorithm completely useless from one day to the next. It has to be taken into context.

rougka 4y ago

I don’t think there’s an infinite number of email addresses. The ‘username’ part is limited to 64 chars, while it almost never exceeds 20 (or even less). The number of domains is also a fixed number at any given time, while I suspect that 10 domains contain over 80% of e-mail addresses I didn’t see the email API and it is not obvious to me if this breaks any privacy protection (or what is the threat), but generating a lot of SHA-1 hashes for popular gmail addresses is probably very possible

vlovich123 4y ago

> [sha256 is] also a slower hashing algorithm Unfortunately, in an otherwise good post, the author is likely just repeating a myth. Due to HW acceleration, sha512 is the fastest and both sha256 and sha512 are faster than sha1. Go ahead. Compare sha1sum, sha256sum and sha512sum on a large file. If you don’t have HW acceleration for some reason Blake3 is the fastest and as secure as sha3 (since sha1 doesn’t benefit from HW acceleration, Blake3 would be a better hashing algorithm from this perspective). That being said, it might be true that sha1 is faster on lots of small inputs as most benchmarks focus on the aggregate speed of large files. Still, my prior would be that sha1 would still lose out unless I specifically benchmarked that use case and found it performed differently. This doesn’t take away from the author’s main point that sha1 is still fine and there’s probably a certain amount of inertia with HIBP that makes changing the hash more difficult operationally/not worth it.

Vecr 4y ago
You can truncate blake3 down to 128 bits output without massive problems to create a perfect drop-in for sha1, and it's still way, way faster.
- vlovich123 4y ago
  The problems would likely not be around the hash length but that the hashes need to be recomputed for a very large amount of data AND that they change from what they were previously (ie clients would have to know to look for a different hash)

jimmywetnips 4y ago

For anyone else going wtf are they on about, read this cloudflare post. https://blog.cloudflare.com/validating-leaked-passwords-with-k-anonymity/ https://blog.cloudflare.com/validating-leaked-passwords-with...