Re: MD5 collisions?
At 01:02 AM 8/18/2004, J.A. Terranson wrote: Since when is on-topic crossposting an issue here? Since forever. Since before either of us joined the list (and I first started reading a decade ago). It's a matter of politeness and degree. A pointer to a discussion archived on the web is more useful than dozens of forwarded messages. Hey, I have an idea! Why don't I write a script crossposting everything from sci.crypt to cypherpunks! How about a few dozen other on-topic newsgroups and mailing lists too? -Declan
Re: MD5 collisions?
At 8:58 PM -0500 8/17/04, Declan McCullagh wrote: I hadn't noticed. How uncharacteristic of him. Never would have guessed. ..and my mother dresses me funny? You can do better than that, Declan -- if you do say so yourself. Self-important git. -RAH -- - R. A. Hettinga mailto: [EMAIL PROTECTED] The Internet Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA ... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire'
Re: MD5 collisions?
..and another thing... At 7:33 PM -0500 8/17/04, Declan McCullagh wrote: -Declan TCM McCullagh Does this mean you spend all day in a Barcolounger dry-jacking a Mossberg, muttering about Janet Reno? ;-) Cheers, RAH Banks in Hong Kong and Shanghai, indeed... -- - R. A. Hettinga mailto: [EMAIL PROTECTED] The Internet Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA ... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire'
Re: MD5 collisions?
At 7:33 PM -0500 8/17/04, Declan McCullagh wrote: One is enough. Less is more. Let's eliminate redundancy, thus eliminating redundancy. Yawn. Let's piss up a rope, shall we? Cheers, RAH -- - R. A. Hettinga mailto: [EMAIL PROTECTED] The Internet Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA ... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire'
Re: MD5 collisions?
Sigh. RAH has descended to the level of a net.kook. Never would have guessed. -Declan
Re: MD5 collisions?
At 09:04 PM 8/17/04 -0400, R. A. Hettinga wrote: At 7:33 PM -0500 8/17/04, Declan McCullagh wrote: One is enough. Less is more. Let's eliminate redundancy, thus eliminating redundancy. LMAO RAH :-) = 36 Laurelwood Dr Irvine CA 92620-1299 VOX: (714) 544-9727 (home) mnemonic: P1G JIG WRAP VOX: (949) 462-6726 (work -don't leave msgs, I can't pick them up) mnemonic: WIZ GOB MRAM ICBM: -117.7621, 33.7275 HTTP: http://68.5.216.23:81 (back up, but not 99.999% reliable) PGP PUBLIC KEY: by arrangement Send plain ASCII text not HTML lest ye be misquoted -- Don't 'sir' me, young man, you have no idea who you're dealing with Tommy Lee Jones, MIB No, you're not 'tripping', that is an emu ---Hank R. Hill
Re: MD5 collisions?
At 10:03 PM -0500 8/17/04, Declan McCullagh wrote: Sigh. RAH has descended to the level of a net.kook. Never would have guessed. You've exactly the same used the same rhetorical device twice now. Are you just lazy, or, more likely, have you just peaked too soon? How does it feel to be someone whose best years are a decade behind him, Declan? You are *sooo* boring. RAH -- - R. A. Hettinga mailto: [EMAIL PROTECTED] The Internet Bearer Underwriting Corporation http://www.ibuc.com/ 44 Farquhar Street, Boston, MA 02131 USA ... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire'
Re: MD5 collisions?
On Tue, 17 Aug 2004, Declan McCullagh wrote: Sigh. RAH has descended to the level of a net.kook. Never would have guessed. -Declan Since when is on-topic crossposting an issue here? -- Yours, J.A. Terranson [EMAIL PROTECTED] 0xBD4A95BF ...justice is a duty towards those whom you love and those whom you do not. And people's rights will not be harmed if the opponent speaks out about them. Osama Bin Laden - - - There aught to be limits to freedom!George Bush - - - Which one scares you more?
Owning Ones Own Words, Peaking Too Soon, The Cypherpunk Purity Test, and Bora-Bora (Re: MD5 collisions?)
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 At 1:40 AM -0400 8/18/04, Declan McCullagh trots out the Cypherpunk Purity Test, among other tasty bits of speciousness: At 01:02 AM 8/18/2004, J.A. Terranson wrote: Since when is on-topic crossposting an issue here? Since forever. To elucidate this a bit, Declan believes in this obscure WELL.nonsense called you own your own words. No. Seriously. *Nobody* can forward *anything* you say, *anywhere* on the net, without your permission. On the net. Without your permission. Pardon me. Almost 10 years after I heard of it, my stomach still hurts from laughing at this ignorant blend of communitarian hippy-logic and 19th century industrial-age legal nostrum. Hint, Declan: the definition of property, especially digital property in an age of perfect digital copies on a ubiquitous geodesic :-) internetwork, is that it's sitting, preferably encrypted, on my hard drive. The, um, bald, fact is, once it's there, I can send it, anywhere on the net, whenever I feel like it, without your permission. Declan's actual subtext in this case is that he's written this nice summary article on ... wait... where do you work this week, Declan? Time Magazine? No. Not there anymore. Wired, right? No, not there either. Oh, that's it, CNET. Still there, right? CNET probably can't hire enough fact-checkers, so you're probably safe there for a while until the cacophony of protests from your misquoted article subjects rises above a dull roar. Reminds me of a cartoon in Tom Wolfe's Mauve Gloves and Madmen, Currier and Vine about the Guy Who Peaked Too Soon. Anyway, as usual, Declan has, dutifully, one imagines, ground out something he wants you to read instead of seeing (mostly relevant :-)) first sources in more or less real-time, on this list where you read it, instead of interrupting your flow to click around on the web for it. This way, though, he owns the words, you see. And, obviously, if you click the link, provided here as a courtesy, http://zdnet.com.com/2102-1105_2-5313655.html?tag=printthis, he gets paid more money. Sooner or later. Or at least they might pay his way to more conferences, like they used to during the Clinton Internet Bubble :-). Maybe. Anyway, maybe if we all click it a lot of times, Dear Declan might sit down, shut up, and move that sock from his trousers to his pie-hole. By the way, the reason I didn't send *that* article to the list, too - -- before he pissed on my shoes -- is that he whines at you offline about it. And, before this, I took pity on the once-richer-now-poorer erst-ink-stained wretch. Fuck that. I expect to be getting a phone call from CNET's lawyers for copyright violations under COPA, or whatever, now, as a result, but what the hell. Since before either of us joined the list (and I first started reading a decade ago). Here we go, folks. The ol' cypherpunks purity trick. My tenure on these lists longer than yours. Or, I've been voting libertarian longer than you have. Or, I play on Cato's Invisible Foot and you don't. Or, I can dry-jack a Mossberg, or Nikon Coolpix, or whatever, faster than you can. Or whatever. For the record, I've been here since March or April of 1994. Whatever. This list, and it's lineal predecessors, is long past the time when cutting edge cryptography was discussed here for the first time instead of somewhere else. So, periodically, the tree of cypherpunks must be watered with the blood of other lists. Or something. :-) In the meantime, remember that Declan's main purpose here is to sniff around for stories. Which is fine, until he starts pretending he's Tim May (I knew Tim May -- he wished I didn't -- and, Mr. McCullagh you're... Oh, forget it), or, paradoxically for cypherpunks, that he owns the list somehow, and that, like Mighty Mouse, he's here to save the day and play list.policeman. It's a matter of politeness and degree. True enough. And, frankly, I've respected both of those in what I've sent here over the years. The only people who've complained, at least until I've explained myself to their satisfaction, have been professionals who owned their own words and got scooped. If one can consider forwarding something important from cryptography to this list to be scooping the CNET Political Editor in Chief. Or whatever they say he is these days. A pointer to a discussion archived on the web is more useful than dozens of forwarded messages. Hey, I have an idea! Why don't I write a script crossposting everything from sci.crypt to cypherpunks! How about a few dozen other on-topic newsgroups and mailing lists too? Go ahead. Are you going to reformat them for legibility first, if necessary? Are you going to personally decide, in *your* opinion, what's worth forwarding and what isn't? Are you going to be topical? More to the point, Declan, are you going to do it in such a way that the residents of the list actually *use* in further discussion? Or are you going to do it to prove that, reductio ad absurdum,
Re: SHA-1 rumors
--- R. A. Hettinga [EMAIL PROTECTED] wrote: This would SEEM to put the SHA family into jeopardy as well, but we should know more tomorrow evening. John Black Wasn't the attack to find two chosen messages hashing to the same value? But that doesn't mean that it is easy to find a message M1:H(M1)= H(M2),given M2. Sarath. __ Do you Yahoo!? Yahoo! Mail - 50x more storage than other providers! http://promotions.yahoo.com/new_mail
Suggestion
I hereby suggest to postpone the flamewars for the winter, when the weather brings the need of some spare waste heat. I thought we're above name-calling here. But perhaps it was just a quiet period and the current situation will rectify on its own in couple days, as it usually does. Besides, the recent development around the hash functions is quite important to know about.
Re: MD5 collisions?
On Wed, 18 Aug 2004, Declan McCullagh wrote: At 01:02 AM 8/18/2004, J.A. Terranson wrote: Since when is on-topic crossposting an issue here? Since forever. Since before either of us joined the list (and I first started reading a decade ago). It's a matter of politeness and degree. A pointer to a discussion archived on the web is more useful than dozens of forwarded messages. Hey, I have an idea! Why don't I write a script crossposting everything from sci.crypt to cypherpunks! How about a few dozen other on-topic newsgroups and mailing lists too? We're not talking about just sci.crypt chatter here, he has been forwarding posts on one of the single most interesting (to anyone crypto-inclined) topics in *years*. And not everyone (crypto-inclined or not) subs to all of the many sources: if you want to get the word out to the less than hard-core, this list is a great starting point. You complaints on this appear (based mostly on your banter with RAH) to be more a personal problem than anything else. Perhaps you should step back and look at the big picture here? -Declan -- Yours, J.A. Terranson [EMAIL PROTECTED] 0xBD4A95BF ...justice is a duty towards those whom you love and those whom you do not. And people's rights will not be harmed if the opponent speaks out about them. Osama Bin Laden - - - There aught to be limits to freedom!George Bush - - - Which one scares you more?
Plonk this
At 09:20 AM 8/18/04 -0400, R. A. Hettinga wrote: Hey, I have an idea! Why don't I write a script crossposting everything from sci.crypt to cypherpunks! How about a few dozen other on-topic newsgroups and mailing lists too? Go ahead. Are you going to reformat them for legibility first, if necessary? Are you going to personally decide, in *your* opinion, what's worth forwarding and what isn't? In the meantime, remember that Declan's main purpose here is to sniff around for stories. Which is fine, until he starts pretending he's Tim May (I knew Tim May -- he wished I didn't -- and, Mr. McCullagh 1. Having a mainstream meme injector like DMcC is occasionally useful, RAH (Consider that DHS lameass document security made it to the big time and was reported here first.) 2. How the hell can we be reading about crossposting *and* Tim May and *not anywhere* in your flame see the word plonk ??? With all the implied discussion about consumer-end technological filtering vs. central censorship? 3. In all honesty I think Declan's partial-quote followed by a snip and a URL saves bandwidth and also does positively reinforce the folks feeding the authors of the partially quoted content. Of course, subscription-only (or even registration-only) services don't get such caring treatment, they get fair-used 'with prejudice'. And you are free to abuse street-performer-protocols of course, such is the nature of things; and they are free to post their words as .GIFs.
hash attacks and hashcash (SHA1 partial preimage of 0^160)
(This discussion from hashcash list is Cc'd to cryptography and cypherpunks.) Hashcash uses SHA1 and computes a partial pre-image of the all 0bit string (0^160). Following is a discussion of what the recent results from Joux, Wang et al, and Biham et al on SHA0, MD5, SHA1 etc might imply for hashcash SHA1 (and for hypothetical hashcash SHA0, MD5 etc by way of seeing what it will mean if SHA1 eventually suffers similar fate to SHA0). (All as far as I understand so far). Hashcash stresses the SHA1 function in a different direction than sigantures and MACs -- in assuming partial pre-images are hard (ie an k-bit partial pre-image should take about 2^k operations). (Partial 2nd pre-images are also interesting against hashcash -- see below). (As a security argument if partial pre-images say up to mn bits were to turn out to be easy (take much less than 2^m work effort) then this could be used to find full pre-images with 2^n effort, and full birthday collisions with 2^(n/2) effort -- where n is the hash output size). Hashcash is computing partial preimages (of the all 0 bit string). The original hashcash (alpha format) computed partial 2nd-preimages as follows: H( time || resource ) =partial H( time || resource || random ) so the image is H( time || resource ), the pre-image is time || resource, and the (partial) 2nd pre-image is time || resource || random, and the images H( time || resource ) and H( time || resource || random ) partially match. Then several people independently (Hal Finney, Thomas Boschloo) suggested using a fixed image (0^160, ie all 0 bits) instead of the image H( time || resource ). (Hashcash version 0 and version 1 formats use the all 0 bits approach.) ie so one is looking for: H( time || resource || random ) =partial 0^160 As long as SHA1 is a good hash function this should be just as fair a string to find partial pre-images of. So with the last days news: as I read it the MD5 attack can find relatively arbitrary pairs of pre-images (which differ in a few well-chosen bits). As a birthday attack, or perhaps with some more work as a 2nd pre-image attack (2nd pre-image unclear). Birthday style attacks don't help against hashcash as the atacker has limited control over the H( time || resource ) in the alpha format and no control over the 0^160 in v0 and v1 format hashcash. So the way to apply a 2nd pre-image attack (if general 2nd pre-image is possible with the approach) is to find one partial hash collision the usual way (brute force), then re-use the work a bit and use it to get subsequent collisions. As far as hashcash is concerned these will be of approximately the same value as the original (and not full collisions) because they are against 0^n and the partial hash collision (which a full collision was found against) only has 0^k bits of leading 0s. So I think if hashcash were using SHA-0, the following attack should work: spend lots of work create eg a 50-bit hashcash token, use the SHA-0 attack (Wang et al attack has work order 2^40 hash operations) to find another (and maybe a small family of) hashcash stamps which are full collisions with the 40-bit partial collision we just created. I have not seen any indication if there is a family of collisions that come more cheaply after the initial 2^40 operations of the Wang et al approach. As long as the work to create each 2nd pre-image in the family that can be derived from one starting stamp is less than the value of the stamp, the spammer wins in some way. He can get some economies of scale (up to the family size) in creating multiple stamps for the same recipient. However this is not so interesting to the spammer he would sooner have economies of scale in sending to _everyone_ not DoSing one user. Also until we know the family size we do not know how bad even a DoS advantage there would be. For SHA-1 so far none of the above holds. If someone manages to extend the Biham attack to the full 80 rounds then the similar argument to the SHA-0 based hashcash would presumably hold. But this is based on what has been said so far about how the attacks work. Perhpas the same or related techniques now people have seen how they work could be adapted to provide partial pre-images more efficiently than brute force directly. Adam On Wed, Aug 18, 2004 at 02:03:09PM -0400, Jean-Luc Cooke wrote: To be clear: MD5 is borken. The whole thing: http://www.md5crk.com/md5col.zip SHA-0 is broken. The whole thing: http://www.md5crk.com/sha0col HAVAL-128 and RIPEMD-128 and MD4 are also broken using the same techniques. 56 round SHA-1 (out of a possible 80) is broken. The event of the pasat week cast heavy doubt on the current common techniques used in hash algorithms. MD4 was the first to use this unblanced Fiezel network. Wirlpool and Tiger are sometimes called wide-trail hashs. Different beasts entirly. I suspect even SHA-256 and SHA-384/512 may be vulnerable to these attacks to
