Building a Secure Messenger From Scratch

Throughline

Each layer solves the problem left by the previous one: agree on a secret, turn it into keys, protect ciphertext integrity, then replace compromised keys.

1. Agreeing on a secret

• Introduce a cyclic group $\mathbb G$ of prime order $q$ with generator $g$.
• Keep the hardness hierarchy precise:

$$\text{DDH hard}\Rightarrow\text{CDH hard}\Rightarrow\text{DLOG hard}$$

A discrete-log solver breaks CDH and DDH; the reverse implications are not known in general.

• Walk through Diffie–Hellman:

$$A=g^a,\qquad B=g^b,\qquad B^a=A^b=g^{ab}$$

• Mention ElGamal as Diffie–Hellman turned into public-key encryption.

Reference: Katz–Lindell §9.3; Boneh–Shoup §15.1–15.3

2. Deriving usable keys

• Explain why $g^{ab}$ is not used directly: it has structure, the wrong format, and one key should not serve multiple purposes.
• Use HKDF to extract uniform key material and expand labeled subkeys:

$$k_{\text{enc}}\parallel k_{\text{mac}} =\mathsf{HKDF}(g^{ab},\text{salt},\text{info})$$

• State the rule: separate keys by purpose and direction.

Reference: Boneh–Shoup §8.7.2, §8.10.5

3. Authenticating ciphertexts

Compare the three generic compositions:

• Use padding-oracle attacks as the concrete MAC-then-encrypt failure mode.
• Keep the lesson: secure primitives do not guarantee secure composition.

Reference: Katz–Lindell §5.1–5.3

4. Ratcheting keys

• Ask what happens when today's device state leaks.
• Define:
  • Forward secrecy: current compromise does not expose deleted past keys.
  • Post-compromise security: fresh secret input lets the conversation recover.
• Separate the two ratchets:
  • Symmetric-key ratchet: derive and delete one message key per message.
  • Diffie–Hellman ratchet: mix in a fresh DH secret when the sending direction changes.
• Walk one exchange: Bob sends $g^{b_2}$; both sides mix $g^{a_1b_2}$ into the root chain and delete superseded keys.
• Mention skipped-message keys and bounded out-of-order delivery.

Reference: Signal's Double Ratchet specification

5. Implementation notes

• Use the chained-CBC near-miss to show that passing round-trip tests does not imply a secure construction.
• Record C++ and library friction:
  • nonce and IV ownership
  • byte/string conversions
  • key separation
  • key deletion
  • which mistakes types catch versus which need adversarial tests

Assumptions introduced

• Discrete logarithm, CDH, and DDH hardness in the selected group.
• Secure KDF, encryption, and MAC primitives.

Go deeper

• Katz–Lindell ch. 5 and §9.3
• Boneh–Shoup §9 and §15.1–15.3
• Signal's Double Ratchet specification
• Scribed applied cryptography notes, §3.3–5.3