Is using a rolling code as a constantly-changing shared secret effective for signing?

Question

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?

---

Edit

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...

Answer 1

I'm confused at your suggestion that your clients would not have access to a public key signature facility, given that you assume that they have crypto hashes and can run code of your authorship. More generally, the fact that you're trying to roll your own crypto doesn't bode well.

Also, I'd suggest that you have a hard look at the challenges implied by your idea of using a "one-time secure channel" to establish shared keys with your users. What happens, for example, when one of your users tells you that their key has been compromised? Invalidating your own copy of that key is easy, but now you need the (supposedly "one-time") secure channel once more to establish a new one. What's the cost and inconvenience of that?

Or even worse, imagine the case where your database of pre-shared secret keys gets compromised. You then have to establish a new shared key with every single one of your users, all at once. Ouch.

Compare this to, say, the way GitHub uses public-key cryptography to manage access to users' repositories:

1. Users generate private/public key pairs on their own computer.
2. Users log in to the website using conventional user authentication mechanisms (e.g., passwords, security tokens, SMS, etc.)
3. Users can then upload public keys, or delete earlier ones that they'd uploaded.

Notice what you gain in this case:

• "Self-service": users can add and delete keys at their leisure. Now when your users' keys are compromised they just log in to your site, delete the compromised ones and upload new ones.
• No secret keys are ever transmitted over the wire. Which implies that you're never storing any secret keys on your side, so if your public key database is disclosed it's not a big deal.
• You do need a user authentication system, but:
  • That can be outsourced (think of all those websites that allow you to log in with your Google or Facebook credentials);
  • Even if you built one in house, with strong user passwords and proper password storage then a compromise of your password database is would likely be much less damaging than a database of shared secret keys.

---

But to address your narrower questions, I'd make two observations. First, your hash(message + secret) scheme is insecure. Read up on HMAC, which is a standard and secure way of using a hash function as a message authentication code.

Second, you can avoid replay attacks by incorporating a counter into the message that you compute a MAC over. No need for the random numbers; each client just keeps track of the most recent message number they received from the other party, and rejects messages numbered earlier than the most recent one.

A good MAC will be secure against forgeries. An attacker who sees the messages and tags (but not the key) for...

tag[1] = HMAC(key, rand[1] + message[1])
       .
       .
       .
tag[n] = HMAC(key, rand[n] + message[n])

...will not be able to forge a valid

fake_tag = HMAC(key, rand[n+1] + fake_messsage)

even if they can predict rand[n+1]. The unpredictability of the RNG's output gains you nothing. All you need is a way to spot replays—which a counter will do just fine.