Is it Ok in practice to rely only on the first 64 bits of a scrypt hash in this scenario?

Question

I’m in a situation where I need to perform authentication against a large set of exactly 8 bytes longs passwords (with however full choice of encoding from the user and even custom encoding support): more exactly 15,000,000,000 passwords corresponding to the same numbers of unsorted hash which should be used on a public custom blockchain (with however no lookup services).
Due to the public nature of the process, the plan is to only keep the first 8 bytes of each scrypt hash without salt (yes salting is not used) in order to reduce storage. So hash sizes would have the same length as passwords.

If a single collision is found against only one of those passwords it’s game over (since there’s no randomnization generation in the process each inputs will always match a specific hash).

Result

The sets of passwords are changed every 2 years so there would be no benefit from finding a collision on no longer valid data.

Additionally, it’s a modified version of scrypt designed to take way more times longer than the original. The results still give the same hashing characteristics than original scrypt but with differents hashs than plain scrypt given the same data. The algorithms itself has been audited by a third party professional as being sound both on paper and rust implementation.
This also gives the benefit of being both initially gpu and asic resistant (an implementation could still be designed but the money required would outweigh the reward/damage obtained in this scenario).

Question

This situation sounds risky, but I think the probability is still low for being secure in practice. Though I recognize I’ve no idea on what would be the lookup time on a such large table built from the valid hash lists.

So from a pure performance standpoint, is it correct to assume no collisions can be found using cpu (including those without any support for simd instructions) only methods on a reasonable timespan in practice?
The reference generic implementation used performs a Hash every 5 seconds on a Skylake cpu (and it was optimized with code coverage but is not simd outside using the 128 bits Builtin type). An attacker would have to cope with such low speed if he/she want to brute force (it’s also possible to create a naïve and far slower implementation).

Answer 1

No, you cannot assume that no collisions can be found if there is a chance of $1 \over 2^{32}$ per try. That's too high a risk for almost any kind of cryptographic scheme, especially if parallel attacks are possible. This is true by definition for scrypt as you can simply try multiple passwords at the same time. That kind of parallelization cannot be avoided even if you modify scrypt.

Answer 2

15,000,000,000 passwords

For a 64-bit hash, the probability that a collision exists is approximately $1 - e^{-(15,000,000,000)^2 / (2^{64} \times 2)} \approx 0.9978$. So whatever the hash algorithm is, it's very likely that there is a collision, the only problem is to find it.

If your algorithm is a cryptographic hash, then the only way to find a collision is to calculate values until you find one. The expected number of attempts is around $\sqrt{2^{64}} = 2^{32}$. To find a collision, you need to store all the hashes calculated so far. For a 64-bit hash, this takes $2^{32} \times 64 \:\mathrm{b} = 32 \:\mathrm{GiB}$, which fits on a small SSD drive: storage won't be a problem. The only limit is how long it'll take.

You've timed your hash calculation at $5 \:\mathrm{s}$. A determined adversary might rent one of the world's largest supercomputers with 202752 cores for one day. They would be able to calculate about 3.5 billion hashes if they achieve the same single-threaded performance as your implementation. That's close to $2^{32}$ which gives a good chance at finding a collision.

You're using a blockchain, which is only useful if your system involves a large number of stakeholders and is so sensitive that you can't trust a central authority. You're planning a long-lived system, since you mention credential renewal after 2 yeas. So such an adversary is definitely in your threat model. Your system is broken.

And that's without even considering the possibility that someone might make a custom FPGA or ASIC, which only gets cheaper over time. There are off-the-shelf ASICs for mining scrypt, which is used in some cryptocurrencies. They may or may not be useful for your modified version, but modifying the design to attack your custom version only adds a moderate one-time cost.

---

But that's not the only problem, or even the biggest one. There are many red flags.

Unsalted hashes for something that's supposed to be a password? As soon as someone uses your system with a password that isn't generated uniformly at random over the whole space, you're toast. And one only needs to break it once: once someone's done the precomputation for an attack, they can store the rainbow table, sell it or publish it.

The password space is “exactly 8 bytes longs passwords” (so $2^{64}$ possible inputs), but actually “15,000,000,000 passwords” (so about $2^{22.8}$)? Which is it? I know you simplified the system description to present it here, but it does seem that you don't have a clear idea of what these “passwords” are. Any non-randomness will increase the probability of a collision.

A “modified version of scrypt”? Where are the peer-reviewed articles that fail to break this modification?

“The algorithms itself has been audited by a third party professional”. If they didn't scream in horror when you said “modified version”, don't trust their advice.

Yet another red flag is the way you've framed your question: “is it correct to assume …”? It sounds to me like you already know your system isn't reliable, but you're trying to get some reassurance that it is. Nope, sorry, it isn't.

A system that's complex enough that you've built a blockchain into it, and you've gone against common wisdom (unsalted hashes, sizes well below the standard minimum), would need a lot of scrutiny before anyone could reasonably assume it to be secure. Publish it, get a few cryptographers in good standing to actively try to break it, have them fail at it for several years, and we'll talk.