You are correct in questioning the security of this setup. As far as I can see, you have the classic shared secret (key distribution) problem.
The id and message are sent out as plain text while the md5 hash is based on that plaintext plus other values known only to the client and server.
Imagine the following scenario:
- Attacker is capturing packets (tcpdump, ettercap, wireshark etc).
- Attacker grabs the shared secret over the wire.
- Client sends a request to the server.
- Attacker obtains the client's id.
- The attacker can now create valid commands - md5(id+message+secret)
- The system is compromised.
Script kiddies will probably be stumped by the existing system. A competent attacker will break it in no time flat.
Judging by the sample URL you posted, all this is going over http as GET requests. My first suggestion is to get SSL running*.
That will make sniffing packets more difficult (attacker will need a man-in-the-middle attack).
To provide any kind of security, the cypher text must be generated using a key known only to the client and server (and which is never revealed). This is the key distribution problem.
The best solution is, as you mentioned, public key crypto.**
MD5 has lost favour as a hash/digest recently too (see below). SHA is preferred although not perfect either.
PHP supports SHA256 via the hash() function:
$cypherText = hash("sha256", $plainText);
As aalexaa suggested above, the proper use of a good salt will drastically reduce collisions (the basis for rainbow table attacks). The method aalexaa gave above is actually how vBulletin (forum engine this site runs on) deals with passwords:
$enc_pass = md5(md5($password).$salt);
* There can be problems with SSL too. See MD5 references above.
** I'm more code-monkey than cryptanalyst so take all this with a pinch of salt (bad pun, I know...)