Pernambuco

[sh_code]

@PJH said:

@SEMI-HYBRID code said:

...doesn't using a salt only creates another md5 to which you can find a collision string?

Yes. That's the whole point of a salt - to produce a different hash. Using a different salt for each user means that everyone who uses password123 as their password, for example, ends up with a different hash in your password database, whereas unsalted, they would all have the same hash of 482c811da5d5b4bc6d497ffa98491e38. @SEMI-HYBRID code said:

...do you salt before creating a hash, or after?

Usually before.

 

 

oh, different salt for every user, that makes some more sense (but still,how do you/where do you store the salt itself? if it's in db in each user's record, then it's just pointless. and even if it wouldn't be visible, all it does is that every password needs to be cracked individually (even when two or more are the same), but the chance/time to find collision for each one doesn't change...?

[Xyro]

Salts are to render precomputed hashes useless, not to prevent collisions. Assuming the crypto algorithm has uniform domain (and it should), the risk of collision is fixed to the size of the key; nothing can change that.

Question for salt people who know what they're talking about: is using the username as the salt a bad idea? Specifically, would running the hash algorithm on a literal concatenation of username+password any better or worse than a randomly-generated salt? I'm thinking... if the database would be compromised, the leaked information would potentially be the same; but if the internals of the password protection mechanism was known, then passwords could start being brute-forced even without the stolen database... So maybe it is a bad idea, humm..

[PJH]

@SEMI-HYBRID code said:

but still,how do you/where do you store the salt itself? if it's in db in each user's record, then it's just pointless. and even if it wouldn't be visible, all it does is that every password needs to be cracked individually (even when two or more are the same), but the chance/time to find collision for each one doesn't change...?

It is indeed, usually, stored in the same record as the hashed pass+salt. It just forces the cracker to go through their dictionary of words for each individual user, rather than just having to do it once for the whole DB if they all used the same salt, or not even bother if there wasn't a salt by using a rainbow table.

[sh_code]

@dhromed said:

@SEMI-HYBRID code said:

...doesn't using a salt only creates another md5 to which you can find a collision string?

 

OK, here's the thing.

1. You have passwords.

2. Database stolen? => You're fucked

3. Hash them!

[...snip...]
Point 4 and further become meaningless once the hash algorithm and hardware are fast enough. Bruteforcing becomes a viable option. Even worse when the hash algo is broken, because then the attacker doesn't even have to burteforce it.

 

 

the best security quicktut evAr!

 

<offtopic what="cs is funny">i thought that the double-char delete on backspace is just a simple bug, but turns out... it's got its own complexity/beauty. 

1. white something, press right arrow - there is a space you did not write.

2. backspace, deleted two characters.

3.right arrow, again a space you didn't write, backspace, again, two char delete.

4.write something, ending with space, backspace, only one char (your space) gets deleted.

5. write something, press right arrow to move after the space you didn't write, press any character -> the character is appended to your last word (replaces the "fictious" space char)

6. write something ending in two spaces, press backspace, only one gets deleted.

7. the two-char delete occurs when cursor is behind the "fictional" space that cs for some reason adds/has on the end of your text, which is usually just after the cursor,

8. omg funniez, why is the space added there? and why it behaves like it behaves? i wanna know!

</offtopic>

 

[Xyro]

@SEMI-HYBRID code said:

6. write something ending in two spaces, press backspace, only one gets deleted.

what... in... blue... blazes...

Well this is why I've broken down and switched to the write-your-own-damn-HTML editor mode. Since then, my HTML tag typing skills have improved over 29%!!

[The_Quiet_One]

@Xyro said:

Since then, my HTML tag typing skills have improved over 29%!!

 

That's almost 30%!

[pjt33]

@Xyro said:

@SEMI-HYBRID code said:

6. write something ending in two spaces, press backspace, only one gets deleted.

what... in... blue... blazes...

Well this is why I've broken down and switched to the write-your-own-damn-HTML editor mode. Since then, my HTML tag typing skills have improved over 29%!!

The crazy thing is that even in the HTML editor the quote stuff is still in whatever bastardised phpbb-derived syntax the forum software uses.

[blakeyrat]

@pjt33 said:

@Xyro said:

@SEMI-HYBRID code said:

6. write something ending in two spaces, press backspace, only one gets deleted.

what... in... blue... blazes...

Well this is why I've broken down and switched to the write-your-own-damn-HTML editor mode. Since then, my HTML tag typing skills have improved over 29%!!

The crazy thing is that even in the HTML editor the quote stuff is still in whatever bastardised phpbb-derived syntax the forum software uses.

I'm actually anal-retentive enough to remove the mysterious extra paragraph tags and randomly-placed non-breaking spaces from quotes, when I quote people. I know, I have a problem, I need therapy...

For example, this software interprets a QUOTE bbcode tag as the beginning of a paragraph, so you don't need a paragraph tag inside it... yet it always puts a paragraph tag inside it. Ditto with /QUOTE. So you quote a single sentence, and it turns into like 3 separate paragraphs for no reason.

As for the non-breaking spaces, I don't have the imagination to come up with a plausible reason why that bug exists.

[Xyro]

@blakeyrat said:

I'm actually anal-retentive enough to remove the mysterious extra paragraph tags and randomly-placed non-breaking spaces from quotes, when I quote people. I know, I have a problem, I need therapy...

Nah, I do the same. I mean, you may need therapy, but not for this. You and I at least share in common an extreme attention to detail, and that is a trait no one should ever try to take away.

[serguey123]

@Xyro said:

@blakeyrat said:

I'm actually anal-retentive enough to remove the mysterious extra paragraph tags and randomly-placed non-breaking spaces from quotes, when I quote people. I know, I have a problem, I need therapy...

Nah, I do the same. I mean, we need therapy. You and I at least share in common a bit over the standar attention to detail, and that is a trait that is good in moderation.

FTFY 

Too much of anything is bad for you

Also what is wrong with the tags or it is just me?

[boomzilla]

@Xyro said:

@blakeyrat said:

I'm actually anal-retentive enough to remove the mysterious extra paragraph tags and randomly-placed non-breaking spaces from quotes, when I quote people. I know, I have a problem, I need therapy...

Nah, I do the same. I mean, you may need therapy, but not for this. You and I at least share in common an extreme attention to detail, and that is a trait no one should ever try to take away.

Yeah, plus all the extra <br> tags that you get. I also like to get the quote tags all on their own lines to make it easier to see what's going on.

[PJH]

@boomzilla said:

@Xyro said:

@blakeyrat said:

I'm actually anal-retentive enough to remove the mysterious extra paragraph tags and randomly-placed non-breaking spaces from quotes, when I quote people. I know, I have a problem, I need therapy...

Nah, I do the same. I mean, you may need therapy, but not for this. You and I at least share in common an extreme attention to detail, and that is a trait no one should ever try to take away.

Yeah, plus all the extra <br> tags that you get. I also like to get the quote tags all on their own lines to make it easier to see what's going on.

... just piping up as another who deletes the tag-soup in the plain editor that CS decides it simply must insert to no useful effect (and the quote stuff if I start deleting bits of it.)

[dhromed]

@PJH said:

@boomzilla said:

@Xyro said:

@blakeyrat said:

I'm actually anal-retentive enough to remove the mysterious extra paragraph tags and randomly-placed non-breaking spaces from quotes, when I quote people. I know, I have a problem, I need therapy...

Nah, I do the same. I mean, you may need therapy, but not for this. You and I at least share in common an extreme attention to detail, and that is a trait no one should ever try to take away.

Yeah, plus all the extra <br> tags that you get. I also like to get the quote tags all on their own lines to make it easier to see what's going on.

... just piping up as another who deletes the tag-soup in the plain editor that CS decides it simply must insert to no useful effect (and the quote stuff if I start deleting bits of it.)

 

Why bother?

[derula]

@boomzilla said:

@Xyro said:

@blakeyrat said:

I'm actually anal-retentive enough to remove the mysterious extra paragraph tags and randomly-placed non-breaking spaces from quotes, when I quote people. I know, I have a problem, I need therapy...

Nah, I do the same. I mean, you may need therapy, but not for this. You and I at least share in common an extreme attention to detail, and that is a trait no one should ever try to take away.

Yeah, plus all the extra <br> tags that you get. I also like to get the quote tags all on their own lines to make it easier to see what's going on.

What, nothing more? I also indent them properly, and set my actual post one line apart from the quote block to make it look extra-pretty.

[blakeyrat]

@derula said:

@boomzilla said:

@Xyro said:

@blakeyrat said:

I'm actually anal-retentive enough to remove the mysterious extra paragraph tags and randomly-placed non-breaking spaces from quotes, when I quote people. I know, I have a problem, I need therapy...

Nah, I do the same. I mean, you may need therapy, but not for this. You and I at least share in common an extreme attention to detail, and that is a trait no one should ever try to take away.

Yeah, plus all the extra <br> tags that you get. I also like to get the quote tags all on their own lines to make it easier to see what's going on.

What, nothing more? I also indent them properly, and set my actual post one line apart from the quote block to make it look extra-pretty.

I print out all my posts and snail-mail a copy to the US Copyright Office. So there.

[Scarlet_Manuka]

@PJH said:

@boomzilla said:

@Xyro said:

@blakeyrat said:

I'm actually anal-retentive enough to remove the mysterious extra paragraph tags and randomly-placed non-breaking spaces from quotes, when I quote people. I know, I have a problem, I need therapy...

Nah, I do the same. I mean, you may need therapy, but not for this. You and I at least share in common an extreme attention to detail, and that is a trait no one should ever try to take away.

Yeah, plus all the extra <br> tags that you get. I also like to get the quote tags all on their own lines to make it easier to see what's going on.

... just piping up as another who deletes the tag-soup in the plain editor that CS decides it simply must insert to no useful effect (and the quote stuff if I start deleting bits of it.)

And I'm another. I feel much better about it now. :)

[ender]

@dhromed said:

Why bother?

OCD? (glad I'm not the only one)

[PJH]

@ender said:

@dhromed said:

Why bother?

CDO? (glad I'm not the only one)

FTFY.

[dhromed]

@PJH said:

@ender said:

@dhromed said:

Why bother?

CDO? (glad I'm not the only one)

FTFY.

 

Compulsive Disorder Obsession.

[Scarlet_Manuka]

@blakeyrat said:

@da Doctah said:

Better still: hang on to both hashes of whatever password they entered when entering the above pseudocode.  If BetterHashForUser() matches, proceed as above.  If MD5HashForUser() matches instead, update the database with the BetterHashForUser() hash so that from then on they're actually using that one.

That is a better idea. +1.

I don't deal with any of this sort of thing at all, so I try to learn what I can from discussions like this one. So you have my apologies if this is a stupid question. Can't an attacker still just try to get an MD5 hash collision with the BetterHashForUser() hash? Or would BetterHashForUser() hashes generally not be valid MD5 hashes? How much commonality is there between the hash spaces of various hashing algorithms?

[blakeyrat]

@Scarlet Manuka said:

I don't deal with any of this sort of thing at all, so I try to learn what I can from discussions like this one. So you have my apologies if this is a stupid question. Can't an attacker still just try to get an MD5 hash collision with the BetterHashForUser() hash?

We're presuming that BetterHashForUser() is indeed a better hash-- collisions are still possible, of course, but the advantages are that:

1) Newer hashes generally don't have pre-built rainbow tables available

2) The odds of a collision for newer hashes is much, much, much lower than MD5, which is known to be easily exploited

3) Newer hashes generally take more CPU time, making the "guessing" (if the attacker doesn't have, or can't use, a rainbow table) take significantly more time

@Scarlet Manuka said:

Or would BetterHashForUser() hashes generally not be valid MD5 hashes?

I think the odds of a collision between MD5 and another hashing algorithm are close enough to zero to be negligible. Maybe a more math-y person than me can answer this.

[Sutherlands]

@blakeyrat said:

@Scarlet Manuka said:

Or would BetterHashForUser() hashes generally not be valid MD5 hashes?

I think the odds of a collision between MD5 and another hashing algorithm are close enough to zero to be negligible. Maybe a more math-y person than me can answer this.

The odds of a MD5 hash matching a non-MD5 hash (assuming both are the same length) is the same as an md5 hash matching another md5 hash (or 0% if they're not the same length). 

@Scarlet: While the MD5 algorithm is still in the code, and used for logins, the vulnerability is the same assuming you use the either-or login method that blakey first posted.  If you only have the latest available hash, then the code would most likely check which algorithm was used, so matching between different algorithms wouldn't be possible.  With the first method, the point is to eventually get off of the either-or method, removing the vulnerability at that time.

[Scarlet_Manuka]

@blakeyrat said:

@Scarlet Manuka said:

I don't deal with any of this sort of thing at all, so I try to learn what I can from discussions like this one. So you have my apologies if this is a stupid question. Can't an attacker still just try to get an MD5 hash collision with the BetterHashForUser() hash?

We're presuming that BetterHashForUser() is indeed a better hash-- collisions are still possible, of course, but the advantages are that:
1) Newer hashes generally don't have pre-built rainbow tables available
2) The odds of a collision for newer hashes is much, much, much lower than MD5, which is known to be easily exploited
3) Newer hashes generally take more CPU time, making the "guessing" (if the attacker doesn't have, or can't use, a rainbow table) take significantly more time @Scarlet Manuka said:

Or would BetterHashForUser() hashes generally not be valid MD5 hashes?

I think the odds of a collision between MD5 and another hashing algorithm are close enough to zero to be negligible. Maybe a more math-y person than me can answer this.

I realise now that I didn't word my initial question well enough. What I meant was that previously, the attacker had to find a string that had an MD5 hash equal to one piece of pseudo-random text (the MD5 hash of the password); now he has to find a string with an MD5 hash equal to a different piece of pseudo-random text (the BetterHashForUser() hash of the password). As far as I can tell these tasks are equivalent, assuming that a BetterHashForUser() hash is in the range of the MD5 hashing algorithm. I don't know if that's a good assumption or not. I also don't know if the tasks are equivalent even if the ranges are identical (perhaps BetterHashForUser() has hashes more evenly distributed throughout the range, while MD5 hashes tend to cluster at certain values). So these are the points I'm curious about, and any enlightenment will be gratefully accepted.

Of course, once existing passwords have been transitioned to BetterHashForUser() you can take away the check for the MD5 hash and then you will indeed be more secure, for the reasons you've listed. I'm asking about the transition period, when you're still accepting MD5 hashes as well as BetterHashForUser() ones.

And while I was posting this, Sutherlands posted a reply which answered most of my questions. Namely, the risk is the same until you remove the check for the MD5 hash (assuming the hashes are the same length), but making the very good point that the check should be designed to say "User X has upgraded to BetterHashForUser(), don't check the MD5 hash for them." Then the vulnerability is reduced for each user as soon as they log in. Thanks, Sutherlands.

[blakeyrat]

I got bored, so I wrote this little ditty:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

using System.Security.Cryptography;

using System.Threading;
namespace FindHashCollisions

{

class Program

{

const int NUMBER_OF_THREADS = 4;

const int MAX_PASSWORD_LENGTH = 24;
	static public HashAlgorithm md5Hash = new MD5CryptoServiceProvider();
	static public HashAlgorithm sha1Hash = new SHA1CryptoServiceProvider();

	static public long tested = 0;
	static public long collisions = 0;

	static public Random rand = new Random();

	static public List<Thread> threads = new List<Thread>();

	static void Main(string[] args)
	{
		for (int i = 0; i < NUMBER_OF_THREADS; i++)
		{
			Thread thread = new Thread(new ThreadStart(CreateTextThread));
			thread.Start();
			threads.Add(thread);
		}
	}

	static void CreateTextThread()
	{
		while (true)
		{
			int length = rand.Next(MAX_PASSWORD_LENGTH);
			StringBuilder textBuilder = new StringBuilder();

			for (int i = 0; i < length; i++)
			{
				textBuilder.Append(Convert.ToChar(Convert.ToByte(rand.Next(255)) + 1));
			}

			string text = textBuilder.ToString();

			CheckHashCollision(text);
		}
	}

	static void CheckHashCollision(string text)
	{
		string sh1Result = null;
		string md5Result = null;

		byte[]] textBytes = Encoding.UTF8.GetBytes(text);

		lock (md5Hash)
		{
			byte[]] md5Bytes = md5Hash.ComputeHash(textBytes);
			byte[]] sha1Bytes = sha1Hash.ComputeHash(textBytes);

			md5Result = Convert.ToBase64String(md5Bytes);
			sh1Result = Convert.ToBase64String(sha1Bytes);
		}

		if (md5Result == sh1Result)
		{
			string line = "Collision:\t" + text + "\t" + md5Result + "\t" + sh1Result;
			Log(line);

			collisions++;

			if (collisions % 10000 == 0)
			{
				Log("Collisions found: " + Convert.ToString(collisions));
			}
		}

		tested++;

		if (tested % 10000 == 0)
		{
			Log("Values tested: " + Convert.ToString(tested));
		}
	}

	static void Log(string line)
	{
		Console.WriteLine(line);

		StreamWriter file = new StreamWriter("results.txt", true);
		file.WriteLine(line);
		file.Close();
	}
}

}

We'll see if it finds any MD5 == SHA1 collisions if run overnight. Or if it crashes, which is much more likely.

Edit: wow, despite the Lock(), .net's keeping my CPU 99.5% occupied with this little gem. Threading in C# is so easy it's like cheating...

[fatbull]

 Well, since MD5 returns 128 bits and SHA-1 returns 160 bits, I seriously doubt you'll find a collision ...

[blakeyrat]

@fatbull said:

Well, since MD5 returns 128 bits and SHA-1 returns 160 bits, I seriously doubt you'll find a collision ...

Haha yes, I didn't think of that when I wrote it. I just wrote it due to insomnia anyway. Where were you last night to point that out!??

Values tested: 6370000000 | Collisions found: 0

[Weng]

@blakeyrat said:

 

Edit: wow, despite the Lock(), .net's keeping my CPU 99.5% occupied with this little gem. Threading in C# is so easy it's like cheating...

Yeah. It is schmexy. "What do you mean I can thread that without adding more than 2 lines?" is a common refrain.

[blakeyrat]

@Weng said:

@blakeyrat said:

Edit: wow, despite the Lock(), .net's keeping my CPU 99.5% occupied with this little gem. Threading in C# is so easy it's like cheating...

Yeah. It is schmexy. "What do you mean I can thread that without adding more than 2 lines?" is a common refrain.

I managed to get rid of the lock() on the version I actually ran overnight, by letting each thread keep track of its own HashAlgorithm classes. It didn't affect performance one iota, as far as I can tell. Which means C# is not only awesome, but it's doing some weird-mojo optimization on the threading.

[derula]

@blakeyrat said:

@fatbull said:

Well, since MD5 returns 128 bits and SHA-1 returns 160 bits, I seriously doubt you'll find a collision ...

Haha yes, I didn't think of that when I wrote it. I just wrote it due to insomnia anyway. Where were you last night to point that out!??

Values tested: 6370000000 | Collisions found: 0

Just cut the last 32 bits from the SHA-1.

[Xyro]

@blakeyrat said:

I managed to get rid of the lock() on the version I actually ran overnight, by letting each thread keep track of its own HashAlgorithm classes. It didn't affect performance one iota, as far as I can tell. Which means C# is not only awesome, but it's doing some weird-mojo optimization on the threading.

Perhaps, but I would think that the lock() contention is so minute compared to the time the hashing algorithms take that it doesn't show up in the numbers. If instead of a hash, you just created random strings, the lock() may be far more visible.

Edit: oh wait ... never mind. Next time I'll read the code [i]within[/i] a day of posting a comment on it.

[blakeyrat]

@Xyro said:

@blakeyrat said:

I managed to get rid of the lock() on the version I actually ran overnight, by letting each thread keep track of its own HashAlgorithm classes. It didn't affect performance one iota, as far as I can tell. Which means C# is not only awesome, but it's doing some weird-mojo optimization on the threading.

Perhaps, but I would think that the lock() contention is so minute compared to the time the hashing algorithms take that it doesn't show up in the numbers. If instead of a hash, you just created random strings, the lock() may be far more visible.

Edit: oh wait ... never mind. Next time I'll read the code within a day of posting a comment on it.

Yeah. Well, I could post the code I actually ran, which is a bit better, but since it's pointless I won't bother. The answer to the question is: "there is exactly zero chance of a hash collision, because the hashes are different byte sizes."

[Renan]

@blakeyrat said:

@Xyro said:

@blakeyrat said:

I managed to get rid of the lock() on the version I actually ran overnight, by letting each thread keep track of its own HashAlgorithm classes. It didn't affect performance one iota, as far as I can tell. Which means C# is not only awesome, but it's doing some weird-mojo optimization on the threading.

Perhaps, but I would think that the lock() contention is so minute compared to the time the hashing algorithms take that it doesn't show up in the numbers. If instead of a hash, you just created random strings, the lock() may be far more visible.

Edit: oh wait ... never mind. Next time I'll read the code within a day of posting a comment on it.

Yeah. Well, I could post the code I actually ran, which is a bit better, but since it's pointless I won't bother. The answer to the question is: "there is exactly zero chance of a hash collision, because the hashes are different byte sizes."

Unless the size of the field in which the hash is going into the database is no longer than the shortest byte size. I've seen people discarding the last few bytes of a hash because the database wasn't storing them whole.

[blakeyrat]

[quote user="Renan "C#" Sousa"]Unless the size of the field in which the hash is going into the database is no longer than the shortest byte size. I've seen people discarding the last few bytes of a hash because the database wasn't storing them whole.[/quote]

Yeah, well, you can say "unless {something extremely WTF}" all day long. Obviously.

"The sky is blue." "Unless you've been living in a greenhouse with the glass panes painted red your entire life and you think that's the sky because your parents are evil jerks who lied to you!!"

I don't see that as relevant.

Of course the bigger WTF would be the database that silently truncates, but, then again, I've used older versions of MySQL so I've been there.

[C_Octothorpe]

@blakeyrat said:

"The sky is blue." "Unless you've been living in a greenhouse with the glass panes painted red your entire life and you think that's the sky because your parents are evil jerks who lied to you!!"

This explains a lot of the anger issues...

[serguey123]

@blakeyrat said:

[quote user="Renan "C#" Sousa"]Unless the size of the field in which the hash is going into the database is no longer than the shortest byte size. I've seen people discarding the last few bytes of a hash because the database wasn't storing them whole.

Yeah, well, you can say "unless {something extremely WTF}" all day long. Obviously.

"The sky is blue." "Unless you've been living in a greenhouse with the glass panes painted red your entire life and you think that's the sky because your parents are evil jerbils who lied to you!!"

I don't see that as relevant.

Of course the bigger WTF would be the database that silently truncates, but, then again, I've used older versions of MySQL so I've been there.

[/quote]

Improved That For You (ITFY)