ECDH-OMR: ECDH based Oblivious Message Retrieval

ECDH-OMR aims to solve the following problem:

1. Alice wants to leave a message for Bob on a server.
2. The server is not supposed to know that the message is for Bob.
3. Eve should neither be able to count the amount of real messages available for pick-up on the server, nor if new messages came in or or old ones were removed.
4. Bob should be able to pick their message up from the server without the server knowing whether this has happened or not.

ECDH-OMR solves this by using the commutative property of Diffie-Hellman key exchanges to implement a form of public key [blinding], allowing third parties to send messages to a recipient this third party cannot identify at rest or when relaying it. It is a form of Private Information Retrieval.

This library implements this scheme with x25519-dalek and (generically) with RustCrypto's elliptic-curves, as well as their AEADs (again, generically).

Warning This work has not yet been independently audited

While the scheme at it's core received preliminary reviews with positive results, more rigorous proofs should be published before considering its use. The implementation is a first stab at what a reasonable generic API for this could look like and has not received any reviews so far.

For experimental use and research only.

Basics

Although its use is not widespread, ECDH supports shared secrets among multiple parties. Effectively, the whole reason why this scheme works is because these two statements are equivalent:

• ECDH ( Server_SK, ECDH ( Alice_SK, Bob_PK ) )
• ECDH ( Bob_SK, ECDH ( Server_SK, Alice_PK ) )

This allows a server (or another third party) to encrypt information for a recipient the real public key they don't know of, and a recipient to decrypt information without having identified them to the server (or another third party).

Scheme flow

For the purposes of the breakdown below, Alice sends an unencrypted message to Bob. How Alice would encrypt a message to Bob would have to be handled by a different layer of a protocol using this scheme.

1. Alice obtained Bob's public key. Alice blinds Bob's public key. This is done by generating an ephemeral secret key, and using it to create a shared secret with Bob's public key. This shared secret is Bob's blinded public key (BK). The ephemeral secret's public counterpart acts as blinding factor (BF). Both of them are sent to the server along with a message.
   Alice → Server:
   • BlindedBob_BK = ECDH ( Ephemeral_SK, Bob_PK )
   • BlindedBob_BF = G^Ephemeral_SK
   • Message
2. To field a request, the server generates its own ephemeral (per-request) key pair, and combines it with Bob's blinded public key and its blinding factor. A nonce is generated and used alongside the resulting shared secret to symmetrically encrypt the message:
   Server → Anyone:
   • BlindedBlindingFactor_BK = ECDH ( Request_SK, BlindedBob_BF )
   • Nonce
   • MessageCiphertext = AEAD Enc ( ECDH ( Request_SK, BlindedBob_BK, Nonce, Message)
3. Bob now received an encrypted message from the server, even though the server was not ware of Bob's real public key. Bob also received all information they need to recover the message left by Alice.:
   Bob → Bob:
   • Message = AEAD Dec ( ECDH ( Bob_SK, BlindedBlindingFactor_BK ), Nonce, MessageCiphertext )

API Flow

For an annotated version of this that also includes "decoys" or, please see examples/decoyed.rs which also shows the use of decoy hints.

use ecdh_omr::*;

use x25519_dalek::*;
use rand_core::OsRng;

type Hint = ecdh_omr::Hint<X25519, ocb3::Ocb3<aes::Aes128>, 32>;

fn main() {
    // Bob
    let bob_secret = StaticSecret::random_from_rng(&mut OsRng);
    let bob_public = PublicKey::from(&bob_secret); // -> Alice

    // Alice
    let bob_blinded_by_alice = bob_public.blind(&mut OsRng); // -> Server
    let alice_message = [42u8; 32]; // -> Server

    // Server
    let hint = Hint::new(&bob_blinded_by_alice, &alice_message, &mut OsRng).unwrap(); // -> Bob

    // Bob 
    let bob_recovered_message = bob_secret.try_to_take_the(&hint).unwrap(); // ✅

    assert_eq!(alice_message, bob_recovered_message);
}

Notes

API Documentation

… Yes. That is necessary. That will exist. Soon. Promise ✨

Scale

Fundamentally, because it is a polling based scheme, rather than Fuzzy Message Detection for example where the server does matching work, its scale is limited by bandwidth and compute.

Post-Quantum Considerations

CSIDH/CTIDH technically supports this scheme, but aren't researched well enough researched to be viable at this point. Due to the scale limitations of ECDH-OMR though, it may be conceivable that CTIDH-OMR or ECDH-CTIDH-OMR could be usable in certain circumstances.

ML-KEM is not commutative, so this would require a way for a third party to change the ciphertext without changing the secret embedded within. We're not aware of whether this is possible or not.

Acknowledgements

ECDH based Oblivious Message Retrieval was developed by @eaon as part of Reach, an end-to-end encrypted communication platform designed for collaborative groups who wish to let anonymous individuals contact them with information and/or requests. Reach and the research that led to this crate has been self-funded so far, please get in touch if you would like to change that 😉

The author also contributed the scheme to SecureDrop's E2EE protocol research.

• The author would like to thank Davide @TheZero for his early contribution to the aforementioned research, whereby an unusual use of multi-party Diffie-Hellman key exchanges were used to ephemerally "prove" secret key possession in a challenge/response protocol.
• The author would also like to express their gratitude to Jacob Young for highlighting how the challenge/response protocol would allow servers to quickly correlate messages and infer identity properties of recipients, leading the author to take up this problem once again. And then also for taking even more time at [Recurse Center] to review the ECDH based Oblivious Message Retrieval scheme implemented in this crate. 🐙