I want to restrict access to my web service to only approved client
applications.

This has to be done from inside the web service, so Windows
Authentication is not an option.

I would like to allow the possibility of non windows clients, so I am
not sure if any of WS Security is an option. I am pretty sure I will
have to implement a custom authentication.

My first thought was to have the client possess a public key which will
be used to encrypt some data and send it to the web service. If the web
service can decrypt it with it's private key, the client can be assumed
to be authenticated+authorized (also depending on the content of the
encrypted data).

The drawback to this, is each client will need to have the public key
compiled in, and kept secret. I know this is bad form, but in any
senario, won't the client be required to have some form of
authentication compiled into it?

Unless there is some complicated agorithm that could generate a unique
string that the web service could verify that the string was generated
by the algorithm?

There has to be some secure method of doing this, but all the .NET docs
really focus on windows authentication. Does anyone have any input?