Like Tree5Likes

State of the Art of Password Hashing

This is a discussion on State of the Art of Password Hashing within the General Discussions forums, part of the Community Boards category; A few weeks back I lamented about the poor state of affairs regarding password hashes. Well, after quite a bit ...

  1. #1
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708

    Exclamation 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):
    Attached Files Attached Files
    Last edited by Sebastiani; 11-08-2013 at 03:17 AM.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,717
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,698
    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.

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote 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).

    Quote 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.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,717
    Quote 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.

    Quote 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?

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote 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.

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

    Quote 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.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,717
    Quote 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).

    Quote 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".
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Oct 2006
    Posts
    2,402
    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?
    laserlight and Sebastiani like this.
    Code:
    namespace life
    {
        const bool change = true;
    }

  9. #9
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by Elkvis View Post
    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.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  10. #10
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    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.
    Last edited by Sebastiani; 11-08-2013 at 12:25 PM.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  11. #11
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    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
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  12. #12
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    1,623
    Quote Originally Posted by Sebastiani View Post
    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
    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.
    A class that doesn't overload all operators just isn't finished yet. -- SmugCeePlusPlusWeenie
    A year spent in artificial intelligence is enough to make one believe in God. -- Alan J. Perlis

  13. #13
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Quote Originally Posted by Yarin View Post
    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.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,717
    Quote 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:
    Quote 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?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,246
    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
    Sebastiani and laserlight like this.
    “Often out of periods of losing come the greatest strivings toward a new winning streak.” -- Fred Rogers
    “Salem Was Wrong!” -- Pedant Necromancer

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 01-07-2009, 09:35 AM
  2. Why hashing?
    By audinue in forum Tech Board
    Replies: 6
    Last Post: 01-01-2009, 07:41 AM
  3. I need help Hashing!!
    By LittleTim in forum C Programming
    Replies: 3
    Last Post: 11-17-2005, 09:46 PM
  4. hashing help
    By alokin in forum C Programming
    Replies: 17
    Last Post: 10-28-2002, 05:33 PM
  5. hashing
    By sweets in forum C++ Programming
    Replies: 1
    Last Post: 05-26-2002, 04:22 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21