Finnish Firm Claims Fake P2P Hash Technology

An anonymous reader writes "As reported by The Inquirer, a Finnish company known as Viralg Oy claim to have developed software that can create a junk file with the same hash as a genuine p2p download. This, according to the company, can altogether stop the sharing of copywritten files by flooding p2p networks with corrupt/junk data, which then spreads through the network, causing less and less of the original file to be available. However, with the resolve of the p2p userbase, is this software really going to 'beat all Peer 2 Peer pirates at their own game,' or simply prove a minor annoyance?"

Just an annoyance

[whoppers]

People will always creatively find a way around everything!

Re:Just an annoyance

[bherman]

Except /. dupes!

Re:Just an annoyance

[ePhil_One]

Any evidence that what they've really done is found a way to trick the P2P software into reporting whatever hash they want for a given file? The remote client can't really verify the hash until the complete file is downloaded, so you are clearly relying on the comprimised remote computer to computre this. So if they lie about the hash and stream /dev/random onto the network, what is the check?

Re:Just an annoyance

[mancontr]

I meant: The file isn't verified only when complete, every chunk is verified when received. (BT:1/2mb,ED2k:10mb) Sorry, me fail english... (that's not umpossible...)

Re:Just an annoyance

[ePhil_One]

Its a perfectly cromulent word...

Re:Just an annoyance

[Psiolent]

Ah, yes. That ancient principle pontificated by Dr. Ian Malcolm: Life will find a way.

Re:Just an annoyance

[Dutchmaan]

Don't you mean..

"Life... uhhhh.. will..uhh... find a way!"

Agreed

[John Seminal]

I wonder why people who use P2P don't help each other out a little more. For example, you have someone with 200 files shared. They are downloading and sharing at the same time. Sometimes they download a bad file, and share it. It would make more sense to have a "unchecked" folder for downloads, then more it to the "checked" folder to share.

What is neat, or not so neat depending on your point of view, are music files which deteriorate after a while. I don't know how they are made, but I have listened to music that sounds pretty good, but after the 10th playing it starts skipping. Or it could be those skips are not very noticable when first played, but once identified, they become annoying.

Re:Agreed

[metamatic]

I have listened to music that sounds pretty good, but after the 10th playing it starts skipping. Or it could be those skips are not very noticable when first played, but once identified, they become annoying.

I suspect your hard drive is failing.

Re:Agreed

[CSMastermind]

http://www.newscientist.com/article.ns?id=dn4248 [newscientist.com]

Not definitly...I've seen that technology for games(see link) and I remember microsoft had suggested doing that for MP3s and some other things with DRM [soundonsound.com]. I don't know if the it's been put into place yet or not.

Re:Agreed

[UrgleHoth]

What is neat, or not so neat depending on your point of view, are music files which deteriorate after a while. I don't know how they are made, but I have listened to music that sounds pretty good, but after the 10th playing it starts skipping.

These are zoot files. Every once in a while, they skip a groove.

Re:Agreed

[Nebu]

Sometimes they download a bad file, and share it. It would make more sense to have a "unchecked" folder for downloads, then more it to the "checked" folder to share.

The filesharing programs I use force you to share the directory you download into. Sure, I could name the download directory "unchecked", but few people bother to view the full paths as set by the sources from the people they download.

What is neat, or not so neat depending on your point of view, are music files which deteriorate after a w

Re:Agreed

[Jeremiah Cornelius]

Shareaza has a "commenting" system for just this purpose.

Re:Agreed

[Jjeff1]

I've also heard MP3s that work fine on my PC, but skipped horribly on my car player. Different players handle corrupted or badly compressed files differently.

Re:Agreed

[Have Blue]

Because the vast, vast majority of P2P users are trying to get stuff for free, not create an alternative-media-distribution free-expression utopia. They're not going to do anything on anyone else's behalf because it does not directly benefit them or immediately help them get more free stuff faster.

Re:You're just a paranoid troll. That's not insigh

[Sj0]

eMule definitely helps you better yourself.

Patience is a virtue, right?

incomplete downloads

[TamMan2000]

I wonder why people who use P2P don't help each other out a little more. For example, you have someone with 200 files shared. They are downloading and sharing at the same time. Sometimes they download a bad file, and share it. It would make more sense to have a "unchecked" folder for downloads, then more it to the "checked" folder to share.

That would break a feature which enables greater sharing... Uploading of parts of files that you do not have all of. Think BitTorrent, but less organized...

Re:Agreed

[Anonymous Coward]

What is neat, or not so neat depending on your point of view, are music files which deteriorate after a while. I don't know how they are made, but I have listened to music that sounds pretty good, but after the 10th playing it starts skipping.

The files are perfectly normal -- you're simply realizing that most of the music out there is trash which simply repeats the same verses over and over again so much that it sounds like it's skipping. Add to that the endless remixes which ruin perfectly good songs, and I can see how you'd mistake that with repetitive skipping. Rest assured that a better choice in music will alleviate this problem.

Re:Not going to work that way....

[DickBreath]

Just need a better hashing mechanism.

How about a hash of the entire file, plus a hash of every 128 KB segment. Constructing a file that matches all of the 128 KB section hashes, plus the overall hash is a much more difficult problem.

Plus, you know after downloading only 128 KB that the file is not the real deal. It only takes 8 * 128 bytes or 1024 bytes of hash information per megabyte of download -- really only a few packets to communicate the hash list for, say, a 10 MB file. The benefit for this

Re:Just an annoyance

[merlin_jim]

For instance, hash with two different algorithms. In theory it is possible to find a file that can hash to the same value in two different algorithms, but its a lot harder than finding a file that hashes to a specific value in one algorithm.

Re:Just an annoyance

[merlin_jim]

Actually we were both wrong; it is (2^keylength)^2 number of keys. However this number is equivalent to 2^(keylength*2), not 2^(keylength^2)

Why would this not be "just double work"?

First you find all files matching the first hash, then filter out one matching the second.

And where exactly do you think the work is occuring? Computing the second hash. If you have one hash algorithm, you only have to match once. If you have two hash algorithms and you did it this way, you have to match enough with the first algorithm to find a match for the second algorithm. This isn't twice as much work, this is twice as much keyspace (with each bit increase in keyspace representing twice the work)

Re:Just an annoyance

[Hannes Eriksson]

Thank you for pointing out my mind slip.
While I'm at it...

With an 8-bit hash key, there are 256 possible keys. This means that 1/256 files will match the hash. With another hash function with 8-bit keys there are 1/256/256=1/65536=1/(256^2)=1/((2^8)^2) files matching the two keys. This keyspace is indeed the same size as that of a 16-bit key with the important difference that it is much easier to find matches if you can partition the search space.

Picture yourself an unpainted 65536-piece square jigsaw puz

This is so stupid

[commodoresloat]

If the copyright issues were not present here and someone built a program that did something like this, they would be universally reviled as a malicious hacker. Hey! Here's a program that creates phony web pages with false information masquerading as legitimate pages! Here's one that copies Excel spreadsheets on the web and subtly pollutes the database with phony information, then stores multiple copies around with the same name! This handy tool attaches to a photocopy machine and randomly scrambles the words on the page you are photocopying!!

P2P is a technology. Yes it can be used for copyright violations, just like a photocopy machine or tape recorder. But it also has amazing possibilities in terms of creating a universal organic archive. Crippling like this -- and through using lawsuits -- is an unnecessary attack on a system in its infancy.

The copyright issues will work themselves out -- until the 20th century human art and ingenuity survived for thousands of years without the ability to make millions selling recorded music and video. If p2p has a major effect on the entertainment industry's ability to profit (and I'm still not convinced that it really will), human art and culture will survive. And people will continue to find ways to make a living creating art.

Re:This is so stupid

[WaterBreath]

Yes it can be used for copyright violations, just like a photocopy machine or tape recorder.

And those things were each also embroiled in copyright lawsuits by big corporations in their day. The difference is that today, the big corps have finally gained enough political leverage to get it their way.

Corporations are the new first-class citizens. Any individual, regardless of race, gender, or creed, is second-class compared to a corporation.

I honestly fear that by the time the American people get fed-up enough to realize this, the transformation will be complete, and we will be powerless to change it.

Re:This is so stupid

[patio11]

This doesn't cripple P2P. It just makes a dent in pirate-2-pirate. There is a difference, you realize. The Blizzard Bittorrent patch downloader will still function perfectly. Indie bands who release their new CDs to Kazaa won't have anybody trying to pollute their download pools. And it probably won't even work, more's the pity.

Re:This is so stupid

[BlowChunx]

Nope, the solution to this is the Grokster case. Once you show that the creator of a product is liable for it's (mis)use, you can sue the pants off the company that made corrupted files that crippled your indie band's viability.

Hell, you could hire hackers to flood the network, prove damages, and then earn <dr evil> BILLIONS </dr evil>. Of course, this implies the Supreme Court in the US rules the way I am implying...

Re:This is so stupid

[ComputerizedYoga]

That is assuming the "1337 hax0rs" don't get hold of the algorithms. I can just imagine people messing around with p2p networks just for fun.

early in the lives of gotwoot and scarywater (large, fairly well known fansub bittorrent tracker sites), they encountered ddos issues...

people were using botnets and what amounts to trivial network code to send false complete requests to the trackers, and volunteering as seeds. So, in a field of maybe 100-200 legitimate seeds, there would be ~30,000 fakes poisoning

Re:This is so stupid

[kamapuaa]

You realize this technology doesn't block *all* p2p traffic, right?

The main concern shouldn't be the use by the RIAA or MPAA to stop the bootlegging of copyrighted concerns. It's within their rights. The main concern should be possibility of the technology getting out to griefers who block the legitimate use of Bittorrent.

But honestly, if this doesn't get out to hackers (which it probably will), this is a lot better solution than having to sue warez websites, or the users who illegally trade movies.

Re:This is so stupid

[StikyPad]

If the copyright issues were not present here and someone built a program that did something like this, they would be universally reviled as a malicious hacker.

This isn't some idealistic universe where all decisions are morally right or wrong regardless of the criteria. Your knee-jerk reaction is baseless and inflammatory.

"Look people.. If this gangrene wasn't present here, chopping off my leg would be completely unacceptable! How can we just go around chopping off people's legs? Just because I have g

Re:Just an annoyance

[bman08]

The magic of this system is that it also works in reverse: "Your honor, my client hates p2p filesharing. All those songs he downloaded, he thought they were phonies with duplicate hashes and deliberately shared them in order to poison the network."

Nope

[No Such Agency]

Sorry, that level of doublethink is only alowed for corporate lawyers. Your lawyer will be smacked down for trying it, since it is not a defense permitted to second-class citizens (see earlier post).

They have cracked strong hashes, huh?

[Flywheels of Fire]

This is not true. It might work on Kazaa but most other P2P networks use MD5 or better. Okay, they have found collisions but no one has found a way to generate file for a given key. So the claim by the finnish company is bogus.

Or they have cracked even the strong hashes. In which case they are really cool. I know Mr. Torvalds is Finnish, but I doubt even he could come up with algorithms to do that.

In their conceited press release, they have compared Spoofing vs DRP/a [mithuro.com]

Re:They have cracked strong hashes, huh?

[martok]

Indeed. In order for example to do this with
BitTorrent, they would need to be able to
generate colisions in sha1 hashes. The
implications of which would go well beyond p2p.

Re:They have cracked strong hashes, huh?

[CharonX]

And the best:
You cracked SHA-1. Oh well, time to switch to SHA-256

Re:That sig is from diskworld, isn't it?

[CharonX]

Hehe, yup, its one of the great lines HEX produced.
I can really reccommend Terry Pratchett's [wikipedia.org] books to everyone.

Re:They have cracked strong hashes, huh?

[CDarklock]

I've wondered this myself. Theoretically, if you MD5 a file *and* SHA1 a file, the complexity of matching both hashes is 288 bits. Basically, given a standard distribution, 1 out of every 2^128 files will match the MD5 of your file... and 1 out of every 2^160 of those will match the SHA1. (1/2^128)/2^160 = 1/2^288.

I'd really like to know if this interpretation is flawed. Even when hash algorithms are broken, if you parallelise them, you can still get enough bits of security to work. It seems to me that you

Re:They have cracked strong hashes, huh?

[redhog]

Nah, you are both wrong. Two 160bit hashes are prolly somewhere in between as strong as a 320bit hash and a 160bit hash, depending on exactly how the hash-values distribute over the input space. If the hash where perfect, the distance between any two hash-values with one bit of difference would be the same. However, in reality, that would hardly be the case except for some hashes with a given data-to-hashsize-ratio. But taking two random hashfunctions would probably combine into one where many bits are redundant (not the same bits for all hash-values of course). Hm, hope that goes for enought of an explanation. Otherwize, go read up on coding theory at mathworld.wolfram.com or wikipedia. A search for "Hamming distance" might also be a good start :)

Re:They have cracked strong hashes, huh?

[CDarklock]

> Two 160bit hashes are prolly
> somewhere in between as strong
> as a 320bit hash and a 160bit
> hash

That's exactly what I'm saying. If the two hashes are completely independent -- zero bits of redundancy -- then you have a 320 bit hash. If they're completely redundant, you have a 160 bit hash. So the question is how independent MD5 and SHA1 are; if they're completely independent, then they combine to a 288 bit hash. If they're completely redundant, they combine to a 160 bit hash and you may as w

Re:They have cracked strong hashes, huh?

[LiquidCoooled]

There is a world of difference between a valid collision and an invalid one.

The anti p2p software appears to find invalid collisions which mean the downloaded file is useless.
Finding collisions where the movie/app/document remains valid will be MUCH more tricky.

Re:They have cracked strong hashes, huh?

[garbletext]

Yeah! easily! i'm working on a free program that turns a 1KB hash into a 4 GB DVD ISO, or anything else you want! it turns out we don't need to share files, just write the hash down on a piece of paper and you can transmit ANY size file with almost NO bandwidth! and if you hash the hash, it gets smaller and smaller until it's just a zero or a one!

I'll make millions!

Re:They have cracked strong hashes, huh?

[darkmeridian]

Can they have a collision that is the same size as a desired file? Guess not. Haha.

Re:They have cracked strong hashes, huh?

[Sycraft-fu]

I'm sure that they just found some P2P client that has a weak hash and managed to make a generator for that. Then they are either morons that don't know there's more than one hash algorithm, or they do and are just pimping it to try and get money.

Either way, I give it about a 0 chance they figured out how to quickly find collisions in a strong hash space. If they had, they'd be talking to the NSA, not the RIAA.

Re:They have cracked strong hashes, huh?

[jdray]

...or they do and are just pimping it to try and get money

Safe money bets that horse.

Re:They have cracked strong hashes, huh?

[drgonzo59]

Agree, this is more like news for the marketing and general folk who don't know what hash is. From the news post the implication is that they can generate another file with the same hash as a given file. If they had indeed found a crack in all the hash algorithms (all SHAs and MDs) the news wouldn't be about P2P but about a major breakthrough in cryptography.

Re:They have cracked strong hashes, huh?

[Trurl's Machine]

Either way, I give it about a 0 chance they figured out how to quickly find collisions in a strong hash space. If they had, they'd be talking to the NSA, not the RIAA.

What makes you so sure that NSA pays better?

Re:They have cracked strong hashes, huh?

[Feyr]

they pay in life

"hand this over, or we'll make sure you never see the sun ever again"

Re:They have cracked strong hashes, huh?

[tryone]

"hand this over, or we'll make sure you never see the sun ever again"

Oh noes! The NSA are going to destroy the sun!

Re:They have cracked strong hashes, huh?

[Stiletto]

Why the stereotype about NSA agents disappearing people? That kind of crap only happens in dictatorships. You can't do that in the USA because we are the land of the free! I know some NSA agents and they're great gu.f.a.,.adf,.ty....mrgATZ+++++

Re:They have cracked strong hashes, huh?

[Local ID10T]

Have you ever tried turning down a request from the NSA? Talk about an offer you cant refuse...

Blaaaaaah

[mindriot]

Not only the company's, but also the submitter's claim seems to be bogus. Neither the Inquirer article nor the viralg.com website anywhere seem to be talking about hashes. Moreover, I'm kind of wondering where the Inqurer got their stuff from, since the viralg website contains... nothing. Nothing but blaah. No word at all on how they protect anything from anyone. A random link to the Finnish Top 40 allegedly showing how BMG became the market leader for domestic music. Umm, except that nothing whatsoever proves that Viralg had anything to do with it. (If you have evidence to the contrary, please post it!) Then there's some blurb about being insiders with mathematical knowledge up in the lonely north where there's nothing else to do is what got them where they are. So, where are they? Not like they actually tell us. No contact information besides the email address either (and nothing in the whois info). Apparently, being up in the lonely north with nothing else to do doesn't get you much further than producing a nonsensical website claiming you know how to save the world, find the question to the answer to life, the Universe and everything, with "stunning results."

And, breaking hashes, nonsense. If anything, maybe they are managing to manipulate P2P protocols to send you data you weren't supposed to be getting, but which is not actually going into the checksum?

Nothing for you to see here, methinks... and here I am wasting my time actually writing a reply to a trollish article. :)

On another random note, I kind of liked how their website looked in links.

Empty. :)

Re:They have cracked strong hashes, huh?

[me at werk]

Wouldn't it not be the same size, though? "Wow, this Britney Spears MP3 is 5 times the size yet it has the same hash!"

Sure, you can find a collision, but finding a collision which has a size close enough to the more popular real file is a lot more difficult, I'd think.

Re:They have cracked strong hashes, huh?

[mboverload]

Bittorrent clients ban IP's that send them a certain number of bad pieces.

RIAA can lie to the tracker

[davidwr]

The RIAA can put out "evil clients" that find good files and lie to the tracker telling the tracker it's a bad file.

Unless the tracker double-checks the file itself, or has some way to trust the clients it's getting reports from, it's vulnerable to being lied to.

Bite My Shiny Metal Ass

[B3ryllium]

Bah! Screw you guys. I'll just make my own P2P hash algorithm. With blackjack. And hookers. In fact, forget the P2p hash algorithm. And the blackjack.

Re:Bite My Shiny Metal Ass

[Saeed al-Sahaf]

Bah! Screw you guys. I'll just make my own P2P hash algorithm. With blackjack. And hookers. In fact, forget the P2p hash algorithm. And the blackjack.

Forget the p2p algorithm and the blackjack, I'll take the HASH!

"Copyrighted"

[As Seen On TV]

It's "copyrighted," not "copywritten." We're talking about rights, not writings.

Preview/Trailer

[fembots]

I guess there are two schools here.

One believes this kind of fake files will only add burden to the internet, as users will just download one fake file after another until they got a hit.

The other believes that such annoyance will put most people off, because the total time/cost it takes to acquire something is now higher than the actual product.

I don't think MP3s will be affected because you can start playing the song if you've got the first bit. Can/will other file formats do that too?

Re:Preview/Trailer

[KarmaMB84]

I'm not downloading copyrighted music, I'm downloading junk to burden the p2p network with useless traffic. It just so happens I go a real file in the process!

Coral Cache

[Anonymous Coward]

I took the liberty of pre-caching the site on Coral before it went live - http://www.viralg.com.nyud.net:8090/index.html [nyud.net]. I think Slashdot should really consider doing this as part of the proceedure...this site won't last a minute under the weight of our collective, nerdy asses.

Re:Coral Cache

[lpp]

won't last a minute under the weight of our collective, nerdy asses

What would?

Re:Coral Cache

[Talking Goat]

I'm trying to figure out why the guy on this website's banner is pointing (what looks like) a Gamecube controller at me. Is he going to ruin our P2P experience from a Nintendo? How 1337.

The question is..

[k98sven]

How big is that 'junk file'?

Possible? Yeah

[robpoe]

I've always thought it would be extremely possible to create a file with the same MD5 hash.

Now, what the company has to do is create a file of the SAME FILE SIZE, with the same MD5 hash that's a fake .. then I'll be impressed.

There is one way....

[Col. Blackwolf]

You can always ensure an identical hash and size by filling the file with identical data and then uploading the new file to the P2P network. Imagine how quick filesharing would stop if all of the major industry groups started doing this. P2P wouldn't stand a chance, no siree.

Re:Possible? Yeah

[Council]

Oh, I get Mr. Schneier's thing and I'm not behind on the news; I am under the impression that that there have not been demonstrated preimage attacks on MD5, which is what I was referring to.

Re: SHA-1:

These are not theoretical results but actual collisions.

Again, here it is preimage attacks that are the problem, not just any collisions. But the results mentioned in the link are NOT actual collisions, just an algorithm to produce those collisions that might be feasable to run sometime soon. They didn't

Minor annoyance at first....

[dgatwood]

...but if you can create a random junk file in a reasonable period of time, the mechanism can probably be extended easily enough to make it possible to add arbitrary junk to the end of a trojaned executable in a future version of the tool....

claims?

[geoffspear]

I read the article and everything I could find by following links on their website, and found no reference to how their product supposedly works, or any claim having to do with identical hashes. Did the article submitter just make up the identical hash claim, or is there more information on this product available somewhere else?

What hashing algorithm do they claim to have broken so completely? Sounds like BS to me.

Re:claims?

[SpecBear]

Looks like a fraud/hoax/jok/whatever.

• There's no text on the site. It's all images and flash animations. This immediately raises suspicions.
• They claim that the technology has already been successfully used by BMG.
• No Company info, phone number, or address, just a single email address
• No details of how the tech works.
• Claims 100% effectiveness.
• Red alert phrase: "virtual algorithm"

Anybody remember the name of that company that promised extremely high lossless compression rates on arbitrary files?

Allow me to be one the first to say...

[Ann Elk]

Bullshit. "Virtual Algorithms" my ass.

Re:Allow me to be one the first to say...

[bigberk]

Bullshit. "Virtual Algorithms" my ass.

You called it. They can either do proper MD5/SHA1 collisions with unchanged filesize, or they can't. My guess is, they can't.

Secure Hashes vs. Fake Files

[CharonX]

Well, there have been reports that some hash algrorithms are prone to "collisons" i.e. it is possible to find, with some effort, files that produce the same hash value and having the same size despite having different content.
The easy solution:
Use a safer Hash function.

Re:Secure Hashes vs. Fake Files

[Capt'n Hector]

Use a safer Hash function.

Or even better, use more than one. If file_x is hashed 10 different ways, using 10 different algorithms, there's no way the file generated by this firm will behave the same way for ALL of them, perhaps not even for two.

Re:durfy durfy

[adamruck]

Partially true. If you take your strongest hash and just increase the number of bits of the result, assuming that someone can crack that hash, it will simply take longer to compute a collision. This would probably increase in a linear fashion.

Howoever, If you use more than one algrithm, it becomes harder to find a collision that fits both systems AND has the correct file size. This would probably increase in a exponential fashion(read: impossible).

For all the new 'copysafe' tech that comes out...

[FortKnox]

... it only takes most pirates (at most) a week to find a work around and everything is back to (pirating) normal.

Er..

[t_allardyce]

They might be able to fake one hash, but don't most P2P networks use a combination of different hashes? if not then it would be easy to implement - you can either go for more than one different type of hash like md5 and sha etc or add salt/pepper to a chunk and make any number of hashes where each additional hash makes it insanely harder to crack..

Add another hash

[Fjornir]

*shrug* Then the p2p networks will respond by using two different hashing algorithms, and a collision will be that much harder to generate.

Their site is down so I can't get any real details, but I think this is smoke and mirrors in any case.

Possible Solution

[BlacBaron]

Use 2 (or more) different hashing algorithms on the file, and check the file size.

I'm pretty sure that should reduce the collisions to some stupidly small value.

Link to the patent application

[Zarhan]

in pdf form [espacenet.com]

Note the claims section and references - they keep talking about Napster and Kazaa - nothing about anything that use hashes.

Re:Link to the patent application

[antime]

Thanks for the link. If you look at page four of the document, it explains that because the UUHash algorithm used by Kazaa hashes only a small part of the file it is feasible to change other parts and produce hash collisions through brute-force attacks. Then the attacker just pretends to be a normal node and feeds bad data into the network.
The obvious way to counter this is to either fix Kazaa or switch to a network where the whole file is hashed.

Only The Whole File?

[TheFlyingGoat]

Don't most P2P programs use MD5? I was also under the assumption that P2P programs do a checksum on each piece of the file they receive, and if it's inaccurate it automatically re-downloads that part of the file. I've had pieces of a bittorrent download fail due to corruption and the client has just downloaded that part again.

Seems like this company's setup would only work in very specific circumstances, meaning it won't have much of an effect at all.

Seems bogus to me

[gtoomey]

It takes 2^69 operations to find collisions with SHA1 [cryptography.com]

Unless they have lots of supercomputer time, seeding the occasional p2p file with bad data will be very expensive.

Re:Seems bogus to me

[pjrc]

Remember that those 2^69 "operations" (each many CPU cycles) are for a SHA1 "collision" attack. A "preimage" attack that would be necessary to inject corrupt data into a p2p network using SHA1 (such as Bittorrent) is much harder and has not been discovered and published.

Quoting from the linked page [cryptography.com]:

Q: What is a collision attack and a preimage attack?
A: A preimage attack would enable someone to find an input message that causes a hash function to produce a particular output. In contrast, a collision attack finds two messages with the same hash, but the attacker can't pick what the hash will be. The attacks announced at CRYPTO 2004 are collision attacks, not preimage attacks.

Re:Seems bogus to me

[imsabbel]

haha.

A sha hash is what? 256bit?
so you get 32byte per block.
Now how many pertubation can you get...
Lets assume your p2p software uses block sizes of 4byte. For a complete database you would need 2^32*32Byte=128Gbyte.
For a complete 8byte set you would need 2^64*32byte.
All the storage space in the world wouldnt even be enough for a 128Byte block, and bittorrent uses a minimum of 32Kbyte, edonkey even has a hash over the total filelenght.
For 32Kbyte, there isnt enough matter inthe universe to store enough inf

Sharing

[man_ls]

The time-vs-accuracy tradeoff is a big one. One client which I know some people who use, takes almost 48 hours to index a full hard drive of files to share, and hash them all.

Anything less robust, you're liable to have collisions, such as these, apparently. Any more, and if you have a lot of files, there's a major time committment before you can actually begin to serve anything -- most people aren't willing to have their CPU pegged for 2 days straight while their P2P client hashes their 35,000 MP3s and 200 movies, or so.

Hash

[PureCreditor]

isn't the whole point of a hash is that it's computationally-infeasible to create a file that that H(new file)=H(original).

if this technology is true, it'll completely undermine the safety of today's unix passwords, which are stored in clear text of their hash.

By God

[somethinghollow]

If I have one of these files and share the hell out of it, I better not be contacted by RIAA. If this spreads, not only will it make sharing difficult, it will make tracking legitimate (haha) piracy more difficult to detect. This (sort of) reminds me of a more high tech version of the time everyone started changing the name of their tracks to things like "Br1tn3y Sp34rs" to evade blocked searches.

Hashes are cheap, use several

[mihalis]

Let's just concede they can actually produce a junk file which has the same hash. I'll even skip over which hash - let's also say it's one of the useful ones.

I'd be tempted to step up the credentials for a file, say one hash for the entire file, and another for the first 1kb, and so on. It should get significantly harder with each additional verification point.

If they crack the hash

[miracle69]

I'm switching to hashish.

Sword Cuts Both Ways

[4of12]

If someone can really poison P2P networks with junk that hash matches (and I have a difficult time believing they've cracked all the hash generators), then consider some hypothetical entity probing illicit distribution of copyrighted material using hashes. They could end up making false accusations against individuals for trading trash instead of Trash©.

bittorrent uses sha1

[pjrc]

Hard to believe this is gonna work on bittorrent... the most important file sharing app in use today.

The Bittorrent protocol uses SHA1 hashing [bittorrent.com].

Yes, there was recently a paper presented that "broke" SHA1, but the result is 2**69 operations instead of 2**80 [schneier.com] to find a SHA1 collision. 2**69 is still a very large number of operations... a lot less than a full 2**80, but still a prohibitively large number (more costly than the actual realized losses the entertainment industry is suffering).

Collateral Damage

[DumbSwede]

Since P2P can also distribute legitimate files (I am looking into one such project even now) this can only be seen as something that will lead to unintended collateral damage(assuming it works of course).

Here is a tool specifically designed to cripple the flow of data, how can it be thought of as anything but a virus? Should it work I could see TV and Movie studios using it surreptitiously to cripple net-based fledgling media companies.

This should be outlawed just like another intentionally malevolent software. Why shouldn't everyone write viruses and malware when the big guys do it and the government sanctions it. This is just the kind of thing that keeps web commerce from taking off to its full potential.

Interesting idea, how can we apply it to spam?

[Progman3K]

If increasing the noise ratio on P2P networks is a good thing, maybe we can use a similar technique to defeat spammers?

For example, if we could pollute spammers' email address databases with millions of bogus e-mail addresses, then instead of delivering millions of spam e-mails to real e-mail accounts every day, maybe spammers could only reliably send a few hundred to users, the rest of their messages would be to bogus addresses and be "noise" that spammers have to deal with.

How could we go about doing this?

Re:Interesting idea, how can we apply it to spam?

[rbarreira]

Your post advocates a

(X) technical ( ) legislative ( ) market-based ( ) vigilante

approach to fighting spam. Your idea will not work. Here is why it won't work. (One or more of the following may apply to your particular idea, and it may have other flaws which used to vary from state to state before a bad federal law was passed.)

( ) Spammers can easily use it to harvest email addresses
( ) Mailing lists and other legitimate email uses would be affected
( ) No one will be able to find the guy or collect the money
( ) It is defenseless against brute force attacks
( ) It will stop spam for two weeks and then we'll be stuck with it
( ) Users of email will not put up with it
( ) Microsoft will not put up with it
( ) The police will not put up with it
( ) Requires too much cooperation from spammers
( ) Requires immediate total cooperation from everybody at once
( ) Many email users cannot afford to lose business or alienate potential employers
(X) Spammers don't care about invalid addresses in their lists
( ) Anyone could anonymously destroy anyone else's career or business

Specifically, your plan fails to account for

( ) Laws expressly prohibiting it
( ) Lack of centrally controlling authority for email
( ) Open relays in foreign countries
( ) Ease of searching tiny alphanumeric address space of all email addresses
( ) Asshats
( ) Jurisdictional problems
( ) Unpopularity of weird new taxes
( ) Public reluctance to accept weird new forms of money
( ) Huge existing software investment in SMTP
( ) Susceptibility of protocols other than SMTP to attack
( ) Willingness of users to install OS patches received by email
( ) Armies of worm riddled broadband-connected Windows boxes
( ) Eternal arms race involved in all filtering approaches
(X) Extreme profitability of spam
( ) Joe jobs and/or identity theft
( ) Technically illiterate politicians
( ) Extreme stupidity on the part of people who do business with spammers
( ) Dishonesty on the part of spammers themselves
( ) Bandwidth costs that are unaffected by client filtering
( ) Outlook

and the following philosophical objections may also apply:

(X) Ideas similar to yours are easy to come up with, yet none have ever
been shown practical
( ) Any scheme based on opt-out is unacceptable
( ) SMTP headers should not be the subject of legislation
( ) Blacklists suck
( ) Whitelists suck
( ) We should be able to talk about Viagra without being censored
( ) Countermeasures should not involve wire fraud or credit card fraud
(X) Countermeasures should not involve sabotage of public networks
( ) Countermeasures must work if phased in gradually
( ) Sending email should be free
( ) Why should we have to trust you and your servers?
( ) Incompatiblity with open source or open source licenses [hey, it's Microsoft... they've probably already submitted the patent...]
( ) Feel-good measures do nothing to solve the problem
( ) Temporary/one-time email addresses are cumbersome
( ) I don't want the government reading my email
( ) Killing them that way is not slow and painful enough

Furthermore, this is what I think about you:

(X) Sorry dude, but I don't think it would work.
( ) This is a stupid idea, and you're a stupid person for suggesting it.
( ) Nice try, assh0le! I'm going to find out where you live and burn your house down!

Bad news for the music industry

[nizo]

What will they do when people like the files with random noise better than any of the current music?

Just finding a hash collision isn't enough really

[James Youngman]

I suppose their method is based on the fact that it turns out that it's easier to find SHA-1 and MD5 collisions than was earlier thought [schneier.com]. In fact there's another paper [hyperlink.cz] (this paper is not by the Chinese team) which shows that this can be achieved on individual PCs in mere hours, which puts this sort of thing into the realm of commercial exploitability.

For example, you send the company a copy of the .mp3 file you want to drive out of circulation. They feed it to a computation cluster and eventually out comes another file which has the same hash. You then publish this new file with the same filename on the victim P2P network and hope that it spreads enough to poison the P2P well, so to speak. There are a number of problems with this scheme (assuming of course that this is the sort of scheme that they offer):

1. The new 'collision' file might have the same MD5 hash, but is it a valid MP3 file?
2. All it takes to beat this scheme is for P2P software to use more than one hash function, for example

   hash (data)
   {
   return concatenate(md5(data), sha1(data));
   }

   After all, even though we now know how to find collisions in MD5 and SHA-1 (quite slowly) we don't yet know an efficient way to find a single file that is a hash collision for both of them.
3. If the company paying the money for the 'collision' file is doing so because somebody has spread their material around the P2P network, then the file must be quite prevalent. So why would they expect the 'collision' file to preferentially spread around the network enough to displace the original file?

Why this won't affect Slashdot.

[stlhawkeye]

As anybody who reads Slashdot knows, perfectly legal and legitimate downloading comprises the majority of internet downloading, and actually bolsters profits to member organizations of such content ownership cartels as the RIAA.

"This, according to the company, can altogether stop the sharing of copywritten files by flooding p2p networks with corrupt/junk data"

Slashdot should rejoice at this! Since none of us download illegal material and nobody that any of us knows downloads illegal material, this technology might allow us to continue our legal, legitimate downloading of media and only target those handful of ruffians who engage in illegal filesharing. I'm all in favor of this!

Missing the Point

[Jherek Carnelian]

Y'all are missing the point.
These guys are not about taking out P2P.
They are part of a denial of service attack against the RIAA and MPAA, and we need more companies like them in order to make it effective.

You see, it works like this:

1) Make up a really snazzing sound anti-piracy product,
2) Back it with lots of sexy buzzwords and hand-waving
3) Sell, sorry LICENSE, it for lots of money to the (RI|MP)AA.
4) When it fails to perform, let in the next guy ready to do the same.

Repeat until (RI|MP)AA bank accounts have been depleted.

As someone who actually _does_ have a P2P attack..

[Effugas]

It's a couple pages in my paper here [doxpara.com]. Basically, the first 300Kb of Kazaa's files are hashed normally, then every 32Kb chunk of the file is hashed independently. This allows independent chunks to be downloaded out of order. These out of order chunks are recursively hashed against one another to create one final value, called a "kzhash" [chronosempire.org.uk], which is verified after the file is downloaded.

The attack is to use the recently released collision -- which creates two blocks that, when mixed against the default initial state of MD5, emit the same system state. Every 32K, you can embed one or the other in the file you're transmitting, and kzhash can't tell. What can you do with this? Morph a file as it traverses the network; have an installation executable describe the systems its being installed on as it propogates through a network. With a fairly large installer, you'd get quite a few bits in there.

You still don't get to do random noise, and while it's no Tiger Tree, kzhashing doesn't appear so exploitable that this group is likely to have anything. I could be wrong, but then, virtual algorithm? Right.

Re:Already done

[B3ryllium]

By the time this is submitted, it will probably already be redundant (even though it's informative :)) - but the hashes are used for parallel download streams of the same file. So, if you saturate the network with the same hash, you can corrupt the data when the client automatically assumes it's the same file and tries to merge it with the other incoming data.

Re:Already done

[rkcallaghan]

how will this be different from the flodding of fake files already on P2P networks like Kazaa. Sure, the hash will be the same, but what "JHoe Sixpack" looks at hashes?!

Joe Sixpack may not look at hashes, but his P2P software probably does. I know aMule uses the hash to match files that have had their names changed.

~Rebecca