Re: Hamiltonian path as protection against DoS.
-- Florian Weimer wrote: > How do Hamiltonian paths protect against the H.R.4411 > attack? H.R.4411 is not a DoS attack. > (Part of the DoS problem online casinos face is that > due to their activity, which was illegal before, they > are extremely reluctant to approach law enforcement > about this matter.) I was unaware that law enforcement does anything about DoS attacks. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG J/PQ9VnDD/6V3E2EFdJ5YlRKN1f8VW3eeiOrlW0n 4ZN9+U3RbPuc6REG0rZS2Bz/81I7N5FBe2J2FMkrR - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Hamiltonian path as protection against DOS.
* James A. Donald: > DOS is now a major problem - every business, online > games, money movers, banks, porno sites, casinos, now > comes under DOS attack from extortionists. How do Hamiltonian paths protect against the H.R.4411 attack? (Part of the DoS problem online casinos face is that due to their activity, which was illegal before, they are extremely reluctant to approach law enforcement about this matter.) - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Hamiltonian path as protection against DOS.
What is the complexity class for Eulerian paths/trails? Wikipedia doesn't say. -- "If you're not part of the solution, you're part of the precipitate." Unix "guru" for rent or hire -><- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Hamiltonian path as protection against DOS.
James A. Donald wrote: This is obviously the right way to do it - the current system has security and checking boundaries in the wrong place, as well as being unnecessarily verbose. Yet the plan never went anywhere. What happened? There is a gap between communications that are highly efficient with TCP, and communications that are highly efficient with UDP. Brief transactions (which must be reliable and two way, but are brief, are not efficient with either one. Indeed, ideally we would have one protocol that rapidly starts to approximate TCP behavior with communications that for which TCP is good (transferring large files) and that approximates UDP with communications for which UDP is good. ref: http://www.garlic.com/~lynn/aadsm25.htm#17 Hamiltonian path as protection against DOS so much of postings at http://www.garlic.com/~lynn/subnetwork.html#xtphsp talks about attempting to standardize xtp as HSP (high-speed protocol) in ansi x3s3.3 (and iso chartered organization) ... which was under mandate that no standardization work could be done on networking protocol that was in violation of the OSI model. turns out xtp/hsp violated OSI model in at least three different ways. xtp implementation was an adjunct to the tcp/ip (typically kernel) protocol stack. I've often commented that both SSL and VPN were successful because they added security layer w/o requiring changes to the (kernel) tcp/ip protocol stack. A person that we had worked with quite a bit introduced something (that since become to be called VPN) in gateway working group at the '94 san jose IETF meeting. my view was that it caused quite a bit of consternation in the ipsec crowd ... which were working on implementation that had hits to the underlying tcp/ip stack. VPN got a lot a lot of immediate uptake because it added security w/o requiring hits to the protocol stack in the end-nodes. The ipsec crowd somewhat reconciled VPN by starting to call it lightweight ipsec ... and some number of others then started called (regular) ipsec, heavyweight ipsec. original (lightweight ipsec) vpn resulted in some peculiarities being a countermeasure to internet anarchy by being a boundary router between corporate intranets tunneled thru the internet ... w/o requiring changes to the end-points. part of the issue was that some of the router vendors had sufficient extra processing capacity to do the necessary vpn crypto and some didn't. so two months after the san jose ietf meeting ... you saw some router vendors announcing VPN "products" that were actually just add-on of traditional hardware link encryptor boxes. so i've frequently claimed that ssl got market traction in much the same way that vpn got market traction ... by providing a solution that avoided hits to the (kernel) tcp/ip protocol stacks (modulo some really emergency server fixes at some high-end websites to handle the finwait list handling problem). requiring coordinated (most frequently kernel) tcp/ip protocol stack upgrades for all (or majority of the) machines in the world, is a uptake inhibitor. ssl wasn't necessarily the optimal networking solution ... but it did have the minimum impact on existing deployed infrastructure. in any case, some of the xtp features are starting to appear in some of the real-time streaming extensions ... like one of my favorites ... rate-based pacing (which i was forced to implement in high-speed backbones in the mid-80s) many of the online xtp resources have since gone 404 ... however there still are a few around http://usuario.cicese.mx/~aarmenta/frames/redes/xtp/biblio.html http://www.pcmag.com/encyclopedia_term/0,2542,t=XTP&i=55105,00.asp http://www.ccii.co.za/products/xtp.html HTTP1.1 attempted to amortize multiple HTTP interactions across a single tcp session (attempting to mitigate the overhead of reliable session protocol for something that was frequently very transaction oriented). again w/o requiring hits to the underlying protocol stack. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Hamiltonian path as protection against DOS.
-- Anne & Lynn Wheeler wrote: > so a real SSL simplification, when the client contacts > the domain name infrastructure to do the domain name > to ip-address translation, the domain name > infrastructure can piggy-back the public key and any > necessary ssl options on the ip-address reply. > > the client then composes a XTP transaction (has > minimum 3-packet exchange for reliable operation) that > has an "SSL" packet structure. the client generates a > random transaction key, encrypts the communication > with the random generated key and encrypts the random > key with the server's public key ... and sends it off > the encrypted random key and the encrypted > communication. This is obviously the right way to do it - the current system has security and checking boundaries in the wrong place, as well as being unnecessarily verbose. Yet the plan never went anywhere. What happened? There is a gap between communications that are highly efficient with TCP, and communications that are highly efficient with UDP. Brief transactions (which must be reliable and two way, but are brief, are not efficient with either one. Indeed, ideally we would have one protocol that rapidly starts to approximate TCP behavior with communications that for which TCP is good (transferring large files) and that approximates UDP with communications for which UDP is good. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG CA0JQkWZ0L1FZxznjfOXmVHVt4WiIwUva7ci5uD5 40h63MI/n3cU70SFRfoJG50yK9ZloczGB6D4pc25c - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Hamiltonian path as protection against DOS.
-- Anne & Lynn Wheeler wrote: > as an aside, i've pointed out before that in the > mid-90s that as webserver activity was increasing ... > a lot of platforms experienced severe throughput > degradation with HTTP transaction protocol use of TCP. > Most platforms had a highly inefficient session close > implementation around checking of the FINWAIT list ... > the assumption as that most session activity had > relatively infrequent session open/close activity. The > HTTP transaction activity violated those TCP activity > assumptions ... and for a period of time you found > platforms spending over 95percent of their processor > utilization dealing with the FINWAIT list. Has this been entirely fixed, or is some substantial degree of inefficiency inherent in the TCP protocol if one uses it in a manner that tends to approximate UDP. (Lots of brief connections that are predominantly one way.) The keep-alive extension to the HTTP protocol was intended to make HTTP activity more TCP like. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG 8PdgpCY8lcy6qRnKRQ4rc2g1XHLHgfmlDh2ajbn/ 4Tdc/z1dVOW8Pb51y7ZwS1xLayi1u3YmFU8aAvRdv - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Hamiltonian path as protection against DOS.
-- alan wrote: > But if the packets are forged, wouldn't that turn it > into a different kind of DOS? > > If I can get you to blacklist Alice by sending n > forged attack packages, then my DOS succeeded, if my > goal is to deny a connection between you and Alice. The goals is usually to shut down a money making service, in order to extort protection payments from them. Shutting off a few clients is not a goal. The photuris protocol that Bill Stewart mentioned does an initial exchange wherein the server sends some random bytes to the client, and the client must respond with those random bytes before the server does any work at all. This means that the adversary cannot easily and cost effectively impersonate Alice's IP, for large numbers of Alices, unless they have upstream control of the server's pipe - which would require them to be physically rather close to the server, and if they are physically rather close then the owner of the server can find them and go after them with an axe handle, reducing the problem to the previously solved problem of protecting property rights in physical space. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG Vd1vET3dgr85QVK7NkeKqXbuKv71rJtvAtE/6g9O 4rd/c+MMCzQCtCpvt4KYLGwIMyBJauOzgF9YYvZIU - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Hamiltonian path as protection against DOS.
On Tue, 15 Aug 2006, Bill Stewart wrote: Crypto is usually about economics and scalability. If you're doing this for DOS/DDOS prevention, you don't need the NP-completeness perfection you get from Hamiltonian paths or similar problems - SHA is fine, or any other hash that's quick to verify and hard to reverse. Even MD5 is probably still ok... Calculating any of the hashes probably takes less time than handling the packets does. It's almost certainly better for you if they harass you by sending you bogus SHA pieces that you can process quickly than bogus DH pieces that take you a while, and if it's not too distributed an attack, you can also blacklist senders IP addresses. But if the packets are forged, wouldn't that turn it into a different kind of DOS? If I can get you to blacklist Alice by sending n forged attack packages, then my DOS succeeded, if my goal is to deny a connection between you and Alice. -- "I want to live just long enough to see them cut off Darl's head and stick it on a pike as a reminder to the next ten generations that some things come at too high a price. I would look up into his beady eyes and wave, like this... (*wave*!). Can your associates arrange that for me, Mr. McBride?" - Vir "Flounder" Kotto, Sr. VP, IBM Empire. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Hamiltonian path as protection against DOS.
mikeiscool wrote: Could this sort of system be something that is implemented way before a HTTP connection even starts? Say, implemented by OS vendors or API vendors of sockets. That is to say, when you open a socket connection for the first time, for certain protocols, you need to pay this fee. The socket lib would be adjusted to do it, and then you are good to go. It would mean that other services get the benefit of protection. But is there legimate need to connect to many, or one, host many thousands of times? I'd guess there is. Take the discussed handshakes. Could something be incorporated there? Maybe there could be a new low level protocol, kind of like SSL, but less cost involved ... then you could tell your server to operate in that mode only... it can be considered from the standpoint of a lot of SSL is transaction oriented. you start with reliable TCP session support ... which has a minimum of 7-packet exchange. then you encapsulate all the HTTPS hand-shaking ... which eventually possibly reduces to doing a transaction packet exchange (as opposed to really requiring full session semantics). in the late 80s, there was work on reliable XTP, a transaction oriented protocol that supported reliable internet with a minimum of 3-packet exchange (disclaimer, my wife and I were on the XTP technical advisory board) http://www.garlic.com/~lynn/subnetwork.html#xtphsp so a lot of the SSL stuff around ssl server certificates is validating that the server you think you are talking to is actually the server you are talking to by checking the domain name from the URL that you supposedly typed in against the domain name in the ssl server certificate. a big vulnerability was created when a lot of the merchant servers ... that were the original prime target for ssl server certificates ... backed way from using SSL for the whole web experience and reduced it to just the payment transaction. the problem then was that the supposedly typed in URL came from a button provided by the server ... and not actually typed in by the client. the ssl server process then became checking the domain name in the URL provided by the server against the domain name in the certificate provided by the server (totally subverting original security assumptions). lots of past collected posts mentioning ssl server certificate infrastructure http://www.garlic.com/~lynn/subpubkey.html#sslcert So the next part was that somebody applies for a SSL server certificate which basically involves the certification authority checking the applicant provided information against what is on file with the domain name infrastructure. there was some integrity issues with this information being hijacked/changed ... so the certification authority industry was backing a proposal that domain name owners register a public key (with the domain name infrastructure) along with the other information. Then all future communication would be digitally signed (as countermeasure to various hijacking vulnerabilities). the issue then is that certification authorities can also request that ssl server certificate applications also be digitally signed. the certification authorities, then can validate the digital signature with the onfile domain name infrastructure (turning a time-consuming, error-prone, and expensive identification process into a much simpler, less-expensive and efficient authentication process) note that the existing infrastructure has the trust root with the information on file with the domain name infrastructure (that has to be cross-checked for identification purposes). the change to registering a public key retains the domain name infrastructure as the trust root (but changing from an expensive identification operation to a much simpler authentication operation). so a real SSL simplification, when the client contacts the domain name infrastructure to do the domain name to ip-address translation, the domain name infrastructure can piggy-back the public key and any necessary ssl options on the ip-address reply. the client then composes a XTP transaction (has minimum 3-packet exchange for reliable operation) that has an "SSL" packet structure. the client generates a random transaction key, encrypts the communication with the random generated key and encrypts the random key with the server's public key ... and sends it off the encrypted random key and the encrypted communication. for purely transaction operation, there is minimum (XTP) 3-packet exchange between client and server. however, if more data is involved, then as many packets as necessary are transmitted. I've suggested this design numerous times in the past. as an aside, i've pointed out before that in the mid-90s that as webserver activity was increasing ... a lot of platforms experienced severe throughput degradation with HTTP transaction protocol use of TCP. Most platforms had a highly inefficient session close imp
Re: Hamiltonian path as protection against DOS.
Crypto is usually about economics and scalability. If you're doing this for DOS/DDOS prevention, you don't need the NP-completeness perfection you get from Hamiltonian paths or similar problems - SHA is fine, or any other hash that's quick to verify and hard to reverse. Even MD5 is probably still ok... Calculating any of the hashes probably takes less time than handling the packets does. It's almost certainly better for you if they harass you by sending you bogus SHA pieces that you can process quickly than bogus DH pieces that take you a while, and if it's not too distributed an attack, you can also blacklist senders IP addresses. At present I'm skeptical about the need for that kind of protection - a simple UDP or TCP handshake and maybe a Photuris cookie are enough to take care of most forgery attacks and let you blacklist hostile senders. But malware writers are tenacious bastards, and perhaps there are or will be applications where this sort of protection could be useful - merely insisting that attackers use _your_ protocol is probably enough to cut down on 99.99% of attacks unless you get the protocol widely adopted. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Hamiltonian path as protection against DOS.
Could this sort of system be something that is implemented way before a HTTP connection even starts? Say, implemented by OS vendors or API vendors of sockets. That is to say, when you open a socket connection for the first time, for certain protocols, you need to pay this fee. The socket lib would be adjusted to do it, and then you are good to go. It would mean that other services get the benefit of protection. But is there legimate need to connect to many, or one, host many thousands of times? I'd guess there is. Take the discussed handshakes. Could something be incorporated there? Maybe there could be a new low level protocol, kind of like SSL, but less cost involved ... then you could tell your server to operate in that mode only... -- mic On 8/16/06, Bill Stewart <[EMAIL PROTECTED]> wrote: Crypto is usually about economics and scalability. If you're doing this for DOS/DDOS prevention, you don't need the NP-completeness perfection you get from Hamiltonian paths or similar problems - SHA is fine, or any other hash that's quick to verify and hard to reverse. Even MD5 is probably still ok... Calculating any of the hashes probably takes less time than handling the packets does. It's almost certainly better for you if they harass you by sending you bogus SHA pieces that you can process quickly than bogus DH pieces that take you a while, and if it's not too distributed an attack, you can also blacklist senders IP addresses. At present I'm skeptical about the need for that kind of protection - a simple UDP or TCP handshake and maybe a Photuris cookie are enough to take care of most forgery attacks and let you blacklist hostile senders. But malware writers are tenacious bastards, and perhaps there are or will be applications where this sort of protection could be useful - merely insisting that attackers use _your_ protocol is probably enough to cut down on 99.99% of attacks unless you get the protocol widely adopted. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Hamiltonian path as protection against DOS.
On Mon, Aug 14, 2006 at 12:23:03PM +1000, mikeiscool wrote: > But you're imaging an attack with a distributed bot net DDoS'ing you, > correct? Couldn't they then also use their botnet to process the > messages faster then normally? They already have the computering > power. Just a minor addon to the bot client app. If you're using a hashcash token which takes 20 seconds of your CPU, it'll slow the spammer down if they owned node has broadband. (Think about 5k message size, multiple Bcc recipients etc; the spammer of an owned botnet node can send multple many per second if hashcash reduces the number of messages that can be sent by a factor of 100, thats a good thing.) Whether its enough of a slow down is an open question -- but I think its difficult to imagine a security protocol that prevent spam with the attacker owning some big proportion of nodes. Adam > Or if it is many requests from one or thousands of clients, can you > not, per host, ask them to use a cached version? Per X timeout. > > Of course, you can't do this with SSL, though. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Hamiltonian path as protection against DOS.
But you're imaging an attack with a distributed bot net DDoS'ing you, correct? Couldn't they then also use their botnet to process the messages faster then normally? They already have the computering power. Just a minor addon to the bot client app. Or if it is many requests from one or thousands of clients, can you not, per host, ask them to use a cached version? Per X timeout. Of course, you can't do this with SSL, though. -- mic On 8/14/06, James A. Donald <[EMAIL PROTECTED]> wrote: -- DOS is now a major problem - every business, online games, money movers, banks, porno sites, casinos, now comes under DOS attack from extortionists. Before one does any potentially expensive operations, for example constructing a shared transitory secret with DH, or even setting up a connection, one would like to make the client pay a significant computational cost, preferably with one and half round trips of UDP datagrams. To do this the server should send the client some random bytes, and require the client to respond with something costly to construct from those random bytes, but trivial to verify. Commonly we use SHA - client responds with some bytes that when hashed with the server's bytes, produces a hash of special form. A single SHA operation likely costs two to four microseconds when efficiently done. If SHA is hard to reverse, client has to try bytes at random until it comes up with something that just happens to have the special form. But SHA was not really designed for this purpose. Further, there is no strong theory justifying SHA. It would be nice to do this with a Hamiltonian path. But Hamiltonian paths are tricky - it is not trivial to produce graphs of known difficulty. Ideally one would like to efficiently produce small Hamiltonian problems that are known to have a solution, and known to be hard on average. Has some work been done on this problem? Are there standard algorithms, or better, standard code, that I can copy? On the other hand, if we try to do something clever, we are likely to exceed a few microseconds, which defeats the purpose. While Hamiltonian path problems are more elegant, and directly appropriate to the problem, SHA is hard to beat. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG lxWf/Gt7dQkPv3EH7yXrYUWf/eCa0XA9bhesMQPf 46vWt67xdWudo2rkAO3DXrKLUYGguTLiyyovbxymM - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Hamiltonian path as protection against DOS.
-- DOS is now a major problem - every business, online games, money movers, banks, porno sites, casinos, now comes under DOS attack from extortionists. Before one does any potentially expensive operations, for example constructing a shared transitory secret with DH, or even setting up a connection, one would like to make the client pay a significant computational cost, preferably with one and half round trips of UDP datagrams. To do this the server should send the client some random bytes, and require the client to respond with something costly to construct from those random bytes, but trivial to verify. Commonly we use SHA - client responds with some bytes that when hashed with the server's bytes, produces a hash of special form. A single SHA operation likely costs two to four microseconds when efficiently done. If SHA is hard to reverse, client has to try bytes at random until it comes up with something that just happens to have the special form. But SHA was not really designed for this purpose. Further, there is no strong theory justifying SHA. It would be nice to do this with a Hamiltonian path. But Hamiltonian paths are tricky - it is not trivial to produce graphs of known difficulty. Ideally one would like to efficiently produce small Hamiltonian problems that are known to have a solution, and known to be hard on average. Has some work been done on this problem? Are there standard algorithms, or better, standard code, that I can copy? On the other hand, if we try to do something clever, we are likely to exceed a few microseconds, which defeats the purpose. While Hamiltonian path problems are more elegant, and directly appropriate to the problem, SHA is hard to beat. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG lxWf/Gt7dQkPv3EH7yXrYUWf/eCa0XA9bhesMQPf 46vWt67xdWudo2rkAO3DXrKLUYGguTLiyyovbxymM - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
