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; Originally Posted by laserlight It might not be a fluke, but I wonder if you're solving the right problem: I ...

  1. #16
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,639
    Quote Originally Posted by laserlight View Post
    It might not be a fluke, but I wonder if you're solving the right problem:

    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?
    There are a variety of functions in common use today; some provably broken (MD5, SHA-1), others theoretically so or at least in just limited circumstances (SHA-2, for example), and then a handful with few-to-none known "major" issues (AES, SHA-3).

    Preimage resistance is obviously one the most important properties of a good hash function, but there are other points to consider as well. MD5, SHA-1, and SHA-2 are all susceptible to length extension attacks and so cannot be safely used as message authentication codes. MD5 is prone to bit-flipping attacks. Few (including the venerable SHA-3) produce remarkably high entropy density output (which ultimately opens the door to more efficient cryptanalysis). Most are based on what amounts to "complex shuffling routines" (to broadly simplify things, of course), a fact which severely complicates the ability to *prove* the assumption of security of the system. Finally, ALL of the algorithms are generally designed in a very rigid, non-scalable manner; complex initialization constants seem to be the rule, meaning that a change from say 256-bit to 512-bit keys can be problematic and hazard-prone at best.

    In contrast, what I am proposing instead focuses on a very fundamental number theory question, one which is many orders of magnitude easier to prove than such "smoke and mirror" techniques (the well-understood Diffie-Hellman problem is a good example of what I am striving for here) and as a result should be much more resilient to the types of vulnerabilities seen today (of course, whether or not it is prone to some other kind of attack remains to be seen). Incidentally, the randomness produced by the algorithm which provides such a high degree of collision resistance isn't even forced by the design - it just arises naturally from the normal course of operation. Last but not least, the whole scheme is easily scalable (so easy that one just has to modify the size parameter of a function call to produce a hash of arbitrary width).

    So yes, I do feel quite justified in saying that this is the right problem to be working on.
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  2. #17
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    Quote Originally Posted by Sebastiani
    There are a variety of functions in common use today; some provably broken (MD5, SHA-1)
    They are provably broken for collision attacks, but collision resistance is not necessary for the security of password storage as long as there is second preimage resistance.

    Quote Originally Posted by Sebastiani
    Preimage resistance is obviously one the most important properties of a good hash function, but there are other points to consider as well. MD5, SHA-1, and SHA-2 are all susceptible to length extension attacks and so cannot be safely used as message authentication codes.
    (...)
    In contrast, what I am proposing instead focuses on a very fundamental number theory question, one which is many orders of magnitude easier to prove than such "smoke and mirror" techniques (the well-understood Diffie-Hellman problem is a good example of what I am striving for here) and as a result should be much more resilient to the types of vulnerabilities seen today (of course, whether or not it is prone to some other kind of attack remains to be seen).
    In other words, the title of and introduction to this thread is inaccurate. You're not aiming for the state of the art for password hashing in particular, but rather you're aiming for something somewhat grander: the state of the art for cryptographic hash functions (as in a new crytographic primitive).
    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. #18
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,639
    Quote Originally Posted by laserlight
    They are provably broken for collision attacks, but collision resistance is not necessary for the security of password storage as long as there is second preimage resistance.
    Sure, preimage resistance is important. It certainly isn't the sole consideration though.

    Quote Originally Posted by laserlight
    In other words, the title of and introduction to this thread is inaccurate. You're not aiming for the state of the art for password hashing in particular, but rather you're aiming for something somewhat grander: the state of the art for cryptographic hash functions (as in a new crytographic primitive).
    Maybe not so much "inaccurate" as "inconcise", but yes, the implication here is more specifically a generic cryptographic primitive.

    Moreover, this isn't just a single algorithm we're talking about but rather a whole new class of them to draw from. There is a reason why number theory has been called the "Queen of Mathematics" - it's perhaps the most inexhaustible wellspring of potential available to us.
    laserlight likes this.
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

Page 2 of 2 FirstFirst 12
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