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]
Think Cash

By hardburn in Internet
Wed Apr 11, 2001 at 06:46:22 PM EST
Tags: Help! (Ask Kuro5hin) (all tags)
Help! (Ask Kuro5hin)

There has been some discussion on the Freenet development mailing list in the past about the idea of "Think Cash". This story intends to describe the problem that brought up this discussion and open it up for wider peer review on Kuro5hin.


The problem is that an attacker of Freenet or another distributed network may insert a lot of meaningless data very quickly, possibly overloading select nodes in the network. Therefore, some sort of slow down must be in effect for someone to insert a given piece of data.

The first suggestion that came up was "Hash Cash", whereby the inserter must spend a given amount of CPU cycles to compute a "hash", or a computationaly difficult problem. However, Moore's Law works against us in this system, and it also make it easier for people with very fast computers to insert data then those with slower ones, thus creating a division of the haves-and-have-nots that the Freenet developers aren't happy with.

The next suggestion was "Think Cash". There are certain rules that must be applied to Think Cash:

1) It should be easy for a computer to generate the test.
2) It should be difficult for a computer to perform the test, but easy for a human.
3) It should be easy for a computer to check for the correct answer to the test.

The idea is that upon an insertion, the computer on the other end generates a test and asks the human sitting at the computer to solve it. The human answers and sends the answer back to the computer. Given that the answer is correct, the computer allows the insertion of the data.

There have been many suggestions for doing this ("which one of these pictures is a bird?" might be one such test), but nothing that can really fit all the rules above. It is a fascinating problem, one which I'm sure many will enjoy thinking about. However, by merit of being a fascinating problem, it is also a difficult problem. Thus, I share it with all, hoping to find an answer.

Sponsors

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

Login

Related Links
o Kuro5hin
o Freenet
o Also by hardburn


Display: Sort:
Think Cash | 65 comments (62 topical, 3 editorial, 0 hidden)
Got to be some form of pattern recognition (3.50 / 2) (#1)
by streetlawyer on Wed Apr 11, 2001 at 10:11:03 AM EST

Any problem which admits of an algorithmic solution is not going to satisfy both 2 and 3. So we're really looking for some sort of gestalt; a pattern-recognition problem that humans are good at. I thought of a couple of photoluminescent boundary recognition things, but they'd probably fail on 1 before generating enough tests for the computer to be sure that it wasn't dealing with an algorithm.

My best shot so far is probably speech recognition from a cold start, which humans are very good at in their native language, though not in others, so that's bad. But humans are good at recognising that sounds are speech. If the computer could repeatedly chosse, with equal probability 1) a random 0.5 second segment of Sally Field's Oscar acceptance speech, sampled at a suitably high frequency so that sufficient numbers of distinct three-second segments existed or 2) a random non-speech sound file, and ask the subject whether they had heard speech or non speech, then I would imagine that repeating this test about ten times would go some way toward sorting sheep from goats.

--
Just because things have been nonergodic so far, doesn't mean that they'll be nonergodic forever

expanding on the bird suggestion (2.00 / 1) (#3)
by tetsuo on Wed Apr 11, 2001 at 10:36:30 AM EST

Now, I'm admittedly operating without a lot of knowledge as to how freenet works; but given your example of 'which of these pictures is a bird', I presume it can display images, request answers (html form type?) and relay them, I'd suggest this:

Generate a random 64 bit integer. For each '1', generate a picture of a bird (for securities sake, shift/rotate/randomize the pallete each time). For each '0', white noise(or anything). Give the user an 8x8 array of pictures and ask him/her to select all birds.

It would be easy for a human to select all the birds, but computationally infeasable for a computer to check the images(assuming you hash a random value and assign that to the filename, instead of using "bird.gif" hehe) or to bruteforce.

Hope I'm not missing something too obvious here.

The obvious missing something (4.00 / 1) (#7)
by MisterX on Wed Apr 11, 2001 at 11:29:31 AM EST

Hope I'm not missing something too obvious here.

You are. The user may be blind.

Not, of course, that I can think of a better solution.

However this problem is solved, it should not rely on any technique which excludes users. The question and answer would have to be textual.

Paul



[ Parent ]
argh (none / 0) (#14)
by tetsuo on Wed Apr 11, 2001 at 01:11:18 PM EST

Ok. (S)He had mentioned the bird test in the submission so I hadn't thought about blind users.

The problem with a text based solution, as I see it, is that it will have to rely on human analysis to solve. Like those SAT questions that ask you to analyze a paragraph of text. There's only so many paragraphs that you can choose from. And there's only so many correct answers. Eventually the knowledge of the attackers will equal that of the attackee.



[ Parent ]
It's a tough nut to crack (none / 0) (#15)
by MisterX on Wed Apr 11, 2001 at 01:42:08 PM EST

As soon as I saw the bird test mentioned, I immediately thought of blind users. Likewise audio is useless for deaf users.

I think as technical folks it's all to easy to see technical answers without actually considering the user. The only reason I even thought about blind people is that I once had to write software which could work with a screen reader. Totally changed the way I had to think about the user interface.

I've been pondering this one (on a low priority thread in the back of my mind) since I saw it. Still nothing...

I suspect that the final answer, if there is one, will be so painfully simple that the collective forehead-slapping all over the world will actually be audible ;-)

Paul

[ Parent ]
Actually, how about (4.00 / 1) (#8)
by tetsuo on Wed Apr 11, 2001 at 11:32:01 AM EST

Instead of a static picture of a bird (which might eventually get picked up upon with software), I'd suggest selecting random pictures from /usr/share/wallpaper wallpapers, and asking "which of these is a tileable wallpaper", vs whitenoise. This, to me, would be a better solution than the bird.

[ Parent ]
what? (none / 0) (#23)
by delmoi on Wed Apr 11, 2001 at 05:24:49 PM EST

I think it would be much easier for a computer to calculate a tiled wallpaper then a human, just compare the values on all the edges with the values on the opposite edges, if they match... you have a tile. A human would have more trouble with this...
--
"'argumentation' is not a word, idiot." -- thelizman
[ Parent ]
I dunno (none / 0) (#25)
by tetsuo on Wed Apr 11, 2001 at 06:26:20 PM EST

I meant tiled wallpapers like propagandas ... the edges rarely have the same color pixel on both sides; it's shifted up/down/left/right a few pixels, and the shading might not always be the same. So comparing them, I think, is still a difficult thing for a computer to do. At best, it can make a good guess as to it. But since the node wouldn't return which ones are right and which ones are wrong, it would never know.

[ Parent ]
What? (none / 0) (#37)
by delmoi on Thu Apr 12, 2001 at 12:58:08 AM EST

In a tiled wallpaper, the pixles on both sides of the image need to 'flow', that is they need to look like they are 'in place' with the rest of the graphic. Lines need to be contiguous, and very often this means that the color is going to be pretty close. A computer could analizes this (using both color and shape) pretty easily, a human might not be able to.
--
"'argumentation' is not a word, idiot." -- thelizman
[ Parent ]
Incorrect requirements (4.00 / 2) (#4)
by DesiredUsername on Wed Apr 11, 2001 at 11:18:43 AM EST

1) It should be easy for a computer to generate the test.
2) It should be difficult for a computer to perform the test, but easy for a human.
3) It should be easy for a computer to check for the correct answer to the test.

The idea is that upon an insertion, the computer on the other end generates a test and asks the human sitting at the computer to solve it. The human answers and sends the answer back to the computer. Given that the answer is correct, the computer allows the insertion of the data.


References to "a computer" and "the computer" confused me for a while, so let me spell out my understanding: Server S detects an attempt to insert data coming via Client C. S wants to know if there is a User U sitting in front of C or if C is "acting alone". Right?

Then the three rules need to be written as follows:

1) It should be easy for S to generate the test.
2) It should be difficult for C to perform the test, but easy for U.
3) It should be easy for S to check for the correct answer to the test.

This seems pretty easy. Example: S sends N images, only one of which is a bird. Steganographically embedded is a random number. It doesn't matter if C discovers this number, because S has assigned them randomly. U chooses the bird and S determines that number from that image matches the one sent out. Adjust N such that 1/N is an acceptable accidental hit-rate for C acting alone.

Yes?

Play 囲碁
Not going to work (none / 0) (#6)
by streetlawyer on Wed Apr 11, 2001 at 11:28:42 AM EST

The root of the problem is that if N is large enough to prevent the kind of DoS attack discussed, then this is going to be unbearably fucking tedious for U. This is also a problem for my suggestion below.

My revised suggestion would be to play a .wav file of a randomly selected English sentence, and ask U to type in what the sentence said, making the task unfeasibly difficult to brute-force with only one response required. But I can't seem to get over the fact that this would restrict FreeNet to English speakers.

--
Just because things have been nonergodic so far, doesn't mean that they'll be nonergodic forever
[ Parent ]

Depends on FreeNet arch, but possible sol anyway (3.00 / 1) (#9)
by DesiredUsername on Wed Apr 11, 2001 at 11:41:20 AM EST

"The root of the problem is that if N is large enough to prevent the kind of DoS attack discussed, then this is going to be unbearably fucking tedious for U."

Maybe, maybe not, it depends on how FreeNet works. For instance, if C reponds incorrectly can a (time intensive to create) connection be severed?

In any case, a relatively simple add-on solution is to exploit some combinatorial features. Like, for each image also generate M radio buttons with questions about the bird ("is it red", "is it in flight", etc). Now the chances are 1/(M*N) but the load on U isn't too much worse. Example: Let N be 9 (a three by three array of images). U is going to spot the bird immediately. Let M be 5 and U won't take more than a second or two to answer, but already C will get be wrong 44 out of 45 times. N = 16, C is wrong 79 out of 80. N = 25 (5x5 array, still pretty easy) and C will be wrong 124 out of 125 times.

You could also make the system progressive. The first insertion (during a "connection" or something else--again, it depends on FreeNet) is free. The second requires a 1/10 guess. The second a 1/100. The third a 1/1000. Etc.

Play 囲碁
[ Parent ]
shen ma? (none / 0) (#20)
by delmoi on Wed Apr 11, 2001 at 05:01:40 PM EST

My revised suggestion would be to play a .wav file of a randomly selected English sentence, and ask U to type in what the sentence said,

你为什么说'英文片语', 你想 Freenet 只为英文说的人吗?可能你的解答不太好了。
--
"'argumentation' is not a word, idiot." -- thelizman
[ Parent ]
Translation: (5.00 / 1) (#35)
by Mantle on Thu Apr 12, 2001 at 12:51:07 AM EST

Why do you say an English sentence, you think Freenet is only for English speaking people? Maybe your answer isn't too good.

[ Parent ]
Speech not a huge barrier (none / 0) (#44)
by jkeene on Thu Apr 12, 2001 at 11:14:54 AM EST

Regarding the .wav to text translation as the test, it wouldn't be limited to just English, and wouldn't be a terribly effective gatekeeper.

Years ago the NSA setup Sun workstations to scan the phone lines leaving the USA for "interesting" words. These could do real-time scanning in multiple languages. That was the late 80's. Now we have speech to text translation software on retail shelves for American English, British English, French, Spanish, German and Italian.

Couple hours with these and some Perl script and I'll get past a .wav gatekeeper.

As the author wrote, it's a neat problem.

[ Parent ]

here's a dumb afterthought to that SL (none / 0) (#47)
by jayfoo2 on Thu Apr 12, 2001 at 03:05:15 PM EST

This problem is a real head scratcher, I don't have a much better idea than any of the others already posted, so I'm going to cheat.

In the case of freenet it is perhaps ok for the check to be highly tedious. This is because freenet (as I understand the philosophy) is intended to be a tool that allows secure sharing of highly sensitive documents without censorship. I.e. news from belgrade, messages between dissidents , political speach etc.

Because this is high value, and lower volume, traffic it is worth it for the poster to spend a good amount of time 'opening the locks'.

It of course is not practical if all you are doing is sharing the latest n'sync single or some naughty pictures. However that may be ok in this case.



[ Parent ]
Hmm... (4.00 / 2) (#5)
by trhurler on Wed Apr 11, 2001 at 11:25:32 AM EST

Interesting, but probably impractical. You should investigate the most recent research in image databases; image recognition is getting to be fairly good. The other obvious answers are sound recognition, which is easier than people think, voice/speech recognition, which is harder, but suffers from a different problem I'll mention below, and things like "which of these is an impressionist painting" where you're not just asking about a shape/color assessment with rough boundaries, but about a high level analysis of characteristics of the work which are not easily described in exact terms. The last just might work, but there aren't enough different kinds of such tests, I don't think.

The problem with voice/speech stuff is related to the problem with the "impressionist painting" approach. Basically, let's say a given server has a million samples of voice and nonvoice. Why not just set a network of hacked machines, ala DDoS, to work making requests to post but never actually posting, and then take the data, have a human pick out the correct answer a hundred times, and do pattern recognition? I guarantee you that the waveform for speech or a given person's voice can be identified given sufficient samples, and that isn't as many as you'd hope. Once you have the nature of the test(if there are more than one, just do some more work; it is easier for you to break them than for the server operators to implement them, after all...) you use that information to mount your automated attack. With sufficient cleverness, this could be done quickly, be difficult to detect and/or defend, and be essentially impossible to trace, because of the fact that you're always coming from machines that aren't yours and that falsify routing info.

Security is hard, folks. A lot harder than most wannabes seem to think.

--
'God dammit, your posts make me hard.' --LilDebbie

Implimentation problem? (3.66 / 6) (#10)
by Signal 11 on Wed Apr 11, 2001 at 12:08:43 PM EST

Back in the mid-90's, a fair number of computer game manufacturers used a method vaguely similar to this to copy-protect their games. What it would do is say "Type in the third word in the first sentence of the second paragraph on page 15 of the manual." There was a NASCAR computer game which prompted you with a picture and asked you to identify which track it was (again, using the manual).

The problem with this, and other methods, is that they are vulnerable to brute force. Assume you have a 50 page manual. Assume that there are 400 words on each page. This gives you 20,000 possibilities, which seems like a lot, until you realize that a 28.8k modem can send about 40 TCP/IP packets per second (no compression, full headers). So in just over 8 minutes, it's even money that just knowing ONE possible answer will yield the correct choice. Now, expand that to the speed of a T1 connection, and we're talking seconds, not minutes, to insert a piece of data into the network.

And this assumes that there are 20,000 possible responses for each question! It also assumes that you only know the answer to one question, and not most or all of them. Presumably lists of standard questions would be published and made available for download (with the answers) so that freenet node admins could just drop in a file or two and not have to come up with a few dozen questions each. Even if this functionality wasn't explicitly made available, people would write utilities to make it this easy... which means that how fast you get into freenet becomes a matter of how many such lists you have.

And therein lies the problem with "Think Cash"... unless the questions are rotated regularily, have a high amount of entropy in the answers, and a sufficiently large pool of questions, anyone can automate stuffing the freenet network with useless data.

That aside, there's another problem - this is a client-side security model! For sending data server-to-server, this model simply cannot work. There's too much data, and for the network to respond quickly to surges in download requests of particular pieces of data, it needs to be able to propagate that data without human intervention. This brings back the problem of the rogue server... and anyone serious about crashing freenet would opt for this, instead of messing around with client-based insertions.

Just some food for thought...


--
Society needs therapy. It's having
trouble accepting itself.

Something I don't understand. (4.00 / 3) (#11)
by i on Wed Apr 11, 2001 at 12:18:36 PM EST

Freenet is based on absence of a central server. Assume a good test exists. Who decides which node will validate a submission, and how do we ensure that the validating node is not one of the attacker's nodes?

and we have a contradicton according to our assumptions and the factor theorem

Work on that when we get there (none / 0) (#16)
by hardburn on Wed Apr 11, 2001 at 01:55:39 PM EST

I get the feeling that most developers are just trying to solve the basic problem. Adding into that how we're going to apply it to Freenet compilicates things too much.


----
while($story = K5::Story->new()) { $story->vote(-1) if($story->section() == $POLITICS); }


[ Parent ]
If I understand freenet (none / 0) (#32)
by roystgnr on Wed Apr 11, 2001 at 10:47:53 PM EST

To make this secure, every computer you push an inserted file to would have to push back a test to you. This would mean that the average file you inserted would require you passing half a dozen tests, and if you failed test 5 then your file wouldn't make it to nodes 5 or 6 in the chain.

Note the subject line, though. I read the freenet white paper a year or so ago and my memory's a little hazy now.

[ Parent ]

A Turing test with a different observer (3.50 / 2) (#12)
by jkeene on Wed Apr 11, 2001 at 01:07:53 PM EST

So it seems that you want a computer to be able to tell the difference between a computer replying to questions and a human replying to questions? A softare gatekeeper to keep out others of its own ilk, as it protects the creation of its alien masters?

Not just a cool problem, but in the right hands it's a decent plot.

Well, that dosen't seem all that hard. (3.00 / 2) (#17)
by TheLaser on Wed Apr 11, 2001 at 03:29:50 PM EST

Just have the computer who wants to prove it is talking to an actual human render an image of a string of 8 alphanumeric characters. The image should be as noisy as possible to defeat OCR. Say perhaps letters made of twigs or carved in coarse stone or something. Rotate the background from time to time to mix things up.

Then just ask the user for the 8 characters. A computer probably won't be able to discover those nearly as well as a human could, and even if it could, it would probably take some time.

Of course, if your human lacks eyesight, this isn't going to work.

Er... (none / 0) (#29)
by trhurler on Wed Apr 11, 2001 at 07:08:43 PM EST

There are two cases here. Either the image is merely picked from among a set made by a human being, in which case it will be easier for an attacker to accumulate and identify them all than for the defender to create more, or else it is generated, in which case the old rule applies: what a computer can create, a computer can usually analyze. Injecting noise into an image by automated means isn't really injecting noise - real noise cannot be algorithmically generated. This, of course, means that computer generated pseudonoise can be filtered.

--
'God dammit, your posts make me hard.' --LilDebbie

[ Parent ]
You've confused my PC with a Turing machine (none / 0) (#33)
by roystgnr on Wed Apr 11, 2001 at 11:00:01 PM EST

Injecting noise into an image by automated means isn't really injecting noise - real noise cannot be algorithmically generated.

No, but real noise can be snagged out of /dev/random pretty easily. Lots of cryptographic and security systems today depend on computers being able to generate random noise. When this assumption fails, it's a bug.

[ Parent ]

Ah (none / 0) (#42)
by trhurler on Thu Apr 12, 2001 at 10:44:39 AM EST

As an amusing experiment in how limited /dev/random is, try running something like 'time dd if=/dev/random of=/tmp/myfile bs=1 count=65536' and see what happens. Then try it with count=8096 and so on, after allowing time for the entropy pool to refill. Guess what? It takes quite a while, independent of the speed of your machine. Good enough for crypto? Yes, because crypto generally doesn't require large quantities of entropy. Good enough to generate noise all over a photograph? No.

By the way, the Linux style /dev/random is NOT a true random source. It simply approximates one very, very well. If you don't know the difference, I suggest Bruce Schneier's writings as an excellent source of information.

--
'God dammit, your posts make me hard.' --LilDebbie

[ Parent ]
One way functions (none / 0) (#36)
by delmoi on Thu Apr 12, 2001 at 12:54:39 AM EST

There are plenty of one-way functions. A one way function is something where you have g = f(x,y,z..), and g is easy to find, but x,y,z... is imposible to find only knowing g. All of cryptography is based on this.
--
"'argumentation' is not a word, idiot." -- thelizman
[ Parent ]
I know that. (none / 0) (#43)
by trhurler on Thu Apr 12, 2001 at 10:47:49 AM EST

However, there are no functions which, in principle, are one way to a computer but two way to a human being, or even one way in the other direction. Granted, you can find some things where current research is lacking, and exploit those temporarily, but that's about it. Anything you exploit simply encourages research in that direction, too, thereby hastening the day when you will not be able to do that anymore.

Of course, you can find all sorts of things people are good at that computers aren't, but usually those don't involve definite yes/no answers, which is required here.

--
'God dammit, your posts make me hard.' --LilDebbie

[ Parent ]
Yeh, (none / 0) (#51)
by delmoi on Fri Apr 13, 2001 at 01:21:24 AM EST

I don't think it's possible. At best all you can do is find something where f(x) is something the human mind already does very, very well, but we can't figure out how get a computer to do it, or it will take to long on a computer (The human brain is basicaly a very powerfull computer optimized for certan tasks)
--
"'argumentation' is not a word, idiot." -- thelizman
[ Parent ]
OCR problems, Lynx browsers and ADA (none / 0) (#46)
by pin0cchio on Thu Apr 12, 2001 at 02:53:29 PM EST

render an image of a string of 8 alphanumeric characters. The image should be as noisy as possible to defeat OCR ... Rotate ... Then just ask the user for the 8 characters.

AltaVista's URL submission form does what you described, nearly to the letter.

Of course, if your human lacks eyesight, this isn't going to work.

Don't downplay this issue, as it can have serious legal implications. For example, AltaVista REJECTS all Lynx users and other users who can't view GIF images for hardware, patent, or disability reasons. There is something called an Americans with Disabilities Act, you know.


lj65
[ Parent ]
Jokes (3.00 / 4) (#18)
by spacejack on Wed Apr 11, 2001 at 03:56:02 PM EST

Which of the following is funny:

a) The chicken crossed the road to get to the other side. Luckily there was no traffic.

b) I ate a hamburger and spilled relish all over myself. Man that sucks. Then I had some fries. Then I went home.

c) An old man runs into a confessional booth and says excitedly: "Father, father, I must tell you, last night I slept with a woman 1/4 my age!"
The pries replies "Well, do 4 hail Marys."
"I can't do that, I'm Jewish."
"So why are you telling me this?"
"Are you kidding? I'm telling everyone!"

Frankly I hope Freenet fails. But if they can make it work, so be it.

The problem.. (5.00 / 1) (#21)
by skim123 on Wed Apr 11, 2001 at 05:17:56 PM EST

Remember stipulation "1) It should be easy for a computer to generate the test." How does a computer make up a joke that is funny and two that are not? Granted, it could have a pool of user-entered, "These are funny jokes, and these over here are not," but if you have that, then couldn't a computer easily solve this problem by comparing those phrases with this pool to find the funny one?

I think this is a much harder question than you've made it out to be. The big question, I think, is "Find a function f such that computing f is simple for a computer, but computing the inverse of f is difficult for a computer." Granted, there are such f's readily known, but then the added stipulation is thrown on top: "oh yeah, the inverse of f must be easily solved by humans." Ah!

Money is in some respects like fire; it is a very excellent servant but a terrible master.
PT Barnum


[ Parent ]
d) None of the above (none / 0) (#40)
by NoseyNick on Thu Apr 12, 2001 at 04:33:58 AM EST

d) None of the above

sorry.

[ Parent ]

Money (4.00 / 3) (#19)
by spacejack on Wed Apr 11, 2001 at 03:59:57 PM EST

can do anything. If the RIAA wants to hire a bunch of minimum-wage drones to answer dumb questions all day so they can feed it fake versions of the latest Britney Spears single, I'm sure they will. Heck, it could be the next big sweatshop gig in some 3rd world country. Yea, the Freenet legacy will be grand...

Not possible. (3.50 / 2) (#22)
by delmoi on Wed Apr 11, 2001 at 05:19:07 PM EST

I don't think this is really possible, at least from my understanding of Freenet. There are lots of things that people can do, and computers can't very well, computers can check these, but only if they already know the answer. This would be an easy thing if Freenet were a client/server model, but it isn't. It's node to node, and each node is 'equal.' In other words, if you want to use server-side security, you'd need to have people asking this question to each other for every free net transaction, I don't think that's possible, without breaking Freenet entirely.

So, as far as I can tell, you want something that can verify an answer without pre knowledge of what answer is correct. I know there are mathematical algorithms that have this property. I think they are called NP-hard, (but I'm not sure). The problem is that these problems are just as NP-hard for humans as they are for computers.

The only thing I think that humans have better at then computers right now is Visual and Linguistic capabilities. And keep in mind this isn't due to any intrinsic properties of the human brain, but rather the fact that these are very difficult things to program not to do. And the fact is that there is code out there that can do these things, they are just not in wide use.
--
"'argumentation' is not a word, idiot." -- thelizman
The rise of cyborgs (4.00 / 2) (#24)
by slaytanic killer on Wed Apr 11, 2001 at 06:00:42 PM EST

What odd comments. There are an unbounded number of things humans can do that computers can't (currently) do, but can check rapidly. Making of theorems, for example. Theorems can be checked for validity fairly easily (by making sure that assumptions are held and the end result is air-tight). Can a computer be better than I am at a given theorem? Perhaps, but not on the majority number of others.

And that is because someone needs to program it to beat me at solving those other theorems. And at that point it's human vs. augmented human.

I'm surprised. Gödel Escher Bach was all about that.

But the really, really interesting thing is this link I found at the Economist. I was about to do a story on it, but I can't find my copy of a book by von Neumann that should be lying around, which I was going to use. We are again lurching forward to the point where cyborg companies are more than a glimmer of the eye.

Theorems. (none / 0) (#27)
by trhurler on Wed Apr 11, 2001 at 06:58:52 PM EST

Well, there IS a whole branch of CS dedicated to theorem finders, theorem provers, and programs that apply input theorems to input datasets. Arguably they're not as good as people yet, but the yet is an important consideration if you want to really "solve" the problem Freenet is having.

--
'God dammit, your posts make me hard.' --LilDebbie

[ Parent ]
Battles of the humans vs. the bots (none / 0) (#45)
by pin0cchio on Thu Apr 12, 2001 at 02:43:46 PM EST

And at that point it's human vs. augmented human.

Except when a human augments himself with scripts that can spam. In some cases (such as signing up for accounts at web hosts or adding URLs to a search engine), the server presents a relatively hard OCR problem (identify these letters in obscure fonts and in several orientations) that can supposedly be solved only by a human with good eyesight. Note that this excludes visually impaired users and users whose browsers cannot display GIF images, for hardware or patent reasons. Specifically, Lynx users are left in the cold.


lj65
[ Parent ]
Rise of the SPAMBORG (none / 0) (#53)
by delmoi on Fri Apr 13, 2001 at 01:27:26 AM EST

p33r. :)
--
"'argumentation' is not a word, idiot." -- thelizman
[ Parent ]
Individual tests (4.00 / 1) (#26)
by Woundweavr on Wed Apr 11, 2001 at 06:41:47 PM EST

I'm not especially familiar with Freenet so this may not be feasible.

However, why not have a wide selection of tests? This could be extended to even to the point where each node had its own test. When uploading some file, you may get several types of test and many examples of them with random answer selections.

Some examples:
Tree, Hen, Cat, John Denver, Annapolis Which of these walks on four legs? [text or audio]

A selection of sounds only one of which is actually a word, the rest are just noises, which must be identified(audio).

However the best one for the sighted would be....

A selection of images, most of human faces. Select which is male or which is female and/or which is old/young OR a human face and describe the emotion.

People can identify such things much better than computers even with newest image recognition.

Actually, (none / 0) (#28)
by trhurler on Wed Apr 11, 2001 at 06:59:40 PM EST

Sex recognition is a solved problem; computers can now be made to get it right more often than human beings, in fact, because the techniques they use(precise measurements of numerous facial characteristics) are actually superior to the ones we use(which are similar, but less precise, according to current theory.) Everybody knows that one person that you can't quite tell; flat chested, no figure, large build, squarish face, etc. Well, the best computer programs CAN tell.

The problem with emotion is that in a static image, people can only identify emotion if it is dramatized, or at least very dramatic. You'd like to think otherwise, but if I gave you a normal emotional reaction in a picture, your accuracy in identifying it without any context whatsoever would be pretty bad. And if we only allow really dramatic "identifiable" faces, then a computer will be programmable to recognize them just as it can identify the sex of a person based on a face. For a shocking example of just how hard this problem is, get a dozen pictures of people making faces that are only slightly different than a relaxed face, signs of mild to moderate emotion, and get a dozen people to write down what they think each person is feeling. Then compare them with each other. Ignore what you think the person was "really" feeling in doing the comparisons; that isn't the point.

--
'God dammit, your posts make me hard.' --LilDebbie

[ Parent ]
take a shot (4.00 / 1) (#30)
by speek on Wed Apr 11, 2001 at 09:45:27 PM EST

It seems to me the test has to be generated on the spot. Any test that comes from a list of predefined tests can be cracked by brute force, I would think. Also, it should probably take the contents of the file being submitted as a starting point for generation of the test.

Because of Freenet's architecture, the challenge would have to come from a node other than your own (you could easily have modified the programming of your node to skip the challenge). This raises other problems, however, because now a node has to know whether it is the first node to receive the new file and whether it should issue the challenge. But you could easily have installed several nodes within your network. Basically, it gets down to every node having to challenge every file that gets pushed onto it, and in order to challenge the human who actually added the file, freenet would have preserve where the originating node was - a definite no-no for freenet.

But, anyway. Pretend there are not these considerations (or more likely, that I have no clue what I'm talking about above). A server could issue a challenge based on the file by creating an image of the file as it would normally be displayed on the computer screen, and than randomly dividing the image into chunks and and re-arranging it. The re-arranged image would be fed back to the human and asked to give the correct ordering of the image chunks. The challenging server would know the right answer because it did the rearranging. Software that tried to pass the test would have to be image recognizing software - and further, it would have to have been trained on the specific file being uploaded to freenet.

There's all kinds of problems with this, like what if you can't bring the file up on screen to create the image? What if it's a wave file or mp3? Yup, I know. But I'm wondering if what I described above would work for, say, text files. Would it be solvable by humans and not by computers?

--
al queda is kicking themsleves for not knowing about the levees

One problem's solution (none / 0) (#31)
by roystgnr on Wed Apr 11, 2001 at 10:37:25 PM EST

Basically, it gets down to every node having to challenge every file that gets pushed onto it, and in order to challenge the human who actually added the file, freenet would have preserve where the originating node was - a definite no-no for freenet.

Preserving where the originating node was would be unnecessary - you just pass the challenge to the computer that pushed you the file, which passes it to the computer that pushed it the file, etc. The challenges will get back to the originating human eventually, without anyone else in the chain knowing who the originator is.

[ Parent ]

infinite challenges (none / 0) (#41)
by speek on Thu Apr 12, 2001 at 07:59:49 AM EST

Given Freenet's architecture, does every node have to do this, thus requiring a separate challenge for every freenet node that gets the file?

--
al queda is kicking themsleves for not knowing about the levees
[ Parent ]

Only challenge file "push"es (none / 0) (#49)
by roystgnr on Thu Apr 12, 2001 at 07:03:23 PM EST

I believe freenet gives you two ways that a file can get sent to your node: if you or another node pulls it through you, or if another node pushes it to you. You would only challenge the "push" requests.

[ Parent ]
Match images with captions? (3.00 / 1) (#34)
by roystgnr on Wed Apr 11, 2001 at 11:15:26 PM EST

Scour some subset of the web for a random collection of ALT tagged images. Require the user to match each of the images in a suitably large set with it's ALT tag. Add a little noise to (and rescale, etc) the image and a few typos to the ALT tag to foil search engine lookups. Then require the user to match some percentage of the set correctly.

The obvious counterattack is for the attacker to run his own search engine, and index images by some easily looked up "hash" that can't be altered without rendering the image unrecognizable. I don't see any perfect theoretical way to prevent this counterattack, but I don't think I could implement such a "hash" myself that wouldn't be defeatable by very simple things like image cropping, noisifying, warping, and resizing.

Bird recognition (2.00 / 2) (#38)
by plastik55 on Thu Apr 12, 2001 at 01:26:30 AM EST

It's funny that this story came up today; I just started picking up some extra cash by collecting images of birds for Pietro Perona's lab. They need the images to test some of their recognition algorithms.

Based on earlier results they published, I'm guessing a performance of about 90% on my data set (where the task is to discriminate images of birds from images not containing birds.)

Discriminating images of birds from images of white noise, or discriminating speech from white noise, as some people suggest below, is trivial. I could whip up a Matlab script to do that an a couple of hours, and maybe 10 lines. You just take the power spectrum and check if it looks flat.

Discriminating classes of images from one another, like the birds, is more difficult--but don't think it can't be done.
w00t!

A not very practical solution. (4.00 / 2) (#39)
by i on Thu Apr 12, 2001 at 03:32:59 AM EST

Have two video cameras. Point one of them to a cage with a live parrot, the other to a cage with a mechanical parrot (must be reasonably sophisticated to emulate most of the movements of a live parrot). Have the user to tell which one is live. Pretty easy for humans, next to impossible for computers. (Not very practical because the required bandwidth is too high, and then requiring every node to be equipped with a live parrot is a little too much. But then, if we're talking about a centralized server and not a beast like Freenet, this is entirely possible.)

When they finally train their software to tell the two parrots apart, start using fish instead.



and we have a contradicton according to our assumptions and the factor theorem

50% (4.00 / 2) (#52)
by delmoi on Fri Apr 13, 2001 at 01:24:54 AM EST

You would be able to post half your spam. Even if your suggestion was remotely partical.
--
"'argumentation' is not a word, idiot." -- thelizman
[ Parent ]
Though repeat tests lower the odds (none / 0) (#63)
by kmself on Thu May 17, 2001 at 06:39:31 PM EST

...according to a rather familiar schedule: Repeats : Odds (1 in...)
1 2
2 4
3 8
4 16
5 32
6 64
7 128
8 256
9 512
10 1,024
11 2,048
12 4,096
13 8,192
14 16,384
15 32,768 ....etc.

A reletively simple test repeated multiple times would rule out pure chance.

--
Karsten M. Self
SCO -- backgrounder on Caldera/SCO vs IBM
Support the EFF!!
There is no K5 cabal.
[ Parent ]

Ian Clarke's take on the subject (4.50 / 2) (#50)
by sanity on Thu Apr 12, 2001 at 11:29:48 PM EST

You can read a further article on this here.

URL borked - try this: (none / 0) (#59)
by sanity on Tue Apr 17, 2001 at 02:24:55 PM EST

Try http://www.half-empty.org/ideas/a7/dc/9b/f4/21/default_index.html. Additionally, someone has actually taken a crack at implementing think-cash using image recognition, find out more on Freenet at freenet:MSK@CHK@8GfuCtnk0S~aq2VrJALgi3V2oYYLAwE,kEMmdndjbqUfU8U06kJONQ//dl.html (See here if you don't have Freenet installed).

[ Parent ]
imagemap (none / 0) (#54)
by dr k on Fri Apr 13, 2001 at 03:07:21 PM EST

Why not create a moderately sized image (say 100x100 or 200x200) containing a small (5x5) blue square and nothing else (noise), and ask the poster to click the blue square. Make the whole think an imagemap, so the coordinates where the user clicks would be sent back to the server. The odds of a random correct answer are several magnitudes worse than a simple multiple choice question.

You may end up in an arms race, however. Someone can always write code to search the image for the blue square, so you create some variations on color, or shape. Create animated images and ask for the blinking green triangle, &c.
Destroy all trusted users!

Parsing the imagemap (none / 0) (#55)
by hardburn on Fri Apr 13, 2001 at 03:25:48 PM EST

An image map must have some way to tell the computer to "do this if the user clicks here". An attacker would just parse that command string (in HTML this is in an "IMAP" tag, IIRC) and go. So, you would have to leave lots of links that point to the wrong answer. A human will automaticly know which is which (the one with the blue square), but a computer will have to try each link one at a time (a.k.a., brute force). You would have to leave lots of false links, none of which can overlap, to make the brute force approach difficult to do in a reasonable ammount of time.

Also, you need a good, long source of cryptographicly secure random numbers to generate the noise. Most psedo-random number generators (like /dev/random) are only cryptographicly secure up to a few hundred bytes (as some posts below pointed out). We're going to need a few thousand bytes, at least. I'm guessing true, hardware random number generators will be needed.


----
while($story = K5::Story->new()) { $story->vote(-1) if($story->section() == $POLITICS); }


[ Parent ]
random (none / 0) (#56)
by dr k on Fri Apr 13, 2001 at 06:02:46 PM EST

You don't actually have to include a map (i.e. a list of shapes and their target URLs) with an imagemap, you can simply request an x,y pair. The client sends back the x,y pair and a key identifying the image, and thus the posted item, that this request is validating. On the server, you've got a table of the pending posts, the image keys, and the "correct" coordinates. Only allow one try per post, and add a spam throttle for excessive reposting.

The randomness of the "noise" is not particularly important or interesting. It would just be there to put more computational burden on the would-be spammer. In other words, if they write a program to defeat the "blue square", they now have to account for a lot of useless noise. Doesn't matter how nice (truly random) the noise is.

Beyond that, my implication was that the best way to defeat any kind of computational cheat is to keep moving the target. If you used letters instead of shapes, the cheater now has to make his program recognize letters.

All it takes is one person to defeat the validation scheme and share it with others. But what is the actual incentive for this? If defeating the validation gives you an advantage (increased sales, &c) then logically you wouldn't want to share your solution. Or you'd sell it rather than share it. Which gets us back to the moving target situation, which is pretty much what was happening with copy protection in the late 80's.

Fast Hack'em Rules!
Destroy all trusted users!
[ Parent ]

Accessibility issues (none / 0) (#65)
by pin0cchio on Sat Sep 22, 2001 at 11:21:26 AM EST

You don't actually have to include a map (i.e. a list of shapes and their target URLs) with an imagemap, you can simply request an x,y pair. The client sends back the x,y pair and a key identifying the image

So how will a visually impaired human user know where to click?


lj65
[ Parent ]
i don't see the problem (none / 0) (#57)
by mikpos on Sat Apr 14, 2001 at 12:12:48 PM EST

I must be missing something. It sounds like what they're talking about is someone stealing all the bandwidth from a node. From the point of view of Freenet, this is no problem (one node doesn't matter, and you can't DOS them all), though it would be irritating at least for the node operator.

First of all, if the DOS is distributed: doh. There's not a lot you can do there (depending on how distributed it is), but a bird test isn't going to help anything either.

If the DOS is not distributed, then conventional techniques will work just as well. The node operator has tens of thousands of lines in his logs of the attacker's IP if he wants to use the police and/or his hosts.deny. Otherwise you can just set up standard bastard firewall rules: only so many connections or so much bandwidth per IP per unit of time.

Not just for Freenet (none / 0) (#60)
by hardburn on Wed Apr 18, 2001 at 09:20:25 AM EST

This wasn't thought up just for Freenet's benifit. I should have made this more clear in the article. The idea came up in relation to our work on Freenet, but there is no reason why it couldn't be implemented in Gnutella, Free Haven, or some other distributed network. It could even be embeded in IP itself, if there was a high enough demand for stoping spam.


----
while($story = K5::Story->new()) { $story->vote(-1) if($story->section() == $POLITICS); }


[ Parent ]
How 'bout this: (none / 0) (#58)
by Chris Andreasen on Tue Apr 17, 2001 at 01:29:39 AM EST

How 'bout this: send a series of images (or ideally one big image containing a sequence of images) of, say, a bird, chair, table, cat, clock, etc... Utilize some method or distorting the individiual images for each transmission. The correct response to the test will be a series of bits identifying, in order, which ones are living/animate objects and which aren't (or something along those lines). It takes a whole two or three seconds to go over a set of about 16 pictures and identify which isn't alive and which is, the odds are 1 in 65,536 that a blind guess will give the correct answer, and if this is used as a common protocol for submission to every node you won't have to worry about an only-in-english problem since you can explain the protocol in the documentation.
--------
Is public worship then, a sin,
That for devotions paid to Bacchus
The lictors dare to run us in,
and resolutely thump and whack us?

New information (none / 0) (#61)
by hardburn on Wed Apr 18, 2001 at 10:24:08 AM EST

This recently showed up on the Freenet development list in relation to this (from Matthew Burnham):

Just had another thought though, wonder if 'moving pictures' could be used somehow to trick a human into perceiving a particular number which a computer would have more difficulty determining being as it has to take account of a number of frames (and make it so that combining all the frames wouldn't give a OCRable picture).


----
while($story = K5::Story->new()) { $story->vote(-1) if($story->section() == $POLITICS); }


altavista/submit url does use "think cash&quo (none / 0) (#62)
by Highlander on Thu Apr 19, 2001 at 09:32:51 AM EST

-- I think a better name than "think cash" is "human test".

Moderation in moderation is a good thing.
Not "human test". Vision test. (none / 0) (#64)
by pin0cchio on Sat Sep 22, 2001 at 11:19:14 AM EST

I think a better name than "think cash" is "human test"

AltaVista's scheme (recognize images of Latin letters in obscure fonts) rejects bots, but it also has the false negative of rejecting visually impaired human users and human users on text browsers, neither of whom can see GIF images.


lj65
[ Parent ]
Think Cash | 65 comments (62 topical, 3 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!