What is the best hash for HMAC?
I know SHAKE128 and 256 are part of the SHA-3 standard but is the SHA3 standard officially released yet? i can only find a draft of the publication, does this mean it's not official and therefor not proven to be secure?


No, SHA-3 has not been formally approved.  On the other hand, what do you mean "not proved to be secure"?  Do you really thing that NIST approves only things that are "proven"?  In practice, we have only a handful of things that are "proven" (OTP, secure sharing); while NIST certainly tries to vet what they place on the approved list, they have no proof.

In any case, from your questions, it appears that you are interested in speed.  Now, SHA-3 is actually slower in software than SHA-2 (what SHA-3 excells at is if you can implement it with hardware gates); hence it would appear to be the wrong direction for you.


  What is the best hash to use, obviously it needs to be relatively fast and by my standards sha-512 isn't fast


Well, before I get into that, I would like to point out that your HMAC implementation can likely be improved.

In HMAC, as you know, we use the key to generate an IPAD and an OPAD; we then compute $a = Hash(IPAD | Message)$, and then compute $b = Hash(OPAD | a)$, and $b$ is the result of the HMAC.

Now, IPAD and OPAD are sized to be precisely 1 Merkle-Damgaard block of the hash function; hence one thing you can do is you can compute the initial hash compression function evaluation $Compress(IV, IPAD)$ and store that intermediate state; similarly, you can compute the initial hash compression function evaluation $Compress(IV, OPAD)$ and store that.

Then, to compute $a = Hash(IPAD | Message)$, you can restore the initiate state for that, and just compute the hash over the message (just using the precomputed evaluation as the IV, and adjusting the final padding to account for the longer message); similarly, you can use the same trick when computing $Hash(OPAD | a)$.

This allows you to compute HMAC using two fewer hash compression operations over the naive method.  Now, if you are computing the HMAC only once for a key, or if you are computing HMAC over a huge message, this doesn't help much.  However, if you are computing HMACs over a number of tiny messages, this helps a lot.

I suspect you aren't using this optimization, because if you were, the time differential between 64 bytes messages and 128 byte messages would be considerably larger.

Implementing this may have the time taken to HMAC a 64 byte message on SHA256 by 40% (3 hash compression operations rather than 5).

Now, as for the "best hash"; well, if you want to stick with NIST approved operations, the fastest alternative is HMAC-SHA1 (which is FIPS approved still); if you don't care for that, well, the best you have is HMAC-SHA256.