Impossible authentication situation? Hint for algorithm needed

Question

This is the situation:

Server nor client can be trusted (both run on users' pc's). Trusted users have a secret key on their computer, along with the client. The goal of the algorithm is to authenticate trusted users as trusted on the server without exposing the secret key to the server.

Technical difficulties:

The language we use (Game Maker) isn't that fast nor precise. We have an implementation of MD5 hashing ready, but me nor the team is capable of/has the time for implementing incredibly hard crypto algorithms.

Answer 1

You might be able to produce one secret per server using only MD5. I'm not sure this is correct, so don't take my word for it.

Each server has a unique ID, which can be public, and also a local secret equal to MD5(trusted secret + unique ID) or similar. You'll have to get the local secret onto the server by some external secure channel, but for example if it's downloaded from a single company site by HTTPS along with the server code, and if you ensure that you never send out the local secret for a given unique ID more than once, then I think that's OK.

The server can then send its ID to the client along with the server ID. A trusted client can generate MD5(trusted secret + unique ID) for itself, but an untrusted client can't generate it. That gives the server and the trusted client a shared secret, which can be used to authenticate using (for example) HMAC-MD5.

If a local secret leaks, then it only gives untrusted clients the ability to fool that leaky server, not other servers.

Obviously this has weaknesses - for example a MITM between a server and a trusted client can provide the correct response to any challenge the server makes, without knowing any secrets. But it doesn't expose the client's secret to the server, and it doesn't expose the server's secret to the client, so it's somewhat better than nothing.

It also has cryptographic weaknesses - MD5 is somewhat broken. If I'm a server and I can find x such that MD5(x + my_id) == my_secret, then chances are x is the secret key. I don't know how computationally feasible it is to find x given one or more local secrets: that depends on the current degree of broken-ness of MD5.

I think MITM is absolutely inevitable given your constraints, although I may be wrong. A trusted client has no way to tell one server from another, in particular whether a server is using its proper unique ID, and therefore will always give the correct responses to any challenges that a MITM passes along. However, provided that the messages include some value that the attacker cannot control, such as a server-generated nonce or the date, then simple eavesdropping doesn't lead to replay attacks. I'm not aware of a way to prevent MITM without using asymmetric encryption and a PKI, that is to say different basic crypto building blocks that you don't have the time/capacity to implement in your language.

It's possible to make the system provide for key revocation of a sort. If you set up your company authority to hand out pairs of (random server ID, local secret) on demand, then servers could update their local secret from time to time (and change their ID at the same time). Then you could change the trusted secret, and servers would stop authenticating clients that use the old one, and start authenticating clients that use the new one, as soon as they next get an ID. As stated that's a fairly painful handover, you'd probably want to soften it a bit if you were building in such a scheme.

Answer 2

Expanding on harold's comment, a zero-knowledge proof scheme appropriate for this problem is Feige-Fiat-Shamir. Peggy proves to Victor that she knows the factorization of a large modulus without revealing it to Victor.

This scheme doesn't support revocation, which is a serious problem if you can't trust your "trusted" users not to reveal the secret.