Denial of water
May 14, 2000
Dear [50 first names]
(Yes! We hit 50.)
I just back got back from a magnificent weekend of cycling on Cape Cod. Cape Cod is an island that stretches out into the Atlantic Ocean southeast of Boston. Florian (a German friend; no contradiction in terms there) and I first went by train to Plymouth (yesterday) and then cycled 100 kilometers in drizzling rain. It was terrible because the roads were hilly, up and down and up and down. It was killing. The road was bad and there were cars passing us all the time. In a small village called Brewster we decided to call it a day and try to find a place to sleep. We found an Inn that said there was still a vacancy. It looked like a plain, normal house and we found an entrance after some searching. The entrance turned out to be a back-door right into the living room of the house. We yelled a few times and looked around. No answer. After a little investigation we found a note saying that we could just check ourselves in for $95 per night. We knocked on the kitchen door out of which we heard some sounds coming. The hostess came out, welcomed us and that's where we spent the night. It was marvelously cute. This morning she prepared us a great breakfast and we continued our journey to catch the 4PM ferry back to Boston Harbor. It was a great day! Very warm, clear sky and a nice cool ocean wind. We were on a bicycle path without any cars for large parts of the day. One stretch was along the Atlantic coastline; it was pretty and we felt this was our award for the previous day of hard labor. We biked another 60 kilometers to Provincetown, which is probably the ugliest place on Cape Cod.
In Provincetown I walked into a pub to ask for some water for our bottles. The bartender refused to give me water saying that "the water is really expensive around here, you know". I walked to the other side of the street to Provincetown City Hall and filled the bottles at a little tap. I walked back to the pub and told the bartender that, since his water is so expensive, he might be interested in knowing that the water on the other side of the street is free so that he should try to make a deal with them to get his water for free. I said this as loud as I could to get the message to all his customers. He was *not* amused, to put it mildly. He yelled at me "Get the fuck out of here!". For a moment I was scared that he might pull his automatic gun, but it was only a simple revolver which he fired a few times. He only shot me in the leg, which was no problem since I didn't need to cycle anywhere anymore. For the rest of the day I kept yelling "let's get the fuck out of here" at Florian. I'm a little afraid that I will do this at MIT, too. I can't control myself. I do it all the time.
Florian has a total cynical view of Americans. Listening to him you'd almost start to think that he hates it here, which, after asking him, turns out to be true. He has made some nice observations the past few months.
His first observation is that people here always give you a few options when you ask them a simple question:
"Hi, how are you today?"
"I'm fine, thank you. I'll have a Coke, please"
"Regular or diet?"
"For here or to go?"
"For *here* or to go?"
"Oh... Uhhm... To go"
"Small, medium or large?"
"Straight or bendable?"
"You're all set"
"Yes. Have a nice day"
"How are you guys feeling today?"
"OK, thank you"
"How can I help you"
"I'll have the hamburger, please"
"How would you like your burger?"
"Preferably dead, please"
"Would you like to have your burger rare, medium or baked through"
"What do you want on your burger?"
"What are the options?"
"Salad, mayonnaise, ketchup, bacon, cheese, mushrooms and onions"
"Oh, uhm... everything except bacon and cheese, please"
"Do you want your onions raw or baked?"
"Will you take French fries or mashed potatoes with that?"
"French fries. Some mayonnaise, please"
"What would you like to drink with that?"
"Just water, please"
"Mineral or tap?"
(Both are close to real life examples, I'm afraid)
Another typical thing is that everybody measures distances in hours-by-car. "How far away is Provincetown?" we asked our hostess. "40 minutes" was her answer. *Everybody* does this, without a single exception. Now when people ask me my length I tell them that it depends on the speed, but at a speed of 55 miles per hour, it's 72 milliseconds, thank you.
It is too bad that Florian has to leave this Wednesday. He's going back to Germany. It is very unfortunate that all the good friends I make here are abandoning me. I recently changed my strategy: I'm making some American friends now. In general, my social situation is improving.
A very exciting thing has happened. There is a yearly competition at MIT called the MIT $50K Competition where all contenders write a business plan and within a few iterations the best 3 business plans win a prize (guess how much). The prize is not the main issue, though. There is a lot of press coverage and prestige around this competition. Many contenders of previous years turned out to be successful, multi-million (in some cases even multi-billion) dollar companies.
One of the (218, I believe) contenders this year was a company that wrote a business plan around Click technology. (Click is the name of the software that the group I'm in at MIT is writing; it's the project that I have joined). 2 of the founders of this company are from my group. One of them is Max. Max is my advisor with which I work daily.
This company (called Mazu Networks) got to be the runner-up (i.e. shared second place) in the competition!
The reason that I find all of this very exciting is that this company used the "solution against Denial-of-Service attacks" as their main point of attention. Of course Click is much more than just a solution against Denial-of-Service attacks, but this was their flagship in the competition. Needless to say that I feel a bit proud. The bad news is that we still have to implement most of it.
I will explain our technique using an analogy with the Belastingdienst. The Belastingdienst is the tax agency in the Netherlands that processes tax-forms and claims tax money from civilians and companies.
Imagine that a group of people (say, a few dozen) wishes to cripple the Belastingdienst. How do they proceed? Planting a bomb is stupid and also dangerous. The goal is not to harm people but to disable the Belastingdienst. Actually, the goal is of course not to pay tax anymore; very appealing to Americans. One way to harm the Belastingdienst is by filling out thousands of tax forms with nonsense and sending them to the Belastingdienst. Do this every day and they'll run into problems eventually. The Belastingdienst has to open the envelopes one by one, look at the contents, make a decision whether or not it is nonsense and either throw it away or send an answer. There is a certain amount of time/energy/activity involved with each envelope that the Belastingdienst receives. I can not guess how many bogus tax-forms it requires for how many weeks to seriously slow down the Belastingdienst, but I am sure those numbers exist and that it might be easier than you think. With a few hundred people sending a few hundreds tax-forms every day for a few weeks, you might be able to pull it off. (Disclaimer: blah blah blah).
The Belastingdienst will be so busy processing nonsense that they can not process legitimate tax-forms at an acceptable speed anymore: voilà, a Denial-of-Service attack. We're denying 'good' people service of having their legitimate tax-forms being processed in time because the Belastingdienst is too busy handling nonsense tax-forms.
Now let's suppose that I am one of the attackers. What do I do? Every day I fill in a few hundred forms, put each of them in an envelope, write the Belastingdienst's address on it and throw them in the mailbox. All my co-attackers do the same and every morning a few trucks filled with tax-forms (good and bad) arrive at the Belastingdienst.
Let's go through some possible solutions for this problem. The Belastingdienst might try to find a feature that all nonsense tax-forms have in common and quickly throw all tax-forms away that have this feature. This is a risky strategy, though, because they can never be sure that legitimate tax-forms do not have this feature sometimes, too. That would mean they would throw away 'good' tax-forms, too. If the attacker is smart (which is our assumption), he fills the tax-forms with smart nonsense that is not immediately recognizable as being nonsense. This forces the Belastingdienst to seriously look at the form before it can decide on its fate. This slows them down even more.
One other strategy for the Belastingdienst is looking at the return address of the envelope. Who sent it? If they received hundreds of tax-forms from Thomer M. Gil yesterday, they can safely assume that I am one of the attackers and they simply throw away all tax forms from Thomer M. Gil that come in today. There are 2 big problems with this approach, though. First of all, I don't necessarily have to write down my own address. In fact, I can write down any return address I want. The second problem is that I can indirectly attack Jossi Gil by sending hundreds of envelopes with "Jossi Gil" on it to the Belastingdienst. Now when Jossi sends his real, legitimate tax-form to the Belastingdienst they will throw it away without opening it thinking that it is part of an attack. I successfully mounted a Denial-of-Service attack against Jossi Gil because he won't get an answer from the Belastingdienst. Conclusion: filtering on return address is a bad, bad strategy.
They might increase the number of people processing tax-forms, but this is a cat-and-mouse game that the attacker will win easily.
The basic problem is that the Belastingdienst can only make a decision about a tax-form *after* opening the envelope and looking at it. This is exactly what I want them to do.
You got the analogy by now. Attackers on the Internet attack a Web site by sending it so much traffic that it can't handle anymore. Attackers can make the traffic look very normal and they can put the wrong return address in it.
Remember that all these tax-forms go to the Belastingdienst by mail. I can't simply go to the Belastingdienst and drop hundreds of tax-forms on their desk. I will be caught and arrested. I have to be somewhat anonymous. I drop all my nonsense tax-forms in a mailbox close to where I live. The mailwoman that comes at 6PM to empty the mailbox has to do some work, though, to make this plan succeed.
It works as follows: Dutch ZIP codes look like NNNN XX (N is a digit, X is a character). The mailwoman has a big list with 10.000 numbers on it. It looks like this:
It's a list of all the first 4 digits of every ZIP code. She has a separate list for every mailbox that she has to pick up the mail from. Imagine she comes (on a normal day. There is no attack on that day.) at the Sarphatistraat (which some weird people think is the most beautiful street in the World) and puts all the mail from the Sarphatistraat mailbox in a bag. Now when she's back in her car with the bag, she takes every envelope out of the bag, one by one, and marks how many envelopes are going to what ZIP code. After that, her list will look like this:
LIST FOR MAILBOX AT SARPHATISTRAAT
11th of May 2000
In total, she had 21 envelopes in the bag. 5 had a ZIP code starting with 0001. 1 had 3721 on it, etc.
She puts the envelopes back in the bag and they get processed as usual.
For every mailbox that she empties, she has this list. Every day she makes a new list and she keeps all the old lists in a big archive. You can imagine that this information will tell her what to "expect". Armed with some statistics she can make a reasonable guess how many envelopes there will be for 3721 in the mailbox at the Sarphatistraat, for example.
Now I mount the attack against the Belastingdienst and I throw 1607 envelopes for the Belastingdienst (which has ZIP code 1062) in the mailbox at the Sarphatistraat.
The same mailwoman comes to the mailbox on the Sarphatistraat, opens it and puts all the envelopes in her bag. She makes the list, which will be somewhat similar to this:
LIST FOR MAILBOX AT SARPHATISTRAAT
22nd of June 2000
Most of the entries are within the margins that she expects. She is surprised at all of the envelopes going to ZIP code 1062, though. It is not what she would think to be "normal" according to her archive and her statistics. Now, what is she to do?
Unfortunately, these lists are not enough proof for the mailwoman to throw the envelopes going to 1062 away. She needs more proof that the receiving end of my mail has a problem with handling my mail. The only one who can give her definite proof is the Belastingdienst itself; she needs to be sure that they are under attack before she can throw my envelopes away. Let's suppose that the only way that she can reach the Belastingdienst to ask them this question is by mail. She could send the Belastingdienst a letter asking them: "Are you under attack? Please let me know. Yours truly, the mailwoman."
This scheme is no good for several reasons:
1. I (the attacker) could send the mailwoman a letter saying: "No, everything is fine. We have no problem. Yours truly, the Belastingdienst." How can she tell that the letter really came from the Belastingdienst? She'll probably receive an answer from the Belastingdienst, too, but that will only tell her that one of both answers did not really come from the Belastingdienst. She won't know which one.
2. If the Belastingdienst is really under attack, they might not have time to answer her question.
3. I could try to intercept her letter to the Belastingdienst.
4. A malicious person could send hundreds of "Are you under attack?" messages to the Belastingdienst. This is a new, very nice, very effective attack on the Belastingdienst.
Conclusion: sending the Belastingdienst a letter asking them whether or not they are under attack is a very bad idea. But still the mailwoman has to be sure that they are under attack before she can throw my mail away.
She has one definite clue, though. Since she is the mailwoman that empties my mailbox, she is probably also the mailwoman that brings me my mail every morning. Now if she sees that 1607 ANSWERS are coming BACK from the Belastingdienst within reasonable time, she will know that the Belastingdienst had no problem processing my 1607 tax-forms; even if they were nonsense. As long as answers are coming back from the Belastingdienst she can just as well send my envelopes to the Belastingdienst. If, on the other hand, she sees no answer coming back from the Belastingdienst to me, then she knows that the Belastingdienst is in trouble and she will block my mail going to the Belastingdienst.
Voilà; problem solved. Let's open a bottle of champagne and get the fuck out of here.
"Yes, Thomer, this sounds very nice, but what if you don't write your own return address on the envelope? The mail FROM the Belastingdienst will never come back to YOU which means that the mailwoman sees 1607 envelopes going TO the Belastingdienst and 0 coming back to you. She will think that the Belastingdienst can't handle the tax-forms and that they are under attack. That means she will throw away all the envelopes going to the Belastingdienst from the mailbox that you are using. She will even throw away the envelopes of your neighbors who throw their legitimate tax-forms in the same mailbox as you do. You are mounting a Denial-of-Service attack against your neighbors because their mail TO the Belastingdienst will be thrown away. Got you. Get the fuck out of here and come up with a better plan. This is bull."
Not so fast. There is one more thing that the mailwoman does with the envelopes. She will only process mail in the mailbox at the Sarphatistraat if the ZIP code of the return address (!) on the envelope starts with 1018, which happens to be the ZIP code of the Sarphatistraat. That means that I can not write a wrong return address on the envelope anymore because that means my envelopes will be thrown away by the mailwoman as soon as she takes them out of the mailbox and sees the wrong return address on them.
"Yes, Thomer, but you can write your neighbor's address as the return address since he has the same ZIP code as you. The mailwoman won't throw it away and it also means that your neighbor will receive all the 1607 answers from the Belastingdienst and not you. Your neighbor will be flooded by mail and he won't be able to find his REAL answer from the Belastingdienst anymore. You can still mount a Denial-of-Service attack against your neighbor. Back to work, you."
Yes. That is correct. I can still mount an indirect attack against people close to me (i.e. people who use the same mailbox as I do) but not against the whole country by disabling the Belastingdienst. What do you prefer?
"Yes, Thomer, but what if you organize this attack with so many people that no single attacker sends enough envelopes for the mailwoman to be suspicious of the envelopes going to the Belastingdienst."
Yes. You go organize so many people to mount an attack like that and I will find my next solution, OK? The whole point is that we're trying to make it HARDER to mount an attack, not impossible. Now get the f...
"But Thomer... Why would the mailwoman do all of this work for you? What's in it for her?"
Eehhmm... That's because this analogy is bad. In the Internet there is no clear distinction between the "traffic transporters" and the "traffic senders/receivers", but still you have a point.
"But Thomer... The mailwoman is already so busy driving around between all the mailboxes. Does she have time to do all of this? Won't this slow down the whole process of mail delivery?"
Yes. It slows things down a bit. This is a real problem because Internet providers (and others) will not accept this easily. We have to make it fast, indeed. Max and I are trying to make those lists and other things as fast and optimized as we can. I promise. But, there will always be a little extra work per envelope. Sorry.
"But Thomer, this sounds too simple to be true. You can't possibly mean that nobody else came up with this idea."
Well, actually, I am saying that. I couldn't find it.
Although the analogy is not optimal, I hope you do understand the basic technique.
For all of you who will react to this mail by writing me: "Yes, Thomer, but you didn't tell us how you feeeeeeeel? Are you happy? Are you alone? Do you eat well? Are you warm enough? Don't you have holes in your socks? Do you miss me? Will you stay in the US? Do your wear your helmet? Do you sleep enough? How's your health?
Mostly, sometimes, no, yes, no, yes, no, mostly, no, ok.