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