The following explains a different way (then one-time pre keys) for Bob to securely generate ephemeral keys asynchronously without a limit while still being able to delete the private key immediately after the session is created.

I am wondering can you find a security flaw in this? or any suggestions?

Edited from when I asked it on: Signal community forum

Derived Ephemeral Key

1.0. Overview

1.1. Goal

Solve X3DH - Protocol Replay and X3DH - Key Compromise.

1.2. Purpose

The purpose of a derived ephemeral key is to replace the current signedPreKey + oneTimePreKey scheme.

To do this, we must first learn more about both them:

Their purpose is to make sure the initial shared secret of a session cannot be calculated if a device was taken after the session was created.

1.3. SignedPreKey

Signed pre key changes every interval (usually a week) and is semi ephemeral.

The purpose of signedPreKey is to provide some protection if no one-time pre key was given, if a device was taken after the interval the initial shared still couldn't be calculated.

1.4. OneTimePreKey

A one-time pre key is ephemeral, the client sends N (usually 100) one-time pre keys to the server and the server polls (gets and removes) a single one-time pre key (if available) every request of data bundle.

If a one time pre key was not available, it gives no one-time pre keys making "Bob" (the one who's data bundle was requested) has no ephemeral key.

The purpose of oneTimePreKey is to provide an ephemeral key to "Bob"'s part, the ephemeral private key can be deleted as soon as the shared secret was calculated so if a device was taken later, the shared secret could not be calculated.

Now that we understand their purpose we can see the problem, if a oneTimePreKey wasn't used and the signedPreKey has still yet to change, the initial shared secret can be calculated.

2.0. Generator key pair

A generator key pair is a base key pair that will be frequently changed and used to derive new ephemeral keys.

A generator key pair must be deleted and changed to a new value as soon as used (or if the user is currently not connected, he should only after he finishes reading his mailbox (encase new sessions are available)).

3.0. Derived ephemeral key

Deriving ephemeral key is a crucial part of this process, to derive a new ephemeral key you would generate a nonce and using a one-way function such as Elliptic curve point multiplication (also known as Elliptic curve scalar multiplication) you would put the generator key and nonce and derive a new derived ephemeral key.

The derived ephemeral key is needed so you can use an ephemeral key which can be deleted immediately because it is used for only a single user whereas if I were to use a key for multiple users, I must wait for all users to finish before deleting the key.

4.0 How it will work

  1. Bob publishes his data bundle to the server which will now be an Identity public key and a generator public key.
  2. Alice requests Bob's data bundle from the server.
  3. The server generates a nonce and derives a new derived ephemeral public key using the current generator public key and the generated nonce.
  4. The server adds the nonce, Alice's identifier and if confirmation is used (confirmation is explained later) then the generator public key to Bob's mailbox.
  5. The server replies with the identity key and derived the ephemeral public key to Alice.
  6. Alice creates a session and sends her identifier and the ephemeral key she used (not derived ephemeral key) to Bob in her initial message.
  7. Bob receives the message from the server.
  8. Bob derives a new derived ephemeral private key using the given nonce and the generator public key Alice used and saves it under Alice's identifier.
  9. Bob generates a new generator key pair and sends it to the server.
  10. Bob sends the new generator public key to the server and waits for confirmation (or time out, which is recommended to be about a minute) that the server changed it then deletes the old generator key pair. The confirmation is recommended (but not required) so if the server took a new data bundle request in the time it took for Bob to generate his new generator key pair Bob would still be able to process it.
  11. Bob receives Alice's initial message and uses the derived ephemeral private key to create his own session.

5.0. Integration

To integrate into Signal, the X3DH protocol must be changed, the signedPreKey and oneTimePreKeys should be removed and instead replaced with this design.

6.0. Advantages

  • Fits the purpose described in 1.1.
  • Takes up less storage.

7.0. Disadvantages

  • If the used one-way function was found to be not one-way keys would be exposed if the nonce is known.
  • The one-way function most likely (depends on application) requires good performance (since it is used every request).
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Maarten Bodewes
    Jul 5, 2019 at 12:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.