Thread: State of the Art of Password Hashing

A few weeks back I lamented about the poor state of affairs regarding password hashes. Well, after quite a bit of thought on this I decided that the real problem isn't stolen password lists and rainbow tables - these are trivially mitigated by salts/nonces - no, it's the inherent weaknesses (and flaws) of the very algorithms that we rely on.

What I've done is taken a completely different approach altogether. I've developed a method that is foremost rooted in a very hard number-theoretic problem (related to discrete logarithms) and second-most upon the principle of scalability. I'm withholding details of the algorithm until I absolutely verify that it has been implemented correctly, but let me just say that the preliminary results are rather promising, to say the least. Statistical analysis (provided by Diehard, TestU01, Ent, plus various compression utilities) seem to indicate an unusually high entropy density (ie: essentially indistinguishable from truly random data), extremely high collision resistance, and an apparent lack of susceptibility to bit-flipping attacks and the like.

I've shown the algorithm to a few good friends who happen to be professional mathematicians and their initial responses have been quite encouraging. I'm very excited about this, and I can't wait to release a detailed description of the algorithm once it has been thoroughly studied and verified. I've devoted literally hundreds of man-hours to this project in a very short period of time and I'm exhausted, frankly (and perhaps a bit delirious), but truly happy that all of the effort just might have been worth it.

Okay, so how about some visuals?

Here are the unsalted hashes of some simple, single character passwords, first their 64-bit values, followed by their 256-bit values (the algorithm scales to any number of bits):

Code:

// 64-bit hashes

'a':
    28191714584FD46F
'b':
    C9B8A0C07AA27E9B
'c':
    BF466002D82DA9C1
'd':
    38A418BEF6D7084C
'e':
    CC89B87148317CED
'f':
    A759812A3127E2C6
'g':
    9C6605AAC49C881B
'h':
    C9671139CD0A5489
'i':
    580B935F34F92C22
'j':
    2871EEC5CE32D711
'k':
    76EBB34389732F76
'l':
    ECD6678712E75EEC
'm':
    DDFAEC50E2DC8B1D
'n':
    B73E3B9438F76207
'o':
    5B9F1D4A9C7BB103
'p':
    76EBB34389732F76
'q':
    C4AFC76E7D762871
'r':
    165837691A132990
's':
    3FE49AA205D64D9A
't':
    F143AE295A60DDA4
'u':
    C70FB9A668817593
'v':
    B4992A508E1F724D
'w':
    CD4407D266AA4039
'y':
    E0846A7E478FCD44
'z':
    1E08558017942E89

// 256-bit hashes

'a':
    1139CD0A54893911370E2986AFFD350213C06E490D76CFDC28191714584FD46F
'b':
    C86956A04ACC89B87148317CEDAF119800764B6AB07BE646C9B8A0C07AA27E9B
'c':
    947A7773580B935F34F92C22A759812A3127E2C621C5F0B5BF466002D82DA9C1
'd':
    EC2C731D9152EF6E0E6B61F28B269F45E4342B5025E644DC38A418BEF6D7084C
'e':
    25CEBDD859E63A22A5DEDD1CD6C2E4174D3E8BC86956A04ACC89B87148317CED
'f':
    63B73E3B9438F7626799EB88947A7773580B935F34F92C22A759812A3127E2C6
'g':
    8FDDFAEC50E2DC8B9D65AE2352EADDCD612D4C7ED1E4B3889C6605AAC49C881B
'h':
    6810BF1EBBF5D9A1C4B9173BCB5C47A4D4BB9BC35A98FCA2C9671139CD0A5489
'i':
    24C8EA95010DE2D763B73E3B9438F7626799EB88947A7773580B935F34F92C22
'j':
    397EC835450BAC9B348D89144890D52B031AC4AFC76E7D762871EEC5CE32D711
'k':
    365305CAF143AE295A60DDA4694CA44082AC5E19D0207E3D76EBB34389732F76
'l':
    6DA60A94E3875C53B4C0BA49D39848810459BD32A041FC7AECD6678712E75EEC
'm':
    CD548172FC906B8A165837691A13299020AB570634885F8FDDFAEC50E2DC8B1D
'n':
    3355A01C3FE49AA205D64D9AC6440A24C8EA95010DE2D763B73E3B9438F76207
'o':
    992A508E1F724DD102EB264D6322051264F5CA8006F1EBB15B9F1D4A9C7BB103
'p':
    365305CAF143AE295A60DDA4694CA44082AC5E19D0207E3D76EBB34389732F76
'q':
    4407D266AA40397EC835450BAC9B348D89144890D52B031AC4AFC76E7D762871
'r':
    8017942E89A9C009D5FC8E1E9B890EA4CD548172FC906B8A165837691A132990
's':
    B4074215E005A54B622A704235BFA3C766A203693355A01C3FE49AA205D64D9A
't':
    4F7B2054015E50BA24A6022754F33B7A6C263A90365305CAF143AE295A60DDA4
'u':
    3EED8150057841E992980A9C50CDEFE8B199E840DA4C1528C70FB9A668817593
'v':
    93EA01F97DDA03A10AF082D225311538A19ADFD16333D181B4992A508E1F724D
'w':
    EF3A8C4EAA07E4F7690F842AC00B4A97C454E0846A7E478FCD4407D266AA4039
'y':
    58995DA877A5EF3A8C4EAA07E4F7690F842AC00B4A97C454E0846A7E478FCD44
'z':
    D2EC271099C0E38510B132BB50EF4ADF75189D540FC8EFD31E08558017942E89

And here's the SmallCrushTest results using the worst seed value possible - a zero! (That is, zero-length and zero-value):

How fast is it to compute? Remember, one problem is that an attacker does not have to attack the problem as if the passwords were randomly generated as often they are chosen by humans such that intelligent guessing can feasibly result in the password. However, such an attack is not very feasible if the computations are slow.

Originally Posted by laserlight

How fast is it to compute? Remember, one problem is that an attacker does not have to attack the problem as if the passwords were randomly generated as often they are chosen by humans such that intelligent guessing can feasibly result in the password. However, such an attack is not very feasible if the computations are slow.

Right, that's one reason why an unsalted hash should be never be used in practice; an attacker could simply construct a rainbow table of common passwords as an efficient method of attack. In fact, I would go as far to say that the only real application for unsalted hashes would be generating checksums of non-secret data (ie: for the purpose of file-integrity verification and the like).

As far as speed is concerned anyway the algorithm is fast enough to be practical, though not nearly as fast as most algorithms in use today. For example, the proof-of-concept implementation I came up with (which was limited to 4-byte passwords) was capable of producing roughly 30,000,000 bytes per second. The more generalized (and as yet unoptimized) version is currently running at about 12,000,000 bytes per second. The processing time is directly related to the size of the parameters used, so if you really wanted to slow things down a bit you could just choose a very large salt of say 1000 bytes or so.

And just to be clear, the only reason I posted the unsalted hashes was to demonstrate the quality of the output generated even from simple inputs - the algorithm doesn't even take into account the size of the input and works the same regardless. Again, I would never ever advocate the use of unsalted hashes in practice (for several reasons, not the least of which being the use of rainbow tables).

Originally Posted by whiteflags

Well I wouldn't totally discard password fundamentals, because if you assume that an attacker knows the algorithm, then a single character password would not be secure, since you would just try all of the single characters.

That depends. If the salt or at least a good portion thereof is a secret known only to say the sysadmin and sufficiently complex then it wouldn't really matter. Otherwise, I agree.

Originally Posted by Sebastiani

Right, that's one reason why an unsalted hash should be never be used in practice; an attacker could simply construct a rainbow table of common passwords as an efficient method of attack.

The approaches I am referring to can be used even where salts are in use. They won't be as fast, of course, but they may still be feasible.

Originally Posted by Sebastiani

As far as speed is concerned anyway the algorithm is fast enough to be practical, though not nearly as fast as most algorithms in use today. (...) The processing time is directly related to the size of the parameters used, so if you really wanted to slow things down a bit you could just choose a very large salt of say 1000 bytes or so.

Are you comparing to schemes designed for password storage such that the cost is adjustable, e.g., PBKDF2, bcrypt and scrypt, or to the cryptographic primitives used for hashing?

Originally Posted by Sebastiani

If the salt or at least a good portion thereof is a secret known only to say the sysadmin and sufficiently complex then it wouldn't really matter.

As per Kerckhoffs's principle, it should be assumed that the attacker knows the algorithm, which in this case includes the salt and other parameters besides the password itself.

Originally Posted by laserlight

The approaches I am referring to can be used even where salts are in use. They won't be as fast, of course, but they may still be feasible.

Assuming the salt is publicly known, yes, of course.

Originally Posted by laserlight

Are you comparing to schemes designed for password storage such that the cost is adjustable, e.g., PBKDF2, bcrypt and scrypt, or to the cryptographic primitives used for hashing?

Not exactly, but it turns out that this would be very easy to do; since the execution time is pretty much directly proportional to the number of iterations performed (each iteration produces just a single bit), it would be trivial to add a tunable cost parameter to the API to achieve such a thing.

Originally Posted by laserlight

As per Kerckhoffs's principle, it should be assumed that the attacker knows the algorithm, which in this case includes the salt and other parameters besides the password itself.

Right, and most systems would likely publish the salt value. That said, the use of a secret salt value wouldn't necessarily be a very difficult thing to implement in practice, so it may well be a good idea to adopt such a strategy anyhow.

Originally Posted by Sebastiani

Not exactly, but it turns out that this would be very easy to do; since the execution time is pretty much directly proportional to the number of iterations performed (each iteration produces just a single bit), it would be trivial to add a tunable cost parameter to the API to achieve such a thing.

That's good to hear. I thought I would mention this because "it's the inherent weaknesses (and flaws) of the very algorithms that we rely on" is criticism that I only recall concerning the crytographic primitive hash algorithms when they are used with minimal modification for password storage, e.g., a single iteration with a salt. The algorithms to beat are the ones that I mentioned and those considered their equals, and given what you have listed as the qualities of your algorithm, it doesn't sound like you're actually doing better (though you might not be doing worse once you add this tunable cost parameter).

Originally Posted by Sebastiani

That said, the use of a secret salt value wouldn't necessarily be a very difficult thing to implement in practice, so it may well be a good idea to adopt such a strategy anyhow.

If there were a way to keep the salt secret such that it is beyond the reach of an attacker, then that way would be used to keep the password secret. Unfortunately, public key cryptography is not useful for that purpose since the secret key needs to be available to use such an encrypted salt. The approach I have seen is to have a second salt, often a global rather than user specific value, that is kept separately from the storage in which the hashed password is stored, e.g., it might be in source code. It should still be assumed that the attacker can get to this second salt, but nonetheless the attacker's job becomes more difficult. I would not call this a "secret salt".

not sure if anyone else has noticed, and I don't know if it's relevant, but I noticed that the last 16 characters of the 256-bit hash are identical to the hash generated by the 64-bit hash. from this, I would conclude that the 256-bit version is not stronger than the 64-bit version, and since there are affordable(?) machines that crack a 56-bit DES key in a matter of hours, cracking a 64-bit hash in a matter of days is not out of the question. if you know that this particular hash algorithm is used, it's not unrealistic to expect even a poorly funded hacker to beat it.

am I way off base here?

Originally Posted by Elkvis

not sure if anyone else has noticed, and I don't know if it's relevant, but I noticed that the last 16 characters of the 256-bit hash are identical to the hash generated by the 64-bit hash. from this, I would conclude that the 256-bit version is not stronger than the 64-bit version, and since there are affordable(?) machines that crack a 56-bit DES key in a matter of hours, cracking a 64-bit hash in a matter of days is not out of the question. if you know that this particular hash algorithm is used, it's not unrealistic to expect even a poorly funded hacker to beat it.

am I way off base here?

No, that's a very good point, actually! Come to think of it, the attacker could simply construct very small hashes of common passwords and simply look for trailing values that match as such in order to narrow down the search. Fortunately, this is easily mitigated with a minor modification which I'll post shortly here.

Okay, so here are the new unsalted hashes (thanks again to Elkvis for pointing out the obvious!):

Code:

// 64-bit hashes:

'a':
    7C28F6B663E6A6D5
'b':
    43B1B71D3337ADEE
'c':
    3D2E6CB08459A26A
'd':
    B6E6C86BA1C7850D
'e':
    91836B6CCD91D742
'f':
    56B7111D450EAEB1
'g':
    58DD46741439B8C6
'h':
    59323BB0BA8DE828
'i':
    E40E95923F4B6607
'j':
    6C174EA436A10B7E
'k':
    73A6C360BB7022B5
'l':
    E64C87C176E1446A
'm':
    9CE930D82E9C48ED
'n':
    673A0CB60B2752FB
'o':
    331D06DB8513A9FD
'p':
    73A6C360BB7022B5
'q':
    283961CE74186C17
'r':
    EB204602F20AC16A
's':
    6F8CAEC53A889180
't':
    F7C6E85AAC831809
'u':
    DF1BA36BB10E6224
'v':
    F591C3F5BE3746D7
'w':
    FB066FD6470ED7FB
'y':
    BA753014F9B2FB06
'z':
    3828844D7FE8C86F

// 256-bit hashes:

'a':
    5EFF6ED903637ECDF6A71F77BAC7045CDD70FCFB587108D5A93284AFEE222A88
'b':
    FA77CB1E18F36BB63FFDB8D33D26E0EA86E3DFC78A43A84E95217C75175141E4
'c':
    EFA58992DDA16798E8BBD3EBDF2D7B60CCAFD9FEF4E34EF79880AB1B8E7F1F2B
'd':
    DD21B44EF5BD3451B23BF40C137D777AFDBB650F8CF935DB9F7EDCE91E137075
'e':
    3421C9BA43689DEA7B69A26477E81926FAEEF4FA77CB1E18F36BB63FFDB8D33D
'f':
    38C252E6D18424EB0EA175AAEFA58992DDA16798E8BBD3EBDF2D7B60CCAFD9FE
'g':
    E0084B99471392AC3B84D6A9BE97264A76879E61A2EF4EAF7FB7EC8131BF66FB
'h':
    C42243C01196328F2624597708AD537D2F4D94EC0E3DC344DF9D5EFF6ED90363
'i':
    1DB830479258640838C252E6D18424EB0EA175AAEFA58992DDA16798E8BBD3EB
'j':
    1674ADA43BB0F6B32B81DD1F3B70618E24B1C8107084A5CCA30949D61D42EB54
'k':
    586D18B0A06B25DD81B59F5D09ECFED8810B732489458680232C651E4D48B2EE
'l':
    B1DA306041D74ABA036B3FBB12D8FDB10317E648128B0C014758CA3C9A9064DD
'm':
    561B062CE85A497760ED675702BB3F76E0C21C49629121E0084B99471392ACBB
'n':
    D586010BBA56D21D58FBD995C0EE8F1DB830479258640838C252E6D18424EB6E
'o':
    6AC380055D2BE90EACFDEC4A60F7C70E5C9823492C32041C6129F36842927537
'p':
    586D18B0A06B25DD81B59F5D09ECFED8810B732489458680232C651E4D48B2EE
'q':
    06581DAB0D031674ADA43BB0F6B32B81DD1F3B70618E24B1C8107084A5CCA309
'r':
    0A6A47E449DCB0603933B7D1930CB03A561B062CE85A497760ED675702BB3F76
's':
    7EE296A682DA117912372C58CECC6DF42403AC8ED586010BBA56D21D58FBD995
't':
    EE276E692AA81D912771C382E5CCDC464F32C0EA586D18B0A06B25DD81B59F5D
'u':
    BB9FB8A5A9A076449EC40D0B9633731B3DC900AB63B561C082AE957407D67E76
'v':
    8555C79B773F714B5341ED883C891B162C67E6367A920156C76AC380055D2BE9
'w':
    3E45F317561D6FDEFDC42D4D05B523F2246E58B09C99DBE84906581DAB0D0316
'y':
    2DA591D5FE663E45F317561D6FDEFDC42D4D05B523F2246E58B09C99DBE84906
'z':
    F9B036A4B4E70941CD5A4A23ABFDCD7C8AE62FAC3ADEBCFB895B9A0A6A47E449

Also note that the method employed here prevents the attacker from producing partial hashes altogether.

I've fixed a logic error in the previous implementation. Here's a representation of the current status of the hashing algorithm:

Code:

'a': D48EC8F2F53515E2DD86FA813E3C9C25 
'b': 19B2DC092B1B67A031D159F62B350167 
'c': C6E74081417363E2AEB457EBF34BF5CD 
'd': 3351D8B44DCEA1031102088418ADDEEC 
'e': 98F03A7CF1C253F110C7058D0C491670 
'f': D80A6F0C3E034E6247721527CF8914FB 
'g': FA4C07497302A2B0C446CA6F16E4038F 
'h': 39C7EE4DA8BF880708E35B59F380FD87 
'i': 31D4EC1915A086D15756A721C9493B39 
'j': 7CC5BA0EFDAC26A1F4BAF862FA1A9CCE 
'k': 8907F491CB65FD78C6E71508C93D8913 
'l': 944414E99FC6380EDCC4677193CD07FA 
'm': DF9241BDC34C5C707168F0EDD76E387A 
'n': 0AA9C4CFF6CC90CB6D25E4C9704C6BD4 
'o': B20F5E10E7EBCBDC12AE2B9319FEE20C 
'p': E43676226EDC7DD83FB3A95B5BFC4FD7 
'q': BA8923054D0320C2D071883B1B4D2FCF 
'r': 34864C09277D0FD68D7DD2EBD139542D 
's': 79C00299D97CEF7C213B1B28C2BEA877 
't': B8AACD01DC3810B2181A8DF59A417B46 
'u': 44CFEC0B077D743F30A99BB65E4A0AC5 
'v': 59DFE4A75596F33E94841BBCFBE00C45 
'w': 7100A7F37EF3ADF949698BFAB7E6E49C 
'y': 6B4149F1D01742B03403EA6B76679AFA 
'z': 4449BC3A6833B014884EBD51304BB51A 

'a': C88FD04404CFCE457091D63054D5BA034536A4A336679A65BFA01337FC8AD9AB 
'b': AF8266E18A930D0EE0BFCD4FC4B25541E8DA78E9661CE14F839CED5BBBC9E6F0 
'c': 6AD302228E80470856116CA3B1C2BDBB4407CDD1F89FE70D7B341E92C19B7AD1 
'd': 2D0C626640DFBDE021DCFC9E8726421184D7E21172E043C5B7AFBE9066359A98 
'e': 5D9C81B152185197936466C7322D61F10A5A94B008B75972D903E1AD932F334F 
'f': 687EEDB535480149FA793D4A7DCBE2CE1709E4F9CB0ED8B307B4093780016B0E 
'g': 7475B03C30A1A1D299C43683B6BD90B75EA04EFF57F44CA7ED3B24279FBC8214 
'h': C6CEB5F2AC622B5501B6E56EBB96D785BB9094E63439BE630A76F02F32CD9A02 
'i': F15E6C47D3A7D2687B3F102F2534C65C7A9DABECFD35F585C8A0C3F4033174F6 
'j': 3A9EB1D124D541D951E020742D6A2BB144CF42BB543971A70EA4641D066B9EB9 
'k': 5B05511AF52122CC184582D55405CC5FDCBC4BD05C9BD292E3CD87A9184F1BB9 
'l': 53D8F0AFDBF3E0B20F9FDE530A39160D4F02116B1C15F368261B7D7971C2F51D 
'm': FDE6C1C947B23099C8EDE88C79C3A045EB0A5DDA68C78458B13868112CF6A595 
'n': D5D0EECDFEF91E8FDB95AA788D0191CF116385708695C55053637F33AD6EF154 
'o': F6F7516CDCCF20A41842A0CACFFCFBD30F13D45817A0799E3BBB30A56520925D 
'p': 752562C37165CD5EFDEC1C56B04EE10EF687571FAE1B1089CB97412EFC36C298 
'q': 398566EE441E7830FF17D67BA81128990ED2C74B8B0496410821B0CEA07AD7B7 
'r': 61569278E820991C90C8235E4AEB4DC4E3CBDD2BA6E621AA0BE161DBED6C22B5 
's': F1852B171B31EBE27962E5BE4A9EE981C65AB7248EF5762D0F863D3B1690F93D 
't': C3DFB6D30AD8156CB5892B78D0A671DCE4576902EC886C83382781A7F70303EA 
'u': B6460712DB32DB541A3919DDB13E2C1637C52AFFADBDD0E9003256F64F89DB54 
'v': CDDBAB17262769DCBC63EDBD2186E8E083485C100AC83AAC52DE62F80971DDF9 
'w': F40E789DCA5FA398288EF79216C2FDDB170BD03FD4B1B461E5E896C8AA7FCAA0 
'y': 39837EF54C45A2E53DC0246273AA67830117A93DF8AB4E546FAD2537D496C859 
'z': 1D37ACAC113A698F1DFE593F108E96E06B9ABA8FB402418FC36573C0902B4AE3

Originally Posted by Yarin

This could be the result of an algorithm of horrid security, but without details we have no way of knowing. I don't want to disparage your work, this snippet just doesn't mean much.

No worries, I don't expect you to simply "take my word for it". That said, while I've certainly made my share of mistakes, I can assure you that this is no fluke. And just to be sure, you actually can learn a lot about the quality of an algorithm by inspecting it's output, statistics, etc. The proof is in the pudding, as they say.

Originally Posted by Sebastiani

No worries, I don't expect you to simply "take my word for it". That said, while I've certainly made my share of mistakes, I can assure you that this is no fluke.

It might not be a fluke, but I wonder if you're solving the right problem:

Originally Posted by Sebastiani

Well, after quite a bit of thought on this I decided that the real problem isn't stolen password lists and rainbow tables - these are trivially mitigated by salts/nonces - no, it's the inherent weaknesses (and flaws) of the very algorithms that we rely on.

I get the impression that you've come up with your own cryptographic hash function, except that it is intended specifically for password hashing, to address "the inherent weaknesses (and flaws) of the very algorithms that we rely on". The thing is, when we're talking about hashing a password for storage, we're talking about preimage resistance, but (as far as we non-NSA people know) the algorithms commonly used for password hashing these days are preimage resistant, even if it is just plain MD5 applied once with no salt.

Consequently, the algorithms that build on these for better password hashing don't address preimage resistance since attackers are unlikely to approach the problem from that angle anyway. From what I understand, they just assume that if the password is random and sufficiently long, it really is computationally infeasible to find the password given the hash and the algorithm, thus the problem to solve is how to protect passwords that are not so random and/or not sufficiently long.

Do you disagree with this assessment? What are the "inherent weaknesses (and flaws)" that your algorithm fixes?

Well, after quite a bit of thought on this I decided that the real problem isn't stolen password lists and rainbow tables - these are trivially mitigated by salts/nonces - no, it's the inherent weaknesses (and flaws) of the very algorithms that we rely on.

[Edit]
I didn't intend to rant, but I guess I did all the same.
[/Edit]

O_o

The "inherent weaknesses of the very algorithms that we rely on" is a myth. Oh, sure, you can easily attack some security installation relying on unsalted, single iteration MD5. (You can download an assault package from millions of places.) Of course, we don't rely on unsalted, single hash MD5 and haven't for some time. (I'm obviously ignoring a few entrenched protocols.) The modern approaches, tunable key lengthening, attack space, and hashes-per-second, aren't even just algorithms anymore but packages of carefully selected, heavily vetted techniques used in concert. Make no mistake, "state of the art" attacks aren't built on attacking individual algorithms but the use of cryptography suites.

Modern approaches with simple algorithms, relatively speaking, are sufficiently complex because, lacking a fundamental change in how we understand some bits of mathematics, they may be tuned for radical shifts in compute increasing the costs of an attack, without needing immediate data synchronization, which is telling for a simple reason: the problem with insecure security systems using modern tools isn't the tools but the misuse of tools.

Consider your own implementation at "12,000,000 bytes per second": that isn't an improvement over modern approaches because the cost of the hash is trivial, the hash is too simple. No. I'm not kidding. Increasing the costs of making an attack, online or offline, is the best real security we have available. If I can throw a $5000 (USD) machine at your algorithm over "CUDA" and get billions of hashes per second I can safely consider points of interest behind your algorithm to be low hanging fruit.

Now, my point here isn't to frustrate your design, but to focus your interests on where the real problem lives. Let me offer an example, I serviced a "Drupal" site a few years back where the owners insisted on reducing the "login time" in order to offer a "snappier response". (The real problem facing the user was simply fragmented Javascript.) Let me offer a counter example from my servers: I use "scrypt" tuned for around 1000 hashes per second over 16 MiB of RAM. (I only ever have a few dozen users online at any given time so the "cost of legitimate use" is invisible for normal users.) Tuning "scrypt" to my purposes was remarkably simple: I read the documentation. So, again considering your algorithm, you say it may be tuned for complexity to increase the difficulty of an attack. Unfortunately, when the foolish see "each iteration produces just a single bit" they will tune your algorithm to use far too few bits.

To the point then, whatever your attempts may win, your algorithm has the same "inherent weakness" as "scrypt", "bcrypt", "PBKDF2", and similar tools: people will not use it correctly because the perception of cost is greater than the perceived value.

Sadly, that is to say nothing of how much information is stored in the same databases, even tables, which is a problem beyond the abilities of any algorithm to fix.

Soma