Thread: Want to volunteer?

I've been working on this project (see link in signature) which currently supports 4 languages (C++, Java, Python 3, and Javascript). The algorithm is very simple. The Python version for example is only 59 LOC. I'm looking for other people to contribute their own implementations in other languages, however esoteric they may be (ie: Awk, shell, etc).

The only real requirement is that big-integer maths should either support natively by the language or otherwise be available through some simple package management system configuration or some such. In other words, nothing that requires a hand-crafted BigInt (yours or someone else's).

Ideally it should support UTF-8, but if not, no big deal. As long as it handles ASCII consistent with the other implementations. And submissions with some issues are welcome as well. I can probably help to resolve any problems areas, given a fairly complete implementation.

So if you're interested in contributing, just fork the repo, make your changes, and then submit a pull request.

Cheers!

This sounds more like a cryptographic hash primitive rather than specifically a password hashing algorithm. The latter tends to have "slow" and "frustrate parallelisation" as additional goals.

Originally Posted by laserlight

This sounds more like a cryptographic hash primitive rather than specifically a password hashing algorithm. The latter tends to have "slow" and "frustrate parallelisation" as additional goals.

To be fair, this algorithm does no worse than the most common ones in use today.

Consider:

~/test$ time ./SHA-256
Iterations: 1000000

real 0m10.999s
user 0m10.956s
sys 0m0.012s

~/test$ time ./finabel
Iterations: 1000000

real 0m13.090s
user 0m13.055s
sys 0m0.000s

(The one used here isn't even close to the fastest SHA-256 implementations, by the way.)

With respect to parallelization, the results are similar. While the Merkle–Damgård construction used by SHA-256 is not fully parallelizable, certain steps are. Likewise, the finabel algorithm can also be partially parallelized, though not fully. And in fact research suggests that while best-case optimizations in modular arithmetic provide a noticeable speedup, it's hardly earth shattering.

All that said, I am completely open to suggestions for improvements on the algorithm.

No, what I'm saying is that password hashing algorithms want to be slow and make parallelisation difficult. That is, if you're aiming to provide a password hashing algorithm, the competitors will not be the SHA-2 and SHA-3 families of cryptographic hash algorithms, but rather the likes of argon2 and scrypt that make demands on memory usage that would normally be unnecessary for a hash algorithm. Hence, my point is that it looks like Finabel is not a password hashing algorithm per se as it is a more general purpose cryptographic hash algorithm.

I should also point out that the proper selection of the "rounds" security parameter effectively mitigates the issue.

Compare:

~/test$ time ./finabel 1000000 0
Iterations: 1000000
Rounds: 0

real 0m9.744s
user 0m9.744s
sys 0m0.000s

~/test$ time ./finabel 1000000 10
Iterations: 1000000
Rounds: 10

real 2m36.524s
user 2m36.519s
sys 0m0.004s

And remember, the algorithm is not parallelizable between rounds. So passing a rounds parameter of say 1000 will provide more than enough protection against distributed attacks, while executing reasonably fast to compute a hash on the user's machine.

No, what I'm saying is that password hashing algorithms want to be slow and make parallelisation difficult. That is, if you're aiming to provide a password hashing algorithm, the competitors will not be the SHA-2 and SHA-3 families of cryptographic hash algorithms, but rather the likes of argon2 and scrypt that make demands on memory usage that would normally be unnecessary for a hash algorithm. Hence, my point is that it looks like Finabel is not a password hashing algorithm per se as it is a more general purpose cryptographic hash algorithm.

Point taken, and I will definitely do some comparison tests to see how it fares against these as well.

Okay, so here's a comparison of finabel and argon2:

~/test$ time echo -n "password" | ./argon2 somesalt -t 100 -e -m 16 -p 4 -l 24
$argon2i$v=19$m=65536,t=100,p=4$c29tZXNhbHQ$nJq9Hl tLy8NMRkaL0ThMgCOKO/JlWS9t

real 0m1.684s
user 0m6.360s
sys 0m0.083s

~/test$ time ./ftest 1 100000
Iterations: 1
Rounds: 100000

real 0m1.412s
user 0m1.408s
sys 0m0.004s

As you can see, argon2 is about 100 times slower. And the default number of rounds for that algorithm is actually just 2. Which basically amounts to a finabel hash of roughly 1000 rounds (within an order of magnitude at least).

CORRECTION: the default number of rounds for argon2 is 3, not 2.

For what it's worth, I went ahead and changed the default number of rounds to 1000. It's a breaking change, but results roughly the same run time as scrypt and argon2.

Originally Posted by Sir Galahad

I should also point out that the proper selection of the "rounds" security parameter effectively mitigates the issue.

Ah. From what I understand though, this idea of a "rounds" or "cost" or "work factor" parameter goes back to the key stretching idea applied to make using the old cryptographic hashes stronger when applied for password hashing. So while it works, why I mentioned argon2 and scrypt is because they go beyond this to the idea of memory-hard algorithms, i.e., not only do we force attackers to have to say, buy an array of FPGAs to succeed against CPU-hardness due to the configurable number of rounds, but now they have to contend with the configurable memory requirements, and of course pay for all that electricity. Does Finabel have this property too, or can it be adapted for that?

By the way, may I suggest that you link directly to your webpage or Github repository in your original post rather than leaving the link in your signature? One day you might decide to change your signature, upon which the context for this post would be lost.

Originally Posted by laserlight

Ah. From what I understand though, this idea of a "rounds" or "cost" or "work factor" parameter goes back to the key stretching idea applied to make using the old cryptographic hashes stronger when applied for password hashing. So while it works, why I mentioned argon2 and scrypt is because they go beyond this to the idea of memory-hard algorithms, i.e., not only do we force attackers to have to say, buy an array of FPGAs to succeed against CPU-hardness due to the configurable number of rounds, but now they have to contend with the configurable memory requirements, and of course pay for all that electricity. Does Finabel have this property too, or can it be adapted for that?

Thanks for the input, laserlight. I've created a set of "sandbox files" containing a memory-hard version of Finabel.

Example usage:

node sandbox-cli foo bar 5 64 50000
Usage: ~/test/finabel/sandbox-cli [PASSWORD] [SALT] [ROUNDS] [DIGITS] [EXPENSE]
104b8df5a7ec6e35a907d4d49dbf293fc38b4052cfcd9f87ac a1db8cfd4235f0

It was a simple modification actually, just increase the number of concatenations until a certain number of digits is reached (the so-called "expense" parameter). Although I am a little unsure exactly what the default setting should be. The larger the value, the less rounds would be practical, so those too would have to be adjusted accordingly. Any suggestions?

I've also changed the interface somewhat in order to make invocation of the function a little less error prone. So instead of something like

Code:

finabel("foo", "bar", 5, 64, 50000)

it'd be

Code:

finabel({ password: "foo", salt: "bar", rounds: 5, digits: 64, expense: 50000 })

.

Permalink to the repo: here.

Well that doesn't scale very well. Performing calculations on larger and larger operands just has too much effect on execution time. Request a cost of say 10,000,000 and there's no telling just how long you'd have to wait until the function completes.

So the new approach goes something like this:

(1) Append a sequence of hashes to a buffer until we've reached a target level of "expense".
(2) Iterate through the buffer and append a digit at some calculated index of the buffer to the result. (The index is incremented by some value of "skip".)
(3) Repeat for a certain number of iterations (computed based on the number of rounds versus cost).

It still needs a bit of work however. Computing 100 rounds at an expense of 1,000,000 should execute in roughly the same amount of time as 100 rounds at a cost of 10,000,000. Currently, it performs more like 100 @ 1,000,000 == 10 @ 10,000,000. (Although not quite within an error margin of an order of magnitude).

After a few days mulling over this, I think I've finally found an acceptable solution. I've posted the updated (Javascript) implementation to the sandbox.

Essentially, the algorithm works by randomly skipping around a list of all of the preliminary hashes in order to construct the result.

The only question now is what a sensible default might be. 100K? 10MB? I just don't know.

No, it wasn't skipping in large enough steps. Also had an indexing issue there. Fixed.

Okay, so revised once again. This version is a lot more straightforward though. The optimal skip distance is simply the cost divided by the average output length, plus one. It's stochastic enough to prevent any sort of currying of sample points too (in an attempt to bypass the memory quota mechanism, that is).

I might also add that different values of "rounds" and "cost" may result in the same hash for a given set of inputs (password and salt(s)). If "cost" is unspecified/zero then it will, if only incidentally. Point is, their purpose is merely to enforce a certain level of "proof of work", obviously.