> Given that this issue has affected a lot of security-sensitive third-party code (keyczar, openid providers, almost every python web service that implements "secure cookies" [1] or other HMAC-based REST API signatures), I do like the idea of adding a warning in the relevant documentation as sbt proposed.

This does sound reasonable, along with the addition of a comparison
function immune to timing attacks to the hmac module (as noted, it's
not specific to hmac, but it looks like a resonable place to add it).
Would you like to submit a patch (new comparison function with
documentation and test)?