How can Alice prove that a message has not been tampered with?

Question

In terms of the usual suspects.

The problem I have is that Alice wants to send Bob a message M, which gives Bob permission to perform some actions. However Alice wants to verify, from time to time, that the Bob has not changed the message in anyway, allowing himself more privileges than Alice originally intended, without having Bob send the message M back to Alice.

Obviously Alice cannot keep asking the same question as Bob could successfully answer once, change the message, and repeat the first answer every time.

Other contributing facts, Alice obviously knows the message M that was sent, and knows that she was talking to Bob, and can trust that the messages and responses are not modified in transit

Answer 1

I think what you are looking for is something called "Proof of Data Possession" where Alice keeps a low amount of data related to a file M, sends M to an untrsuted storage facility and then can with low communication cost convince herself than M hasn't been modified

Here are some links

http://home.ku.edu.tr/~akupcu/papers/dpdp.pdf

http://eprint.iacr.org/2008/114.pdf

I haven't had time to read through them carefully myself, but I quite confident that y

Answer 2

There are two parts here, and not just one message to Bob. Alice's authorization should be viewed as a packet within a packet. This is often referred to as a token. The message from Alice to Bob may be email, but the token is a cryptographic value. Bob can't decrypt the token and play with it, because Bob doesn't have the keys needed.

The permissions Alice is granting are not intended to go to Bob as the final recipient. She isn't telling Bob "you have read access to the database." She is telling an authorizing system "Alice is granting Bob read access to the database." So Alice needs to securely communicate her intent to the authorizing service. In your scenario you describe Bob as seeking Alice's approval, and she replies to him with a message. But Bob is responsible only for receiving the token from Alice and delivering the token to someone else. He might forward it on to the authorizing system, or he might pass it along to the database (who would pass it to the authorizer.)

Think of Bob not as the recipient of the token, but as Eve (the eavesdropper) or Mallory (the malicious attacker) standing between Alice and the authorization system. The token has to be secured against Bob's tampering. When done right, it doesn't matter if those messages are seen by Bob as they flow through his hands.

See Kerberos for an example of a security system that behaves as you describe.