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?

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.

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.