Amazon WS Crypto Sigs v2 Broken (Even Amazon Can't Get Crypto Right)(rdist.root.org)
rdist.root.org
Amazon WS Crypto Sigs v2 Broken (Even Amazon Can't Get Crypto Right)
http://rdist.root.org/2009/05/20/amazon-web-services-signature-vulnerability/
31 comments
There's nothing wrong with AWS's signature version 2. Nate is a smart guy, so I can only assume that he's being disingenuous rather than dumb; he should know perfectly well that the purpose of a message signature is to ensure that messages cannot be forged, and that figuring out what to do with the messages after they have been authenticated -- including verifying nonces -- is not the job of the signature scheme.
Colin, I chose the wording for this title, not Nate, but you should know this is _Practical Cryptography_, page 108, graf 5, leading to "Design Rule 4, The Horton Principle". I don't think you're going to win this argument.
What you call "disingenuous", I call a "more complete consideration of the AWS security system". Even though I think you're aware of Nate's background, I'll assume good faith and just remind you that when you're reviewing protocols professionally, things like "messages are replayable and the protocol is only secure when run over TLS" get called out.
What you call "disingenuous", I call a "more complete consideration of the AWS security system". Even though I think you're aware of Nate's background, I'll assume good faith and just remind you that when you're reviewing protocols professionally, things like "messages are replayable and the protocol is only secure when run over TLS" get called out.
If the application layer cares about replays, sure. But in well-designed distributed systems, the application layer doesn't care about replays, because replays are the only way to ensure that operations succeed given node failures.
Isn't that a bit much to be throwing onto the shoulders of the application developer? At the very least I'd expect it to be explicitly documented that the possibility of replays by untrusted parties needs to be considered. I know you took it into account, but I doubt you have very much company.
At the very least I'd expect it to be explicitly documented that the possibility of replays by untrusted parties needs to be considered.
Hmm, good point. The AWS documentation has never been very explicit about these sorts of issues -- I'll email a few people at Amazon and suggest that they improve this.
Hmm, good point. The AWS documentation has never been very explicit about these sorts of issues -- I'll email a few people at Amazon and suggest that they improve this.
Yes, this is moving toward what I was trying to say. Sorry if that wasn't clear. But I think the answer is not more documentation but handling this for the developer at a lower layer. And instead of Amazon implementing this lower layer themselves, use existing protocols like SSL.
With the exception of identity, SSL provides all the integrity protection, ordering, uniqueness, and even privacy that a developer could want. If you're willing to use client certs or SRP or basic auth, then you have identity covered too.
Amazon is exactly right in recommending SSL primarily. I just think they should stop there and not add "but if you have SSL performance problems, use AWS-Auth".
With the exception of identity, SSL provides all the integrity protection, ordering, uniqueness, and even privacy that a developer could want. If you're willing to use client certs or SRP or basic auth, then you have identity covered too.
Amazon is exactly right in recommending SSL primarily. I just think they should stop there and not add "but if you have SSL performance problems, use AWS-Auth".
Where does the nonce go? I skimmed the REST API for S3 uploads and didn't see a mention of one other than possibly the date, and the date only has a granularity of one second.
There isn't a nonce in S3-REST, because it doesn't need one. PUT is idempotent -- it doesn't matter if an attacker replaces your data with an exact copy.
If you're crazy enough to be issuing PUTs with different data, or PUTs and DELETEs, to the same object name within the time window before the request expires (yes, S3 checks the date/time for validity), an attacker could reorder your operations... but that's not actually a security flaw, since S3 itself is allowed to reorder operations (cf "eventual consistency"). All an attacker would be able to do in that case is break code which is already broken.
If you're crazy enough to be issuing PUTs with different data, or PUTs and DELETEs, to the same object name within the time window before the request expires (yes, S3 checks the date/time for validity), an attacker could reorder your operations... but that's not actually a security flaw, since S3 itself is allowed to reorder operations (cf "eventual consistency"). All an attacker would be able to do in that case is break code which is already broken.
Okay, good point about eventual consistency. I maintain that Amazon really ought to do a better job of explaining this, though. I assume the typical window for consistency is significantly shorter than the leeway that they allow for clock skew when validating the date.
I assume the typical window for consistency is significantly shorter than the leeway that they allow for clock skew when validating the date.
As long as S3 remains connected, it should reach consistency immediately (for PUTing an object which doesn't exist yet) or within a few seconds (for PUTing a new version of an object which already exists or DELETEing an object). But there is currently no way to determine if S3 is connected, so you can't rely on the "typical" consistency window.
BTW, you can specify how much clock skew S3 should permit when you construct your requests.
As long as S3 remains connected, it should reach consistency immediately (for PUTing an object which doesn't exist yet) or within a few seconds (for PUTing a new version of an object which already exists or DELETEing an object). But there is currently no way to determine if S3 is connected, so you can't rely on the "typical" consistency window.
BTW, you can specify how much clock skew S3 should permit when you construct your requests.
However, if the messaging layer provided ordering and uniqueness guarantees, that same code could not be compromised. Also, your comments seem to be specific to SimpleDB. Is it possible other components that depend on AWS-Auth have related issues?
So... are you sure you want to try to build crypto into your application based on your dog-eared copy of Applied Cryptography and a couple of Coding Horror blog posts and comment threads?
The problem Nate talks about (replaying valid messages) is not a cryptographic problem. It's a distributed systems problem, and Nate's suggested solution (adding a nonce) isn't the right one. The right way to handle replays in a distributed system is by making operations idempotent -- which is exactly what AWS did.
So... are you sure you want to try to build crypto into your application
Yes, I am. :-)
BTW, what do I need to do in order to convince you to start recommending scrypt instead of bcrypt?
So... are you sure you want to try to build crypto into your application
Yes, I am. :-)
BTW, what do I need to do in order to convince you to start recommending scrypt instead of bcrypt?
Hi Colin, I decided to jump in here. Can you point to an AWS doc explaining how every operation is idempotent, including all combinations of them? I have a hard time understanding how something like "ADD USER 1", "DELETE USER 1", "ADD USER 1" can be an idempotent sequence where ordering doesn't matter. BTW, I'm not an AWS user; I just looked at the messaging layer based on your vuln report.
I think the lower layer should handle uniqueness, ordering, etc. in addition to integrity protection. As I said in the blog comments, "At some point in the past, I said the following" is not all that is needed for a secure protocol. If ensuring this kind of property is left to the caller, the chance for implementation mistakes would be much higher.
I think the lower layer should handle uniqueness, ordering, etc. in addition to integrity protection. As I said in the blog comments, "At some point in the past, I said the following" is not all that is needed for a secure protocol. If ensuring this kind of property is left to the caller, the chance for implementation mistakes would be much higher.
Idempotence only concerns a single function. There are AWS functions like RunInstances (EC2) that are not principally idempotent. They could drop RunInstances requests with the same timestamp, not sure if they do that. In any case, it is worth noting that requests have a timestamp that expires after 5 minutes.
Yes, and the whole fact that something this important is being left up to the user is my point.
If you look through my comments, I've already started hedging my bcrypt recommendation with scrypt. Note that I've always been a little uncomfortable being "the bcrypt Nazi"; bcrypt isn't really the point, adaptive hashing is.
We hear so often about people getting crypto wrong. (Most often in the context of otherwise knowledgeable and talented programmers applying accepted crypto tools or primitives incorrectly.) Maybe this is one of those areas where some sort of training and certification could be substantive, meaningful, and actually benefit the world?
> where some sort of training and certification could be substantive, meaningful, and actually benefit the world
The problem is, a lot of the recent issues that have been identified have come from people who are probably qualified to write the training courses, and yet they still make mistakes. For example, OpenID still had a hole, even though it's been debated ad nauseum for years on mailing lists around the world by some of the top people in the field. This isn't like building a bridge where you just follow some well understood design principles and the bridge doesn't fall down. We probably just have to admit that this problem is hard (really hard) and there's no amount of rote learning, training or certification that prepares you for the inventiveness and creativity of the people who want to hack your system. The best solution seems to be complete transparency, eternal vigilance, maximum communication and shared experience.
edit: I'm not saying training isn't important for anyone doing this stuff - just that making it mandatory probably won't change much over what we have now.
The problem is, a lot of the recent issues that have been identified have come from people who are probably qualified to write the training courses, and yet they still make mistakes. For example, OpenID still had a hole, even though it's been debated ad nauseum for years on mailing lists around the world by some of the top people in the field. This isn't like building a bridge where you just follow some well understood design principles and the bridge doesn't fall down. We probably just have to admit that this problem is hard (really hard) and there's no amount of rote learning, training or certification that prepares you for the inventiveness and creativity of the people who want to hack your system. The best solution seems to be complete transparency, eternal vigilance, maximum communication and shared experience.
edit: I'm not saying training isn't important for anyone doing this stuff - just that making it mandatory probably won't change much over what we have now.
These things are very difficult to get right, and very hard to check. Sadly the protocol model checking work of people like John Mitchell at Stanford is not close to being a plug in tool implementors can use.
I had the (mis)fortune of having to implement something similar and it took me quite awhile to make sure it was correct in both design and implementation. Do you want to run cryptographic tests for randomness? Do you know how? If not, stay away.
I really agree with tptacek, avoid implementing crypto like the plague.
I had the (mis)fortune of having to implement something similar and it took me quite awhile to make sure it was correct in both design and implementation. Do you want to run cryptographic tests for randomness? Do you know how? If not, stay away.
I really agree with tptacek, avoid implementing crypto like the plague.
I'm really fascinated by all the crypto debate that's been going on lately, but I'm completely green when it comes to cryptography. If Applied Cryptography and Coding Horror aren't enough, where can I go to learn about this? I see a lot of conjecture about how "no one knows how to do crypto right" (except the fellow writing the comment, of course), so I'm interested to know: Where's the right info at? I'd love to learn about this subject.
No. Schneier knows his crypto, of course. His blog, however, is much more about security in the broad sense than crypto.
Becoming a cryptography expert these days is not easy, there is much to learn.
Becoming a cryptography expert these days is not easy, there is much to learn.
If I come to a point where I need to implement cryptography in some form, what should I do? I certainly don't have the money to hire someone who knows what they're doing. It seems strange that skills in other aspects of development (protection from sql injection, UI design, etc.) can be cultivated in the wild with so much greater consistency than cryptography skills.
I'll be giving a talk at Yahoo Security Week in June entitled "When Crypto Attacks!" I hope to post slides afterward.
If you find yourself needing to implement crypto, it's likely you can avoid it by thinking about the situation differently. For example, many web developers get seduced into designing their own crypto as a way to push state to the client instead of managing it on the server. This opens up a much wider attack surface on the server application since now every part of that blob needs to be considered malicious. As the saying goes, "... now you have two problems."
The reason all this is so hard is that crypto is fundamentally unsafe. People hear that crypto is strong and confuse that with safe. Crypto can indeed be very strong but is extremely unsafe.
Have you ever tried to clean up from a root private key compromise? I wrote previously (http://rdist.root.org/2009/05/17/the-debian-pgp-disaster-tha...) about how a one-line change in the PRNG had compromised every DSA private key used on Debian/Ubuntu. Not generated, used. The properties of DSA make it such that your private key is directly revealed to any attacker who knows some bits of your PRNG output. I hope that emphasizes how dangerous crypto is, because it is so sensitive to its prerequisites.
If you find yourself needing to implement crypto, it's likely you can avoid it by thinking about the situation differently. For example, many web developers get seduced into designing their own crypto as a way to push state to the client instead of managing it on the server. This opens up a much wider attack surface on the server application since now every part of that blob needs to be considered malicious. As the saying goes, "... now you have two problems."
The reason all this is so hard is that crypto is fundamentally unsafe. People hear that crypto is strong and confuse that with safe. Crypto can indeed be very strong but is extremely unsafe.
Have you ever tried to clean up from a root private key compromise? I wrote previously (http://rdist.root.org/2009/05/17/the-debian-pgp-disaster-tha...) about how a one-line change in the PRNG had compromised every DSA private key used on Debian/Ubuntu. Not generated, used. The properties of DSA make it such that your private key is directly revealed to any attacker who knows some bits of your PRNG output. I hope that emphasizes how dangerous crypto is, because it is so sensitive to its prerequisites.
I shouldn't be the one answering your question. It's a tough one. If the stakes are low and you can follow standard practices and get somebody who knows what he is doing to just check your work, you might get away with it. If the stakes are high, hire a professional. I wish I knew why it is so hard.
Sorry, just picked the first Scheier link I saw in my history. This one is more relevant: http://www.schneier.com/cryptography.html
I'm amazed Amazon did this. Even casually reading the spec, this jumped out as a red flag. Another example of Rule 5, I guess:
http://cr.yp.to/qmail/guarantee.html
http://cr.yp.to/qmail/guarantee.html
Huh. This is a pretty straightforward vulnerability. The fact that it took anyone this look long to notice makes me skeptical that it's really this simple. I'll make a note to toy with this and see if it's actually exploitable.
No assertion is really being made that it's exploitable now.
Crypto, in general, is really hard to get right.
With 'normal' code, if it's broken, something doesn't work, and you know to fix it. With crypto, if it's 'broken', all the valid requests still work, and you don't know that anything's wrong.
In fact, as far as I know, the only way to know if your crypto code is 'working', is to prove it ... in the form of, if you can somehow break my crypto, you will also be able to break problem X, where X is a problem the crypto community has generally accepted to be hard to solve.
With 'normal' code, if it's broken, something doesn't work, and you know to fix it. With crypto, if it's 'broken', all the valid requests still work, and you don't know that anything's wrong.
In fact, as far as I know, the only way to know if your crypto code is 'working', is to prove it ... in the form of, if you can somehow break my crypto, you will also be able to break problem X, where X is a problem the crypto community has generally accepted to be hard to solve.