Slashdot Mirror
Denial of Service via Algorithmic Complexity
dss902 writes "We (Department of Computer Science, Rice University) present a new class of low-bandwidth denial of service attacks that exploit algorithmic deficiencies in many common applications' data structures... Using bandwidth less than a typical dialup modem, we can bring a dedicated Bro server to its knees; after six minutes of carefully chosen packets, our Bro server was dropping as much as 71% of its traffic and consuming all of its CPU. We show how modern universal hashing techniques can yield performance comparable to commonplace hash functions while being provably secure against these attacks."
I hate to ruin it for everyone, but the second link has the same content as the first, only in PDF format.
They claim to present a new method of low-bandwidth denial of service attack, but it looks like they're demonstrating quite an old, high-bandwidth, denial of service.
Tarsnap: Online backups for the truly paranoid
Several years ago Apache had a function that ran in O(n^2) time, and a HTTP GET request was capable of throwing that function into taking a very long time to process, making it easy to DoS an Apache httpd. The interesting part is that the same function could have been done in O(n) time, but wasnt. The Apache team fixed this by substituting the O(n) algorithm.
The One Rule Of Chess You'll Ever Need: Don't play someone who carries a kit in their bookbag.
you can use a modem to post a slashdot article with a link to the target computer...
...But in terms of raw power, nothing can match a slashdoting. Can anyone else read the link?
Speaking of, uh, denial of service...the site's quickly turning into a smoking ruin from where I'm standing. If it had been text only, it might have survived, but all the mathematical symbols are done using images (is that big O or big uh-O ;-) so the server is choking...
Bring on the MathML.
they don't list slahsdotting!
Do you even lift?
These aren't the 'roids you're looking for.
The project page is http://www.cs.rice.edu/~scrosby/hash/ and actually has details about individual vulnerable applications and test files for several systems. (And is kinder on the server for those who don't want to download the whole paper.)
Anyone got mirrors yet?
How am I supposed to fit a pithy, relevant quote into 120 characters?
This doesn't sit well with me. Should students at a University be studying, developing, and releasing improved methods with which to launch DOS attacks..?
It's a Mansierre!
What is a "Bro server"?
...at Rice university have way too much free time.
Denial of Service via Algorithmic Complexity Attacks
Scott A. Crosby Dan S. Wallach
scrosby_at_cs.rice.edu dwallach*cs.rice.edu
Department of Computer Science, Rice University
Abstract:
We present a new class of low-bandwidth denial of service attacks that exploit algorithmic deficiencies in many common applications' data structures. Frequently used data structures have ``average-case'' expected running time that's far more efficient than the worst case. For example, both binary trees and hash tables can degenerate to linked lists with carefully chosen input. We show how an attacker can effectively compute such input, and we demonstrate attacks against the hash table implementations in two versions of Perl, the Squid web proxy, and the Bro intrusion detection system. Using bandwidth less than a typical dialup modem, we can bring a dedicated Bro server to its knees; after six minutes of carefully chosen packets, our Bro server was dropping as much as 71% of its traffic and consuming all of its CPU. We show how modern universal hashing techniques can yield performance comparable to commonplace hash functions while being provably secure against these attacks.
Introduction
When analyzing the running time of algorithms, a common technique is to differentiate best-case, common-case, and worst-cast performance. For example, an unbalanced binary tree will be expected to consume O(n log n) time to insert n elements, but if the elements happen to be sorted beforehand, then the tree would degenerate to a linked list, and it would take O(n^2) time to insert all n elements. Similarly, a hash table would be expected to consume O(n) time to insert n elements. However, if each element hashes to the same bucket, the hash table will also degenerate to a linked list, and it will take O(n^2) time to insert n elements.
While balanced tree algorithms, such as red-black trees [11], AVL trees [1], and treaps [17] can avoid predictable input which causes worst-case behavior, and universal hash functions [5] can be used to make hash functions that are not predictable by an attacker, many common applications use simpler algorithms. If an attacker can control and predict the inputs being used by these algorithms, then the attacker may be able to induce the worst-case execution time, effectively causing a denial-of-service (DoS) attack.
Such algorithmic DoS attacks have much in common with other low-bandwidth DoS attacks, such as stack smashing [2] or the ping-of-death 1, wherein a relatively short message causes an Internet server to crash or misbehave. While a variety of techniques can be used to address these DoS attacks, common industrial practice still allows bugs like these to appear in commercial products. However, unlike stack smashing, attacks that target poorly chosen algorithms can function even against code written in safe languages. One early example was discovered by Garfinkel [10], who described nested HTML tables that induced the browser to perform super-linear work to derive the table's on-screen layout. More recently, Stubblefield and Dean [8] described attacks against SSL servers, where a malicious web client can coerce a web server into performing expensive RSA decryption operations. They suggested the use of crypto puzzles [9] to force clients to perform more work before the server does its work. Provably requiring the client to consume CPU time may make sense for fundamentally expensive operations like RSA decryption, but it seems out of place when the expensive operation (e.g., HTML table layout) is only expensive because a poor algorithm was used in the system. Another recent paper [16] is a toolkit that allows programmers to inject sensors and actuators into a program. When a resource abuse is detected an appropriate action is taken.
This paper focuses on DoS attacks that may be mounted from across a network, targeting servers with the data that they might observe and store in a hash table as part of their normal operation. Section 2 details how hash table
Basically, the paper says this: If you have a hash table into which attackers can insert arbitrary keys, you'd better be using a hash function for which they cannot easily generate collisions.
I don't know if anyone has *published* this before, but it's certainly not new.
Tarsnap: Online backups for the truly paranoid
I agree that DoS attacks are really lame, but at least this is fairly complex and has some interesting technological implications. Most DoS attacks are just floods of packets, and can't really be defended against. This attack can be prevented, and maybe will help improve security in other ways. I'd rather see 10 people who can pull off a preventable algorithmic complexity attack than 10,000 who just packet a server to death. People will write tools, but they'll still remain too hard for moron DDoSer script kiddies to pull off.
So this is like humans - you don't need a lot of information, just something seemingly complex/intricate, and their brains shutdown for a while?
;-)
(Or maybe this only happens to me?
Since you asked nicely..
This is the HTML version (with lots of images not mirrored, sorry) and this is the PDF version.
If the PDF starts hogging the pipe, don't be surprised if it gets symlinked to the HTML version.
Comment removed based on user account deletion
...we can bring a dedicated _Bro_ server to its knees...
Why they always trin' to bring the black man down?
Karma: The shiznight, mostly because I am the Drizzle.
... Or, this information can be used to inform people of the possibility of DOS attacks and possibly prevent them. If function X can be used to DOS a server, rewrite the code for function X or eliminate function X. ;-).
Are people who work at Ford allowed to test whether your car can be hotwired?
If not well, the price of used Fords just fell by 75%
I understand your question, but it, IMO, is like asking if "the people" should be free to speak about the bad things their King does, and wouldn't that just be bad for the Kingdom?
The only 'bro' server I can think of is buddyhead.com ... Not much of an attack if you ask me ...
Reading the paper which begins with "We present a new class of ..." it sounds like these students discovered a new concept from nowhere.
Maybe their genius has been triggered by the recent advisory about a DOS exploiting hash collisions in netfilter.
They analyzed some softwares but no word about this known vulnerability. Still a good summary but not a discovery.
They exploit the difference between 'typical case' behavior versus worst-case behavior. For instance, in a hash table, the performance is usually O(1) for all operations. However in an adversarial environment, the attacker constructs carefully chosen input such that large number of 'hash collisions' occur. Suitable collisions can be computed even when the attacker is limited to as little as 48 or 32 bits.
These attacks can occur over a very wide gamut of software, with impacts ranging from devestating to innocious.
We have studied and found the following applications possibly vulnerable to a greater or lesser degree:
For the last two, we have a tentative attack file, but have not constructed a test program to confirm the attack.
We have constructed attacks and confirmed the degradation on these:
Also related is the recent linux 2.4.20 route cache attack by Florian Weimer. David Miller is working on a patch that fixes other similar issues in other places of the networking stack.
Our paper discusses a new class of denial of service attacks that work by exploiting the difference between average case performance and worst-case performance. In an adversarial environment, the data structures used by an application may be forced to experience their worst case performance. For instance, hash tables are usually thought of as being constant time operations, but with large numbers of collisions will degrade to a linked list and may lead to a 100-10,000 times performance degradation. Because of the widespread use of hash tables, the potential for attack is extremely widespread. Fortunately, in many cases, other limits on the system limit the impact of these attacks.
To be attackable, an application must have a deterministic or predictable hash function and accept untrusted input. In general, for the attack to be signifigant, the applications must be willing and able to accept hundreds to tens of thousands of 'attack inputs'. Because of that requirement, it is difficult to judge the impact of these attack without knowing the source code extremely well, and knowing all ways in which a program is used.
The solution for these attacks on hash tables is to make the hash function unpredictable via a technique known as universal hashing. Universal hashing is a keyed hash function where, based on the key, one of a large set hash functions is chosen. When benchmarking, we observe that for short or medium length inputs, it is comparable in performance to simple predictable hash functions such as the ones in Python or Perl.
I highly advise using a universal hashing library, either our own or someone elses. As is historically seen, it is very easy to make silly mistakes when attempting to implement your own 'secure' algorithm.
The abstract, paper, and a library implementing universal hashing is available at http://www.cs.rice.edu/~scrosby/hash/.
Scott
** Affected Products: Extremely widespread. Confirmed vulnerable applications include Perl, the Linux kernel, the Bro IDS, and the Squid HTTP proxy cache. Although unconfirmed, vulnerablities appear to be in the GLIB utility library, the OpenBSD kernel, DJBDNS cache, TCL, Python, and Mozilla.
We conjecture that many implementations of hash tables in both closed source and open source software, unless specifically designed to be immune, may be subject to attack. It is likely
Wasn't that some command-line prompt game in 1983 somewhere?
This space for rent.
TOO BAD YOU CANT GET LAID ON A SATURDAY NIGHT!
Now it's time to pass the lameness filter.
Reason: Don't use so many caps. It's like YELLING.
I skimmed the Project Page and aren't a couple of the examples awefully obvious?
The following one line of code brings every UNIX system I've run it on TO ITS KNEES WITHIN MINUTES!! This is a major vulnerability in EVERY UNIX system! Something must be done!
We'll drizzle the shizzle all over the hizzle, my nizzle.
OR
Some random Slashdot Editor posting links to it, thereby calling the attention of the whole damn world to the fact that this class of vulnerability exists, apparently without fixes.
Yes, I know, "Security through Obscurity is no Security at All." On the other hand, in a multi-layered security environment (think defense in depth), obscurity, or secrecy IS a valid (albeit thin) layer. This just eliminated that layer.
Thanks, dipshits, and Slashdot, for making the world a WORSE place.
Given that this is a class of attacks, not a specific attack. How does one inform all of the maintainers of every possible vulnerable application, without it becoming known everywhere? The site discusses a half dozen different applications, by dozens of authors.
And I can think of another dozen applications and languages that may also be vulnerable, such as the C++ STL, Java, Ruby, and others.
How does one manage to inform only those, maintainers too?
What are Rice students still doing in school? Isn't it summer? Strange, very very strange.
Your mammas flamebait.
Naa. KISS.
It is probably easier to get 100 machines to DDOS a server, than to understand and get 1 computer to do a complex attack such as this one. This won't come into play untill they find a way to stop the current brute force attacks.
should not be considered a Denial of Service. If anything, call it what it truely is: shoddy programming. There is nothing being denied when it is the client that has the problem.
Another thing.. this is nothing new. A number of DoS attacks require the server to do more than the client requests. The attacker's complexity would be O(n) whereas the server would be O(n^2) or some such, where n is any given method of communication. The only "new" thing would perhaps be looking at individual programs and algorithms, which is probably applying a very liberal definition of "new." They even admit it themselves by claiming ping-of-death and stack smashing have much in common with what they describe in the article.
Dijkstra Considered Dead
Any attack against a Bro server is obviously a plot perpetrated by The Man, to keep a brother down. Peace to all my dead homies..
That specific attacks are given doesn't change this as the attacks given cover a variety of platforms and software - indeed, such attacks are not limited to network service software, but might be used against software that might be considered secure (behind firewalls with limited access).
The attacks given are not likely to be of general use to network script kiddies. They might be of use to the more technically adept. might.
Its also worth noting that the authors give enough information to build one or more defenses against such attacks. And carrying their hints a bit further would almost certainly enable developers to build a class of such defenses. But for the most part these defenses would still be tailored for the specific application in question and hence a general "one patch fits all" is unlikely to help many.
And if I might be permitted a specific response. The real dipshits are those who would, for whatever reasons, put a priori constraints on what someone might or might not publish. Let enough of these (evidently Divinely Inspired) idiots have their way and no one will be able to say anything.
The links have been cut back and the server is now responding.
- Heap with GC: to collect the garbage's objects until infinite
- Copy-GC: to eliminate the fragmentation
- only nodes and AVLs: no lists, no vectors, no arrays,
.. because they are O(n^2) inserting N items
JCPM (c)This DoS relies on the server being wide open on all ports. Simply putting the server behind a router that does NAT (Network Address Translation) or stateful packet inspection solves the problem of stray packets wandering in. Also note, this DoS does not crash any of the applications it just degrades performance. I would classify this DoS as "mostly harmless".
Worst case, this was a good excercise in analyzing algorithmic complexity and "Big O" notation for the CS students. Speaking of "Big O", I can't wait to check out the O(1) scheduler in the 2.5 Linux kernel.
Very easy. Next time you get /.'d just:
META HTTP-EQUIV="REFRESH" CONTENT="0; URL=http://slashdot.org"
The End
I've never heard of for() being a macro. What C implementation uses a macro? I would love to know.
Outdoor digital photography, mostly in New Engl
Well, back in 1990 when I started in university computer science, this *was* one of the main things that a denial of service attack was considered to be.
DoS attacks were mainly either removal of a service (by crashing it and/or stoping it's reload) or resource starvation, being any of CPU, disk, memory, network, etc.
Good to see these people have bothered to flick through a bit of history probably over 15 years old by now and call it something new, yawn.
Having had enough background in large computer systems, it can become quite depressing watching the constant flow of 'new innovations' that have been done may many years before on big iron, but are seen as new by people who just don't have the experience to realise.
Of course it is easier to DoS a machine by using it's own functionality against it rather than just brute force, welcome to computer science 101.
Just wait six months and someone will be releasing a fantastic new defense against this by limiting the CPU resources of given tasks to defined amounts so they cannot stop the system and only that particular service.
I mean come on, this was a common undergrad trick on the vaxes we used to get to play with way back then.
this dude is just testing the waters for a thesis for himself or someone else...it's just old news just changed enough to make it new enough for a thesis.
asdfdsf
In case you were wondering what Brois.
My brain is resistant to attacks using algorithmic complexity
This is my sig.
There's been extensive discussion of this over on python-dev. Includes some interesting debunking by Python guru Tim Peters, plus another example of the same type of weakness involving backtracking regular expression engines.
But consider a commercial app where customers can send requests to a J2EE app server running within a JVM. That's a very popular, very common setup (JBoss, BEA Weblogic, IBM WebSphere, etc.). The JVM is a single process. It is not CPU-capped because it's designed to stay up and running. When a Java thread handles a request and bumps into a CPU-hogging attack, it is not going to be terminated by the J2EE app server.
So this is potentially a problem, because you currently do not have a CPU-capping parameter in the most popular J2EE app servers. A response to this kind of attacks would require monitoring the amount of CPU consumed by threads processing incoming requests, which is always delicate.
CPU-capping shouldn't be done lightly. It can lead to disastrous failures. For instance, I once tried to use a graphical web application rendering some do-it-yourself tee-shirt lettering. The application was running on an older IIS and apparently had a CPU-time cap, because I got a message "sorry, your request took too long to process" when my design became a bit involved. Needless to say, my business went to a competitor. So CPU-capping isn't even a sure-fire solution.
In summary: Sorry, it is an issue.
--
Mad science! Robots! Underwear! Cute girls! Full comic online! http://www.girlgeniusonline.com/
making the computer do a very tedious job over and over and over again, but in plain english?!
The lunatic is in my head
Exercise: How did Bernstein manage to publish code in 1999 that defends itself against an attack announced in 2003? Choose one of the following answers:
- The part of Bernstein's code that mentioned ``hash flooding'' actually had something to do with illegal drugs. It stops this new attack purely by accident.
- Bernstein doesn't know anything about computer security, but he's mastered time travel.
- This attack isn't new.
You have five seconds to reply.I found your paper very interesting. I'd like to address a couple things.
1. You point out that MD5 is vulnerable to a brute-force search for bucket collisions. Isn't any deterministic hash-function vulnerable to the same attack? I know you solved the problem using a keyed version of MD5. With Carter and Wegman, you alluded to a randomly chosen constant and vector. I didn't notice you addressing this issue with UMAC.
2. The abstract says, "We show how modern universal hashing techniques can yield performance comparable to commonplace hash functions while being provably secure against these attacks." The abstract is ambiguous, but it insinuates that you'll provide a proof. I didn't see one. Perhaps it was in the references? Even if it was, certainly your 20 bit Carter-Wegman construction merits a new proof.
3. You said, "When analyzing algorithmic complexity attacks, we must assume the attacker has access to the source code of the application," I disagree. The attacker doesn't need the source code. They can reverse engineer the compiled binary.
Also, I wonder if an attacker even needs the program. An attacker could reasonably guess that a Perl script will store a certain string in an associative array. Many websites automatically process their Apache logs with Perl. Instead of requesting real pages, a blackhat could request strings that will hash to the same bucket (assuming the site uses Perl). When cron starts processing the logs, the website could slow to a crawl. Granted, the attacker knows the hash function from Perl, but they don't have access to the website's custom-made script.
4. You have a spelling error. Your paper should read, "due to the ten times larger queues of unprocessed events".
It is publish or perish at most universities and even most colleges.
They just found a topic to publish a paper on that extends things a little bit. This paper will then be footnoted by other researchers along with hundreds of other footnotes.
Very little published is new or even remotely creative - creativity is something that I have found is supressed by academia.
I suggest that if there are any questions, we as the slashdot community should collectively send them our pertinate questions.
Seriously though, you have to imagine how this will effect the less fortunate evil genuises of the world who are limited to dialup access (yes, there are bandwidth starved geeks out there). You have to wonder if your server wont be taking part in multiple DDoS attacks per week (its microsofts fault), because less bandwidth is required to do the dirty deed. Now, if you look at it this way, the discovery of this method could be a good thing for the poor sysadmins of the world, i.e. less bandwidth required to bring down a server usingf a DoS attack = less compromised servers needed to perform the attack. See my point? If not, ask yourself your your listening to the ramblings of a 15 year old.
Speaking at Defcon 12 - Credit Card Networks Revisted: Pen
- the suggested replacement for the hash function is slower for typical uses
- the suggested replacement doesn't acutally solve the problem (it just takes longer for the attacker to find DoS-able inputs)
- the suggested replacement returns different hash values for the same input for different processes (violating a garuntee in python)
- input sets large enough to do damage are large enough to be considered a DoS-by-flooding themselves
And of course it is much easier to exploit poorly designed regular expressions. They are common and a 1k string can tie up a server until the heat death of the universe..sig Karma out the wazoo, better to spend points elsewhere if this is above 2 or below 0
I have a lower slashdot user ID than DJB :D
That's made my day
My reply:
4. All of the above
If this guy can lie about observing the vulnerability in your software, it makes you wonder what else was he lying about
People will write tools, but they'll still remain too hard for moron DDoSer script kiddies to pull off.
History shows otherwise. Do you have a basis for your claim?
Such attacks will mostly be possible when you have access to the source-code of a program, and can look through it to find weak algorithmic parts.
I guess it's harder to do this on a proprietary system. Perhaps this the "Open source is less secure"-argument that MS has been hoping for?
I thought up a solution which does not involve the use of universal hashing algorithms. There are probably flaws in it (sounds too simple), so I'd like feedback. ;-)
What about adding a (session-wise) random number (salt) to every key prior to hashing? This way an attacker should first guess the salt. In environments where sessions are not present (like DNS), the salt could be changed every fixed amount of time (re-hashing all the keys). This can be done in a low-priority background process, while the old hash is still in use. When the new hash is ready, they are just flipped, defeating any attempt to brute-force the salt.
So, what about it, Slashdot crowd?
Open adressing hashing schemes have one inherent problem, especially if you use "double hashing", i.e. collision resolution makes use of a second hashing function.
You can not easily delete an item, you have to marked it as "deleted". No big deal, any decent book on algorithms states this very clearly. What is not so obvious, is that this kind of data structure does not easily recover from bad input. Consider the case where the hash table is 80 percent full, and all the remaining entries are marked as deleted. This will severly degrade unsuccessful search, and there is no easy way of "garbage collection". Probably you need to rebuild the whole table. Not a good thing.
A chained hash does not have this kind of problem, because its state is determined only by its actual content.
sig intentionally left blank
One more crippling bombshell hit the already beleaguered *BSD community when IDC confirmed that *BSD market share has dropped yet again, now down to less than a mere fraction of 1 percent of all servers. Coming on the heels of a recent Netcraft survey which plainly states that *BSD has lost more market share, this news serves to reinforce what we've known all along. *BSD is collapsing in complete disarray, as fittingly exemplified by failing dead last in the recent Sys Admin comprehensive networking test.
You don't need to be a Kreskin to predict *BSD's future. The hand writing is on the wall: *BSD faces a bleak future. In fact there won't be any future at all for *BSD because *BSD is dying. Things are looking very bad for *BSD. As many of us are already aware, *BSD continues to lose market share. Red ink flows like a river of blood.
FreeBSD is the most endangered of them all, having lost 93% of its core developers. The sudden and unpleasant departures of long time FreeBSD developers Jordan Hubbard and Mike Smith only serve to underscore the point more clearly. There can no longer be any doubt: FreeBSD is dying.
Let's keep to the facts and look at the numbers.
OpenBSD leader Theo states that there are 7000 users of OpenBSD. How many users of NetBSD are there? Let's see. The number of OpenBSD versus NetBSD posts on Usenet is roughly in ratio of 5 to 1. Therefore there are about 7000/5 = 1400 NetBSD users. BSD/OS posts on Usenet are about half of the volume of NetBSD posts. Therefore there are about 700 users of BSD/OS. A recent article put FreeBSD at about 80 percent of the *BSD market. Therefore there are (7000+1400+700)*4 = 36400 FreeBSD users. This is consistent with the number of FreeBSD Usenet posts.
Due to the troubles of Walnut Creek, abysmal sales and so on, FreeBSD went out of business and was taken over by BSDI who sell another troubled OS. Now BSDI is also dead, its corpse turned over to yet another charnel house.
All major surveys show that *BSD has steadily declined in market share. *BSD is very sick and its long term survival prospects are very dim. If *BSD is to survive at all it will be among OS dilettante dabblers. *BSD continues to decay. Nothing short of a miracle could save it at this point in time. For all practical purposes, *BSD is dead.
Fact: *BSD is dying
Well, you can write a deterministic quick sort that runs worse-case O(n^2). However, There is a completely deterministic Quick Sort that runs in O(n log n) time based on median-of-medians.
Note that you can take up to O(n) to select your pivot of a set of n elements and not change the analysis of quick sort (since it takes O(n) to divide the elements into greater-than-pivot, equal-to-pivot, and less-than-pivot). Consider the slightly simpler quickselect problem of finding the median in O(n) time. Clearly, if you can find the median in O(n) time, then there is a quicksort algorithm that runs in O(n log n) that uses that median algorithm to select its pivot.
Eppstein's lecture notes on O(n) quickselect.
Avrim Blum's lecture notes for cross-check.
Phil Gibbons has notes split across two days: Day 1 and Day 1
Can someone shed some light on the relation between Universal Hashing and the Rabin Fingerprint?
Being well balanced is overrated. -- John Carmack
Repeat with me, a hash is not always a hash
Repeat with me, a hash is not always a hash
"Many websites automatically process their Apache logs with Perl"
So what?
You think anyone would actually keep those
in memory? You're nuts.
perldoc perltie
perldoc DB_File
Mark Jason Dominus demonstrated this some time ago....When Hashes go wrong. Also interesting that the exploit he posted for perl also uses 10,000 inputs to demonstrate the problem.
On my site, I use referrer information for development purposes.
- Search engines:
When I see what people have tried to search, and I can modify my pages so that they are easier to find (instead of getting lost with pages that have almost nothing to do with the thing being searched for).
I can also focus on developing pages about most searched topics.
Mere "hits" don't tell what the user *wanted* to find. Referrer is important.
- Links:
It's very interesting to see where in the world are links to my pages. Discussion boards, web diaries and software collections have links to my writings and programs, and it's good to get to review what kind of context my pages are being referred in.
In my opinion, people, who hide the referrer information, are antisocial in the point of web development.
I really hope this information hiding behavior doesn't spread.
Makes me wonder: Is this Microsoft funding this to help protect people, or to learn how to hit Apple themselves?
Irene KHAAAAAAN!
>It's scary to me to think that people who write code in the first style get to submit code to important projects like Apache. It looks like a Basic programmer writing in C syntax. Even for a string with no double slashes it is far less efficient than the second style.
: ...
:
Actually this is one of the fundamental methodologies used in software development, dating back to the early Slow-Machineazoic period
In theory it goes like this
1. On paper, design the flow of data, what is hoped to be accomplished.
2. Prototype the functionality as a proof of concept, insure that the tools you are using to program the solution are sufficient to do it. Usually this code is pretty gnarly and uses O(n^2) or worse routines (cut and paste in a bubblesort, anybody?), just quick and dirty, screw memory leaks, etc
3. Test the functionality.
4. Using the prototype as a blueprint, rewrite the project using your most awesome coding techniques (replace the bubblesort with a quicksort, etc.)
5. Test the release candidate.
6. Ship it!
The (yes, it is documented) problem with this methodology is that it generally devolves to this
1. On paper, design the flow of data, what is hoped to be accomplished.
2. Prototype the functionality as a proof of concept, using routines that suck and are slow and leak memory like a fish net.
3. Test the functionality.
4. Somebody watching the calendar sees you are already over schedule.
5. Some bean counter over-rules your demands to rewrite the entire package, given that he watched it work.
6. Ship it!
Glonoinha the MebiByte Slayer
Seems to me that a simple way to avoid attacks on most hash functions would be to simply choose a few bytes of random data when the table is initially created then use slot=(R^H(value))%table_size.
The slots used by each value generally dont need to be preserved outside of the process where the hash table lives.
People will write tools, but they'll still remain too hard for moron DDoSer script kiddies to pull off.
Why? If Skript Kiddies could use tools like Trinoo, Stacheldraht, freak88 and mstream then why in the fsck wouldn't they be able to use a simple tool used to take advantage of this new DoS method?
You look to be one of those people who seriously underestimates his enemies, underestimating your enemies is always a bad thing.
When some real hacker writes a point and drool tool to take advantage of this attack I bet that it will be like the new WinNuke, all the kids will be using it.
anything that accepts zlib compressed data can be sent 1kb that expands to 1mb. bla bla bla. and many similar O(n^2) or worse algorithms can be triggered. why is this news?
The biggest implication of this is - if you're an open source application, exposing your internals to the outside world, and you are using a weak algorithm, then this sort of attack can be carried out on you.
Now I'm a fan of open source, but I'm sure that anyone that writes OSS will be taking this on board, so there's no need to worry.
Just joking, of course - everyone writing an accessible service in OSS needs to read this paper.
Sorry - rant over, but if you expose your internal workings, then clever bastards like these will find a way to tie your server up, unless you know their preferred attacks to start with.
oh brave new world, that has such people in it!
Take a trivial idea [gotta use secure hashes and balanced trees], throw in some text, a couple of graphs (preferably non-linear), format the article in two columns, save as PDF and voila it becomes "the new class of denial of service attacks".
Keep it simple, people.
...and not by the obvious method of printing a file containing nothing but 500 form feeds.
When I was at university, about 10 years ago, one of my fellow students came up with a way to tie up one of our shiny new Apple Laserwriters. They were quite expensive to run, and so the university charged us for each page that we printed. The nice thing about this hack, from the evil point of view, was that it produced only one page of output, so the cost to the hacker was negligible - at least in financial terms.
What was this hack? Well, the Laserwriters supported PostScript, which is a complete programming language. So this student wrote a little PostScript program that made the printer output a one-page, high-resolution copy of the Mandelbrot set...
Just another wannabe fantasy novelist...