#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2016
    Posts
    2
    Rep Power
    0

    Lightbulb Analysis of a simple username/password hash function


    I've been thinking about using safe-primes to generate hashes of username/password pairs for website administration and came up with a very simple technique. Basically, the algorithm calculates the sum of two large integers (currently using ~10,000 digit numbers, but this would be scaled down once I've obtained a list of some smaller primes) each of which are (roughly) the product of two distinct prime numbers multiplied by a seed value (derived from the username and password), squared and then taken modulo a third (unique) prime. So six primes in total are being used.

    My sense is that the result should be guaranteed to be irreversible due to the simple fact that it is impossible (barring brute-force methods) to deduce the two addends of any given sum (particularly so with extremely large integers). Not to mention that the use of distinct moduli maps each sub-result to a unique multiplicative group. The output also seems extremely well-distributed and bit-propagation excellent (changing a single bit of the input produces vastly different results). Finally, because the algorithm employs large-integer math it makes it presumably unfeasible for an attacker to quickly and efficiently generate keys (since every hash utilizes both the username and password, pre-generation of keys is out of the question).

    But of course, I could be overlooking something. Does the algorithm appear secure, or are their some obvious flaws in the system? I've developed a proof-of-concept of the algorithm, implemented in Javascript as a plain webpage and posted to pastebin. This one requires an external big-integer library (runs slower) while that one is a stand-alone implementation that is both faster and runs on an off-line machine as well.

    Any comments would be sincerely appreciated!
  2. #2
  3. Headless Moderator
    Devshed Supreme Being (6500+ posts)

    Join Date
    Mar 2007
    Location
    Washington, USA
    Posts
    16,977
    Rep Power
    9647
    Squaring does not add entropy, so you're only working with three primes, one "seed" generated from a known value (username), and one "seed" generated from an unknown value (password).

    Doesn't this all require storing those the three primes, though? And what are you using to generate the seeds?

    But here's some advice. In my opinion you'd be much better off securing your application against attacks than you are trying to invent a new algorithm, because unless your application is so important that you have nation-states interested in your data then your primary concern should be script kiddies and social engineers - and they don't give a damn about what encryption algorithm you're using.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2016
    Posts
    2
    Rep Power
    0
    Originally Posted by requinix
    Squaring does not add entropy, so you're only working with three primes, one "seed" generated from a known value (username), and one "seed" generated from an unknown value (password).

    Doesn't this all require storing those the three primes, though? And what are you using to generate the seeds?

    But here's some advice. In my opinion you'd be much better off securing your application against attacks than you are trying to invent a new algorithm, because unless your application is so important that you have nation-states interested in your data then your primary concern should be script kiddies and social engineers - and they don't give a damn about what encryption algorithm you're using.
    In this case though, squaring does indeed inject entropy into the system. The process is laid out in detail here (the method in question here is in fact based on the Blum-Blum-Shub algorithm, actually).

    The primes are not secret, just very large, although they really don't need to be nearly as big as the ones I've used here. I just don't have a comprehensive list of a broad range of Sofie-Germains, so for now I'm stuck with overkill. And moreover, the chosen primes aren't just public, they're reused over and over again.

    So why "invent a new algorithm"? Well, perhaps because the ones in use to day are so convoluted and flawed and I just wanted to come up with something that works by using easily provable mathematical principles, is easily scalable, and of course flexible in usage.

IMN logo majestic logo threadwatch logo seochat tools logo