Strategies for loose auth in transparent environments?

[David Karr]

Let's say that I have a REST service that multiple clients would use,
and I need to have some control, even weak control, over who uses the
service, and what portions of the REST tree they can reference. This
would be somewhat similar to how Amazon, Google, Facebook, etc. have
clients use their registration-based services.

The service is intended to be called from Javascript/Actionscript.

The simplest solution would be to assign each client a static
generated API key that they send with each request. Obviously, this
is nowhere close to absolute security, but that doesn't exist.

What mechanisms could I implement to make it just a little bit more
secure?

I could tell the clients that along with the API key that we give
them, they have to construct a HMAC that composes the API key with the
message they're going to send. On the server side I would disassemble
the HMAC, verify the API key is valid and is associated with the
requested REST space, and that the requested REST space matches the
actual request. All of that assembly the client would do would be in
script, so anyone could see it, but it's at least a little more
obscure than using a static API key. Security by obscurity isn't
absolute security, but it's better than nothing.

What other strategies are popular?