GATE CSE 2017 | Set 1 | Question: 15

Question

A sender $S$ sends a message $m$ to receiver $R$, which is digitally signed by $S$ with its private key. In this scenario, one or more of the following security violations can take place.

1. $S$ can launch a birthday attack to replace $m$ with a fraudulent message
2. $A$ third party attacker can launch a birthday attack to replace $m$ with a fraudulent message
3. $R$ can launch a birthday attack to replace $m$ with a fraudulent message

Which of the following are possible security violations?

• A. I and II only
• B. I only
• C. II only
• D. II and III only

Comments

Is this topic in gate 2021 syllabus ???

---

Out of syllabus

---

Are you sure?

edit- nevermind saw the tag

Answer 1

As per definition it is as

Birthday attack : Sending fraudulent message with the same hash value as of the original message, along with the digital signature of the original message.

Important: Tanenbaum has given $2$ ways of using digital signatures:

1. For Authentication and Secrecy (in this whole message is encrypted first with senders private key then receivers public key)
2. For Authentication only (in this only Message Digest is encrypted with senders private key)

In question it is given that whole message is encrypted so first case applies. Options:

1. $S$ can launch a birthday attack to replace $m$ with a fraudulent message. 
   $S$ can use some other message, encrypt it with its private key then receivers public key, then send. TRUE 
    
2. $A$ third party attacker can launch a birthday attack to replace $m$ with a fraudulent message. 
   third party can not encrypt new message again, as it requires sender's private key. FALSE 
    
3. $R$ can launch a birthday attack to replace $m$ with a fraudulent message.
   Similarly, $R$ will need sender's private key to encrypt. FALSE

Correct Answer: $B$

Comments

I did n't get the purpose , it seems sender is sending a completely new data, is it apt to call it an attack ?

---

But wont the Reciever again convert msg into hash(H) at reciever side and then compare it with decrypted Hash(H')? Wont the fraud msg produce a different hash?

---

You are saying message digest can be extracted which is encrypted. If that is possible then an encrypted message can also be extracted. Which is clearly wrong

Answer 2

Digitally signed by S means....By using S private key .

that means any one can open it .

Birthday attack.......imagined like birthday gift inside wich is a BOMB ;D

SO , I thought....only S can send this Birthday gift others are only able to open the gift ....but only S can pack & wrap it .

SO Option  B is answer (according to me.....I had never heard of B'Day Attack Before)

Answer 3

How the process of encryption and decryption works,

In general if message is encrypted by X's private key then it can be decrypted only be X public key. Similarly

If it is encrypted by X's public key then it can be encrypted by X's private key.

 

Here in question sender sends message signed by S private key so any one can decrypt message using S public key.

If any 3rd party person want to send fraudulent message he has first decrypt message with S public key, do changes in message but once changes have been done it has to encrypt it with his own private key( because only S have its private key no one else)

Now even if the fraudulent message is received by R, S will be not accountable as fraudulent message does not have any signature of S on it.

Thus option II and III is not possible.

Only S himself can launch birthday attack changing content of message and later claming it was not him popular know as repudiation, which is a security violation

Answer 4

Birthday Attack: https://www.math.columbia.edu/~goldfeld/BirthdayAttack.pdf
In Crytography: http://www.facweb.iitkgp.ac.in/~sourav/lecture_note9.pdf

This attack does not need the attacker to have access to the digital signature, hence answers speculating based on access to digital signatures are wrong. The main purpose of the attack is to find a collision!

Quote from lecture notes of IITKGP
 

 Using this idea we can discuss the birthday attack as follows: 

• The source, A is prepared to “sign” a message by appending the appropriate m-bit hash code and encrypting that hash code with A’s private key. 
• The opponent generates $2^{m/2}$ variations on the message, all of which convey essentially the same meaning. The opponent prepares an equal number of messages, all of which are variations of the fraudulent message to be substituted for the real one. 
• The two sets of messages are compared to find a pair of messages that produce the same hash code. The probability of success is greater than 0.5. If no match is found, additional valid and fraudulent messages are generated until a match is made.
• The opponent offers the valid variation to A for signature. This signature can then be attached to the fraudulent variation for transmission to the intended recipient. Because the two variations have the same hash code, they will produce the same signature; the opponent is assured of success even though the encryption key is not known.

---

1. Statement I (S launching a birthday attack):

   • S is the sender and has their private key. S does not need to perform a birthday attack because they can directly sign any message m or m′ without relying on hash collisions.
   • While S could potentially precompute colliding messages to dispute or repudiate m, this does not align with the typical context of a birthday attack. Therefore, Statement I is not a valid security violation.

2. Statement II (Third-party attacker launching a birthday attack):

   • A third party can exploit the vulnerability of a weak hash function to find a colliding message m′ for the same hash as m. If they can replace m with m′, the signature S generated for m will also validate for m′.
   • Statement II is valid.

3. Statement III (R launching a birthday attack):

   • After receiving m, R could compute a colliding message m′ such that the signature for m also validates for m′. R could then falsely claim that S sent m′. This exploits the hash collision vulnerability and is a form of a birthday attack.
   • Statement III is valid because R has the ability to replace m with m′ after receipt and claim it was the original message.

---

• Statement I is invalid.

• Statements II and III are valid.

Option D is correct!

Answer 5

COMMENT BELOW IF YOU HAVE ANY DOUBT