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).