Maintaining message integrity

Question

I have a message that I am passing to myself which will be subject to man-in-the-middle attacks. Because of that, I am concerned about the integrity of the message being maintained between the time I send it, and the time that I receive it back.

It should be assumed that once I send the message to myself, no information about the message sent will be available to me in the future. The message is completely self-contained.

To that end, I know that should hash the message contents and compare the hashes before I send the message, and after I send the message, if they differ, then the message has been tampered with.

Of course, if the man-in-the-middle knows that the hash is really just the hash of the message contents, as-is, then because the message is self-contained, he can just create new contents and apply the same hash algorithm to the contents.

The question is, to what lengths should I go to randomize the message contents when generating the hash? When does it reach the point of diminishing returns?

In this scenario, I have a set of key/value pairs. To that end, the steps that I know I HAVE to take are:

1. Add a salt to the message. The salt is a secret to the rest of the world. It gets attached to the contents of the message before hashing.
2. Order the key/value pairs in a consistent manner before generating the hash.
3. While not directly relevant, a timestamp is going to be added to the contents of each message before hashing, to prevent replay attacks.

These are the optional steps that I am considering:

1. Transforming the keys before I order them. I've considered reversing them, then ordering by count/key.
2. Playing with the separators that separate key/value pairs (both for the separator for the key/value and the separator for the pair).

NOTE

Message privacy is not a requirement here, so I am not looking for encryption. The values must be transmitted in plain-text.

Finally, what hashing algorithms should I avoid?

---

Specifics

I have an ASP.NET MVC site which I have a controller which handles input validation and persistence.

If (based on a heuristic, it's not important which) the input is determined to be an automated spam attempt, a model of IDictionary<string, string> is created with the input values and a ViewResult is sent to a general CAPTCHA page.

In that view, in the form that contains the CAPTCHA control, the contents of the IDictionary<string, string> will be written out in hidden input fields, and the action of the form will be the same action that the contents were originally posted to. This way, MVC can pick up the values when the form is resubmitted.

It's because of this I can't encrypt the key/value pairs (or maybe I can and should, tell me why and how!).

Of course, I need to add one more value, which contains the hashed message contents. If that value is there, then the controller will check to see that the message integrity is maintained, and allow the input to be persisted if it has.

Solution

I've opted to go with the SignedCms class in the System.Security.Cyrptography.Pkcs namespace, which represents the signging and verifying of CMS/PKCS #7 messages.

To elaborate, I've created a self-issued certificate with MAKECERT.EXE and then in my code, I use the example here to digitally sign the data:

http://blogs.msdn.com/shawnfa/archive/2006/02/27/539990.aspx

Now, it should be a matter of keeping the password on the exported private key secure, as well as security on the server, which makes it less about programming.

I'll have to add an extra key for the timestamp for replay attacks, but that won't be too hard.

The answer goes to Kalium, not for his initial post, but for his follow up comments which pointed the way to digital signatures, and eventually my discovery of how to utilize them in .NET.

Thanks to everyone who contributed.

Answer 1

I think PGP/GPG is what you want here.

Answer 2

You want a Digitally Signed message. Using GPG you can sign the message without encrypting it. But no one will be able to tamper with it, because they can't generate the hash - only you can because the hash uses your private key.

Answer 3

You should probably digitally sign the message (hence PGP/GPG recommended by Kalium is relevant as an option). Any pure hash that you can create can be recreated by the attacker. Digital signing - using your private signing key so that your public key can be used to verify it - is the solution. Anything else is an exercise in futility.

Answer 4

Assuming that you can't pass any information over a "secure" channel (i.e. the hash) here's how you would do it:

1. Hash the message, then sign the hash with a private key. Include the signed hash in the message.
2. When you get the message, use the public key to decrypt the signed hash and verify that it matches the actual hash of the message.

An attacker would not be able to "fake" a message, since they would need to have your private key in order to encrypt their new hash.

As others have mentioned, this is just plain vanilla digital signing and can be handled by something like PGP/GPG

Answer 5

The most straight forward approach to allow your application to verify that its own messages have not been tampered with would be to use a keyed hash message authentication code. The message is sent in the clear, but it also includes a hash to prevent tampering. The hash depends on both the message contents and a secret key. The man in the middle can't forge a hash on an altered message without knowing the key. Since your application both creates and verifies the messages, it never needs to disclose the secret key.

I would particularly recommend the implementation described in RFC-2104 http://www.ietf.org/rfc/rfc2104.txt as it has been carefully thought through to avoid most of the likely pitfalls.

If the messages must also be verified for authenticity by untrusted parties, then you should use a digital signature scheme instead.

There is likely some support for both in the .Net libraries. Miles helpfully provided (as a comment) a link to the MSDN web page for the .Net library functions implementing a keyed HMACs using the SHA1 hash: http://msdn.microsoft.com/en-us/library/system.security.cryptography.hmacsha1.aspx.