To put this in concrete terms, can a web service become a "padding oracle"?
Without getting too much into details, I believe it is possible in some situations. The best way to protect against this is to ensure all your messages are digitally signed. With Wcf this behavior is actually built in to the framework and you cannot send messages which are encrypted but not signed. With older frameworks such as Wse, and some non-MS soap stacks, this is possible, so you might want to check any relevant production application.
Regardless of this it is always a best practice to sanitize customer facing error messages.
I have actually did a little test. I have configured a Wcf service to emit debug information in error responses (this is the most verbose response Wcf is capable of). I have then created a valid encrypted request, manually altered the encryption to make it not valid, sent it to the server and got this soap fault:
No secret data is enclosed here. I have then changed my server implementation to throw a logical exception:
I initiated a legal request and this time got this response:
So Wcf did return a full stack trace with an application exception. This means that Wcf shields us from verbose errors when security exceptions are thrown.
So are we safe?
You never are. For this reason take these precautions when using Wcf:
Disable debugging information in responses
Even though we saw Wcf tries not to disclose security information you should still protect from such information leaking into application level exceptions (or Wcf bugs). Just make sure your service has this behavior:
Protect your trace files at all cost
They may contain the detailed exceptions hackers look for.
What about Asp.Net web services?
Asp.Net web services (asmx) are inherently insecure (WRT message level) unless Wse is used with them. You should apply the same technique and sanitize your Wse error messages as explained in this walkthrough.