Signal - Homework

Please answer the following questions in no more than a few sentences each. We don't expect formal proofs; rather, just a high-level argument from intuition. Please submit your answers as a PDF to Gradescope.

Encryption Schemes

Recall the RSA and ElGamal encryption schemes from class. Recall also the definition of chosen plaintext attack (CPA) security. In short, an encryption scheme is CPA-secure if for any polynomial-time adversary \(\mathcal{A}\) who can query for encryptions of arbitrary messages, \(\mathcal{A}\) cannot distinguish between an encryption of \(m_0\) and an encryption of \(m_1\). All the messages and \(m_0, m_1\) are chosen by \(\mathcal{A}\).

  1. Why isn't RSA encryption CPA-secure?
  2. What should we pay attention to, regarding the plaintext, when we use RSA encryption in practice? Why?
  3. Why is ElGamal encryption CPA-secure?
  4. Given that public-key encryption can be used to construct a symmetric-key encryption, why do we ever want to use symmetric-key encryption over public key encryption, in practice?

Authenticated Encryption

Recall the definition of chosen message attack (CMA) security for a MAC scheme. In short, a MAC scheme is CMA-secure if for any polynomial-time adversary \(\mathcal{A}\) who can query for tags of arbitrary messages, \(\mathcal{A}\) cannot generate a new valid message-tag pair \((m,t)\) where \(m\) hasn't been queried before.

Given a CPA-secure symmetric-key encryption scheme \(\Pi_1=(\mathsf{Gen}_1,\mathsf{Enc}_1, \mathsf{Dec}_1)\) and a CMA-secure MAC scheme \(\Pi_2 = (\mathsf{Gen}_2,\mathsf{Mac}_2,\mathsf{Vrfy}_2)\), we construct an authenticated encryption scheme \(\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})\).

  1. What is Encrypt-and-MAC and why is it not necessarily secure?
  2. What is Encrypt-then-MAC and why is it both CPA-secure and unforgeable?

Man-in-the-Middle (MitM) Attack

In the Signal project, our protocol so far ensures that two parties can establish shared secrets, but it does not ensure that they know exactly who they are talking to. Indeed, an adversary could pretend to be who they are talking to. Describe a man-in-the-middle attack that compromises the security of our application.

Replay Attack

In the Signal project, our protocol is not entirely secure against replay attacks. In particular, once a secure channel is established, the same encrypted messages could be sent multiple times (before the parties switch to a new key). Consider an application that upon receiving a suitable message, will send a dollar to charity.

  1. Describe a replay attack that exploits this system.
  2. Propose a mechanism for protecting against this attack.

(Bonus) Chained CBC

Describe a concrete chosen plaintext attack against block cipher chained CBC mode. In your attack, the two challenge messages (\(M_0, M_1\)) should be of equal length, namely, the adversary should not differentiate the two possible ciphertexts purely based on the length.

(Bonus) Diffie-Hellman Ratchet

An alternative version of the Diffie-Hellman ratchet it to send a new public value for every message sent, regardless of whether or not the flow of communication changed. In what situations does this change help? In what situations does it do nothing? Your answer should be phrased in terms of what information an attacker has managed to obtain.