Chapter 7 - MACs and Signatures

Question 1

What is the problem with message Digest & how to provide authentication and integrity with Mac and Signatures?

Answer 1

• Message digests provide (some degree of) integrity
  
  • Problem: attacker replaces the plaintext and the digest
• To provide authentication and integrity:
  
  • MAC: digest + secret key cryptography
  • Signature: digest + public key cryptography

Question 2

What is MAC & Draw a digram to depict it?

Answer 2

• Message Authentication Code (MAC)
• A MAC is a keyed message digest
  
  • Takes an arbitrary amount of input data AND a secret key to create a short digest
  • Sender sends both plaintext and MAC. Receiver computes his own MAC to see if they match

Question 3

What Do MACs Provide (CIA)?

Answer 3

• Confidentiality: No
  
  • Plaintext is sent
• Integrity
  
  • An attacker without the secret key cannot create a matching digest for the tampered message
• Authentication
  
  • Any other person does not have the correct key to create a matching digest
• Common MAC algorithm: HmacSHA1

Question 4

How can we provide Authentication & Draw the digram to depict?

Answer 4

• We can reverse the use of keys in public key cryptography to provide authentication!
  
  • Since the sender’s public key can decrypt correctly, the message must be encrypted using the sender’s private key
  • Since only the sender has her own private key, this authenticates her
  • Have integrity or confidentiality?
  • Disadvantage: long encryption time

Question 5

What is a Signature & Draw the digram to depict?

Answer 5

Signature: a message digest encrypted with the sender’s private key

Question 6

What Do Signatures Provide (CIA)?

Answer 6

• Confidentiality: No
  
  • Plaintext is sent
• Integrity
  
  • Attacker cannot produce matching digest of tampered message without correct encryption key
• Authentication
  
  • Any other person does not have the correct key to create a matching digest
• Common signature algorithm: DSA

Question 7

What Are Two Uses of Public Key Cryptography?

Answer 7

Question 8

Describe the Attack on Signatures?

Answer 8

• How to “forge” a signature?
  
  • Different message but same digest?
• Attack:
  
  • Alice has a message M with digest D
  • Suppose there is a different message M’ with a digest D’ such that D = D’
  • Alice generates the signature
  • Attacker replaces M with M’, keeps same signature
  • Bob will believe Alice signs M’
• Level of effort:
  
  • If the digest has n bits, then on average, it needs ~2n messages to generate such a match

Question 9

Describe the Birthday Attack On Signatures?

Answer 9

• Consider the following scenario:
  
  • Trudy generates 2n/2 variations M1 , M2 , … of a message M, all with essentially the same meaning
  • Trudy generates another 2n/2 variations N1 , N2 , … of a different message N
  • It is likely that D(Mi) = D(Nj) for some i and j (probability > 0.5)
  • Trudy gives Mi to Alice to sign
  • Trudy gives Alice’s signature and Nj to Bob
  • Bob believes Alice signed Nj
• Level of effort: ~2n/2, much smaller than before
• (1 second vs. billions of years, for n = 128)