Page 1 of 3 123 Last
  • Jump to page:
    #1
  1. It's only wrong if you're caught....
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Dec 2003
    Location
    Sydney, Australia
    Posts
    1,286
    Rep Power
    174

    Hashing Algorithms


    Hi guys,

    Anyway a bit of backstory to what I'm going to try and say here first:

    A few days ago (or was it yesterday, I can't remember) me and a friend found a rather large site which stored md5 hashes of the user's password in cookies, anyway other than this being bad practise it got me thinking, how did I notice it? Simple; md5 hashes are fairly distinct, and even SHA hashes are rather distinct in what their output looks like so using that family wouldn't have helped much, and so since these hashes are all fairly distinct and many people already have extremely extensive rainbow tables for all these hash functions it might as well have been plaintext to us, now here's an idea I would think *may* help throw some people off:

    If we were to use keyed hashing functions instead of unkeyed, this would make problems such as these infinitely more difficult to solve. Now it sounds much simpler than it is, firstly if you're using a constant key for all users, then it would only really be effecive if the user cannot find a hash of a given string, if they can then they can try all keys which would give the results of the resulting hash when hashing the actual password, and then the cracker would have your key anyway, and it would only have added a single amount of cracking time to obtain the key, and from this point onwards it may as well be an unkeyed hash function....On the other hand if you do something that depends on something like a username, then if your method of constructing a key from a username seed was conprimised, it may as well be an unkeyed one again...And then you could simply have a hash that is stored, and you simply generate a random key that isn't dependant on anything for each user and store it, we can assume since that if the cracker has the hashes (we're talking about a system that hasn't been poorly coded, and so to get the hash the cracker had to gain access to either your server, or your database server) then s/he also has the list of keys, so the only real solution to the probelm of having the keys that has occured to me (its not without its problems, and needs; great needs) is to have the user have 2 passwords, and 2 hashes would be stored, fthe first hash would be the first password hashed using the second password as a key, and a secon hash which is done in reverse, now this is probably not the best method, and it would have to generate fairly large hashes to avoid collisions, though thats the idea of storing 2 hashes, I'm not sure wether that would make it tronger or weaker, but anyway you'd have to have a large hash being outputted anyway to stop collisions....

    Now these are just my ideas so yeah, if anyone has any better I'd love to hear them....

    P.S. This whole idea of using a keyed hashing function stemmed from the fact that hashing functions these days are so easily identifiable, and as there are only a very small amount of them, so its quite pheasible for people to have rainbow tables for all the more secure ones, since the less secure ones could be broken much more easily, wel you get the idea....

    [EDIT]: Ok, I decided to edit this before some smart*ss decided to raise this point, I understand that rainbow tables don't contain all values, but the more common ones, and special passwords can defend against this, but on the other hand they'll get most of them, and I'm talking about application security, not making your users use overly complex passwords, its what you can do as a developer, not what you can force down your user's throats.....
    Last edited by kuza55; October 23rd, 2005 at 02:11 AM.
  2. #2
  3. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2005
    Location
    Perth, Western Australia
    Posts
    6
    Rep Power
    0
    I think that there already are some "keyed hashes" out there. I believe that I used to use one for my web apps long ago, before switching to MD5. In PHP, the function crypt(), where you supply the string, and a "salt", which is like a key, for example. When generating hashes for user password for example, I'd run crypt on the username, using the password as a salt, then use the resulting hash as the salt to hash the password.

    _jameshales
  4. #3
  5. It's only wrong if you're caught....
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Dec 2003
    Location
    Sydney, Australia
    Posts
    1,286
    Rep Power
    174
    Originally Posted by _jameshales
    I think that there already are some "keyed hashes" out there. I believe that I used to use one for my web apps long ago, before switching to MD5. In PHP, the function crypt(), where you supply the string, and a "salt", which is like a key, for example. When generating hashes for user password for example, I'd run crypt on the username, using the password as a salt, then use the resulting hash as the salt to hash the password.

    _jameshales
    yeah, i've used crypt before as well, but the problem with it is its not all that long, since the keys won't be that long, since they're usernames...., and also the only thing that hashing the username using the password as salt does it make sure people cant use rainbow tables, but yeah, this is just theoretical ways to make things more difficult....
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2005
    Location
    North of the 49th Parallel
    Posts
    28
    Rep Power
    0
    Out of curiosity, what algorithm does crypt() use? I'm not a PHP guy, so I honestly don't know.

    However, if I understand you correctly, you want to do this:

    output1 = h( salt + username1 )
    output2 = h( output1 [as salt] + username2 )

    where h() is a cryptographic hash function.

    Personally, I'd rather do this:

    output1 = SHA1( salt1 + username )
    output2 = RIPEMD160( salt2 + username )

    because no user will actually remember two usernames. Two hash algorithms reduce the chance that someone is going to get lucky with the username, especially given the recent attacks on SHA1.

    If I have totally misunderstood you, kindly correct me
  8. #5
  9. Crypto-Con
    Devshed Supreme Being (6500+ posts)

    Join Date
    Apr 2004
    Location
    Frisco, Texas
    Posts
    6,704
    Rep Power
    1236
    You're right on track, kuz. This is indeed a problem, and is usually solved by using salts.

    The biggest problem with salts, as you pointed out, is how you can securily save them. If the salts are comprimised, then the only thing left for them to protect against is pre-compiled hash dictionarys (aka, rainbow tables). However, if the salt is kept secret, it works more like a key and protects against BF attacks as well.

    Obviously, using a private salt/key would be preferable. But how can a key be stored such that if the hash db is broken into, the keys are not stolen as well?

    Personally, I would recommend just using a seperate key for each user, and then also using the users password itself as a form of key. Asking the user to remember two passwords is fine, if you're at the NSA. If you're dealing with average Joe Schmoe, you're lucky if they can remember just one password. By creating an algorithm that takes the user's password and manipulates it in some fun and interesting ways, you can create a final result that then gets combines with the salt and hashed.

    Obviously, the password minipulation algorithm itself must be kept secret, but if the attacker does not know that such a process even existed (say it was a custom hack to VB), they would be unaware that they needed to grab it as they were looking around for stuff to steal.

    Comments on this post

    • ranjangoyal agrees : I don't understand much abt security and ur link will help to understand this. Thanks
    - "Cryptographically secure linear feedback shift register based stream ciphers" -- a phrase that'll get any party started.
    - Why know the ordinary when you can understand the extraordinary?
    - Sponsor my caffeine addiction! (36.70 USD received so far -- Latest donor: Mark Foxvog.
    )
  10. #6
  11. It's only wrong if you're caught....
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Dec 2003
    Location
    Sydney, Australia
    Posts
    1,286
    Rep Power
    174
    Ok, firstly at B-Con's post: Thanks for the linky, the one thing I think you're missing in there is if you have a private salt, but the attacker knows the algorithm which you use (say s/he knows you're using crypt() with a salt) and the user knows a single password with its resulting hash the s/he could brute-force the key, and so that was what I'm trying to find away around, the fact that in any public sign-up systems, or any system which the attacker has an attacker on the inside of, no matter how low, as long as they have a password, and s/he can obtain the hash, then the private hash will be just as trivial as a public hash....

    Now having a hash salt based on the password is rather pointless since, an attacker can simply mod their brute forcer to alter the password (I'm assuming pretty much all worst case scenarios) to make the salt based on the password as well, how, either obtain the actual code, or get a couple of passwords and their hashes, brute force the hashes and do some analytical work on finding the method of how you generat the salts and there you go, back to square one for you, and the attacker can simply go on as if you never had any salts, the same goes for usernames, since you're breaking username/password combos, not just th hashes alone....Now this method would provide a bit more security of private salts since an attacker woldn't be able to use pre-made rainbow tables, but I think it is still entirely reasonable that the attacker will gain access to a few accounts, probably the ones with the highest privelages.....

    So yeah, the only thing I've been able to think of that would make it harder for the attacker would be 2 password...

    Also, I'm not 100% sure how salts work, are the characters in the salt simply shoved in between the characters of the password? if so thats not actually what I meant, I meant a keyed hashing algorithm, where the salt that I've talked about in this post is the key, because then the 2 password method would actually work quite well, because the ideal algorithm would be one that produces the possibilities of SHA-512, but accepted a key so it would be exponentially difficult to find the key, since the hashes are both dependant, and not independant so the amount of work would be O(n^2) not O(2n), because the problem with salts is that you will still be able to brute force to find what the salted string is, here that would be impossible....

    @Quantumn Skyline; I'll wrote more about this when i get to school, since I need to go have breakfast in a minute, but anyway, though I did acknowledge crypt(), it isn't really what the ideal function would be, I'd prefer something like:
    h (password1, password2)
    where in that case password 1 is the string, and password 2 is the key, and the key would somehow alter he function, but the function would still remain a hashing algorithm......

    The reason I suggested the 2 password system is because it would robably take something along the lines of O(n^2) operations, where n is the normal amount to crack a hashing algorithm where there is no key, since you don't know either the password or key, so you would have to try: h(asc(1), asc(1)), h(asc(1), asc(2)), h(asc(2), asc(1)).....etc, etc, because there is no pheheasible length of characters which would single an end, err, I'm not sure how to explain it, but what would have to be written would be similar to a breadth based search, well sorta anyway...

    And the reason I say it would need to be fairly long is that an attacker can control both x and y in h(x, y), and you'd need to be sure that there is no possible combination c and d where h(x, y) == h(c, d), unless x =< c && y<= d, in which case it wouldn't matter because you'd hit x and y first anyway....

    And now I have to go to school, bleh, but I want to re-emphasise that this is an ideal security system, so lets pretend the users are at the level of the NSA....
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2005
    Location
    North of the 49th Parallel
    Posts
    28
    Rep Power
    0
    OK, I get it now.

    The thing that gets me is ... I don't know any hash functions that take two inputs. It sounds like you want a message authentication code - something that uses a hash function and a secret key.
  14. #8
  15. (retired)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Dec 2003
    Location
    The Laboratory
    Posts
    10,101
    Rep Power
    0
    The whole point behind salting is to defeat ( or make much harder ) brute force attacks. So - if your user has the password "secret" ( and most of them will have simple dictionary words ), then all the attacker has to do is run through her rainbow tables until it hits the hash of "secret". Salting it, however, would do something like md5( 'salt'+'secret' ) which immediately makes a dictionary attack pointless. The idea is that you have multiple salts, preferably one for each user. You do need to make sure that you're not re-salting any incoming passwords or you're wasting your time.

    It will NOT save you if your attacker has access to the database.

    This is why it's always necessary ( especially for web apps. ) to have a log-in time limit ( i.e. 5 login attempts gets the account closed for 30 minutes or something ) to help stop this.

    Quantum Skyline: PHP's crypt() uses the standard UNIX DES (libcrypt?) by default, but can also take advantage of other installed libraries like blowfish etc.

    --Simon

    Comments on this post

    • M.Hirsch agrees
  16. #9
  17. It's only wrong if you're caught....
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Dec 2003
    Location
    Sydney, Australia
    Posts
    1,286
    Rep Power
    174
    Originally Posted by SimonGreenhill
    It will NOT save you if your attacker has access to the database.
    Yes, the idea of my idea above is to make it more difficult for people to gain access if they have read access to the database, because if they can change values then its stuffed right there, so yeah, I'm just putting an idea forward to see what others think.......

    Originally Posted by SimonGreenhill
    This is why it's always necessary ( especially for web apps. ) to have a log-in time limit ( i.e. 5 login attempts gets the account closed for 30 minutes or something ) to help stop this.
    Yep, but it a person has read access to the database, and know how the hashes are computed they can crack it off-site......

    So yeah, I was just wondering what people thought of the idea, the theory at least, because I know of no functions (if I'm wrong, please tell me) which would work like the one I described above, and I also forgot to say that you should store 2 hashes h(x, y) and h(y, x) to make it harder for people to brute force the hashes, so that collisions wouldn't occur earlier than the actual password.....
  18. #10
  19. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,593
    Rep Power
    4207
    The security of the hash function is the large # of possible hashes. A lookup dictionary for all possible words with all possible salts is going to be extremely large indeed. By the way, the master.passwd file on most *nix systems is only readable by root, so if anyone can read it, they've already got root on the box.

    By the way, what's wrong with the salt approach that they outlined above?
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  20. #11
  21. Crypto-Con
    Devshed Supreme Being (6500+ posts)

    Join Date
    Apr 2004
    Location
    Frisco, Texas
    Posts
    6,704
    Rep Power
    1236
    Originally Posted by kuza55
    So yeah, the only thing I've been able to think of that would make it harder for the attacker would be 2 password...
    Yes, aside from two-factor authentication, that is basically the only option. The problem, though, is how to store the two passwords. Stringing them together like hash('pwd1' + 'pwd2'), as simple as it sounds, is one of the better options.

    Also, I'm not 100% sure how salts work, are the characters in the salt simply shoved in between the characters of the password?
    Yeah, basically. It's up to the sysadmin were to stick the salt (which is why salts's contain two values, really: what to append, and where to append it).

    if so thats not actually what I meant, I meant a keyed hashing algorithm, where the salt that I've talked about in this post is the key, because then the 2 password method would actually work quite well, because the ideal algorithm would be one that produces the possibilities of SHA-512, but accepted a key so it would be exponentially difficult to find the key, since the hashes are both dependant, and not independant so the amount of work would be O(n^2) not O(2n), because the problem with salts is that you will still be able to brute force to find what the salted string is, here that would be impossible....
    I think you're underestimating the difficulty of BFing a salt. Assuming that you don't know where the salt was inserted, you have a very, very difficult task ahead of you. Finding both the value and location(s) of the salt is not a task for the faint of heart

    Could you define more clearly how you draw the line between a salted hash and a keyed hash? It's getting difficult to find that line.

    Also, you might be interested in HMAC.

    I also forgot to say that you should store 2 hashes h(x, y) and h(y, x) to make it harder for people to brute force the hashes, so that collisions wouldn't occur earlier than the actual password.....
    Storing two hashes of the two passwords in different combinations makes no difference. Once they BF the first (finding x+y), they have the input (y+x) to the other, and the only problem for them is figuring out how to break the password up into the X and Y sections, which is trivial because there aren't that many combinations.
    - "Cryptographically secure linear feedback shift register based stream ciphers" -- a phrase that'll get any party started.
    - Why know the ordinary when you can understand the extraordinary?
    - Sponsor my caffeine addiction! (36.70 USD received so far -- Latest donor: Mark Foxvog.
    )
  22. #12
  23. It's only wrong if you're caught....
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Dec 2003
    Location
    Sydney, Australia
    Posts
    1,286
    Rep Power
    174
    Ok, firstly: sorry for taking so long to reply, that was mainly because I haven't had much time lately, and I also couldn't remember my reasoning....

    Originally Posted by B-Con
    Yes, aside from two-factor authentication, that is basically the only option. The problem, though, is how to store the two passwords. Stringing them together like hash('pwd1' + 'pwd2'), as simple as it sounds, is one of the better options.
    while reading about an attack on ORACLE password hashes (http://www.sans.org/rr/special/index.php?id=oracle_pass) I remembered one of the things I was thinking of before, if you did a simple appendage (some people may/may not use it, I don't know but doing something that simple does have a vulnerability) if your first password was 'password1' and your second password was 'password2' then the following combination: 'password' '1password2', would generate the same hash, now this shouldn't be too much of a problem, but its one that exists....


    Originally Posted by B-Con
    I think you're underestimating the difficulty of BFing a salt. Assuming that you don't know where the salt was inserted, you have a very, very difficult task ahead of you. Finding both the value and location(s) of the salt is not a task for the faint of heart
    Either is obtaining the password hashes in the first place, and if you are able to get some hashes where the values are known I'm pretty sure that someone who is slightly skilled will be able to compute the salt....

    Originally Posted by B-Con
    Could you define more clearly how you draw the line between a salted hash and a keyed hash? It's getting difficult to find that line.

    Also, you might be interested in HMAC.
    Thanks for the linky, thats what I was pretty much thinking of, and where do you draw the line? Well a salted hash is one where you simply insert a salt, (duh) but a keyed algorithm would be one where there would be some kind of switches (I could blather on about the acta algorithm but It'd probably be nonsensicle drivel, which would be insecure anyway, :P) inside it depending on the key....


    Originally Posted by B-Con
    Storing two hashes of the two passwords in different combinations makes no difference. Once they BF the first (finding x+y), they have the input (y+x) to the other, and the only problem for them is figuring out how to break the password up into the X and Y sections, which is trivial because there aren't that many combinations.
    I may have been unclear, I only meant that storing 2 hashes then it'd be much more difficult to find h(c, d) which is equal to (x, y) and where h(d, c) is equal to h(y, x), but I'm probably just not putting enough faith in the actual algorithms.....

    I think I posted this topic more to stimulate some kind of discussion than anything else, 'cos this place is feeling rather empty....

    Comments on this post

    • B-Con agrees : Good link :)
  24. #13
  25. Crypto-Con
    Devshed Supreme Being (6500+ posts)

    Join Date
    Apr 2004
    Location
    Frisco, Texas
    Posts
    6,704
    Rep Power
    1236
    Originally Posted by kuza55
    while reading about an attack on ORACLE password hashes (http://www.sans.org/rr/special/index.php?id=oracle_pass) I remembered one of the things I was thinking of before, if you did a simple appendage (some people may/may not use it, I don't know but doing something that simple does have a vulnerability) if your first password was 'password1' and your second password was 'password2' then the following combination: 'password' '1password2', would generate the same hash, now this shouldn't be too much of a problem, but its one that exists....
    Excellent point. I forgot to mention one *critical* little detail: The passwords would have to be seperated by a constant character. It doesn't matter if it's just one character, or an entire string, and it doesn't have to be kept private. Thus, you would actually be storing hash(pwd1 + some_char + pwd2)

    Either is obtaining the password hashes in the first place, and if you are able to get some hashes where the values are known I'm pretty sure that someone who is slightly skilled will be able to compute the salt....
    A good salt will have a potential charset range of ~96, and will be at least 6 characters long. Given the fact that, on the average 5 letter word, there are about 5*4*3*2*1 simple ways to add the salt in two different locations. BFing it would be result in a O(n^(n/2)) time complexity. And the saver could be mean and use two different salts. [/quote]

    I agree, it could be found, and if your adversary is the NSA, I would bet that it would be found with ease. Assuming your adversary is not a state-of-the-art spy agency, however, its practically safe enough.

    [quoteI may have been unclear, I only meant that storing 2 hashes then it'd be much more difficult to find h(c, d) which is equal to (x, y) and where h(d, c) is equal to h(y, x), but I'm probably just not putting enough faith in the actual algorithms.....[/quote]
    I get what you're saying. If, during their attack, the attacker finds an X,Y that hash to the first hash stored in the db, and that X,Y are the user's origonal X,Y passwords, then breaking the second stored hash is trivial.

    However, if the attacker's X,Y are NOT the origonal passwords, then Y,X will not hash to the same second stored hash. Thus, storeing both hashes basically disallows for finding collisions.

    I think I posted this topic more to stimulate some kind of discussion than anything else, 'cos this place is feeling rather empty....
    It's a good discussion, and this forum needs all the activity it can get
    - "Cryptographically secure linear feedback shift register based stream ciphers" -- a phrase that'll get any party started.
    - Why know the ordinary when you can understand the extraordinary?
    - Sponsor my caffeine addiction! (36.70 USD received so far -- Latest donor: Mark Foxvog.
    )
  26. #14
  27. It's only wrong if you're caught....
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Dec 2003
    Location
    Sydney, Australia
    Posts
    1,286
    Rep Power
    174
    Well, lets put it this way:

    People have huge botnets they use for DDoSing servers, what if they put those same botnets to work cracking hashes (or creating TSTO tables, whatever floats your boat), then you're considerably screwed, are you not?

    So yeah, also; I meant storing the 2 hashes h(x, y) and h(y, x) not hashes of x and y seperately.....
  28. #15
  29. Crypto-Con
    Devshed Supreme Being (6500+ posts)

    Join Date
    Apr 2004
    Location
    Frisco, Texas
    Posts
    6,704
    Rep Power
    1236
    Originally Posted by kuza55
    People have huge botnets they use for DDoSing servers, what if they put those same botnets to work cracking hashes (or creating TSTO tables, whatever floats your boat), then you're considerably screwed, are you not?
    True.

    On that note, you might be interested in reading on the Chinese Lottery.
    - "Cryptographically secure linear feedback shift register based stream ciphers" -- a phrase that'll get any party started.
    - Why know the ordinary when you can understand the extraordinary?
    - Sponsor my caffeine addiction! (36.70 USD received so far -- Latest donor: Mark Foxvog.
    )
Page 1 of 3 123 Last
  • Jump to page:

IMN logo majestic logo threadwatch logo seochat tools logo