This doesn't depend on the algorithms you use. The padding oracle attack works just fine with DES-EDE, Serpent, AES or Twofish; HMAC-SHA1, HMAC-SHA256, and (probably) HMAC-MD5 are all equally effective at combating it.
If you need to put sensitive data in cookies, you're doing it wrong!
Note that (a) lots of people have screwed up HMAC recently and (b) HMAC isn't a solution to the padding oracle problem unless you take pains to make sure it isn't.
(Unless I'm mistaken and there's other advantages for choosing encryption over MAC?)
Interesting, how could you exploit padding oracle when you're using HMAC?
In sign-then-decrypt designs --- which, from what I've seen, is what most designs are --- you can still exploit a padding oracle when the app catches padding errors and skips the (pointless) MAC verification for a packet it plans to discard anyways.
If a developer writes a cookie, it's not encrypted and the user can easily change it. Just normal cookies.
If a developer writes a session cookie, ASP.NET encrypts it behind the scene and stores it in a cookie. Because the user doesn't know the encryption key, he can't change the session cookie. The developer doesn't do any encryption himself, he just tells ASP.NET "Please store this value at the user, but he should not be able to tamper with it".
However, crypto is hard, so because of the issue mentioned in this article it is possible to tamper the data.
Could someone correct me if I'm wrong?