End-to-end encryption concept in HLD - System Design Exercise

Design: End-to-End Encryption Messaging System

Design focuses on encryption architecture, key management, message flow, and storage. UI/UX and network transport protocols are out of scope.

Functional Requirements

FR1: Messages must be encrypted on the sender's device and decrypted only on the receiver's device.

FR2: No intermediate server or third party can read the message content.

FR3: Support secure key exchange between users.

FR4: Allow sending text messages and attachments securely.

FR5: Ensure message integrity and authenticity.

FR6: Support offline message delivery with encrypted storage on server.

FR7: Handle multiple users and group chats securely.

Non-Functional Requirements

NFR1: System should support 1 million daily active users.

NFR2: Message delivery latency p99 should be under 500ms.

NFR3: Availability target is 99.9% uptime.

NFR4: Encryption and decryption must happen on client devices only.

NFR5: Server must not store any plaintext messages or encryption keys.

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

Client encryption module

Key exchange service

Message relay server

Encrypted message storage

User identity and authentication service

Push notification service

Design Patterns

Public key cryptography for key exchange

Symmetric encryption for message content

Double ratchet algorithm for forward secrecy

Digital signatures for message authenticity

End-to-end encrypted group messaging protocols

Reference Architecture

  +-------------+       +----------------+       +-------------+
  |  Sender's   | <---> | Message Relay  | <---> | Receiver's  |
  |  Device     |       | Server         |       | Device      |
  +-------------+       +----------------+       +-------------+
        |                      |                       |
        | Encrypt message      |                       |
        | with receiver's      |                       |
        | public key           |                       |
        |--------------------->|                       |
        |                      | Store encrypted       |
        |                      | message if receiver   |
        |                      | offline               |
        |                      |----------------------->|
        |                      |                       | Decrypt message
        |                      |                       | with private key
        |                      |                       |
  +----------------+       +----------------+       +----------------+
  | Key Exchange   |       | Encrypted Msg  |       | Decryption &   |
  | Service        |       | Storage        |       | Verification   |
  +----------------+       +----------------+       +----------------+

Components

Client Encryption Module

Implemented in client apps (mobile, desktop)

Encrypts outgoing messages and decrypts incoming messages using user's private keys

Key Exchange Service

Public key infrastructure (PKI) with secure key distribution

Facilitates secure exchange of public keys and session keys between users

Message Relay Server

Stateless message broker with encrypted message storage

Relays encrypted messages between users and stores messages temporarily if receiver is offline

Encrypted Message Storage

Encrypted database or object storage

Stores encrypted messages without access to plaintext or keys

User Identity and Authentication Service

OAuth 2.0 or similar authentication system

Authenticates users and manages user identities securely

Push Notification Service

Platform-specific push services (APNs, FCM)

Notifies users of new messages without revealing message content

Request Flow

1. 1. Sender's device generates a session key for symmetric encryption.

2. 2. Sender encrypts the message content with the session key.

3. 3. Sender encrypts the session key with receiver's public key.

4. 4. Sender sends the encrypted session key and encrypted message to the Message Relay Server.

5. 5. Message Relay Server stores the encrypted message if receiver is offline or forwards it immediately.

6. 6. Receiver's device receives the encrypted session key and message.

7. 7. Receiver decrypts the session key with their private key.

8. 8. Receiver decrypts the message content with the session key.

9. 9. Receiver verifies message authenticity using digital signatures.

10. 10. For group chats, the process repeats with keys managed per participant using group encryption protocols.

Database Schema

Entities: - User: user_id (PK), public_key, authentication_info - Message: message_id (PK), sender_id (FK), receiver_id (FK), encrypted_session_key, encrypted_content, timestamp, signature - Group: group_id (PK), group_name - GroupMember: group_id (FK), user_id (FK), encrypted_group_key Relationships: - User to Message: 1-to-many (sender and receiver) - Group to GroupMember: 1-to-many - User to GroupMember: many-to-many Notes: - No plaintext message content stored. - Keys stored only in encrypted form or on client devices.

Scaling Discussion

Bottlenecks

Key exchange service can become a bottleneck with many users requesting keys simultaneously.

Message Relay Server may face high load during peak messaging times.

Encrypted message storage can grow rapidly with large user base.

Latency may increase if many users are offline and messages are queued.

Group chat key management complexity grows with group size.

Solutions

Use distributed key exchange servers with caching of public keys to reduce load.

Scale message relay servers horizontally with load balancers.

Implement data retention policies and archiving for encrypted messages.

Use efficient push notification to wake offline users quickly.

Adopt advanced group encryption protocols like Sender Keys to reduce key management overhead.

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing architecture and data flow, 10 minutes discussing scaling and trade-offs, 5 minutes summarizing.

Explain why encryption must happen on client devices only.

Describe how public key cryptography enables secure key exchange.

Discuss how message integrity and authenticity are ensured.

Highlight how offline message delivery is handled securely.

Mention trade-offs between security and usability (e.g., key recovery).

Show awareness of scaling challenges and practical solutions.

Practice

1. What is the main purpose of end-to-end encryption in a messaging system?

easy

A. To speed up message delivery across the network

B. To store messages securely on the server

C. To ensure only the sender and receiver can read the messages

D. To allow the server to read and filter messages

Solution

1. Step 1: Understand the role of end-to-end encryption

   End-to-end encryption means messages are encrypted by the sender and decrypted only by the receiver, preventing others from reading them.

2. Step 2: Identify the main goal in the context of messaging

   The goal is to protect message privacy so that no one else, including servers or network providers, can read the content.

3. Final Answer:

   To ensure only the sender and receiver can read the messages -> Option C

4. Quick Check:

   Privacy between sender and receiver = To ensure only the sender and receiver can read the messages [OK]

Hint: Focus on who can read messages in end-to-end encryption [OK]

Common Mistakes:

• Thinking encryption speeds up delivery
• Assuming servers can read encrypted messages
• Confusing storage security with message privacy

2. Which of the following correctly describes the key usage in end-to-end encryption?

easy

A. Sender uses receiver's public key to encrypt; receiver uses private key to decrypt

B. Sender uses receiver's private key to encrypt; receiver uses public key to decrypt

C. Sender and receiver share the same private key for encryption and decryption

D. Sender uses own private key to encrypt; receiver uses own public key to decrypt

Solution

1. Step 1: Recall public/private key roles in encryption

   The sender encrypts the message using the receiver's public key, which anyone can have, but only the receiver has the private key to decrypt.

2. Step 2: Match the correct key usage pattern

   Sender uses receiver's public key to encrypt; receiver uses private key to decrypt correctly states this: sender uses receiver's public key to encrypt; receiver uses private key to decrypt.

3. Final Answer:

   Sender uses receiver's public key to encrypt; receiver uses private key to decrypt -> Option A

4. Quick Check:

   Public key encrypts, private key decrypts = Sender uses receiver's public key to encrypt; receiver uses private key to decrypt [OK]

Hint: Remember: public key encrypts, private key decrypts [OK]

Common Mistakes:

• Confusing which key is public or private
• Thinking private key is shared
• Mixing sender and receiver key roles

3. Consider a system where Alice sends a message to Bob using end-to-end encryption. Which step correctly describes the message flow?

medium

A. Alice encrypts with her private key -> Server decrypts and re-encrypts -> Bob decrypts with Alice's public key

B. Alice encrypts with Bob's public key -> Server forwards encrypted message -> Bob decrypts with his private key

C. Alice sends plain text -> Server encrypts with Bob's public key -> Bob decrypts with his private key

D. Alice encrypts with Bob's private key -> Server forwards message -> Bob decrypts with his public key

Solution

1. Step 1: Analyze the encryption and forwarding process

   Alice encrypts the message using Bob's public key so only Bob can decrypt it. The server just forwards the encrypted message without decrypting.

2. Step 2: Verify the correct decryption by Bob

   Bob uses his private key to decrypt the message. This matches Alice encrypts with Bob's public key -> Server forwards encrypted message -> Bob decrypts with his private key.

3. Final Answer:

   Alice encrypts with Bob's public key -> Server forwards encrypted message -> Bob decrypts with his private key -> Option B

4. Quick Check:

   Sender encrypts with receiver's public key, receiver decrypts with private key = Alice encrypts with Bob's public key -> Server forwards encrypted message -> Bob decrypts with his private key [OK]

Hint: Remember server only forwards encrypted messages [OK]

Common Mistakes:

• Assuming server decrypts messages
• Using sender's keys for encryption
• Encrypting plain text at server

4. A developer implemented end-to-end encryption but users report messages are readable by the server. What is the most likely mistake?

medium

A. Encrypting messages only on the server before forwarding

B. Using receiver's public key for encryption on the client

C. Decrypting messages only on the receiver's device

D. Using private keys only on the receiver side

Solution

1. Step 1: Identify where encryption should happen in end-to-end encryption

   Encryption must happen on the sender's device before sending, so the server never sees plain text.

2. Step 2: Analyze the reported issue

   If messages are readable by the server, likely encryption is done only on the server, meaning messages travel in plain text from sender to server.

3. Final Answer:

   Encrypting messages only on the server before forwarding -> Option A

4. Quick Check:

   Encryption must be client-side, not server-side = Encrypting messages only on the server before forwarding [OK]

Hint: Encryption must happen before server sees message [OK]

Common Mistakes:

• Encrypting only on server, not client
• Assuming server can decrypt messages
• Misusing keys on wrong devices

5. In designing a secure chat app with end-to-end encryption, which approach best protects user privacy even if the server is compromised?

hard

A. Encrypt messages on server using sender's private key before sending

B. Store all messages encrypted on server; server decrypts before forwarding

C. Use symmetric keys shared via server for encryption and decryption

D. Encrypt messages on sender's device with receiver's public key; server only routes encrypted data

Solution

1. Step 1: Evaluate encryption location and key usage

   Encrypting on sender's device with receiver's public key ensures only receiver can decrypt, keeping server blind to message content.

2. Step 2: Consider server compromise scenario

   If server is compromised, it cannot read messages because it only routes encrypted data without keys.

3. Step 3: Compare other options for privacy risks

   Other approaches expose messages to server or rely on server for key management, risking privacy.

4. Final Answer:

   Encrypt messages on sender's device with receiver's public key; server only routes encrypted data -> Option D

5. Quick Check:

   Client-side encryption with public key = Encrypt messages on sender's device with receiver's public key; server only routes encrypted data [OK]

Hint: Encrypt on sender device; server only routes encrypted data [OK]

Common Mistakes:

• Relying on server to decrypt messages
• Using symmetric keys managed by server
• Encrypting messages on server instead of client