Encryption Safety & Collisions

[Mau]

DRAFT

If you have ever used an encryption hashing algorithm--such as MD5 or SHA1--before, you will have noticed that the number of characters in the output are constant. You find this as a good thing: it's impossible to guess to the original length; and you can store it in a database and know exactly how long it will be. But, with all good things, come the bad. In this case, the bad is something called "collisions."

Collisions are simple: the mean that two or more inputs can have the same output. If you have ever studied parabolas in math, then you know how collisions can be interesting.

Collisions are a bigger problem when dealing with passwords and encryptions. The common way of storing a password is by encrypting it by MD5; when the user logs in, check it with the hash. While this is usually effective, it can cause problems. Remember that collisions exist in hash functions--that means that there is another phrase (and infinite amount of phrases) out there that will generate the exact same hash. What does that mean? Well, it means that you just have a lot of passwords to choose from!

So, why am I telling you this? Although finding a collision is quite hard, it can be magnified. Take this for an example: say the output is abcdefg. Now, let's say that 123 and 987 will both produce abcdefg when ran through the MD90000 function. This means that a user may enter 123 or 987 into the password field and be authenticated. The PHP code:

 $hash = md90000('123');
$hash2 = md90000('987');
// hash = hash2 
  

Now, let's say that we want to be even more secure. We know that 123 becomes abcdefg, and we also know that running abcdefg through the hash function will produce qwertyu. Nevertheless, poiuytr will ALSO produce qwertyu. So, at first glance we decide to do:

 $hash = md90000(md90000($pass)) 
  

Do you know the problem? I will do my best to illustrate:

123 will become abcdefg,which will become qwertyu.
987 will become abcdefg, which will become qwertyu.

Now, we can also say:
456 will become poiuytr, which will become qwertyu.
789 will become poiuytr, which will become qwertyu.

Now do you see the problem? By running our password through the encryption twice, we have just doubled the number of collisions possible. We run it through it a third time, and it increased by 6x. Do it a thousand times, and pretty much everything would equal the hash.

The lesson here: do not encrypt an encryption hash. While you may think it protects you against brute forces, it creates many more collisions.

What about doing something like:

 $hash = sha1(md5($pass)); 
  

Still a bad idea; md5 and sha1 both have collisions, and you are still doubling the amount of them.

So what can you do? You can combine encryptions, which will reduce collisions:

 $hash = sha1($pass).'-'.md5($pass).'-'.encrypt($pass); 
  

While two passwords may produce the same MD5 result, they are unlikely to produce the same result in SHA1 too. Thus, that collision was destroyed.

In brief:

 $hash = md5(sha1($pass)); // BAD
$hash = md5($pass).'-'.sha1($pass); // GOOD 
  

[_jameshales]

Nice. I'll be using that advice in future. It makes perfect sense and you explained it very well. Thanks.

How likely is it that there are collisions in MD5 hashes though?

_jameshales

[Mau]

How likely is it that there are collisions in MD5 hashes though?

Impossible to answer that without having a constraint in how long the input can be. :-) Remember, there are an infinite amount of inputs that will give the same output.

You may find this of interest:
http://www.stachliu.com.nyud.net:8090/md5coll.c (C code to find MD5 collisions)

[Diagmato]

whoa! I thought md5 hashes cant be the same, at all. E.g, qwerty would have a far different hash than qweety (for example). unless ive badly misread :s.

[Mau]

The examples I gave were using an imaginary function, but that function would do something very similar to regular MD5.

If you think about: MD5's produce the same length output all the time. But, there is no restriction on the input length. IE: my 8 page essay could have the same hash as the letter A.

[Vouksh]

Yes, but also, if you do something like you stated above,

 $hash = sha1($pass).'-'.md5($pass).'-'.encrypt($pass); 
  

the hacker could see that it's encrypted several ways. all he has to do is look up the # of characters, and run each part through the encryption.
but with

 $hash = md5(sha1($pass)); 
  

you'll get a 32 character string, and from there, the hacker would think MD5. so he runs it through the MD5 collision program. he has to wait weeks or months before he gets the 40-something character hash that is produced. then the hacker would have to grab his sha1 cracker, and try to find a collision for that. I asked my dad (who's been a hacker all his life) to try to decrypt my password after being run through md5(sha1()). he left his computer on for days, and didn't even have a single DIGIT/CHARACTER.

Sorry to burst your bubble a bit mau, but your right in some ways, but wrong in others.

NEVER run a hash through the same function that hashed it, as, like mau said, it will increase the chances of being able to be cracked.

[Mau]

I completely disagree. You should never let anyone get a hold of the password hashes. If that happens, I would check your database settings, server settings, or whatever holds your passwords. Once this happens--sure, my method may not take as long to crack. The key point here is that both will be cracked if the hashes are given out--there is no way around it.

But, the fact is, hashes are rarely given out. And if they do, they are usually non-sensative information such as just some temporary ID. Passwords for never be stored in cookies for exactly this reason (sessions are better).

My method will protect against brute forcing using your system. For example, you could try to login to my vBulletin account by trying every single combination. Or, you could try to crack the MySQL server that runs on the backend. What is more likely? Cracking the MySQL server would be quite hard, and in the end, probably impossible.

[NuWeb]

Eaither way does not matter. Just make sure your server is secure, dont use the same password for your account as you do for everythign else (not even in ur config files) ..

Then no one will get your passwords from your database, as only you have access to them.

..
ALSO, if a person wants your password, like on this forum, or any other forum (note, that this can be done on any script,where you can view sorce). They take the input,

 $password = $_POST[password]; 
  

and they change it, before it gets md5'd or anything to:

 $password = $_POST[password];
$nonmd5password = $password; 
  

Then just scroll down, to where the data is put in the databse, and create a sepearate row, and input it.
---
Basicaly, encription is pointless.
It is only good, to slow hackers down a bit.

[Mau]

In my personal opinion, I think you should always hash or encrypt your passwords. There is always a chance that somebody *could* break in to your database. As long as you have a hash, it gets hard for the person to decode everything instantly.

Regarding your example, I never code like that way, and I doubt that this forum does something similar (I can look at it if you really want me to). The best way is to do this:

 $password = $_POST['password'];
unset($_POST['password']);
$password = encrypty_do_bobber($password);

/* Now we are going to output
every variable, and the password
is no where to be found. */

print '<pre>';
print_r($GLOBALS);
print '</pre>'; 
  

:)

[callumjones]

When this is sorted out, I think this would be a great wiki tutorial.