I can't spot any errors apart from that you seem to be mixing up Python 2.x with Python 3.x syntax (the u"" thing belongs to 2.x, all strings are automatically unicode in 3.x). The HMAC and the post data should be all correct. I thought the chr(0) might mess up Python's encode("utf-8") but it didn't.

What are you using to submit your request with? urllib.request.Request? Unlink Python 2.x, the urlopen() in Python 3.x doesn't submit your headers, you'd need to use the Request constructor instead. So if you're copying code from people using Python 2.x, you may end up not submitting your headers at all.