Re: client puzzle protocol

["Gregory Stark" <greg () securityguides com>]

----- Original Message -----
From: "Antonomasia" <ant () notatla demon co uk>
> It may prevent spoofing, but I think massive parallel puzzling by large
> numbers of zombies with genuine unwanted connections will beat this and
> anything else of the kind.


The RSA paper does in fact handle this. Similar ideas have been mentioned on
the IPsec mailing list.

The basic idea is to make the client save the state info that the server
normally would save. Part of solving the "puzzle" would be to hand back to
the server the state blob he originally handed you. In a simplified version
of the puzzle, the server computes y = f(x) where f() is a cryptographically
one-way hash function like SHA1 or MD2/4/5. The client must invert the
function and recover x to solve the puzzle. The server gives the client a
"hint", telling it all but k bits of x. The client then tries all the
remaining possibilities for the unspecified k bits until it finds the
correct x. If the server also gives the client an encrypted form (with 3des
and key x for example) of its TCP state (struct TCPState {Window w1;
unsigned long seqnum; Whatever w2}) then the server can deallocate the
memory for this state. If a client completes a puzzle correctly and returns
the TCPState then server can allocate the memory and keep it. The real
protocol would use time stamps, digital signatures / MACs, and secret keys
known only to the server to make it secure, but these are the basics. If you
actually flesh it out, the server doesn't need to store anything, not even
the outstanding (x,y) pairs. See the RSA paper for the actual details.

When a client tries to open a TCP connection the server hands him a puzzle
(via UDP so we do not care if they get it, they'll just have to ask again if
they don't). The client must solve the puzzle and send it back to the server
(via UDP so if the client becomes impatient it can send it again). If the
server receives a correctly completed puzzle, suitably fresh, it reallocates
the state and completes the TCP connection with the client. The server must
be able to cheaply discard bogus solutions so we cannot use public key
cryptography.

Please explain where/why the server must retain state information which
makes it susceptible to DoS?



Greg Stark
    securityguides llc
        Information Security Consultants
greg () securityguides com
www.securityguides.com

(410) 381-9410 (Work)