HMAC SHA256 hash computation in C#

Question

I need to calculate the HMAC by using the SHA256 hash function. I have a secret key encoded in base64 format. Also there is an online tool that correctly calculate the HMAC (verified). http://www.freeformatter.com/hmac-generator.html I wrote the following code snippet:

var signatureHashHexExpected = "559bd871bfd21ab76ad44513ed5d65774f9954d3232ab68dab1806163f806447";
var signature = "123456:some-string:2016-04-12T12:44:16Z";
var key = "AgQGCAoMDhASFAIEBggKDA4QEhQCBAYICgwOEBIUAgQ=";

var shaKeyBytes = Convert.FromBase64String(key);
using (var shaAlgorithm = new System.Security.Cryptography.HMACSHA256(shaKeyBytes))
{
    var signatureBytes = System.Text.Encoding.UTF8.GetBytes(signature);
    var signatureHashBytes = shaAlgorithm.ComputeHash(signatureBytes);
    var signatureHashHex = string.Concat(Array.ConvertAll(signatureHashBytes, b => b.ToString("X2"))).ToLower();

    System.Diagnostics.Debug.Assert(signatureHashHex == signatureHashHexExpected);
}

PROBLEM: My code does not generate the correct HMAC. I verified different steps by using different online tools and alternative C# implementations. Only the conversion from base64 is not confirmed. What am i missing?

UPDATE: Calculated signatureHashHex by my code is "a40e0477a02de1d134a5c55e4befa55d6fca8e29e0aa0a0d8acf7a4370208efc"

ANSWER: The issue was caused by a misleading documentation stating the key is provided in Base64 format. See the accepted answer:

var shaKeyBytes = System.Text.Encoding.UTF8.GetBytes(key);

Answer 1

Your result is correct, the difference is because the tool you link to does not decode Base64 for the key value and treats it as a series of characters.

E.g. To duplicate its result treat your key as a string:

var shaKeyBytes = System.Text.Encoding.UTF8.GetBytes("AgQGCAoMDhASFAIEBggKDA4QEhQCBAYICgwOEBIUAgQ=");

Which yields

559bd871bfd21ab76ad44513ed5d65774f9954d3232ab68dab1806163f806447

(This is obviously not the right way to do it)