hmac and symmetric cipher are not mutually exclusive ideas. In fact, AES-CMAC , which is both MAC (non-hashed) and symmetric encryption, AES-CMAC is a cryptographic primitive that makes WPA secure. (Although WPA can still be broken using the rainbow table).
You do not need an exotic authentication system for this. Logging in with a username and password and maintaining session state with a cookie is usually used because it is easy to implement and secure. Saving state like a cookie, it is no longer technically RESTful, but there is nothing to prevent you from doing this.
However, from an authentication point of view, I believe that asymmetric cryptography, such as RSA, is the most secure. (By default, Amazon uses asymmetric cryptography for ssh connections.) This allows only public keys to be stored, so if your server on which you want to compromise cannot use authentication credentials. It also protects against MITM attacks. In many cases, this can be easily implanted using REST, since HTTPS already supports client certificates. You can sign client certificates for free, and then verify them yourself.
If done correctly, the strength of the hmac against the symmetric cipher basically comes down to the strength of secrecy. If you use a secret as a password, then both systems are equally very weak. These secrets must be large, cryptographically protected by Psudorandom Numbers . Another thing to keep in mind is that symmetric ciphers are very difficult to implement properly. Most programmers do not understand this and ultimately reuse PRNG when using stream encryption or when using block encryption, use the wrong mode and leave the value IV null. Unlike HMACS, itβs very easy to implement, and less can go wrong. If everything is transmitted via HTTPS and you are using hmac, then its easy to implement a secure authentication system. If you really want to implement a symmetric cipher, you should get a copy of Piratical Cryptography , there are several chapters devoted only to symmetric ciphers, because so much can go horribly wrong. You should also consider key distribution, ssl uses DH-Key Exchange for its symmetric keys.
Be sure to read the top 10 OWASPs, especially Broken Authentication and Session Management. This requires the use of https for the entire session ; most web application programmers do not understand this.