Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Yahoo discloses hack of 1B accounts

yahoo.tumblr.com

Post reply on HN
Print view View original

351–360 of 596 posts

Re: Yahoo discloses hack of 1B accounts

#351

Post by schoen »

jsjohnst wrote: post #290
cm2187 wrote: post #282

Earlier quoted context omitted.

That being said md5 does generate collisions. I was playing with the IMDB movie database that you can download. They use a combination of the title and the year as a primary key. I tried using an md5 instead to save space (but giving a reproducible ID instead if an identity column), and got many collisions. No collision with SHA256.

Oh, of course md5 has collisions. It's relatively easy (not computationally easy, but there are known methods) to find two random strings that hash to the same value, it's just very difficult to find a string that hashes to the value of a specific other string.

Not "relatively easy" by chance: it should require 2⁶⁴ entries in your database to see a single collision happen at random! It's only "relatively easy" following cryptographic research in the early 2000s that exploits structure in MD5 to produce collisions deliberately.

Yes, collisions are easier than preimages, but they still shouldn't occur by chance in real applications!

Re: Yahoo discloses hack of 1B accounts

#352

Post by danielweber »

pbhjpbhj wrote: post #292
noonespecial wrote: post #184

Earlier quoted context omitted.

The problem is in collisions. Md5(password) can yield the same result for many different values of password so simply bcrypting that result means that you start with a restricted possibility space. So less secure. Punts the question to how much less secure. Seems to me it would still be worth it to do and then all new passwords going forward are done correctly.

>Md5(password) can yield the same result for many different values of password // Not "many different" using the normal constraints of text/numbers/typographical-marks and with maximum password lengths of 32 or so (I'll bet Yahoo's was shorter than that in 2013). Are there any MD5 collisions in [:graph:]{,32} ?

I really doubt it. When people demonstrate MD5 collisions, they use a hex strings like

0e306561559aa787d00bc6f70bbdfe3404cf03659e70 4f8534c00ffb659c4c8740cc942feb2da115a3f4155c bb8607497386656d7d1f34a42059d78f5a8dd1ef

Re: Yahoo discloses hack of 1B accounts

#353

Post by jsjohnst »

schoen wrote: post #351
jsjohnst wrote: post #290

Earlier quoted context omitted.

Oh, of course md5 has collisions. It's relatively easy (not computationally easy, but there are known methods) to find two random strings that hash to the same value, it's just very difficult to find a string that hashes to the value of a specific other string.

Not "relatively easy" by chance: it should require 2⁶⁴ entries in your database to see a single collision happen at random! It's only "relatively easy" following cryptographic research in the early 2000s that exploits structure in MD5 to produce collisions deliberately. Yes, collisions are easier than preimages, but they still shouldn't occur by chance in real applications!

Realized my wording was way to ambiguous, clarified. Thanks!

Re: Yahoo discloses hack of 1B accounts

#354

Post by danielweber »

user5994461 wrote: post #278
cm2187 wrote: post #141

Earlier quoted context omitted.

But would it require users to change their password? The way I would have implemented it, but would be keen to know how secure it is, is that you start with the md5 of the password ( md5(password) ). You then bcrypt or scrypt that md5 ( bcrypt(md5(password)) ) and replace the md5 in your database with the bcrypt hash. When a user logs in, all you need to do is to calculate the md5 first then check that md5 against th…

It's one way to do it, which is okay sometimes. The other way is to add a new empty column for bcrypt. The next time the user logs in, you save the bcrypt hash and you remove the MD5 hash. Over time, the active users will be migrated to the new scheme. The only issue is the abandoned accounts, they'll keep the old weak scheme.

There are other migration techniques. If you know md5(password), you can create bcrypt(md5(password)).

Re: Yahoo discloses hack of 1B accounts

#355

Post by schoen »

noonespecial wrote: post #184
cm2187 wrote: post #141

Earlier quoted context omitted.

But would it require users to change their password? The way I would have implemented it, but would be keen to know how secure it is, is that you start with the md5 of the password ( md5(password) ). You then bcrypt or scrypt that md5 ( bcrypt(md5(password)) ) and replace the md5 in your database with the bcrypt hash. When a user logs in, all you need to do is to calculate the md5 first then check that md5 against th…

The problem is in collisions. Md5(password) can yield the same result for many different values of password so simply bcrypting that result means that you start with a restricted possibility space. So less secure. Punts the question to how much less secure. Seems to me it would still be worth it to do and then all new passwords going forward are done correctly.

Unfortunately, this isn't an accurate description of the nature of the collision problem with MD5, which involves carefully crafted inputs using a sophisticated cryptographic attack -- not arbitrary user inputs that don't intend to collide with each other. See my and danielweber's comments about this down-thread.

(Yes, susceptibility to collisions was recognized as a problem with MD5 leading to a reason not to use it, but the collisions in question were constructed, not encountered accidentally. There isn't any evidence to date that the probability of a collision given two randomly chosen inputs is higher than the expected 1/2¹²⁸. You could test this yourself by hashing 2⁴⁰ random strings under MD5: you won't see a collision among the outputs!)

Re: Yahoo discloses hack of 1B accounts

#356

Post by [deleted] »

CobrastanJorji wrote: post #337
jsjohnst wrote: post #260

Earlier quoted context omitted.

Apologies, I've heard the details at this point and I can't disclose them. The limit of what I can do is poke holes in the theories that are wrong.

Aren't the details "three years after we were hacked, law enforcement told us that we had been hacked, and we believe them?" The press release explicitly says "We have not been able to identify the intrusion associated with this theft." I especially noticed that the "What are we doing to protect our users?" section doesn't mention anything about Yahoo fixing any security issues. Presumably, then, as a Yahoo engineer,…

[deleted]

Re: Yahoo discloses hack of 1B accounts

#357

Post by cookiecaper »

b2600 wrote: post #349
cookiecaper wrote: post #330

Earlier quoted context omitted.

Yes. We pay an independent Indian contractor rates that are fully competitive with any American contractor's rates. If someone has the same skillset as the competition, their rate is going be in the same ballpark, no matter where they live.

If your statement is accurate, why offshore the work?

He came recommended by someone who had used him before. His country of residence was not relevant to our hiring decision.

Re: Yahoo discloses hack of 1B accounts

#358

Post by hawkice »

pbhjpbhj wrote: post #292
noonespecial wrote: post #184

Earlier quoted context omitted.

The problem is in collisions. Md5(password) can yield the same result for many different values of password so simply bcrypting that result means that you start with a restricted possibility space. So less secure. Punts the question to how much less secure. Seems to me it would still be worth it to do and then all new passwords going forward are done correctly.

>Md5(password) can yield the same result for many different values of password // Not "many different" using the normal constraints of text/numbers/typographical-marks and with maximum password lengths of 32 or so (I'll bet Yahoo's was shorter than that in 2013). Are there any MD5 collisions in [:graph:]{,32} ?

Yes, because MD5 digests are much shorter than 32 characters, even if it's just ascii, so by the pidgeonhole principle there must be. If you're asking if there are _known_ collisions between two messages with less than 32 printable ascii characters -- the answer is likely yes, but there are not known to me and likely not publicly known at all yet.

Re: Yahoo discloses hack of 1B accounts

#359

Post by danielweber »

leereeves wrote: post #226
manarth wrote: post #140

Earlier quoted context omitted.

You can only rehash if you have the plaintext password There are techniques to rehash, even without the plain-text password, and without the user having to login to trigger a rehash. Drupal 7 used such a technique for upgrades from Drupal 6, migrating from MD5 to a salted sha512 hash, but it's not an uncommon technique. The old passwords are stored as MD5 hashes in the databases. The MD5 hash is processed through the…

> hash = sha512(salt + MD5(password)) Passing the password through MD5 reduces the complexity to 128 bits, you can't get that back. So the security level is not the same, though it may be resistant to some attacks on MD5. And it's probably not important for most people, since there are less than 2^56 eight character ASCII passwords.

> Passing the password through MD5 reduces the complexity to 128 bits

No, this is not the problem with MD5. You are not going to find two user-memorizeable-and-typeable passwords with an MD5 collision.

If you are bringing a password with more than 128 bits of complexity to the party, any password storage scheme better than plaintext will have your password safe.

Re: Yahoo discloses hack of 1B accounts

#360

Post by duaneb »

rawfan wrote: post #321
duaneb wrote: post #313

Earlier quoted context omitted.

Race is not a bogus concept. It may be cultural but it's still real. Offshore is not a race. That's just xenophobia.

There is actually no such thing as different human races (in the biological sense of the word). People who believe that are... you guessed it... called racists.

I honestly doubt that many people on this forum hold that opinion. I really hope not, anyway.

I also haven't heard any good conversations about race that deny it. If you accept the existence of racism, you should accept the evident existence of race.

I think the other-ness of offshore labor has parallels to many things in the history of racism—namely, the exploitation of xenophobia and tribalism to justify cheap labor, explicit or implicit. There's also many different aspects: the xenophobia is nationalistic, not phenotypic; offshoring does not imply a poor wage or reduced quality of life for the local economy, just compared to the exploiting economy; we don't see (much) moralistic justification for offshoring.

My point being, this is a complex subject and you're not contributing much by denying race itself. There are easier ways to dispel notions you disagree with than alienating others in the conversation by denying them.

Post reply on HN