Skip to main content

📬 Multiple Envelopes

Out-of-Order Message Handling​

In 15 minutes: Understand how Signal Protocol handles delayed/offline messages
Prerequisites: Forward Secrecy

🎯 The Simple Story​

Alice sends 10 messages. Bob is offline.

Problem: Bob receives messages out of order or in batch!

Solution: Store skipped message keys in a "message keys store".

  1. Alice sends msg 1, 2, 3, ..., 10
  2. Bob receives all at once
  3. Bob needs K1-K10 to decrypt
  4. Bob stores K1-K9 (skipped), processes K10 (current)
  5. Bob can decrypt: msg 1-msg 10!

🧠 Mental Model​

Hold this picture in your head:

Out-of-Order Handling:

Alice sends:
    Msg 1 with K1 → Bob receives later
    Msg 2 with K2 → Bob receives later
    Msg 3 with K3 → Bob receives now
    ...

Bob receives (all at once):
    Msg 1: Needs K1 (deleted? No! Stored!)
    Msg 2: Needs K2 (deleted? No! Stored!)
    Msg 3: Needs K3 (has current K3)

Bob's message keys store:
    K1: Store (skipped msg)
    K2: Store (skipped msg)
    K3: Use current
    K4: Store (skipped msg)
    ...

Bob can decrypt: msg 1, 2, 3, 4, ...

Think of it like:

📬 Multiple envelopes (Keep copies in safe)

🗃️ Cabinet (Store old message keys)

📚 Library (Can check out messages later)

📊 See It Happen​

Handling out-of-order:

🔢 The Math​

Message Keys Store​

# Message keys store (per direction: sending vs receiving)
message_keys = []

# Alice sending chain
for i in 1..10:
    K_i = KDF_C(CK_Ai)
    Encrypt msg_i with K_i

    # Store old message keys for skipped msgs
    message_keys.append(K_i)

# Bob receiving chain
for received_msg in msgs:
    # Which K needed?
    msg_num = received_msg.metadata.number

    # Check store
    if msg_num < current_msg_num:
        # Look up old key
        K_old = message_keys[msg_num]
        Decrypt(msg, K_old)
    else:
        # Missing key (skip for now)
        Keep encrypted msg for later

💡 Why Store Message Keys?​

Without message keys store:

  • Alice sends 10 messages → Bob offline
  • Bob receives all → Needs K1-K10
  • K1-K9 deleted → Can't decrypt msg1-msg9
  • ❌ Bob can't read past messages!

With message keys store:

  • Alice sends 10 messages → Bob offline
  • Bob receives all → Needs K1-K10
  • K1-K9 in message keys store → Decrypt msg1-msg9
  • K10 is current → Decrypt msg10
  • ✅ Bob reads all messages!

✅ Quick Check​

When to store vs delete?

Store for skipped msgs:

If receiving msg N > current msg number: Store K_current.

If receiving msg N < current msg number: Look up in store.

If msg N = current msg number: Delete after use.

How long to store?

Until processed:

Until Bob processes the skipped message.

After processing: Delete K from store.

Trade-off: Storage space vs past message recoverability.

📋 Key Takeaways​

✅ Message keys store: Keep old K_i for skipped messages
✅ Out-of-order: Bob receives all → can decrypt all
✅ Store vs delete: Store for skipped, current uses and deletes
✅ Benefit: Offline users can recover past messages
✅ Trade-off: Storage space vs recoverability

🎉 Out-of-Order Explained!​

Now you understand how Signal Protocol handles offline/delayed messages.

Next: Security properties.