Btw; using md5 for the HMAC algorithm would let someone inject data as well, because creating 16 bytes at the end of a packet that achieves the HMAC you want with MD5 is no longer a computationally hard problem

Actually, it still is. Using MD5 with HMAC is at present knowledge absolutely fine from a functional point of view, but it's really not something you would want to do anyway because:

A) it's bad for PR, because by now the only reaction you will get from people is "why are you using MD5, it's broken" even though in this particular instance none of its effective weaknesses matter

B) you can possibly get better performance using a more modern algorithm with less overhead when fingerprinting small messages - such as network packets - repeatedly with the same key (the SHA-3 finalists are pretty good at it since they have built-in HMAC functionality which aims to optimize this kind of processing, but they aren't standardized yet so it's probably best to go with SHA-256 at the moment)

C) eventually it will no longer be secure, as attacks only get better

So to conclude, HMAC does not rely on collision resistance of the underlying hash function, therefore, as paradoxal as it may seem, using it with MD5 is currently "as secure" as using it with SHA-1 from a technical point of view (ignoring the difference in fingerprint length - 128 bits is enough anyway). But that doesn't mean you should do it.

Either way, you need to build a threat model for your application first. Any work done prior to the assessment of what you are trying to protect against is misguided.

There are two main concerns in the model you suggest:

1) How do I prevent users-on-open-WiFi from having their sessions stolen?

2) How do I make sure that a connection that comes back to a different server is in fact the user it claims to be?

Implementing the "authentication-for-games" mechanism (which can be summariezed as "a basic ticket mechanism a la Kerberos") on top of TCP/TLS will work just fine for these vectors.

So, from clients' point of view:

1) connect with TLS, provide name & password; receive ticket with some lifetime

2) each new connection, still use TLS, provide ticket as proof-of-identity-and-authorization

The benefit of using the ticket instead of just keeping name & password around in the client is that:

a) wiping the password in RAM after sending it is somewhat more secure against accidental disclosure on the client machine

b) each server that gets the ticket only needs a copy of the server-side secret, not actually re-do the user database lookups

For long-lived TCP connections, b) isn't as important (but a may still be); for UDP connections, b) is a real win!

I'll have to look at whether borrowing some of that makes sense