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 majordomometzdowd.com

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 majordomometzdowd.com

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 majordomometzdowd.com

     --
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 majordomometzdowd.com