6 ms·

If anything, this approach shows how good a system passwords are. The downfall will be cheap quantum computers; it seems like we have some time until those are

by Hasz 2y ago

If anything, this approach shows how good a system passwords are. The downfall will be cheap quantum computers; it seems like we have some time until those are available. An A100 is about $2/hr, so cracking even a "basic" password hashed with bcrypt is going to cost a cool $24M in GPU alone. Most people concerned about this kind of attack are using a whole lot more chars. Apps should not be using MD5, use pbkdf2 or bcrypt.

Shank 2y ago
> The downfall will be cheap quantum computers; it seems like we have some time until those are available. This is limited to things that can be easily cracked with a quantum algorithm like public key cryptography via shor's algorithm. "Quantum computers won't solve hard problems instantly by just trying all solutions in parallel." -- Scott Aaronson
- NegativeK 2y ago
  It's been a very long time, but: wouldn't Grover's algorithm apply to password hashes, shortening effective bit length by half? That said, "double your password complexity/length" shouldn't be a problem if people are actually using password managers.
  - Shank 2y ago
    I suppose if we look at the world strictly in terms of a "classic" hash, I believe the answer is yes. However, "modern" password hashes are designed to be memory and CPU intensive. Scrypt hashes, for example, are designed to "waste" cycles and memory to bolster security. The size of the underlying password can remain static while the requirements imposed by scrypt can change. Granted, I'm sure many sites are still using bad hash-based algorithms like md5 without salt today. But modern applications are often built with the goal of slowing down even offline attacks with salting, memory consumption, and CPU cycle consumption. The goal isn't just slow, but costly.
- Hasz 2y ago
  Totally fair, I am conflating two pretty different things. For symmetric crypto, there is Grover's algorithm, which we can mitigate by just doubling key size. However, for asymmetric crypto, shor's algorithm is going to wreck it; intelligence agencies are hoovering up traffic right now to crack latter when it's cheaply available. I would point out the field is in its infancy and new attacks/discoveries will be made that will change things dramatically. These attacks also depend on having access to a "sufficiently large" quantum computer, which in my amateur opinion is 10s of years away from public availability. There is a whole field of "post-quantumn" cryptography being discussed now, but they not really standard or ready for prime-time afaik.
sebzim4500 2y ago
Quantum computers only provide a quadratic advantage to breaking hashes, using Grover's algorithm. This quadratic advantage will likely not be sufficient to overcome the enormous overheads of quantum computing for many decades. Especially since the higher the level of parallelism the smaller the benefit you get from Grover's algorithm.

by Hasz 2y ago

Shank 2y ago

> The downfall will be cheap quantum computers; it seems like we have some time until those are available. This is limited to things that can be easily cracked with a quantum algorithm like public key cryptography via shor's algorithm. "Quantum computers won't solve hard problems instantly by just trying all solutions in parallel." -- Scott Aaronson

NegativeK 2y ago
It's been a very long time, but: wouldn't Grover's algorithm apply to password hashes, shortening effective bit length by half? That said, "double your password complexity/length" shouldn't be a problem if people are actually using password managers.
- Shank 2y ago
  I suppose if we look at the world strictly in terms of a "classic" hash, I believe the answer is yes. However, "modern" password hashes are designed to be memory and CPU intensive. Scrypt hashes, for example, are designed to "waste" cycles and memory to bolster security. The size of the underlying password can remain static while the requirements imposed by scrypt can change. Granted, I'm sure many sites are still using bad hash-based algorithms like md5 without salt today. But modern applications are often built with the goal of slowing down even offline attacks with salting, memory consumption, and CPU cycle consumption. The goal isn't just slow, but costly.
Hasz 2y ago
Totally fair, I am conflating two pretty different things. For symmetric crypto, there is Grover's algorithm, which we can mitigate by just doubling key size. However, for asymmetric crypto, shor's algorithm is going to wreck it; intelligence agencies are hoovering up traffic right now to crack latter when it's cheaply available. I would point out the field is in its infancy and new attacks/discoveries will be made that will change things dramatically. These attacks also depend on having access to a "sufficiently large" quantum computer, which in my amateur opinion is 10s of years away from public availability. There is a whole field of "post-quantumn" cryptography being discussed now, but they not really standard or ready for prime-time afaik.

sebzim4500 2y ago

Quantum computers only provide a quadratic advantage to breaking hashes, using Grover's algorithm. This quadratic advantage will likely not be sufficient to overcome the enormous overheads of quantum computing for many decades. Especially since the higher the level of parallelism the smaller the benefit you get from Grover's algorithm.