Re: Searching for a special challenge&response algorithm

Jan Peter Stotz wrote:
> Hi,
>
> I am searching for a special challenge & response algorithm which allows to
> prevent (or better slow down) denial of service attacks. Until now I did
> not succeed in finding a suitable algorithm, but may be I only used the
> wrong keywords.
>
> The general idea is as follows:
> When a client connects to a server it has to authenticate itself against
> the server. For preventing brute force attacks against this authentication
> (systematic testing) with one client the server creates a challenge which
> has to be solved by the client. For solving the challenge the client needs
> a bit of CPU power which results in a delay of about a second. The server
> only allows an authentication by the client after successfully solving the
> challenge.
> So i am searching for an algorithm which can be used in such an situation.
> An additional demand to such an algorithm is that creating the challenge
> and testing the client answer on server-side, if it is solved correctly
> should be possible with as less as possible resources.
>
> Does anybody know such an algorithm?

What's the DoS you're referring to?? 1 million clients requesting that
they want to be authenticated? Clients receiving the challenge and then
not responding so that the server runs out of resources because it has
to store the challenges?

I don't think any DoS attack is solved with a different C-R protocol;
it's the implementation, if anything. Have the server limit the amount
of requests that it can accept. Specify a sensible timeout for the
clients to respond. Put timestamps to the challenges, and if the
server runs out of capacity for new requests, start discarding the
oldest unresponded challenges, etc. Maybe set up some "reserved seats"
for privileged connections (e.g., from some IPs), so that you never
deny service to those, no matter how many other connections are being
handled.

Other than that, the protocol could be simple -- issue the challenge
from a high-quality, cryptographic random source (if on Linux/Unix
systems, try /dev/urandom) and store a timestamp and an IP address
associated with that challenge; then, have the client compute the
SHA-256 of their password with the challenge concatenated). The
challenge could be 128 bits (16 bytes read from /dev/urandom) --
that should be plenty enough.

HTH,

Carlos

--