I am your average developer looking for some crypto-related guidance.
I am trying to have assurance that a received message is from a particular sender, but have no need for the message content to be encrypted. The sender and receiver are allowed a one-time secure channel to establish a shared secret. I don't want to use a full-on crypto library for message signing because my target audience for the receivers includes websites running on low-end shared hosting where access to such libraries won't always be available. I'm wondering if only needing message signing and allowing a pre-shared secret sufficiently simplifies the problem to where it can be pulled off safely in my own code.
A method I've seen to do this is to simply append the shared secret to the message, apply a hash function to the message+secret, and send the hash function's output along with the message as its signature. That's fine I think except that it would be subject to replay attacks, which is problematic for my application.
If instead of using a static shared secret I used the one-time secure channel to seed a PRNG on both ends, appended the PRNG's current output to each message as input to the hash function, and advanced the PRNG on both ends following each verified communication, would this potentially be effective? I understand there's also a need to make intelligent choices about the hash function and PRNG used, but first of all does this high-level approach have any fatal flaws I can't appreciate as an average-joe developer?
Since there's been an enthusiastic continued response, let me share a bit more. First, I don't need to be convinced of the benefits of an asymmetric key solution, the problem as I've tried to convey is short of implementing one myself in a scripting language, I simply will not have access to OpenSSL/OpenSSH/GNUPG or anything else capable of using public/private keys on 100% of the systems where this needs to run. I am guaranteed to have SHA-256 and other hashing algorithms and HMAC on 100% of the systems where this needs to run.
The application is as a messaging system between websites running Drupal and another similar content management system and the CMS organization's servers, in order to give the organization a means to push official security updates to sites. Full details: https://github.com/mbaynton/cms-autoupdate-design. FWIW, I do plan to ship the security code changes themselves with an OpenSSL signature, but it will only benefit the sites where the administrators have made OpenSSL available to php. The MAC is basically the fallback so sites without OpenSSL still have some assurance of authenticity of the update package. This in and of itself would substantially diminish the value of the shared secret database were it to be compromised...you'd potentially be able to impact such a minority of sites that you'd almost be wasting your time trying.
Solutions that require a pre-shared key are pretty commonplace for this kind of inter-server web service application, I'll cite http://docs.aws.amazon.com/general/latest/gr/signing_aws_api_requests.html. Doing exactly this might be an even better idea...