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.

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