Practical quantum attacks on SHA256 MAC and HMAC Is SHA256 MAC (or HMAC) vulnerable to any quantum attacks?  

Game setup:

The attacker's goal is to produce a valid MAC to be accepted by other devices in the ecosystem.  The ecosystem consists of many devices with a shared secret key (named "key).  The attacker can query an oracle with messages and get MACs.  The oracle only accepts 32 byte messages.  Oracle queries are rate limited to 10ms.  Can the attacker find "key" so that he can produce valid MACs faster than any classical attack.

MAC = H(message[32] | key[32])
There are two points. First the MAC you are using is not HMAC and the way you construct it (first message than key as input without any padding) is only ok if you assume that a) the SHA2 compression function is a random oracle and that b) verifiers check that messages are no longer than 32 bytes. Otherwise one can forge messages at the cost of an intermediate inner state collision without learning key. Hence, it might be a safer choice to put key first, an even safer choice to additionally pad key to the block length (64 byte), and the safest choice to use HMAC from the start.

Second, quantum attacks: Of course you can run grover against this: Just collect, say three (message, tag)-pairs and build an oracle out of it that for a key $k$ outputs 1 if it maps all three messages to the respective tags. This function is a boolean function as needed by Grover. Hence, you can break this in $\mathcal{O}(2^{128})$ queries to SHA2. How long this actually takes is a different story and depends on the size of the quantum circuit to implement the boolean function. 

Note that the rate limitation does not help in any way here as we only need sufficiently many pairs that there exists only one solution $k$ with sufficiently high probability.    



Add-on:
What is the probability that a key that works for two message tag pairs works for a third?

If we model $SHA2-256(m \| k) = t$ as a random function and assume we obtained pairs $(m_1,t_1), (m_2,t_2)$ which were computed using some key $k$ then the probability that a given key $k' \neq k$ maps $m_1$ to $t_1$ is $2^{-256}$. The probability that $k'$ maps $m_1$ to $t_1$ AND $m_2$ to $t_2$ is $2^{-(2*256)}$ and so on. (Here the 256 comes from the output length). 

The probability that $k'$ does not map $m_1$ to $t_1$ AND $m_2$ to $t_2$ is
$(1-2^{-(2*256)})$. The probability that all possible $2^{256}-1$ keys $k'\neq k$ do not map $m_1$ to $t_1$ AND $m_2$ to $t_2$ is
$(1-2^{-(2*256)})^{2^{256}-1}$ (here the outer 256 exponent comes from the size of the key space). So, the probability that there exists a key $k'$ that maps $m_1$ to $t_1$ AND $m_2$ to $t_2$ is
$$1-(1-2^{-(2\cdot 256)})^{2^{256}-1} \approx \frac{2^{256}-1}{2^{2\cdot 256}}\approx 2^{-256}.$$