Thread: Want to volunteer?

  1. #1
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    199

    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!

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,157
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    199
    Quote Originally Posted by laserlight View Post
    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.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,157
    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.
    Last edited by laserlight; 11-23-2020 at 04:01 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    199
    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.

  6. #6
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    199
    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.

  7. #7
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    199
    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.
    Last edited by Sir Galahad; 11-23-2020 at 04:55 PM.

  8. #8
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    199
    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.
    Last edited by Sir Galahad; 11-24-2020 at 12:58 PM.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,157
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    199
    Quote Originally Posted by laserlight View Post
    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.

  11. #11
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    199
    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).

  12. #12
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    199
    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.




  13. #13
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    199
    No, it wasn't skipping in large enough steps. Also had an indexing issue there. Fixed.
    Last edited by Sir Galahad; 11-28-2020 at 10:27 PM.

  14. #14
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    199
    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).

  15. #15
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    199
    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.
    Last edited by Sir Galahad; 11-29-2020 at 02:52 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help creating an HTTP client program - will PayPal compensate the volunteer
    By Miko Stoyanov in forum Projects and Job Recruitment
    Replies: 7
    Last Post: 02-10-2013, 07:08 AM
  2. Searching for a volunteer C++ game dev
    By ArtieFinnigan in forum Projects and Job Recruitment
    Replies: 2
    Last Post: 07-15-2010, 01:50 AM
  3. Volunteer Job
    By Bazerx in forum Projects and Job Recruitment
    Replies: 0
    Last Post: 07-06-2008, 02:56 PM
  4. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  5. Volunteer at C# Online.NET
    By Hyle in forum Projects and Job Recruitment
    Replies: 1
    Last Post: 05-10-2006, 09:27 AM

Tags for this Thread