Question

(Authentication with Alice cheating) Let’s assume Trudy is Alice’s little sister. Alice produces the message “Transfer $100,000 from Bob to Trudy’s account” and appends it with a valid signature sign(x) of Bob. She then claims that she received this message from Bob. Can Bob prove that he could not have signed this message?

1. In this problem, we will compare the security services provided by Digital Signatures (DS) and Message Authentication Codes (MAC). We assume that Trudy is able to observe all messages sent from Alice to Bob and vice versa. Trudy has no knowledge of any keys, but the public key in case of DS. State whether and how (i) DS and (ii) MAC protect against each of the following attacks. The signature sign(x) is computed with a DS or a MAC algorithm, respectively.

Answer 1

Well, the principle is simple. You have some data, in this case x. You want to send said data to someone else, but want to make sure that nobody in between intercepted and altered your data. So you sign them with some additional data, auth(x), which is generated with a key and your original data x. The difference between digital signatures and Message Authentication Codes is the mechanic.

Digital Signatures use private and public keys like for example PGP, which means you generate your private key for yourself and a public key that you give out to anyone who's interested. When you send your data, you use your private key to sign the data and anyone with the public key can check whether the received data are authentic. Also, because only you have that private key, you can also determine that the data was send by you because it was signed with your private key.

MACs use a single secret key that is shared between all parties. That key is used to sign data of all parties, so it's a protection from alteration by outsiders, but it doesn't protect from falsification from within.

The advantage of digital signatures is, that you can always connect a message to one party. The disadvantage is, that it's assymmetric cryptography, which is always slow.
The disadvantage of MACs is that you can only verify that a message was sent by anyone with the secret key, but not by whom exactly. The advantage is that it's symmetric cryptography, which is fast.

a) You have your data x and your signature sign(x). Oscar replaces something from the message, but does not alter the signature. When the recipient tries to validate the signature, he'll notice with either method that someone messed with the data (or that it got accidentally corrupted, but that's another story), because the signature, the actual data and the secret key (MAC) / public key (SIG) won't match.

b) Bob does not notice this with either method because the data x isn't changed and does not include an indicator that protects against replay attacks. The following would prevent replay attacks:

Alice has a sequence number of 1234 and Bob knows that this is the next sequence number
Alice sends x = (1234;"Transfer $1000 to Oscar") and sign(x) to Bob
Alice sets her sequence number to 1235
Bob receives Alices request and increments his sequence number to 1235 as well
Oscar, who intercepted a copy of x and sign(x) sends both to Bob, but Bob is expecting a sequence number 1235, so he won't act on 1234 again

c) The explanation is already stated in the answer. (i) is for digital signatures, (ii) for MACs.

d) Same as c. (ii) is a No because Bob has the secret key as well, so within the scenario he could write checks to himself in Alices name, sign them by MAC and claim validity and just from the data you could not tell whether Alice or Bob wrote that.

Hope that helps.