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.
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.
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?