Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
Can Noise Be Used To Circumvent Censorship?

By in News
Fri Jun 16, 2000 at 09:07:49 PM EST
Tags: Freedom (all tags)
Freedom

David Madore, mathematician at ENS, describes a method that might be the ultimate weapon in the battle against Internet censorship. In his paper A method of free speech on the Internet: random pads he introduces a system of so-called pads, chunks of random data that are used to encrypt controversial information.


Every byte in the source file is XOR'd with exactly one byte in the random file. The result file, by itself, is totally indistinguishable from white noise, provided that the pad used is truly random. Madore now suggests that users store pads on different servers and use several of them in combination to encrypt data.

A FTP or WWW site that stores one of the pads could argue that they are only storing random noise, and another might do the same. It would be mathematically impossible to prove them guilty of storing illegal information (unless there is a way to prove that one pad was created after the other). Only by the combination of the two (or more) files I am able to retrieve the original controversial information. The critical parts are the links to the pads I need to obtain the information, but those might be traded on a distributed system like Gnutella or FreeNet. Plus links take very little space and can be relocated easily to freespace ISPs.

The concept is a little more complicated than my summary here, so please read the paper (and mirror it, it's GPL'd!). There are already scripts and programs to create pads and restore the original files (including a GUI program for Win32). I might add that the idea of pad encryption is fairly old, already used in WWII -- its advantage is that it is mathematically safe if the pads are truly random and only used once, thus its name "One Time Pad".

Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Related Links
o ENS
o A method of free speech on the Internet: random pads
o Gnutella
o FreeNet
o Also by


Display: Sort:
Can Noise Be Used To Circumvent Censorship? | 23 comments (23 topical, editorial, 0 hidden)
This definitely seems to be somethi... (1.00 / 1) (#8)
by Eloquence on Fri Jun 16, 2000 at 06:21:30 PM EST

Eloquence voted 1 on this story.

This definitely seems to be something new. Wonderful addition to the projects already in the works.
--
Copyright law is bad: infoAnarchy Pleasure is good: Origins of Violence
spread the word!

Security through disingenouity, I l... (2.00 / 1) (#5)
by Rand Race on Fri Jun 16, 2000 at 06:51:20 PM EST

Rand Race voted 1 on this story.

Security through disingenouity, I like it. Fairly clever.


"Question with boldness even the existence of God; because if there be one, He must approve the homage of Reason rather than that of blindfolded Fear." - Thomas Jefferson

Using one time pads to aid in the d... (3.00 / 1) (#6)
by l4m3 on Fri Jun 16, 2000 at 06:53:33 PM EST

l4m3 voted 1 on this story.

Using one time pads to aid in the distribution of banned software such as decss will probably not solve much. This is effectivly saying leave it on an ftp site encrypted, and post the passords on a different site. The only difference here is that both sites have to store the full size of the file, whereas the other would only require one of the sites to store a string. This leads to the other main flaw in this idea, that is you are doubling the transfer time for the data. By using a onetime pad you now need to download the cyphertext, and the key, both of which are the same length. Its seems like a good idea, but it will hardly stand up to laywers, and certainly not make it any easier to transfer illicit software

Firstly, this is no use in the UK a... (3.00 / 1) (#1)
by Fish on Fri Jun 16, 2000 at 07:01:40 PM EST

Fish voted 0 on this story.

Firstly, this is no use in the UK against the RIP bill - where in the case of encryption you are guilty unless you hand over the keys.

Secondly, it comes down to PKI management which in some ways is a much harder problem than the more technical cryptography or key negotiation protocols that exist.

Re: Firstly, this is no use in the UK a... (none / 0) (#20)
by Anonymous Hero on Sun Jun 18, 2000 at 12:33:15 AM EST

Right. But the point isn't to claim the data is encrypted. Or rather, under UK law, as I understand it, you must either provide the keys or PROVE THAT YOU DO NOT HAVE THEM. In this case, if the system were so designed, you would be protected from prosecution, so long as you really don't know what the key is. And as it is, with a pad, which is the key, and which is the data? both are indistinguishable.. so you could argue 'that IS the key. you are just missing the data'.

[ Parent ]
But the user has to trust the pad m... (2.00 / 2) (#4)
by marlowe on Fri Jun 16, 2000 at 07:13:29 PM EST

marlowe voted 1 on this story.

But the user has to trust the pad maintainer not to change the contents of the pad on him, or else how can he decrypt later?
-- The Americans are the Jews of the 21st century. Only we won't go as quietly to the gas chambers. --

Using one time pads to ensure secur... (3.00 / 1) (#2)
by Inoshiro on Fri Jun 16, 2000 at 07:38:21 PM EST

Inoshiro voted 1 on this story.

Using one time pads to ensure security is somewhat obvious, if you don't mind me saying it. The problem is that sources of truly random data require specialized equipment. I know I don't have a radioactive decay measuring chamber, nor a heat differential measurment sensor. And the entropy sometimes takes a while to collect in sufficient quantities. /dev/random blocks for this reason.

Plus the plausible deniability is very weak when you consider that police could confiscate the chunks of random data on the grounds that they could easily be death threats against people (such as the US president).



--
[ イノシロ ]
Re: Using one time pads to ensure secur... (2.00 / 1) (#12)
by royh on Sat Jun 17, 2000 at 12:45:10 PM EST

I've heard of 'random chips'. They rely on some kind of flux between transistors or something like that. If that really works, all computers should have one, because I see cryptography becoming really common eventually.

Anyways, "true randomness" is indistinguishable from "completely unpredictability" in every way. You don't need radiation or any other weird quantum data to get cryptographically secure randomness. You can make a number up in your head if you were sure no one would be able to guess it...

[ Parent ]
I don't really understand how this ... (4.00 / 1) (#7)
by eries on Fri Jun 16, 2000 at 07:47:01 PM EST

eries voted 0 on this story.

I don't really understand how this is effectively different than the encrpyted files that Freenet already uses to relieve a server admin of liability. Am I missing something?
Promoting open-source OO code reuse on the web: the Enzyme open-source project

This isn't exactly a new technique,... (3.50 / 2) (#3)
by fluffy grue on Fri Jun 16, 2000 at 07:58:26 PM EST

fluffy grue voted 0 on this story.

This isn't exactly a new technique, which Inoshiro has talked about in one of his security articles. What's much more interesting to me is steganography, which is a lot easier to decode, though signifigantly harder to store large files with. :)

However, even with a one-time pad scheme, you need to use security through obscurity - the key is symmetric, so you have to somehow point out which file is the pad-key for the ciphertext, and there's always a brute-force approach anyway (match all files with all other files). As a result, the point is still moot. Of course, it'd be easy to get some evidence thrown out since any OTP-mangled data can be made to look like any other OTP-mangled data, so you can easily argue that the prosecutors had effectively "planted" the illicit material on your site. On the flipside, it'd be very easy to plant illicit material on your site. :P
--
"Is not a quine" is not a quine.
I have a master's degree in science!

[ Hug Your Trikuare ]

What about the DMCA? (4.50 / 2) (#9)
by dylan on Sat Jun 17, 2000 at 01:42:48 AM EST

If I created an encrypted key and then placed it out in the wild, and then someone comes along and decrypts I could nail them with the DMCA right? Even if it is only copyrighted material, all I have to do is copyright a few dozen keys and I could nail people left and right. What are your thoughts?

Flaws in this (3.30 / 3) (#10)
by mcelrath on Sat Jun 17, 2000 at 03:13:14 AM EST

First of all, if this is meant as a means of circumventing censorship, it will fail. You must publish which pads contain a piece of data. If someone wants to censor that piece of data, they can find out which pads are used to obtain them, and start suing ftp sites to have those pads removed. The only thing this system gains is a little obscurity.

He states: "Assuming there are about 200 pads floating around. The number of files which can be obtained by XORing 6 pads is ober 50 billion." This is false for the simple fact that in order to introduce a new piece of data into the system, you must XOR it with a number of pads to create a new pad. Therefore, with 200 pads floating around you can have at maximum 200 documents. If you were just going to send the "encrypted" data to a friend you'd use a real encryption algorithm. I'm assuming this is for mass dispersion.

One needs there to be more "innocent pads" (his term) out there than pads derived from data, or a brute force attack becomes feasable. You could just start XORing random things, and come up with something "hidden" a sizable fraction of the time.

Another attack method goes like this: Assuming the person creating data pad used N random pads to create his new data pad, one could simply try all possible combinations of XORing N-1 pads. Then compare this new pad (made from N-1 XORs) with each pad out there. Since data is padded with zeroes, the ends of the pads will be identical. In fact, since the probability of two truly random pads having the same set of M bytes at the end decreases drastically as M increases, one could just perform this procedure on the last few bytes of each pad, and therefore save massive computation time. Using his example of 200 pads in existance, and using 7 of them to hide your document, and assuming the attacker can perform an XOR in 1 clock cycle on a 500 MHz computer and he examines only the last 16 bytes (probability of them being the same for 2 truly random pads= ~10^-37), the attack would take 16*200-choose-6/500MHz = 16*200!/6!/194!/500MHz = 2637 seconds= ~44 minutes.

Something which could be reasonably cracked in 44 minutes I would hardly call secure... This would give you, in reasonable time, which pads were "innocent" and which contained data. Suing to have the data ones removed then becomes feasable. (and no defense based on an innocent pad)

Ok, so his example may have been flawed. It's still a decent idea. But you'd need (by my estimates) >1000 pads out there, and you should use at least 10 pads to hide your data. This would give you a brute force time of over a year. Ideally you want this to spread, and there to be tens or hundreds of thousands of pads out there (keep in mind you want more "innocent" ones than data ones, or examining the ends of the pads will easily recover the few innocent ones).

--Bob
1^2=1; (-1)^2=1; 1^2=(-1)^2; 1=-1; 2=0; 1=0.

Re: Flaws in this (none / 0) (#14)
by Decklin Foster on Sat Jun 17, 2000 at 02:45:10 PM EST

I think this can be remedied with a small extension. The first 32 bits of the file should contain the length of the content. Then, everything past the content is padded with random bits.

[ Parent ]
Re: Flaws in this (none / 0) (#22)
by mdpopescu on Sun Jun 18, 2000 at 03:24:39 PM EST

He states: "Assuming there are about 200 pads floating around. The number of files which can be obtained by XORing 6 pads is ober 50 billion." This is false for the simple fact that in order to introduce a new piece of data into the system, you must XOR it with a number of pads to create a new pad. Therefore, with 200 pads floating around you can have at maximum 200 documents.

The idea is that if someone wants to TRY and combine all those files to see which combinations create protected documents, that someone will have an impossibly difficult job at hand. Without the pointers, you can't find out what documents are stored.

One needs there to be more "innocent pads" (his term) out there than pads derived from data, or a brute force attack becomes feasable. You could just start XORing random things, and come up with something "hidden" a sizable fraction of the time.

Yeah, like 200 out of 50 billion. No problem there :)

Assuming the person creating data pad used N random pads to create his new data pad, one could simply try all possible combinations of XORing N-1 pads.

You need to work on your math skills. If N = 2, you can't "XOR 1 pads". If N = 3, and the total number of pads is 200, you'll have 19.900 combinations to work with. Which is already pretty sizeable.

Since data is padded with zeroes, the ends of the pads will be identical.

The whole idea breaks because of your assumption. The same out-of-band info that leads the "good guys" to the daya ("combine random1.bin with random5.bin and random27.bin to get Metallica-One.mp3") can also indicate the correct length of the result ("btw, the result must be 3,603,127 bytes"), so the files can be padded with random data.

[ Parent ]

foolproof method (none / 0) (#11)
by Anonymous Hero on Sat Jun 17, 2000 at 09:25:55 AM EST

just whisper it in the ear of the person you want to talk to

Re: foolproof method (none / 0) (#21)
by Anonymous Hero on Sun Jun 18, 2000 at 08:48:32 AM EST

Egads! Haven't you heard of directional microphones?

[ Parent ]
maybe not by itself, but... (none / 0) (#13)
by Tr3534 on Sat Jun 17, 2000 at 02:41:30 PM EST

i see a lot of people don't quite agree with this idea, but i think it has some hope. the author himself mentioned the idea on the bottom of the paper: combine it with another system like freenet.

his idea of pad repositorys wouldn't be too viable, from what i can see. but what we need now to protect our free speech is not 1 simple flawless solution: it would be better to create as many systems as possible to protect it and see which ones can work. we need about 50 freenets or so, and let natural (legal?) selection do its job to see which would be the best system.

maybe after some of the systems loose and others win, we can see which aspects work and which don't. then we can build the 1 perfect solution.
Sigmentation Fault: Post Dumped.
hehe this reminds me.... (none / 0) (#15)
by Anonymous Hero on Sat Jun 17, 2000 at 06:07:32 PM EST

of the time a few years ago (in school) when i "invented" a "code" for offline written communication that was just adding random noise to a message (the amount and the spacing of the real information was written using numbers with extra meaning). It worked for a few minutes (no one cared to try decoding the message), but a paragraph would take over 1 page...

Most posters here are missing the point (5.00 / 1) (#16)
by Anonymous Hero on Sat Jun 17, 2000 at 06:40:14 PM EST

Let's say you have controversial document X. There is a random pad out there, Y. You encrypt X with Y, producing Z, and save Z to a different website than Y. Now, who is storing the document? If file dates are not stored, then the servers for both Y and Z can both claim that they are storing just random data, not an encrypted document, and there is no way to prove either of them wrong. You can decrypt Y with Z to get X, or you can decrypt Z with Y to get X. The operation is symmetrical. The real protection here is not traditional crypto security, but legal security through providing reasonable doubt about who purposely published X.

With multiple documents, the situation gets even messier for would-be prosecuters. Any random pad or encrypted document can function as a random pad for some other document. Both Y and Z could become the random pads for other documents A and B, and the servers storing Y and Z have no way of knowing whether this is the case. If prosecutors try to remove Y and Z, the server owners can reasonably argue that this would break any number of other documents, which may be legal and valuable. In fact, those documents may have preceded the illegal documents, and it's not the fault of those publishers that the same pads were later used for nefarious purposes.

As long as a there are a fairly large number of true random pads, and a fairly large number of valuable, non-controversial documents in the system, legal censorship becomes highly impractical. The only weak link is the instructions for reconstructing documents. Given that linking to "illegal" web pages is currently under legal attack, it's reasonable to expect that publishing the instructions for which documents to XOR together could itself be illegal, if the result is an illegal document. Of course, if pages full of such links were themselves protected by these random pads, then you'd be all right--all you'd need is an entry point, on a legal page, and you could follow links until you find what you want.

Re: Most posters here are missing the point (none / 0) (#18)
by Anonymous Hero on Sat Jun 17, 2000 at 09:54:55 PM EST

Oops--that last idea does present a problem. Once a document is out there, you can't really edit it, so how do you add links? I guess you would be stuck with "out-of-band" instructions for reconstructing documents.

[ Parent ]
Some explanations (5.00 / 1) (#17)
by David A. Madore on Sat Jun 17, 2000 at 06:50:27 PM EST

Maybe I should add a few comments myself to make things clearer.

First of all, some posters have asked, why not simply encrypt the data, post the encrypted data in one place, and post the key in another? The reason is simple: if I do that, it is immediately obvious which is the data and which is the key. The point about a one-time pad is that you cannot tell which is which: both are, as far as anybody is concerned, complete white noise. This is not merely a matter of obfuscation: nobody can be convited of anything because for a conviction, guilt must be proven and that is impossible. If you can prove that one pad was made after another, then indeed it is the one which was made using the data, but proving that should be hard; in fact, it is not even true in all cases that the latest pad is the culprit (it can be provably innocent), and it is certainly true that the publication date is not necessarily the creation date.

The crux of the matter is whether it is legal to redistribute white noise. I am not a lawyer, so I will not try to answer that question (whether for European or for American law), but I will at least have made one point: if it is, there is something fundamentally rotten in the legal system. However, I am not much of a libertarian, so I won't go furhter in this.

One thing is certain: for my proposed system to work, we need many, many, many pads. Far more pads than documents to be hidden. Many innocent pads, too. So please consider setting up pad repositories, even if you have nothing to distribute. Remember of course that you run the risk of being sued if someone else uses your pads to encrypt illegal data and if your country's legal system is as rotten as it might be.

Another thing: I cannot claim paternity on the idea. It is suggested (in a slightly different form, with coins flipping) in Schneier's book on cryptography.

Re: Some explanations (2.00 / 1) (#19)
by royh on Sat Jun 17, 2000 at 10:26:04 PM EST

Schneier's book also mentioned a protocol called "Anonymous Message Broadcast"; it allows any number of people to generate data such that the originator can only be traced to the group itself. This solves the same kind of problem as your xor system: if there are more than one possible suspects, then it gets very hard to be convicted, or in extreme cases, there are too many suspects to even investigate. It's very neat because it's bullet-proof anonymity. The problem is it's also very
very bandwith-intensive.

One interesting possibility is to upload and download the xors to a variety of servers just like the article says, but to send the instructions for reconstructing the data using the anonymous protocol mentioned above. Since the instructions will be very small, it won't be so bad on the bandwidth.

[ Parent ]
Re: Some explanations (none / 0) (#23)
by jovlinger on Sun Jun 18, 2000 at 04:32:47 PM EST

Well,

the crux of the matter is whether or not the directions for reassembly of a message is equivalent to the message itself. I suspect that any court willing to restrict the free dissemination of information can be persuaded to rule that they are equivalent.

Johan

[ Parent ]
Can Noise Be Used To Circumvent Censorship? | 23 comments (23 topical, 0 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!