Hamiltonian path as protection against DOS.

[mikeiscool]

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 <jamesd at echeque.com> 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 majordomo at metzdowd.com
>

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com