Daemonic Dispatches

AWS signature version 1 is insecure

The important bit first: If you are making Query (aka REST) requests to Amazon SimpleDB, to Amazon Elastic Compute Cloud (EC2), or to Amazon Simple Queue Service (SQS) over HTTP, and there is any way for an attacker to provide you with data which you use to construct your request, switch to HTTPS or start using AWS signature version 2 now. For example, if you allow users to add arbitrary "tags" to documents, and you use SimpleDB to store those tags, this means you. (Amazon Flexible Payments Service (FPS) and Amazon Devpay also use the same insecure signature method, but they already require the use of HTTPS. Amazon S3 and other services use different signature methods.)

I've been sitting on this blog post since May 1st, when I was reading documentation in preparation for writing the accounting code for my tarsnap online backup service and I first noticed that AWS signature version 1 was insecure; but now that the cat is out of the bag thanks to Amazon announcing the new signature version, it's time to publish the details of how their signature version 1 is broken.

AWS signature version 1 signs an HTTP query string as follows:

1. Split the query string based on '&' and '=' characters into a series of key-value pairs.
2. Sort the pairs based on the keys.
3. Append the keys and values together, in order, to construct one big string (key1 + value1 + key2 + value2 + ... ).
4. Sign that string using HMAC-SHA1 and your secret access key.

When Amazon invented this signature scheme, they forgot about one of the foremost design principles relating to cryptographic signatures: Collisions are BAD! In a well-designed signature system, it should be computationally infeasible to construct two different messages which have the same signature; this prevents substitution attacks where an attacker convinces the key holder to sign a "harmless" message, and then attaches that signature to a different message. Looking at how AWS signature version 1 is computed, it's easy to see how to construct collisions: Because there are no delimiters between the keys and values, the signature for "foo=bar" is identical to the signature for "foob=ar"; moreover, the signature for "foo=bar&fooble=baz" is the same as the signature for "foo=barfooblebaz".

To see how this could be exploited, let's return to my earlier example of a website which allows users to add tags to documents. Suppose that each document is identified as a single item in SimpleDB, and that each document has attributes associated with it including an "owner" and one or more "tags" (SimpleDB allows multiple values to be associated with each parameter name). To add the tag X to a document, the website would normally issue the SimpleDB request

?Action=PutAttributes
&Attribute.0.Name=tags&Attribute.0.Value=X
... other stuff

(whitespace added for clarity and to avoid page-width problems) which would be signed with the HMAC of ActionPutAttributesAttribute .0.NametagsAttribute.0.ValueX.... Now consider what happens if someone asks the website to add the tag "fooAttribute.1.NameownerAttribute .1.ReplacetrueAttribute.1.ValueDr.Evil" to a document. The website issues the SimpleDB request

?Action=PutAttributes
&Attribute.0.Name=tags&Attribute.0.Value=foo Attribute.1.NameownerAttribute.1.ReplacetrueAttribute.1.ValueDr.Evil
... other stuff

which is signed with the HMAC of ActionPutAttributesAttribute .0.NametagsAttribute.0.ValuefooAttribute .1.NameownerAttribute.1.ReplacetrueAttribute .1.ValueDr.Evil... -- which would also be the signature for the request

?Action=PutAttributes
&Attribute.0.Name=tags&Attribute.0.Value=foo
&Attribute.1.Name=owner&Attribute.1.Replace=true&Attribute.1.Value=Dr.Evil
... other stuff

Providing that this request is sent over HTTP, Dr. Evil just has to capture this request (via network sniffing or ARP / IP / DNS / BGP attacks) and he can attach the signature from the real request to his fake request, whereupon he sets himself as the "owner" of the document in question. If the request is sent over HTTPS, in contrast, Dr. Evil won't be able to see the signature (unless he has an SSL certificate for sdb.amazonaws.com, which is unlikely) and so he won't be able to apply this attack.

I reported this issue to Amazon via an email to Jeff Barr, the "Lead Web Services Evangelist" at Amazon on May 1st, and while it took a long time -- 7.5 months -- for it to be fixed, I'm happy to say that Amazon took this issue seriously at all times, and the lengthy timeline was simply because of the large amount of work involved. Jeff forwarded my email to someone working on SimpleDB (I've been asked not to mention names), who confirmed that they agreed that this was a problem. As part of their review of my findings, Amazon's security people realized that this also affected EC2 and SQS -- in my initial investigation I had only looked at SimpleDB -- and at the beginning of July they agreed to send me their planned signature version 2 so that I could review it.

Aside from some minor clarifications to the documentation, I saw no problems with the new signature method, and at that point Amazon started the lengthy process of implementation, testing, and rolling out the new signature method. In September, they allowed me to perform some basic interoperability tests between my code (written based on the documentation) and their back-end code; this proved very useful, as it uncovered an ambiguity in the documentation. Amazon then returned to their processes -- including updating their many client libraries in order to make sure that everybody would be able to switch to signature version 2 as soon as it was announced. Now, in mid-December, they've finished updating their servers, documentation, and libraries, and the new signature is finally being announced.

I must congratulate Amazon on a highly professional response to this issue. Companies very frequently have difficulty handling externally-discovered security problems, both because of a temptation to downplay the significance of the issues, and also because of a desire to keep potentially sensitive information out of the hands of anyone outside of the company -- Intel's response to the Hyperthreading information leakage problem is a good example of both of these. The fact that Amazon not only accepted that there was a problem, but was willing to keep me informed during throughout the process of fixing it -- even going to the extent of allowing me to review their intended solution, which is more than the FreeBSD Security Team usually does -- is quite exceptional.

People inevitably make mistakes from time to time. Security problems happen. But when they do happen, Amazon's response is a good example to follow.

blog comments powered by Disqus