Is it possible to brute force a single smaller variable in $\operatorname{HMAC-SHA512}(k, a\ ||\ b\ ||\ c\ ||\ d)$? Given $c' = \operatorname{HMACSHA512}(k, a\ ||\ b\ ||\ c\ ||\ d)$ and the 32-bit integers $a$, $b$, $c$, and $d$ is it feasible to alter $b$ and produce a valid MAC under the unknown key?

I understand that typically it wouldn't be, but I am mostly wondering if it's possible with 4 small independent inputs being used.

Would it change anything if I could observe many MACs over time with all variables constant except one?
Is is feasible to alter b and produce a valid MAC under the unknown key?


We most certainly hope not.  The fundamental security property of a MAC is that, even if that attacker can get a huge number of valid (Message, MAC) pairs (where he gets to choose the messages), he still is unable to generate a MAC for a message he has not seen.  This fundamental property doesn't change just because the inputs are 'small'.

We believe that HMAC-SHA512 is a secure MAC (assuming an unguessable key); hence we believe that it is secure in your case.