GATE CS 2017 Set 1 Q15 — Data Link Layer: Framing, Error Detection, MAC, Ethernet Bridging

To understand which security violations are possible via a birthday attack, let us analyze how digital signatures and hash collisions work.

1. Digital Signature Mechanism

When sender $S$ digitally signs a message $m$:

1. $S$ computes the hash of the message: $h = H(m)$.
2. $S$ encrypts the hash with their private key: $\text{Signature} = E_{S_{\text{priv}}}(h)$.
3. The receiver $R$ decrypts the signature using $S$'s public key to retrieve $h$, and verifies if $H(m) = h$.

2. Birthday Attack vs. Second Pre-image Attack

• Birthday Attack (Collision Resistance Violation): The attacker has the freedom to choose/generate both messages $m_1$ and $m_2$ to find a pair such that $H(m_1) = H(m_2)$. The complexity of finding such a collision is $O(2^{n/2})$, where $n$ is the hash size.
• Second Pre-image Attack: The message $m_1$ (and thus its hash $H(m_1)$) is already fixed. The attacker must find a different message $m_2$ such that $H(m_2) = H(m_1)$. The complexity for this is $O(2^n)$, which is computationally infeasible and cannot be solved using a birthday attack.

3. Evaluating the Statements

• Statement I (Sender $S$): Since $S$ is the creator of the message, $S$ can offline generate a pair of messages—a legitimate message $m$ and a fraudulent message $m'$—such that $H(m) = H(m')$ using a birthday attack. $S$ signs $m$ and sends it to $R$. Later, $S$ can claim they actually signed and sent $m'$ (repudiation). Thus, I is a possible security violation.
• Statements II and III (Third-party $A$ or Receiver $R$): Once $S$ has signed and sent the message $m$, the target hash $H(m)$ is fixed. For $A$ or $R$ to replace $m$ with a fraudulent message $m'$ that has the same signature, they must find $m'$ such that $H(m') = H(m)$ for the fixed $H(m)$. This requires a second pre-image attack, not a birthday attack. Thus, II and III are not possible via a birthday attack.

Hence, only statement I is a possible security violation.