It is meaningless to talk about cryptography without a threat model, just as Robert says. Is anybody actually attacking us? Or are we worried about accidental collisions?
Sent from my Verizon Wireless Phone
-----Original message----- From: Robert Rohde rarohde@gmail.com To: Wikimedia developers wikitech-l@lists.wikimedia.org Sent: Sun, Sep 18, 2011 05:56:15 GMT+00:00 Subject: Re: [Wikitech-l] Adding MD5 / SHA1 column to revision table (discussing r94289)
On Sat, Sep 17, 2011 at 4:56 PM, Anthony wikimail@inbox.org wrote:
On Sat, Sep 17, 2011 at 6:46 PM, Robert Rohde rarohde@gmail.com wrote:
Is there a good reason to prefer SHA-1?
Both have weaknesses allowing one to construct a collision (with considerable effort)
Considerable effort? I can create an MD5 collision in a few minutes on my home computer. Is there anything even remotely like this for SHA-1?
If I've been keeping up to date, the collision complexity for MD5 is about 2^21 operations, and runs in a few seconds (not minutes); and for SHA-1 down to about 2^52 with current results. The latter represents about 100 cpu-years, which is within the realm of supercomputers. That time will probably continue to come down if people find ways to improve the attacks on SHA-1. (The existing attacks usually require the ability to feed arbitrary binary strings into the hash function. Given that both browsers and Mediawiki will tend to reject binary data placed in an edit window, I'm not sure if any of the existing attacks could be reliably applied to Mediawiki editing.)
If collision attacks really matter we should use SHA-1. However, do any of the proposed use cases care about whether someone might intentionally inject a collision? In the proposed uses I've looked at it, it seems irrelevant. The intentional collision will get flagged as a revert and the text leading to that collision would be discarded. How is that a bad thing?
It's a not a big deal, but if I understand prior comments correctly, most of the existing offline infrastructure uses MD5, so I'm wondering if there is a distinct use case for favoring SHA-1.
MD5 is shorter and in my experience about 25% faster to compute.
Personally I've tended to view MD5 as more than good enough in offline analyses.
For offline analyses, there's no need to change the online database tables.
Need? That's debatable, but one of the major motivators is the desire to have hash values in database dumps (both for revert checks and for checksums on correct data import / export). Both of those are "offline" uses, but it is beneficial to have that information precomputed and stored rather than frequently regenerated.
-Robert Rohde
_______________________________________________ Wikitech-l mailing list Wikitech-l@lists.wikimedia.org https://lists.wikimedia.org/mailman/listinfo/wikitech-l
On Sun, Sep 18, 2011 at 7:24 AM, Russell N. Nelson - rnnelson rnnelson@clarkson.edu wrote:
It is meaningless to talk about cryptography without a threat model, just as Robert says. Is anybody actually attacking us?
You mean, like Grawp?
On Sun, Sep 18, 2011 at 7:24 AM, Russell N. Nelson - rnnelson rnnelson@clarkson.edu wrote:
It is meaningless to talk about cryptography without a threat model, just as Robert says. Is anybody actually attacking us? Or are we worried about accidental collisions?
I believe it began as accidental collisions, then everyone promptly put on their tinfoil hats and started talking about a hypothetical vandal who has the time and desire to generate hash collisions.
-Chad
On Sun, Sep 18, 2011 at 5:30 PM, Chad innocentkiller@gmail.com wrote:
On Sun, Sep 18, 2011 at 7:24 AM, Russell N. Nelson - rnnelson rnnelson@clarkson.edu wrote:
It is meaningless to talk about cryptography without a threat model, just as Robert says. Is anybody actually attacking us? Or are we worried about accidental collisions?
I believe it began as accidental collisions, then everyone promptly put on their tinfoil hats and started talking about a hypothetical vandal who has the time and desire to generate hash collisions.
Having run a wiki which I eventually abandoned due to various "Grawp attacks", I can assure you that there's nothing hypothetical about it.
On Sun, Sep 18, 2011 at 5:47 PM, Anthony wikimail@inbox.org wrote:
On Sun, Sep 18, 2011 at 5:30 PM, Chad innocentkiller@gmail.com wrote:
On Sun, Sep 18, 2011 at 7:24 AM, Russell N. Nelson - rnnelson rnnelson@clarkson.edu wrote:
It is meaningless to talk about cryptography without a threat model, just as Robert says. Is anybody actually attacking us? Or are we worried about accidental collisions?
I believe it began as accidental collisions, then everyone promptly put on their tinfoil hats and started talking about a hypothetical vandal who has the time and desire to generate hash collisions.
Having run a wiki which I eventually abandoned due to various "Grawp attacks", I can assure you that there's nothing hypothetical about it.
For those of us who do not know...what the heck is a Grawp attack? Does it involve generating hash collisions?
-Chad
On Sun, Sep 18, 2011 at 5:50 PM, Chad innocentkiller@gmail.com wrote:
On Sun, Sep 18, 2011 at 5:47 PM, Anthony wikimail@inbox.org wrote:
On Sun, Sep 18, 2011 at 5:30 PM, Chad innocentkiller@gmail.com wrote:
On Sun, Sep 18, 2011 at 7:24 AM, Russell N. Nelson - rnnelson rnnelson@clarkson.edu wrote:
It is meaningless to talk about cryptography without a threat model, just as Robert says. Is anybody actually attacking us? Or are we worried about accidental collisions?
I believe it began as accidental collisions, then everyone promptly put on their tinfoil hats and started talking about a hypothetical vandal who has the time and desire to generate hash collisions.
Having run a wiki which I eventually abandoned due to various "Grawp attacks", I can assure you that there's nothing hypothetical about it.
For those of us who do not know...what the heck is a Grawp attack? Does it involve generating hash collisions?
It does not involve generating hash collisions, but it involves finding various bugs in mediawiki and using them to vandalise, often by injecting javascript. The best description I could find was at Encyclopedia Dramatica, which seems to be taken down (there's a cache if you do a google search for "grawp wikipedia"). There's also a description at http://en.wikipedia.org/wiki/User:Grawp , which does not do justice to the "mad hacker skillz" of this individual and his intent on finding bugs in mediawiki and exploiting them.
If you did something as lame as relying on no one generating an MD5 collision (*), it would happen. If you use SHA-1, it may or may not happen, depending on how quickly computers get faster, and how many further attacks are made on the algorithm. If you use SHA-256 (**), it's significantly less likely to happen, and you'll probably have a warning in the form of an announcement on Slashdot that SHA-256 has been broken, before it happens.
(*) Something which I have done myself on my home computer in a couple minutes, and apparently now can be done in a couple seconds.
(**) Which, incidentally, is possibly the single most secure hash for Wikimedia to use at the current time. SHA-512 is significantly more "broken" than SHA-256, and the more theoretically secure hashes have received much less scrutiny than SHA-256. If you want to be more secure than SHA-256, you should combine SHA-256 with some other hashing algorithm.)
On Sun, Sep 18, 2011 at 6:01 PM, Anthony wikimail@inbox.org wrote:
There's also a description at http://en.wikipedia.org/wiki/User:Grawp , which does not do justice to the "mad hacker skillz" of this individual and his intent on finding bugs in mediawiki and exploiting them.
(and/or the Grawp copycats - personally I don't know if it was "Grawp" himself or a copycat that attacked my wiki)
Chad wrote:
For those of us who do not know...what the heck is a Grawp attack? Does it involve generating hash collisions?
-Chad
It's the name of a wikipedia vandal. http://en.wikipedia.org/wiki/User:Grawp
wikitech-l@lists.wikimedia.org