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.