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

    Join Date
    Jul 2011
    Posts
    51
    Rep Power
    55

    Proposal for a Change in storing Password Hashes


    In the Light of the recent Events of Hacking when Databases contaning several Millions of Username and Password Hashes are stolen, I would like to suggest a different and more secure Approach.

    The simple Idea is that the Client does the Math for generating the Hashes and not the Server. On the Server Side nothing useful need to be stored nor any Hardware Encryption Device is necessary if you use the following Algorithm


    ### Split Secret Login ###

    (Preparation)

    1) the Client generate a Client-Hash of Parameters only he know about

    2) the Client split the Client-Hash in two Parts

    3) the Client submit one Part of the Client-Hash to the Server

    4) the Server store this partial Hash in his Database


    (Log-in Process)

    1) the Client send a Log-in Request

    2) the Server send back a random Salt

    3) the Client calculate a new Hash with the Salt and the complete Client-Hash

    4) the Client send back the Result and the other Half of his Client-Hash

    5) the Server now does the same Calculation with the Salt and the complete Client-Hash

    6) after the Calculation the Server immediately drops the other Half of the Client-Hash

    6) the Server compares his Result with the one submitted by the Client

    7) if both Results equals Log-in is granted


    So just let the Client calculate a SHA-256 Hash for Example out of Username and Password - where Password is only known to the Client and never leave his Browser. Would be done fast with JavaScript and even the resulting Hash does not need to be stored on the Client Side as it will be calculated every Time on Demand.

    On the Server Side there is no Calculation needed in Advance, just storing a Part of the SHA-256 Hash submitted by the Client.

    Only on Log-in Request the Server needs to do some Math when he receives the other Half/Parts of the SHA-256 Hash for Comparison of the Salt Calculation Result. The Server only get the full Secret Key Hash temporarily but never stores it. The main Reason is that an Attacker never get Hands on Millions of Hashes for Reverse Engineering them into valid Passwords.

    If there are no Hashes to reverse any Attacker will quite quickly lose his Interest in such a Database.

    I do not claim this as a Ground-breaking new Idea, but in Fact an easy to implement Way to frustrate the unlawful Hackers.

    Cheers,
    Karl-Uwe
  2. #2
  3. No Profile Picture
    Lost in code
    Devshed Supreme Being (6500+ posts)

    Join Date
    Dec 2004
    Posts
    8,300
    Rep Power
    7170
    In the Light of the recent Events of Hacking when Databases contaning several Millions of Username and Password Hashes are stolen, I would like to suggest a different and more secure Approach.
    The problem with the recent database leaks is not a result of a lack of secure password storage methods, it's a result of companies using insecure algorithms in spite of the fact that secure ones are available and not hard to implement. Inventing new secure methods of storing passwords is obviously not a bad thing, but it's never going to solve that problem.

    Whoever designed the authentication system for those leaked databases had absolutely no business doing so. The companies either made a bad decision about who to hire as their programmers or else the management made bad decisions about how to allocate their programming resources.
    PHP FAQ

    Originally Posted by Spad
    Ah USB, the only rectangular connector where you have to make 3 attempts before you get it the right way around
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    51
    Rep Power
    55
    Originally Posted by E-Oreo
    The problem with the recent database leaks is not a result of a lack of secure password storage methods, it's a result of companies using insecure algorithms in spite of the fact that secure ones are available and not hard to implement.
    I totally agree with you so far - but still two problems remain

    1) excessive calculation for the server with several thousand iterations for hashing the password on each and every user login.

    2) storing the salt together with the hash, which could give the hacker a small opportunity to reverse the hashes into passwords again.

    Originally Posted by E-Oreo
    In your well programmed and very good commented and explained PHP code you linked I am missing one important fact - the iteration of the hashing procedure.

    Originally Posted by E-Oreo
    Inventing new secure methods of storing passwords is obviously not a bad thing, but it's never going to solve that problem.
    My proposed idea reduce the chances of any hacker to reveal the passwords of millions of hashes simply because there are no such. Moreover it reduces the massive calculation a server has to do with hashing the user log-in details all the time. Imagine a server that has to handle tens of thousand log-in request per minute, each start a hashing routine with only 16384 iterations on a salted SHA-256 hash.

    Originally Posted by E-Oreo
    Whoever designed the authentication system for those leaked databases had absolutely no business doing so. The companies either made a bad decision about who to hire as their programmers or else the management made bad decisions about how to allocate their programming resources.
    Absolutely correct.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    51
    Rep Power
    55
    --------------------------------------------------------
    Something important was missing (as mentioned by "OmegaZero"), so I added it to this post.

    There is of course a need to verify K1 on the server side, therefore a hash KH = SHA-1(K1) should also be generated by the client on registration and stored on the server for later comparison at the log-in procedure.
    --------------------------------------------------------


    On my opinion the client should do the costly calculation not the server. Also a split half of a huge binary value should be stored on the server where only the client is able to generate the complete value i.e. client key (K).

    #======================
    # (At Registration)
    #======================

    As "kg" mentioned on registration the client should generate a strong hash value.

    U = username
    pw = password
    W = website
    s = salt
    #i = 65535 iterations
    DH = derived hash

    DH = SHA-1(PBKDF2(SHA-1, pw || U || W, s, #i, ...))

    Next step using DH as password for a stream cipher and generate for example a 16384 byte random value as complete client key.

    But first generate a nonce

    Dn = derived nonce same byte length as DH
    #i = 65535 iterations
    r = random value

    Dn = SHA-1(SHA-1, pw || r, #i))

    Now use DH and Dn as start parameter for the stream cipher and let it also go through all #i.

    #i = 4096 iterations
    c = /dev/null
    K = client Key

    K = streamCipher( DH || Dn, c, #i)

    Split K in two equal half's (K1, K2).

    Next a hash value of K1 has to be computed by the client in order to verify K1 later on the server.

    KH = SHA-1(K1)

    Finally encrypt Dn with DH which I suppose should be sufficient

    eDn = XOR(Dn, DH)

    Send the second part of the client key (K2), the hash (KH), the encrypted nonce (eDn) and the salt (s) to the server where they are stored alongside the username (U). On the client side nothing needs to be stored.

    For a stronger K the encrypting can also involve the constant re-calculation of the nonce

    K = streamCipher( DH || SHA-1(pw || U || s) , c, #i)



    #======================
    # (On Log-In Request)
    #======================

    On log-in request the server send the salt (s), the encrypted nonce (eDn) and a server side generated random hash value (RH) to the client.

    The client first re-build DH, decrypt eDn, than re-generate his client key (K) and calculate

    R = XOR(K, RH)

    He send the result (R) and K1 back to the server.

    The server first calculate the verification hash of the submitted K1

    KH' = SHA-1(K1)

    and if KH' == KH he calculate

    R' = XOR((K1 || K2), RH)

    drop K1 and compare both results.

    If R == R' log-in is granted. Of course the whole log-in process should use a secure channel (SSL).

    Cheers,
    Karl-Uwe
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    May 2007
    Posts
    765
    Rep Power
    928
    Hacker (having received a compromised copy of the database) knows K2.

    Hacker makes a log in request receiving eDN, s and RH.

    Hacker chooses his favorite number finds a value with a SHA-1 hash of KH and calls it K1'

    Hacker then computes R = (K1' || K2) xor RH and sends R and K1' to the server.

    The server computes KH' = SHA-1(K1'). K1 and K1' have the same hash, so KH = KH' and the server accepts K1' as K1.

    The server computes R' = (K1 || K2) xor RH.

    But the server is trusting the value of K1 sent by the hacker, which is really K1', so R' = (K1' || K2) xor RH = R and the login is granted.

    Hacker then changes the e-mail address and resets the password.

    Hacker laughs at security system that trusts a random person someone on the internet to do its crypto for it.

    Total cost to hacker: Finding 1 SHA-1 collision (i.e. much cheaper than finding a bcrypt collision).

    What I'm trying to say here isn't "Here's a problem to fix", but "See how easily you missed that". If you roll your own algorithms you're likely to miss something. Good crypto is hard and must be thoroughly analyzed to have a chance at being secure. I don't doubt if you keep on adding bells you can create a version that I can't break at first glance, but to be secure you need to beat the people who are orders of magnitude beyond me and who have months to study your algorithm. There are solid algorithms out there; prefer them over homegrown crypto.

    (Updated to attack the latest iteration of the algorithm--hopefully this reinforces the point)
    Last edited by OmegaZero; July 14th, 2012 at 07:19 AM.
    sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    51
    Rep Power
    55
    Originally Posted by OmegaZero
    Hacker (having received a compromised copy of the database) knows K2.

    Hacker makes a log in request receiving eDN, s and RH.

    Hacker chooses his favorite number and calls it K1'

    Hacker then computes R = (K1' || K2) xor RH and sends R and K1' to the server.

    The server computes R' = (K1 || K2) xor RH.

    But the server is trusting the value of K1 sent by the hacker, which is really K1', so R' = (K1' || K2) xor RH = R and the login is granted.

    Hacker then changes the e-mail address and resets the password.

    Hacker laughs at security system that trusts a random person someone on the internet to do its crypto for it.
    Exaktly, you explained the missing authentication of K1 perfectly, straight and simple.

    Finally a hash value of K1 has to be computed by the client in order to verify K1 later on the server.

    KH = SHA-1(K1)

    That hash should be saved on the server as well in order to prevent your above described scenario.


    Originally Posted by OmegaZero
    What I'm trying to say here isn't "Here's a problem to fix", but "See how easily you missed that". If you roll your own algorithms you're likely to miss something. Good crypto is hard and must be thoroughly analyzed to have a chance at being secure. I don't doubt if you keep on adding bells you can create a version that I can't break at first glance, but to be secure you need to beat the people who are orders of magnitude beyond me and who have months to study your algorithm. There are solid algorithms out there; prefer them over homegrown crypto.
    Obviously something different then salted hashes are needed, so why not publishing some other ways in solving that problem? Perhaps my thoughts directing into a possible solution.
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    51
    Rep Power
    55
    ########################################################################
    #
    # Split Secret Login Scheme vs. salted Password Hashes
    #
    # Server Side Version
    #
    ########################################################################

    Just for the sake of completeness a solution for a server side only client key computation.


    #======================
    # (At Registration)
    #======================
    Code:
    Ask client for username (U) and password (pw)
    
    Generate Password-Hash (dK) using a secure hash function
    
      U  = username
      pw = password
      W  = website
      s  = salt
      i  = 4096 iterations
      dK = derived key
      
      dK = F( SHA-1( SHA-1(s || pw) || U || W || s) ... , i )
    
    
    Generate Nonce-Hash (dN) using a secure hash function
    
      U  = username
      pw = password
      r1 = random value
      r2 = random value
      dN = derived nonce same byte length as dK
    
      dN = SHA-1( SHA-1(r1 || pw) || U || r2 )
    
    
    Generate client key (K) using stream cipher with dk and dN as keyword - on first iteration the stream cipher act as CSPRNG
    
      i = 65535 iterations
      K = client key 16384 byte random value
      
      K = streamCipher( dK || dN, K, i )
    
    
    Build verification hash (vH) from client key (K)
    
      vH = SHA-1(K)
    
    
    Compute an encrypted Nonce-Hash (eN) using Password-Hash (dK) and Nonce-Hash (dN)
    
      eN = XOR(dN, dK)
    
    
    Drop U, pw, dK, dN, K
    
    Store email-address, s, eN and vH in log-in database

    #======================
    # (On Log-In Request)
    #======================
    Code:
    Ask client for username (U) and password (pw)
    
    Generate Password-Hash (dK) using a secure hash function
    
      U  = username
      pw = password
      W  = website
      s  = salt
      i  = 4096 iterations
      dK = derived key
      
      dK = F( SHA-1( SHA-1(s || pw) || U || W || s) ... , i )
    
    
    Decrypted Nonce-Hash (dN)
    
      dN = XOR(eN, dK)
    
    
    Generate client key (K) using stream cipher
    
      i = 65535 iterations
      K = client Key 16384 byte random value
      
      K = streamCipher( dK || dN, K, i )
    
    
    Build verification hash (vH') for comparison from client key (K)
    
      vH' = SHA-1(K)
    
    
    Compare vH == vH'
    
    Drop U, pw, dK, dN, K, vH'
    Additionally any system-wide parameter other than the domain name can be introduced in the hash function or the stream cipher process which is not stored in the database alongside the email-address.




    #======================
    # Hacker get Login-DB
    #======================

    ... and now has salt, encrypted nonce and verification hash of client key (s, eN, vH) for each email-address.

    Clearly he need to build a Password-Hash (dK) mounting a brute-force/dictionary-attack, decrypt dN and than generate some K in order to find the proper hash vH of that K. If he succeed he now know username (U) and password (pw) for this user at this special website only. And regarding my current knowledge it is useless to store these information in some kind of dictionary for future attacks. Also I believe that no binary relationship between username (U), password (pw) and final hash (vH) can be observed.

    All this will slow down such attacks in my opinion. If we can pass the costly calculation to the client is possible to stretch each step even more and reduce the occurrence of remote attacks on website log-ins.

    Of course nothing can withstand a brute-force attack on the username and password with unlimited resources, so only a slow down can be achieve by any solution for the time being.
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    51
    Rep Power
    55
    Originally Posted by OmegaZero
    Hacker (having received a compromised copy of the database) knows K2.

    Hacker makes a log in request receiving eDN, s and RH.

    Hacker chooses his favorite number finds a value with a SHA-1 hash of KH and calls it K1'

    Hacker then computes R = (K1' || K2) xor RH and sends R and K1' to the server.

    The server computes KH' = SHA-1(K1'). K1 and K1' have the same hash, so KH = KH' and the server accepts K1' as K1.

    The server computes R' = (K1 || K2) xor RH.

    But the server is trusting the value of K1 sent by the hacker, which is really K1', so R' = (K1' || K2) xor RH = R and the login is granted.

    Hacker then changes the e-mail address and resets the password.

    Hacker laughs at security system that trusts a random person someone on the internet to do its crypto for it.

    Total cost to hacker: Finding 1 SHA-1 collision (i.e. much cheaper than finding a bcrypt collision).
    You're right so far, but how easy is it in practice finding hundreds of thousands of matching SHA-1 collisions?


    Originally Posted by OmegaZero
    What I'm trying to say here isn't "Here's a problem to fix", but "See how easily you missed that". If you roll your own algorithms you're likely to miss something. Good crypto is hard and must be thoroughly analyzed to have a chance at being secure. I don't doubt if you keep on adding bells you can create a version that I can't break at first glance, but to be secure you need to beat the people who are orders of magnitude beyond me and who have months to study your algorithm. There are solid algorithms out there; prefer them over homegrown crypto.

    (Updated to attack the latest iteration of the algorithm--hopefully this reinforces the point)
    And now imagine changing SHA-1 against SHA-256, how easy will it be to mount your proposed attack now?

IMN logo majestic logo threadwatch logo seochat tools logo