Colin Percival announced an interesting bug back in December in howAmazon Web Services signs data. Amazon allows users of their APIs (e.g., EC2 and SimpleDB) to authenticate requests by applying an HMAC. This is supposed to ensure the request was unmodified after the sender created it; however, there was a subtle flaw that allowed an attacker to forge requests in certain circumstances.
An HMAC works by applying a cryptographic hash algorithm to the user’s data and a secret key. Another party who knows the same secret key can perform the same calculation. If the HMAC results match, the data has not been modified. The problem lies in the lack of structure Amazon applied to the data, resulting in exploitable ambiguity. You can see Colin’s advisory for more details about how this can be exploited. See also the function signParameters() in the client code, AmazonEC2Client.java, for all three versions of this function.
To prepare a URL to be authenticated in AWS-Signature v1, the API caller concatenates all the key/value pairs into a single string (key1 || value1 || key2 || value2). Then, the caller calculates the HMAC of this value and attaches it to the original API request as the “Signature=” key. The HMAC is supposed to authenticate this request, proving that the sender originated the request and that it had not been modified in transit.
It’s pretty obvious that this lack of structure results in an ambiguous interpretation. The HMACs of the following URLs are identical:
…?GoodKey1=GoodValue1BadKey2BadValue2
…?GoodKey1=GoodValue1&BadKey2=BadValue2
As long as the attacker can change the value of any tag in the request and observe the resulting HMAC, he can later add any number of bad keys and bad values and resubmit the request with the same HMAC. The fix in AWS-Signature v2 is to add back various delimiters between the key/value pairs before calculating the URL’s HMAC.
There’s a variant of this attack that even AWS-Signature v2 does not appear to address. If an attacker can observe a single signed request, that request can be resubmitted any number of times. Thus, an API call like “credit account $10” could be repeated any number of times. Of course, using SSL for the request would prevent this attack, and it’s likely that users would send most financially-related messages over SSL. However, given that this protocol is intended to be secure over plain HTTP, it’s possible some users trust it to ensure message uniqueness in addition to integrity protection.
I’ve observed this kind of flaw before in other systems, including specifications for single-sign-on cookies. Vendors that specify their own signature format should get a review of their design to be certain they strictly validate the structure for any values that they sign.
rdist 
How would you address the resubmission vulnerability? Maybe transaction identifiers and timestamps that are also included in the HMAC process? Transaction identifiers could be used for message “aging”. If a transaction identifier is present in a table somewhere then the service knows it has already processed that request. The timestamp might ensure that the aging table can stay “light” (you only need to keep enough transaction identifiers that correspond to your timestamp threshold). It seems like it would resist some forms of replay. What do you think?
A serial number is probably easiest to get right, except you’d have to persistently keep track of the last value to be sure it never repeated (for example, across reboots). You could also use a nonce, hoping that the system PRNG handles uniqueness for you.
With timestamps, you’d always have a small window where multiple requests could get by. In my brief review of the EC2 Java client, it seemed like they had put in a Timestamp parameter at some point but it’s unclear how it is checked, if at all.
What we really should be discussing is how this will slowly grow to become a bad variant of SSL, but less reviewed and with a single company as the only implementation. How likely is that to be secure? Why are we slowly redefining SSL in the first place?
Nate – I was always under the impression that SSL isn’t the best fit for application-layer message authentication. Maybe I’m confused (very likely), but I thought your original post was discussing HMAC to authenticate *messages* not the overall transport security (useful to protect an HMAC from being disclosed/replayed as you mention). Maybe some discussions about how to implement lightweight message security for web applications is in order?
roodee, yes, they can be two different things. However, if you look at what the customer is sending to SimpleDB (for example), it’s a URL query string. HTTPS is used every day to protect URLs and data, giving privacy, integrity protection, and even identity (if you use it with a cookie or client-side certs). This is a simple request/response protocol over HTTP, the perfect place to apply SSL.
The only reason I can think someone came up with this scheme instead of SSL is that they thought SSL was slow. Or, maybe they needed to store data with an untrusted user (i.e., a cookie).
Can you enlighten me how the messages from a website to EC2/SQS/SimpleDB have requirements that SSL doesn’t provide?
Nate, I agree that SSL is useful “protect URLs and data, giving privacy, integrity protection”. However, I would clarify that SSL provides those features in an application agnostic way. An application doesn’t need to know anything about what SSL is doing. This is a good thing ™. However, if client certificates are not viable and an application needs some degree of message level security (authenticating messages for example), we may have to look elsewhere. That was the main point of my earlier comments. In my opinion, without certificates the protections afforded to us by SSL don’t address all of the requirements (most, but not all). In my view SSL provides protection at the transport level, not the message level. Yes, the messages within the SSL stream have those protections, but that is from the context of the *SSL endpoints*, not the *application*. HMAC is an option that can authenticate messages from the context of the application. Like you mentioned in your original post, you’d definitely need to rely on SSL to protect the data stream.
I brought up the SSL vs. AWS-Auth decision because their own page suggests that “SSL is best, but if you can’t do it, here’s something else you can use.” They give two reasons SSL isn’t the answer: latency and lack of library support. The latter is a red herring since all the languages their library supports also have built-in SSL (Java, C#, etc.)
So that leaves latency as the only valid reason. I’m not a web scalability expert, so it boggles my mind that a 1996 protocol could be giving performance problems in 2009. If SSL session resumption is too slow, what about keeping a socket open with the keep-alive option for 10-30 seconds after each API call and forcing a resume otherwise? It seems like latency is solvable as well.
To address your point about authenticating an application, there are a number of options, some not so good. Basic auth is a hack. Client certs are well-integrated but do require distributing a blob to your clients. That may be acceptable since “clients” here means a set of systems you have root on. I’d also suggest SSL-SRP since it gives you excellent security and the user model of basic passwords.
I remain unconvinced why AWS-Auth should exist.
Nate – I couldn’t hit ‘reply’ next to your comment so I’m asking here. I’m not sure I understand how client certs involve distributing a blob to your clients. Dont you mean distributing a blob to your servers? Essentially the server should check whether the client cert matches the cert the client gave you through some out of band mechanism (like uploading through a site).
SK, for client cert auth, you have to distribute the private key (PEM file) to all the clients. Or, you have to provide a tool to the clients to generate their own keys. Either way, it’s not well-integrated with the stock OS. Does Apple’s keychain utility automatically generate client certs/keys?
The following paper discusses splicing attacks and replay, and lots of useful things to consider when implementing a web-based authentication scheme. http://cookies.lcs.mit.edu/pubs/webauth:tr.pdf
Replay of the ‘PAY’ API call won’t work. A parameter of the PAY call is the payment token, which the payer has to explicitly authorized over https to an amazon.com webpage.
A multiple-use token (one which can be charged multiple times without reauthorization) could be vulnerable, but that hole is closed via a “caller ref”, a string value chosen by the caller that identifies the PAY request. Resubmitting the PAY request against the same token with the same caller ref will result in only 1 charge.
Nolan, thanks for commenting. I wasn’t calling out a specific Amazon API (“PAY”) as vulnerable. In fact, it’s good that they’re providing higher-level APIs like that so the customer doesn’t have to roll their own.
Towards the end, I think you start to agree with my point — the authentication scheme itself leaves too much up to the caller. For example, you’re saying they are responsible for making sure “caller ref” is unique and non-repeating. But really, the authentication scheme should do this for them.
In cryptographic terms, the HMAC means “at some point in the past, I said the following”. It only tells you if the fields that are authenticated were changed (i.e., whether you can trust that statement). As you note, the user almost always wants some kind of association (“I said X in response to Y”) or sequence (“I said X before Y”). So this is something the AWS API should be providing by default. It’s too important to leave up to the caller’s design and implementation.
Oh, I absolutely agree with your point, and I use https for all my interactions with AWS.
I was merely compulsively correcting minor misinformation.
There is something called idempotency that applies to any API in general and comes in handy in distributed systems in particular. All the amazon WS APIs are idempotent. So if someone sends two exact requests then he’d get the exact response. This allows the clients to retry on timeouts which are very common over the wire. If a timeout occurs the client will be in blind as to what happened on the server side, a) Did the request timeout b) Was the request processed and the response timed out? So what the client does is just retry the same request, so he’ll get the same response. The onus is on the WS publisher to clearly document in the interface what the idempotency criteria is. This has the happy coincidence that even if an attacker gets hold of a request, the best he can achieve is get back the idempotent response, no big harm done. And if an attacker tries to modify the request and replay it then of course the signature check would fail.
Explain how idempotency saves you here:
ADD_USER(“nate”)
DELETE_USER(“nate”)
ADD_USER(“nate”)
Interesting article. AWS v1 pretty much reminds me of the Facebook signature method,
see
http://code.google.com/p/facebook-java-api/source/browse/trunk/facebook-java-api/src/main/java/com/google/code/facebookapi/FacebookSignatureUtil.java#365
just concatenation without separator (which seems to be at the heart of the problem),
but sorting (which seems not important at first look).
What I took from crypto lectures is that it is hard to get right.
So I wonder who came up with that kind of “AWS signature” scheme
and why was it considered safe?
Nate, I agree that SSL is useful "protect URLs and data, giving privacy, integrity protection". However, I would clarify that SSL provides those features in an application agnostic way. An application doesn’t need to know anything about what SSL is doing. This is a good thing ™. However, if client certificates are not viable and an application needs some degree of message level security (authenticating messages for example), we may have to look elsewhere. That was the main point of my earlier comments. In my opinion, without certificates the protections afforded to us by SSL don’t address all of the requirements (most, but not all). In my view SSL provides protection at the transport level, not the message level. Yes, the messages within the SSL stream have those protections, but that is from the context of the *SSL endpoints*, not the *application*. HMAC is an option that can authenticate messages from the context of the application. Like you mentioned in your original post, you’d definitely need to rely on SSL to protect the data stream.
I appreciate you explaining more, but I still don’t see the need for the distinction you’re making between endpoints and application. However, I can come up with an artificial scenario which should be helpful for discussion.
Consider a client, middle-man, and server. The client wants to authenticate its requests to the server while sending them through the untrusted middle-man. The middle-man should not be able to masquerade as the client and generate its own requests. Obviously, SSL does not provide this protection.
But instead of rushing to implement a separate authenticated message layer, why not reconsider the architecture that creates an untrusted middle-man? In nearly all cases, this is due to an attempt to work around a broken architecture by adding custom crypto. Now you have two problems!
I have seen very few cases where this was actually necessary and in those cases, a high-level API, such as Keyczar, or using an OS subsystem, such as disk encryption, were the right answers.