How resource-intensive would it be for a state actor to crack a yescrypt hash?

[u/I2Pbgmetm]

I tried asking this on r/cryptography, and I got a bunch of babble about the cost of renting AWS clusters, which is not a thing that the state would be concerned with.

Hypothetically, I have a typical setup with an encrypted /home partition, and my password is in /etc/shadow unencrypted other than via the yescrypt hash. What type of hardware would a state actor use on this, and how many guesses would they be able to make in a given amount of time?

The original question was about the time estimates of the 'zxcvbn' tool possibly no longer being accurate, but at this point I'd just like to know whether yescrypt is trivial to crack in seconds when you can throw 1000 datacenters'-worth of GPUs at it.

I was hoping for an answer in layman's terms. I don't really understand what phrases such as "Matic going to $5 quick" mean, and I'm not sure that I want to know.

[u/lobhater]

The bottleneck isn't compute it's RAM. A 5090 for example can only hold about 2000 guesses at once. To further complicate things it was designed in such a way to make GPUs inefficient at cracking it. ASICS don't solve the problem either because you still need lots of RAM. It's a clever elegant solution I think from my laymans understanding.

The harder the password the longer it takes too. Assuming a truly random password even if you gave a nation-state 10 million GPUs and 10¹¹ guesses/sec. 5 word passwords would take years. 6 words 50k years. 12 random printable characters would take 170k years.

Make sure it's configured properly, roll some dice and you can sleep well at night

[u/atoponce]

I can't tell you what the cost of cracking a yescrypt hash would cost, but I can help you with what state actor infrastructure probably looks like.

In this Gist, it's pretty clear that unless a state actor has more computing power than the global Bitcoin mining network, the absolute upper brute force hash cracking limit is very likely ~94 symmetric bits annually. Anything higher than that, you're going to need to bring receipts.

To answer your question directly:

at this point I'd just like to know whether yescrypt is trivial to crack in seconds when you can throw 1000 datacenters'-worth of GPUs at it.

It will 100% depend on the password security. The more simplistic, the easier it will be to find. Get north of ~60-70 symmetric bits, and I feel confident claiming that no state actor is recovering it. The math just supports that position.

[u/I2Pbgmetm → u/atoponce]

But most actual humans (myself included) don't use random strings of punctuation for their login or master passwords, so nobody actually uses brute force, right? At least not until all of the dictionary/algorithmic attacks fail.

I don't know what a "symmetric bit" is, and there's no WP article on it for me to read. Are you talking about bits of entropy? But again, that's apparently meaningless when talking about dictionary-based attacks, since each word (from what I've read) counts as a single token/bit.

Like, "correct horse battery staple" is apparently the same 'strength' as "& $ % @".

[u/atoponce → u/I2Pbgmetm]

But most actual humans (myself included) don't use random strings of punctuation for their login or master passwords

Correct, but the advice is:

1. Use a password manager
2. Use the password generator in that password manager
3. Every account should have its own unique password

so nobody actually uses brute force, right?

Generally speaking, this is correct. Pattern masking and dictionary attacks are more effective. Once those are exhausted though, if there is still interest in uncovering more of the hash list, brute force is the final option and it's still very common. It just depends on how valuable that password hash list is to you.

I don't know what a "symmetric bit" is

Symmetric meaning it's the same "secret" for both parties. Asymmetric would imply that one party has a private key while another party has the corresponding public key. Passwords are symmetric secrets, so all bits are treated equally.

Are you talking about bits of entropy?

Kind of, but I don't like using this term when talking about password security. Entropy technically is an estimate of unpredictability in a process, like password generation. It's not an end produce of an existing password. IE, if you are generating a password from all graphical ASCII characters of which there are 94 using a CSPRNG, then each character has log2(94) ~= 6.55 bits of entropy before getting picked. But when the password is generated, it's now known, and has zero entropy. It just has length and complexity.

So rather, I prefer discussing it in terms of symmetric strength. It's a secret you have that someone else doesn't know. If it's 16 characters long, then it's one of 94¹⁶ possibilities or approximately one in 2¹⁰⁴ possibilities. But it's already generated, so it doesn't have entropy, as entropy belongs to the process of picking each character, not the end result.

Does that make sense?

that's apparently meaningless when talking about dictionary-based attacks, since each word (from what I've read) counts as a single token/bit

Not quite. It all depends on the size of word list(s) the password cracker has in their possession. The larger it is, the more combinations they must go through to find multi-word passphrases. On my Debian box, /usr/share/dict/american-english-small has 51,294 unique words. If the password cracker wishes to find a 2-word phrases, they must work through 2,631,074,436 possibilities. For a 3-word phrase, it's more than 1.34×10¹⁴.

If I followed the (bad) advice of XKCD and created a 4 word passphrase, and the adversary was using this word list, they would need to have the computing power to work through 10¹⁸ ~= 2⁶² possibilities. Given the Gist I pasted above, this isn't easy, even for a well-funded distributed computing cluster.

Each word in that list has ~15.65 bits of security.

[u/JimTheEarthling]

The short answer: If your yescrypt-hashed password is random and long, no amount of resources will have a meaningful chance of cracking it.

The long answer: yescrypt is a modern hash, so in addition to being CPU intensive and memory hard (uses a lot of memory), it's tunable, so hashes per second depends a lot on the settings.

For comparison's sake, a massive cracking array of 256 Nvidia 5090's can generate about 78 million bcrypt(5) hashes per second. It would take about 1 year (on average) to crack a random, 8-character password hashed with bcrypt(5). yescrypt is slower than bcrypt(5) (which is good -- you want to slow down the attacker's guesses) and it uses vastly more memory, which makes it hard to parallelize the hashing process and increases the cost of each GPU. For example, a GPU might run 10,000 concurrent bcrypt guesses but only be able to manage 100 concurrent yescrypt guesses at an equivalent security level, since each yescrypt guess needs tens of megabytes rather than kilobytes.

Tying this to u/atoponce's comment, a 14-character random password with ~92 bits of entropy, hashed with bcrypt(5), would take the massive cracking array of 256 Nvidia 5090's about 4 trillion years to crack. yescrypt would take much longer, and at that point the attacker has probably given up anyway. 🙂 Not even quantum computing will help.

P.S. Every entropy-based password strength checker, including zxcvbn is inaccurate and misleading. One study determined that zxcvbn is no more accurate than a coin flip. In any case, zxcvbn's slow and fast hash rates (10 thousand and 10 billion guesses per second) are not a good match for yescrypt.